时间是两个小时，总共三道编程题目。
第一道题目大意：
输入一个int类型的数，判断它的比特流中有多少个“010”，及第一个“101”的下标（这个下标是从低位向高位数的）。
如：输入：21
输出 2 0
原因：21 二进制表示为 0000 0000 0000 0000 0000 0000 0001 0101
总共两个“101”(两个“101”可以重叠)， 且第一个下标为0，第二个下标为2，所以返回2 0
提交代码如下
1 1 int main(){ 2 2 int num; 3 3 while(cin >> num){ 4 4 int tag = 5, tag1 = 2;// 分别是101 和 010 5 5 int times = 0, numcnt = 30, firstindex = -1; 6 6 while(numcnt --){ 7 7 if((num & tag) == tag && (num & tag1) == 0){ 8 8 times ++; 9 9 if(firstindex == -1) 1010 firstindex = 29 - numcnt; 1111 } 1212 tag <<= 1; 1313 tag1 <<= 1; 1414 } 1515 cout << times << " " << firstindex << endl; 1616 } 1717 return 0; 1818 }
View Code
第二道题目大意：
背景：数据库一条记录（包括多个字段：数值，字符串）合并成一个字符串作为输入，现在的任务是将不同的字段分类开来，输出字段的数目和每个字段的内容。
输入一行字符串，将其分割成多段，输入的字符串应满足的条件：
- 输入的字符串没有空格
- 不同的字段之间以逗号分隔
- 如果一个字段内有逗号(“,”)或者引号(“"”),则该字段首尾会加上引号（“"”）,且字段内的引号写作""(两个引号)
若输入的字符串有问题，则输出ERROR；
否则，输出字段个数，然后输出每个字段 (各占一行)
我的思路是：因为每个字段引号都是成对的，所以遇见逗号的时候判断此时引号是否成对。若不成对，说明该逗号是字段内部的逗号；反之，该逗号为两字段的分隔号。
提交代码如下：
1 1 int main(){ 2 2 int num; 3 3 string inStr; 4 4 while(getline(cin,inStr)){ 5 5 if(inStr.size() == 0){ 6 6 cout << 0 << endl; 7 7 continue; 8 8 } 9 9 int lastIndex = -1; 1010 stack<char> charStack; 1111 vector<string> strVec; 1212 for(int i = 0; i < inStr.size(); ++ i){ 1313 if(inStr[i] == '"'){ 1414 charStack.empty() ? charStack.push('"') : charStack.pop(); 1515 } 1616 if(inStr[i] == ',' && charStack.empty()){ 1717 strVec.push_back(inStr.substr(lastIndex+1, i-lastIndex-1)); 1818 lastIndex = i; 1919 } 2020 } 2121 if(!charStack.empty()){ 2222 cout << "ERROR" <<endl; 2323 continue; 2424 } 2525 strVec.push_back(inStr.substr(lastIndex+1, inStr.size()-lastIndex-1)); 2626 cout << strVec.size() << endl; 2727 for(int i = 0; i < strVec.size(); ++ i){ 2828 if(strVec[i].size() == 0 || (strVec[i].size() == 2 && strVec[i][0] == '"' && strVec[i][1] == '"')) 2929 cout << "--" <<endl; 3030 else if(strVec[i][0] == '"'){ 3131 bool flag = false; 3232 for(auto it = strVec[i].begin()+1; it != strVec[i].end(); ++ it){ 3333 if(*it == '"'){ 3434 if(flag){ 3535 printf("\""); 3636 flag = false; 3737 } 3838 else 3939 flag = true; 4040 } 4141 else 4242 printf("%c", *it); 4343 } 4444 printf("\n"); 4545 } 4646 else 4747 cout << strVec[i] << endl; 4848 } 4949 } 5050 return 0; 5151 }
View Code
第三道题目大意：
背景：好友推荐功能，A和B是好友，B和C是好友，A和C不是好友，则C是A的2度好友；A和B的熟悉度为m,B和C的熟悉度为n,则A和C的推荐度为m+n;
输入：测试用例个数T；
然后输入每个测试用例：用户数m，某个特定用户的id，要求的好友度数t，已知的好友数目n
接下来输入n行，每行的内容为：用户1的id 用户2的id 两用户的熟悉度
输出：先输出特定用户的t度好友个数，没有则输出-1；若有，接下来一次输出用户id，按照推荐度从高到低（若推荐度相同，按照id从小到大）
当时的思路是：dijkstra算法找到特定用户t度好友，然后进行排序输出。（但是印象中题目在有两个距离相同的路径时，推荐度采用最高那个还是第一个没有说清楚，也可能是我没理解清楚题意。当时我是注释了部分代码又提交了一下。）
当时提交过了40%，提交代码如下：
1int T, userCnt, userId, friendVal, pairCnt; 2 3int dist[50]; 4int friendValSum[50]; 5int routeMatrix[50][50]; 6int valMatrix[50][50]; 7void dijkstra(int root){ 8 memset(dist, 0x7f, sizeof(dist)); 9 memset(friendValSum, 0, sizeof(friendValSum)); 10 for(int i = 0; i < userCnt; ++ i) 11 dist[i] = routeMatrix[root][i]; 12 for(int i = 0; i < userCnt; ++ i) 13 friendValSum[i] = valMatrix[root][i]; 14 dist[root] = 0; 15 vector<bool> flagVec(50,false); 16 flagVec[root] = true; 17 for(int j = 1; j < userCnt; ++ j){ 18 int minDis = INF, v = -1; 19 for(int i = 0; i < userCnt; ++i){ 20 if(!flagVec[i] && dist[i] < minDis){ 21 minDis = dist[i]; 22 v = i; 23 } 24 } 25 if(v == -1 || minDis > friendVal) 26 return; 27 flagVec[v] = true; 28 for(int i = 0; i < userCnt; ++ i){ 29 if(!flagVec[i] && routeMatrix[v][i] + dist[v] < dist[i]){ 30 dist[i] = routeMatrix[v][i] + dist[v]; 31 friendValSum[i] = valMatrix[v][i] + friendValSum[v]; 32 } 33 /*else if(!flagVec[i] && routeMatrix[v][i] + dist[v] == dist[i] && valMatrix[v][i] + friendValSum[v] > friendValSum[i]){ 34 friendValSum[i] = valMatrix[v][i] + friendValSum[v]; 35 }*/ 36 } 37 } 38} 39 40typedef struct NODE{ 41 int id, val; 42 NODE(int d, int v):id(d),val(v){} 43}node; 44bool cmp(node a, node b){ 45 if(a.val != b.val) 46 return a.val > b.val; 47 else 48 return a.id < b.id; 49} 50int main(){ 51 int tmpSt, tmpEnd, tmpVal; 52 cin >> T; 53 while(T--){ 54 cin >> userCnt >> userId >> friendVal; 55 cin >> pairCnt; 56 memset(routeMatrix, 0x7f, sizeof(routeMatrix)); 57 memset(valMatrix, 0x7f, sizeof(valMatrix)); 58 for(int i = 0; i < pairCnt; ++ i){ 59 scanf("%d %d %d", &tmpSt, &tmpEnd, &tmpVal); 60 routeMatrix[tmpSt][tmpEnd] = 1; 61 routeMatrix[tmpEnd][tmpSt] = 1; 62 valMatrix[tmpSt][tmpEnd] = tmpVal; 63 valMatrix[tmpEnd][tmpSt] = tmpVal; 64 } 65 dijkstra(userId); 66 //if(friendVal == 0){ 67 // cout << "-1" << endl; 68 // continue; 69 //} 70 vector<node> nodeVec; 71 for(int i = 0; i < userCnt; ++ i){ 72 if(dist[i] == friendVal){ 73 nodeVec.push_back(NODE(i, friendValSum[i])); 74 } 75 } 76 if(nodeVec.size() == 0) 77 cout << "-1" << endl; 78 else{ 79 sort(nodeVec.begin(), nodeVec.end(), cmp); 80 bool flag = false; 81 for(int i = 0; i < nodeVec.size(); ++i){ 82 flag ? printf(" ") :flag = true; 83 printf("%d", nodeVec[i].id); 84 } 85 } 86 printf("\n"); 87 } 88 return 0; 89}
View Code