Category: 不学无术

About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people’s talent and virtue. According to his theory, a man being outstanding in both talent and virtue must be a “sage（圣人）”; being less excellent but with one’s virtue outweighs talent can be called a “nobleman（君子）”; being good in neither is a “fool man（愚人）”; yet a fool man is better than a “small man（小人）” who prefers talent than virtue.
Now given the grades of talent and virtue of a group of people, you are supposed to rank them according to Sima Guang’s theory.
Input Specification:
Each input file contains one test case. Each case first gives 3 positive integers in a line: N (<=10⁵), the total number of people to be ranked; L (>=60), the lower bound of the qualified grades — that is, only the ones whose grades of talent and virtue are both not below this line will be ranked; and H (<100), the higher line of qualification — that is, those with both grades not below this line are considered as the “sages”, and will be ranked in non-increasing order according to their total grades. Those with talent grades below H but virtue grades not are cosidered as the “noblemen”, and are also ranked in non-increasing order according to their total grades, but they are listed after the “sages”. Those with both grades below H, but with virtue not lower than talent are considered as the “fool men”. They are ranked in the same way but after the “noblemen”. The rest of people whose grades both pass the L line are ranked after the “fool men”.
Then N lines follow, each gives the information of a person in the format:

ID_Number Virtue_Grade Talent_Grade

where ID_Number is an 8-digit number, and both grades are integers in [0, 100]. All the numbers are separated by a space.
 
Output Specification:
The first line of output must give M (<=N), the total number of people that are actually ranked. Then M lines follow, each gives the information of a person in the same format as the input, according to the ranking rules. If there is a tie of the total grade, they must be ranked with respect to their virtue grades in non-increasing order. If there is still a tie, then output in increasing order of their ID’s.
Sample Input:

14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60

Sample Output:

12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90

======================================================
此题就是个分几类然后排序的问题，将每个人作为一个对象用STL就很好做了
重载一下运算符<就行了，STL的sort用它来排序的…
切记比较标准的（从C++基础教程上找到的）小于运算符重载的规范

bool operator<( const Object &obj) const;
没啥难度啦~就是有点费时间

#include
#include
#include
using namespace std;
struct Person
{
long id;
int talent;
int virtue;
Person(long _id, int _vir, int _tal)
{
id = _id;
talent = _tal;
virtue = _vir;
}
bool operator<( const Person& p) const { bool flag; //Overload operator < int total_self = talent + virtue; int total_him = p.talent + p.virtue; if(total_self < total_him) flag = true; else if(total_self > total_him)
flag = false;
else
{
if(virtue == p.virtue)
flag = id > p.id; //ID in increasin order!
else
flag = virtue < p.virtue; } return !flag; //Non-increasing order } }; int main() { vector people[4];
int N, L, H;
scanf("%d %d %d", &N, &L, &H);
int M = 0;
for(int i=0; i=H && vir >= H)
{
//Sage
people[0].push_back(p);
}
else if(vir >= H)
{
//Nobleman
people[1].push_back(p);
}
else if(vir >= tal)
{
//Fool
people[2].push_back(p);
}
else
{
//Small man
people[3].push_back(p);
}
}
printf("%dn", M);
for(int i=0; i<4; i++) { //Arrange them sort(people[i].begin(), people[i].end()); //Output for(vector::iterator it=people[i].begin(); it!=people[i].end(); it++)
{
printf("%ld %d %dn", it->id, it->virtue, it->talent);
}
}
return 0;
}


测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	0	710	12/12
1	答案正确	0	710	2/2
2	答案正确	40	990	3/3
3	答案正确	80	3730	3/3
4	答案正确	80	3800	3/3
5	答案正确	0	790	2/2

Sherlock Holmes received a note with some strange strings: “Let’s date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”. It took him only a minute to figure out that those strange strings are actually referring to the coded time “Thursday 14:04” — since the first common capital English letter (case sensitive) shared by the first two strings is the 4th capital letter ‘D’, representing the 4th day in a week; the second common character is the 5th capital letter ‘E’, representing the 14th hour (hence the hours from 0 to 23 in a day are represented by the numbers from 0 to 9 and the capital letters from A to N, respectively); and the English letter shared by the last two strings is ‘s’ at the 4th position, representing the 4th minute. Now given two pairs of strings, you are supposed to help Sherlock decode the dating time.
Input Specification:
Each input file contains one test case. Each case gives 4 non-empty strings of no more than 60 characters without white space in 4 lines.
Output Specification:
For each test case, print the decoded time in one line, in the format “DAY HH:MM”, where “DAY” is a 3-character abbreviation for the days in a week — that is, “MON” for Monday, “TUE” for Tuesday, “WED” for Wednesday, “THU” for Thursday, “FRI” for Friday, “SAT” for Saturday, and “SUN” for Sunday. It is guaranteed that the result is unique for each case.
Sample Input:

3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm

Sample Output:

THU 14:04

===========================================
题目看上去挺简单，自己做的时候粗心大意轻视了。
注意以下几点：
1.第一次比对的是从’A’-‘G’之内的相同字母，其他任何字符相同的无效
2.第二次比对的是从’0’-‘9’及’A’-‘N’之内的相同字符，其他无效
吐槽下第一次用VS2005感觉比VS2012差了好几条街，根本没有智能提示，估计是我变成习惯不好，编译错了N次…但是免研的时候估计没那么新版本，还是适应一下吧~
============================================

#include
#include
#include
using namespace std;
const char* wkdays[] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
int main()
{
const int BUFFER = 61;
char str1[BUFFER];
int results[3]; //存放四个数字结果
//第一次读取
cin >> str1;
int len1 = strlen(str1);
//第二次读取
char str2[BUFFER];
cin >> str2;
int len2 = strlen(str2);
int endIndex = (len1=7 ) //'G'
continue;
}
else
{
if(chrIndex < 0 || chrIndex >= 14) //'N'
{
if(digIndex <0 || digIndex >9)
continue;
digitFlag = true;//是个数字
}
}
if(str1[i] == str2[i])
{
if(firstTime)
{
results[0] = chrIndex;
firstTime = false;
}
else
{
results[1] = digitFlag? (digIndex):(chrIndex + 10);
break;
}
}
}
//第三次读取
char str3[BUFFER];
char str4[BUFFER];
cin >> str3 >> str4;
int len3 = strlen(str3);
int len4 = strlen(str4);
endIndex = (len3='a' && str3[i]<='z'; bool cond2 = str3[i]>='A' && str3[i]<='Z'; if(cond1 || cond2) { if(str3[i] == str4[i]) { results[2] = i; break; } } } cout << wkdays[results[0]] << " " << setw(2) << std::setfill('0') << results[1] << ":" << setw(2) << std::setfill('0') << results[2]; return 0; }

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input:

10
1 2 3 4 5 6 7 8 9 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

========================================
翻译过来就是…完全二叉搜索树
两个特征：二叉搜索树+完全二叉树
后面的代码里面可能有一点冗余的地方，就是那个if里面的，不过运行结果不影响，就没去改了。
我想的办法是自顶向下的，从一堆排好序的数中揪出那个“中间的”，然后分为两棵子树做，如此迭代(具体输出用<queue>的数组一层层弄就行了，这边懒得写)：

function foo:
本行完整的应有m = log2(N)个
本行多出的有r = N – m个 （就是完全树的最底下一行多余的节点数）
if r==0:
太完美了..将中间的数找出，放入输出队列中
else:
最后一排填满的话会有k=2^m个元素
那么左右边分开的话，各有k/2个
这样就能算出左边右边应该有多少个元素“多余”，去除左右边多余的剩下就是真正的长度
去除多余的元素，根据长度找出中间的元素，放入输出队列
递归接着算

=======================================================================

#include
#include /* qsort */
#include
#include
using namespace std;
int compare(const void *a, const void *b)
{
return ( *(int*)a - *(int*)b);
}
queue *results;
void run(int* srcAry, int fromIndex, int toIndex, int level)
{
int length = toIndex - fromIndex + 1;
if(length < 1) return; if(length == 1) { //到底了 //printf("%d ", srcAry[fromIndex]); results[level].push(srcAry[fromIndex]); return; } int m = log((double)length)/log((double)2); int r = length - pow(2.0f,m) + 1; if(r == 0) { int midIndex = fromIndex + length/2; //printf("%d ", srcAry[midIndex]); results[level].push(srcAry[midIndex]); run(srcAry, fromIndex, midIndex-1, level-1); run(srcAry, midIndex+1, toIndex, level-1); } else { int k = pow(2.0f, m); int left = k/2, right = k/2; if(r <= left) { //只有左边有 left = r; right = 0; } else { //右边也有 right = r - left; } int restLength = length - r; int midIndex = fromIndex + left + restLength/2; //printf("%d ", srcAry[midIndex]); results[level].push(srcAry[midIndex]); run(srcAry, fromIndex, midIndex -1, level-1); run(srcAry, midIndex+1, toIndex, level-1); } } int main() { int N; scanf("%d", &N); int *ary = new int[N]; for(int i=0; i[level +1];
run(ary, 0, N-1, level);
int count = 1;
level++;
while (level--)
{
queue q = results[level];
while(!q.empty())
{
printf("%d", q.front());
if(count < N) printf(" "); count ++; q.pop(); } } return 0; }
 

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p₁^k₁* p₂^k₂ *…*p_m^k_m.
Input Specification:
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification:
Factor N in the format N = p₁^k₁ * p₂^k₂ *…*p_m^k_m, where p_i‘s are prime factors of N in increasing order, and the exponent k_i is the number of p_i — hence when there is only one p_i, k_i is 1 and must NOT be printed out.
Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

 
=======================================================
就是一个找质数的问题，其实很简单啦~
切记从小的这头开始尝试，因为试想一下，除掉2，3这种小数字之后，需要尝试的明显少了N多！

#include 
#include 

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.
Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results — namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.
For example, 3 games’ odds are given as the following:

 W    T    L
1.1  2.5  1.7
1.2  3.0  1.6
4.1  1.2  1.1

To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.1*3.0*2.5*65%-1)*2 = 37.98 yuans (accurate up to 2 decimal places).
Input
Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.
Output
For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.
Sample Input

1.1 2.5 1.7
1.2 3.0 1.6
4.1 1.2 1.1

Sample Output

T T W 37.98

============================================================
史上最简单的一道题，直接放代码…

#include 
#include  // std::setprecision
using namespace std;
int main()
{
    float best_odds[3] = {0.0, 0.0, 0.0};
    char mark[3] = {'W','T','L'};
    char best_mark[4] = {' ',' ',' '};
    float result = 1.0;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            float temp;
            cin >> temp;
            if(temp > best_odds[i])
            {
                best_odds[i] = temp;
                best_mark[i] = mark[j];
            }
        }
        result *= best_odds[i];
        char out = best_mark[i];
        cout << out << " ";
    }
    result = (result * 0.65 - 1) * 2;
    cout << fixed << setprecision(2) << result;
    return 0;
}