本文主要是介绍训练赛3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2348&cid=1232
题意：
有两个磁盘，第一个磁盘有n个安装包，第二个磁盘有m个安装包。有些安装包的安装依赖于其他安装包的安装，即如果x依赖与y，那么包y必须在包x之前安装，每次可以插入这两张磁盘中的一张去安装一些包，求以最小的交换次数安装好所有的包，保证依赖关系不存在环，开始插入和最后取出都算一次交换，初始是磁盘设备是为空的。
解题思路：做两次拓扑排序即可，分别代表先插第一个磁盘和第二个磁盘的交换次数，然后取最小值。
ps:比赛时一直没看懂题意。结束后听人说是拓扑排序。因为安装包的安装是有先后依赖关系的，才感觉有点像拓扑排序。结果自己敲愣是没敲出来。sad。。。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
int n,m,k;
vector <int> edge[100010];//保存依赖该点的点
queue <int> que[2];
int in[100010],deg[100010];//保存入度
int ans;void toposort(int kind)
{//用两个队列分别维护两个磁盘，假如先对第一个磁盘拓扑排序，那么交换次数增1是在第一个队列为空时，//因为这时就要拔掉第一个磁盘，插入第二个磁盘。当两个队列都为空时，拓扑排序完成。while(!que[0].empty()) que[0].pop();while(!que[1].empty()) que[1].pop();int cnt = 0;for(int i = 1; i <= n+m; i++){if(deg[i] == 0) //入度为0的点全部进队列{if(i <= n) que[0].push(i);else que[1].push(i);}}while(!que[0].empty() || !que[1].empty()){while(!que[kind].empty()) {int u = que[kind].front();que[kind].pop();for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];deg[v]--;if(deg[v] == 0){if( v <= n) que[0].push(v);else que[1].push(v);}}}//当前队列为空，说明一个磁盘中的包安装完了，应换另一个磁盘，所以增1。kind = kind^1;cnt++;}ans = min(ans,cnt);
}int main()
{while(~scanf("%d %d %d",&n,&m,&k)){if(n == 0 && m == 0 && k == 0) break;for(int i = 1; i <= n+m; i++)edge[i].clear();memset(in,0,sizeof(in));memset(deg,0,sizeof(deg));int u,v;while(k--){scanf("%d %d",&u,&v);edge[v].push_back(u);in[u]++;}ans = INF;for(int i = 1; i <= n+m; i++)deg[i] = in[i];toposort(0);//假如先插入第一个磁盘，进行拓扑排序。for(int i = 1; i <= n+m; i++)deg[i] = in[i];toposort(1);//假如先插入第二个磁盘，进行拓扑排序。printf("%d\n",ans+1);}return 0;
}
http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2351&cid=1232
题意: 给一个数n，代表n个人，n是用xyez表示的十进制数。x表示第一个数，y表示第二个数，z表示后面0的个数。n个人围城圈，从第二个人开始（先出圈），每隔一个未出圈的人就出圈一个人(出圈只是一种标记，还在圈中)。问最后一个人的编号是多少。
思路：继续淡定的找规律吧。。n是偶数的条件下，n是2的幂结果为1，否则是n与2的幂（小于n且距离n最小）差值的2倍.
n奇数,结果比n-1时大2.
#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;int pow2[30] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,
524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728};int main()
{char str[5];while(~scanf("%s",str)){if(strcmp(str,"00e0") == 0)break;if(strcmp(str,"01e0") == 0){printf("1\n");continue;}int x,y,z;x = str[0]-'0';y = str[1]-'0';z = str[3]-'0';int mul = (int)pow(10,z);int num = x*mul*10 + y*mul;//printf("%d\n",num);if(num % 2 == 0){if((num & (num-1)) == 0){printf("1\n");continue;}for(int i = 0; i < 28; i++){if(pow2[i] < num && pow2[i+1] > num){printf("%d\n",(num-pow2[i])*2+1);break;}}}else{num = num-1;if((num & (num-1)) == 0){printf("3\n");continue;}for(int i = 0; i < 28; i++){if(pow2[i] < num && pow2[i+1] > num){printf("%d\n",(num-pow2[i])*2+3);break;}}}}return 0;
}/*int main()
{for(int i = 0; i <= 27; i++)printf("%d\n",(int)pow(2,i));
}*/ 题意：给定一个字符串,如果有连续相等的字符，输出该字符的个数和该字符，如果个数大于9，要分开输出，先输出前9个，再输出剩余的。如果有连续不相等的字符，那么在该段字符前后分别加上'1'，若其中有字符'1',就输出两个'1'。
思路：用一个数组num[]记录从当前字符起，连续相等的字符的个数。如果大于1说明有连续相等的子串，否则，说明没有连续相等的子串。
#include <stdio.h>
#include <string.h>char s[1010];
int num[1010];int main()
{while(gets(s)){int len = strlen(s);for(int i = 0; i < len; i++){num[i] = 0;int cnt = 0;for(int j = i; j < len; j++){if(s[i] == s[j])cnt++;else break;}num[i] = cnt;}int flag = 1;for(int i = 0; i < len;){if(num[i] == 1){if(flag){printf("1");flag = 0;}if(s[i] == '1') printf("%c%c",s[i],s[i]);else printf("%c",s[i]);i++;}else{if(flag == 0){printf("1");flag = 1;}if(num[i] <= 9){printf("%d%c",num[i],s[i]);i += num[i];}else{printf("9%c",s[i]);i += 9;}}}if(!flag) printf("1");printf("\n");}return 0;
}这篇关于训练赛3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
