题目链接：http://acm.hust.edu.cn/vjudge/contest/131124#overview
贴了链接这里就不上原题的描述了。
A：
B：
分析：这里用到简单的拓扑排序的算法。这里你会发现它给出的胜负关系不是线性的，无法用一个线性表存储，因此这里自然想到构图。然后用到拓扑排序的原理，我们建立有向图，用v1 —>v2表示v2战胜了v1，那么在建图完成之后，这个图中入度为0的点就是最后一名，因为它没有战胜任何人。如果当前图入度为0的点有多个，就按照题目要求将小数放在前面。然后去掉这个最后一名，同时，战胜它的节点入度减1，这是为了下次遍历图找到最后一名。直到这个图变成了空图，排名也就出来了。
简单的参考代码如下：
#include<stdio.h> #include<string.h> const int maxn = 505; int n , m , G[maxn][maxn] , q[maxn] , Indegree[maxn]; using namespace std; void toposort() { int i , j , k; i = 0; while(i < n) { for(j = 1;j <= n;j++) { if(Indegree[j] == 0) { Indegree[j]--; q[i++] = j; for(k = 1;k <= n;k++) if(G[j][k]) Indegree[k]--; break; } } } } int main() { int x , y , i; while(scanf("%d %d" , &n , &m) != EOF) { memset(Indegree , 0 , sizeof(Indegree)); memset(G , 0 , sizeof(G)); memset(q , 0 , sizeof(q)); for(i = 0;i < m;i++) { scanf("%d %d" , &x , &y); if(G[x][y] == 0) //一步对处理输入数据的小小的优化，少了会引起超时。 { G[x][y] = 1; Indegree[y]++; } } toposort(); for(i = 0;i < n;i++) { if(i == n - 1) printf("%d " , q[i]); else printf("%d ",q[i]); } } }
C：
题目大意：给出一个方阵，方阵的一些位置标记为X，一次攻击可以消灭一行或者一列的X，那么给出一个方阵，求消灭所有X需要的最少攻击次数。
分析：这个题目是一个巧妙的二分图建模加上一个定理“二分图最小点覆盖数 = 二分图最大匹配数”。首先简单介绍一下概念，所谓“二分图最小点覆盖”，就是说给出一个二分图，选出能够覆盖全图数目最少的点，而所谓“覆盖”的概念，是在你选择了一个点vi之后，和这个点(当然包括这个点)相连的所有点标记为“已覆盖”。
那么对于这个题目，我们将n行视作n个元素当成二分图的一个分图，n列视作n个元素当成二分图的一个分图，结合最小点覆盖的概念，你选择一个点，然后覆盖与其相连的所有点的过程，是否就是原题中“消灭一行、或者一列”的过程？这便是建模的关键。
完成了建模，我们在利用上文提到的定理： 二分图最小点覆盖数 = 二分图最大匹配数。而对于一个二分图求最大匹配数，利用我们已经学过的匈牙利算法即可。关于这个定理的严谨证明，可以参考《算法导论》或者参考网上的资料。
参考代码如下：
#include<iostream> #include<fstream> #include<cstring> #include<cstdio> using namespace std; int n, k; int v1, v2; bool Map[501][501]; bool visit[501]; int link[501]; int result; bool dfs(int x) { for (int y = 1; y <= v2; y++) { if (Map[x][y] && !visit[y]) { visit[y] = true; if (link[y] == 0 || dfs(link[y])) { link[y] = x; return true; } } } return false; } void Search() { for (int x = 1; x <= v1; x++) { memset(visit,false,sizeof(visit)); if (dfs(x)) result++; } } int main() { scanf("%d %d",&n,&k); v1 = v2 = n; int x, y; memset(Map,0,sizeof(Map)); for (int i = 1; i <= k; i++) { scanf("%d %d",&x,&y); Map[x][y] = true; } Search(); printf("%d ",result); return 0; }
D：
题目大意：给出m、n，在数轴上[1,n]这个区间段，找到一个整数a，使得c取得[1,n]内任意一个数，|c-a|<|c-m|的概率取得最大。如果有多个满足这样的数字，输出最小的。
分析：比较简单的题目，分情况讨论进行模拟即可。分情况的标准是n的奇偶，以及m的位置(在n的中间？中间偏左？中间偏右？)
简单的参考代码如下：
#include<cstdio> using namespace std; int main() { int n , m; while(scanf("%d %d",&n ,&m) != EOF) { if(n == 1) printf("1 "); else if(n%2 == 1) { if(m == n/2 + 1) printf("%d ",m-1); if(m > n/2 + 1) printf("%d ",m-1); if(m < n/2 + 1) printf("%d ",m+1); } else { if(m == n / 2) printf("%d ",m+1); if(m < n / 2) printf("%d ",m+1); if(m > n / 2) printf("%d ",m-1); } } }
E：
题目大意：先给你四个数a,b,c,d，再给出第五个数e，让你找1~e之间，是前四个数的倍数的数字的个数.
分析：简单的暴力即可。
参考代码如下：
#include<cstdio> using namespace std; int main() { int k , l , m , n; while(scanf("%d%d%d%d",&k,&l,&m,&n) != EOF) { int d; scanf("%d",&d); int ans = 0; for(int i = 1;i <= d;i++) { if(i%k == 0 || i%l == 0 || i%m == 0 || i%n==0) ans++; } printf("%d ",ans); } }
F：
这种条件下，字符串是abcd、或者ababab这种类型，循环次数的计算公式是l/(l-next[l])，如果循环次数是1，那么需要添加l个字符，否则的话不用添加。
情况2：l%(l-next[l])!=0
字符串是abaaa这种类型，就是说没有循环节，但是末尾有“部分循环节”，这种情况与abcd这种字符串比较处理。
对于abaaa这种字符串的处理方法，length = l - next[l]是去掉“部分循环节”的字符串长度，将其视为循环节，那么需要添加的最小字符串个数就是length - next[l]。
而为什么通过这些式子进行计算，全都来源于next数组自身的定义，又怎样的定义就有怎样的性质，这里花时间需要充分理解。
参考代码如下。
#include<stdio.h> #include<string.h> const int maxn = 1000000 + 5; char b[maxn]; int next[maxn]; void getnext()//模板 { int l=strlen(b); int i=0,j=-1; next[0]=-1; while(i<l) { if(j==-1||b[i]==b[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int main() { int a,l,i; int t; scanf("%d",&t); while(t--)//输入一个小数用%d.%S的方法便于处理 { scanf("%s",b); getchar(); l=strlen(b); getnext(); if(l%(l-next[l])==0)//说明从开始判断到结束有循环节 { if(l/(l-next[l]) == 1) printf("%d ",l);//循环了几次 else printf("0 "); } else { int length = l - next[l]; // printf("%d %d",next[l],length); int add = length - next[l]%length; printf("%d ",add); } } return 0; }
G：