时间是两个小时, 总共三道编程题目.
第一道题目大意:
输入一个 int 类型的数, 判断它的比特流中有多少个 "010", 及第一个 "101" 的下标(这个下标是从低位向高位数的).
如: 输入: 21
输出 2 0
原因: 21 二进制表示为 0000 0000 0000 0000 0000 0000 0001 0101
总共两个 "101"(两个 "101" 可以重叠), 且第一个下标为 0, 第二个下标为 2, 所以返回 2 0
提交代码如下
- int main(){
- int num;
- while(cin>> num){
- int tag = 5, tag1 = 2;// 分别是 101 和 010
- int times = 0, numcnt = 30, firstindex = -1;
- while(numcnt --){
- if((num & tag) == tag && (num & tag1) == 0){
- times ++;
- if(firstindex == -1)
- firstindex = 29 - numcnt;
- }
- tag <<= 1;
- tag1 <<= 1;
- }
- cout <<times << " " << firstindex << endl;
- }
- return 0;
- }
- View Code
第二道题目大意:
背景: 数据库一条记录 (包括多个字段: 数值, 字符串) 合并成一个字符串作为输入, 现在的任务是将不同的字段分类开来, 输出字段的数目和每个字段的内容.
输入一行字符串, 将其分割成多段, 输入的字符串应满足的条件:
输入的字符串没有空格
不同的字段之间以逗号分隔
如果一个字段内有逗号 (",") 或者引号("""), 则该字段首尾会加上引号("""), 且字段内的引号写作 ""(两个引号)
若输入的字符串有问题, 则输出 ERROR;
否则, 输出字段个数, 然后输出每个字段 (各占一行)
我的思路是: 因为每个字段引号都是成对的, 所以遇见逗号的时候判断此时引号是否成对. 若不成对, 说明该逗号是字段内部的逗号; 反之, 该逗号为两字段的分隔号.
提交代码如下:
- int main(){
- int num;
- string inStr;
- while(getline(cin,inStr)){
- if(inStr.size() == 0){
- cout << 0 << endl;
- continue;
- }
- int lastIndex = -1;
- stack<char> charStack;
- vector<string> strVec;
- for(int i = 0; i <inStr.size(); ++ i){
- if(inStr[i] == '"'){
- charStack.empty() ? charStack.push('"') : charStack.pop();
- }
- if(inStr[i] == ',' && charStack.empty()){
- strVec.push_back(inStr.substr(lastIndex+1, i-lastIndex-1));
- lastIndex = i;
- }
- }
- if(!charStack.empty()){
- cout << "ERROR" <<endl;
- continue;
- }
- strVec.push_back(inStr.substr(lastIndex+1, inStr.size()-lastIndex-1));
- cout << strVec.size() << endl;
- for(int i = 0; i < strVec.size(); ++ i){
- if(strVec[i].size() == 0 || (strVec[i].size() == 2 && strVec[i][0] == '"'&& strVec[i][1] =='"'))
- cout << "--" <<endl;
- else if(strVec[i][0] == '"'){
- bool flag = false;
- for(auto it = strVec[i].begin()+1; it != strVec[i].end(); ++ it){
- if(*it == '"'){
- if(flag){
- printf("\"");
- flag = false;
- }
- else
- flag = true;
- }
- else
- printf("%c", *it);
- }
- printf("\n");
- }
- else
- cout << strVec[i] << endl;
- }
- }
- return 0;
- }
- 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%, 提交代码如下:
- int T, userCnt, userId, friendVal, pairCnt;
- int dist[50];
- int friendValSum[50];
- int routeMatrix[50][50];
- int valMatrix[50][50];
- void dijkstra(int root){
- memset(dist, 0x7f, sizeof(dist));
- memset(friendValSum, 0, sizeof(friendValSum));
- for(int i = 0; i < userCnt; ++ i)
- dist[i] = routeMatrix[root][i];
- for(int i = 0; i < userCnt; ++ i)
- friendValSum[i] = valMatrix[root][i];
- dist[root] = 0;
- vector<bool> flagVec(50,false);
- flagVec[root] = true;
- for(int j = 1; j <userCnt; ++ j){
- int minDis = INF, v = -1;
- for(int i = 0; i < userCnt; ++i){
- if(!flagVec[i] && dist[i] < minDis){
- minDis = dist[i];
- v = i;
- }
- }
- if(v == -1 || minDis> friendVal)
- return;
- flagVec[v] = true;
- for(int i = 0; i <userCnt; ++ i){
- if(!flagVec[i] && routeMatrix[v][i] + dist[v] < dist[i]){
- dist[i] = routeMatrix[v][i] + dist[v];
- friendValSum[i] = valMatrix[v][i] + friendValSum[v];
- }
- /*else if(!flagVec[i] && routeMatrix[v][i] + dist[v] == dist[i] && valMatrix[v][i] + friendValSum[v]> friendValSum[i]){
- friendValSum[i] = valMatrix[v][i] + friendValSum[v];
- }*/
- }
- }
- }
- typedef struct NODE{
- int id, val;
- NODE(int d, int v):id(d),val(v){}
- }node;
- bool cmp(node a, node b){
- if(a.val != b.val)
- return a.val> b.val;
- else
- return a.id <b.id;
- }
- int main(){
- int tmpSt, tmpEnd, tmpVal;
- cin>> T;
- while(T--){
- cin>> userCnt>> userId>> friendVal;
- cin>> pairCnt;
- memset(routeMatrix, 0x7f, sizeof(routeMatrix));
- memset(valMatrix, 0x7f, sizeof(valMatrix));
- for(int i = 0; i <pairCnt; ++ i){
- scanf("%d %d %d", &tmpSt, &tmpEnd, &tmpVal);
- routeMatrix[tmpSt][tmpEnd] = 1;
- routeMatrix[tmpEnd][tmpSt] = 1;
- valMatrix[tmpSt][tmpEnd] = tmpVal;
- valMatrix[tmpEnd][tmpSt] = tmpVal;
- }
- dijkstra(userId);
- //if(friendVal == 0){
- // cout << "-1" << endl;
- // continue;
- //}
- vector<node> nodeVec;
- for(int i = 0; i < userCnt; ++ i){
- if(dist[i] == friendVal){
- nodeVec.push_back(NODE(i, friendValSum[i]));
- }
- }
- if(nodeVec.size() == 0)
- cout << "-1" << endl;
- else{
- sort(nodeVec.begin(), nodeVec.end(), cmp);
- bool flag = false;
- for(int i = 0; i < nodeVec.size(); ++i){
- flag ? printf(" ") :flag = true;
- printf("%d", nodeVec[i].id);
- }
- }
- printf("\n");
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3438694.html