题目链接：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 = ; int n , m , G[maxn][maxn] , q[maxn] , Indegree[maxn];
using namespace std; void toposort()
{ int i , j , k;
i = ;
while(i < n)
{
for(j = ;j <= n;j++)
{
if(Indegree[j] == )
{
Indegree[j]--;
q[i++] = j; for(k = ;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 , , sizeof(Indegree));
memset(G , , sizeof(G));
memset(q , , sizeof(q));
for(i = ;i < m;i++)
{
scanf("%d %d" , &x , &y);
if(G[x][y] == ) //一步对处理输入数据的小小的优化，少了会引起超时。
{
G[x][y] = ;
Indegree[y]++;
} } toposort();
for(i = ;i < n;i++)
{
if(i == n - )
printf("%d\n" , 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[][];
bool visit[];
int link[]; int result;
bool dfs(int x)
{
for (int y = ; y <= v2; y++)
{
if (Map[x][y] && !visit[y])
{
visit[y] = true;
if (link[y] == || dfs(link[y]))
{
link[y] = x;
return true;
}
}
}
return false;
} void Search()
{
for (int x = ; 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,,sizeof(Map));
for (int i = ; i <= k; i++)
{
scanf("%d %d",&x,&y);
Map[x][y] = true;
}
Search();
printf("%d\n",result);
return ;
}
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 == ) printf("1\n"); else if(n% == )
{
if(m == n/ + ) printf("%d\n",m-);
if(m > n/ + ) printf("%d\n",m-);
if(m < n/ + ) printf("%d\n",m+);
} else
{
if(m == n / ) printf("%d\n",m+);
if(m < n / ) printf("%d\n",m+);
if(m > n / ) printf("%d\n",m-);
} }
}
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 = ;
for(int i = ;i <= d;i++)
{
if(i%k == || i%l == || i%m == || i%n==)
ans++;
}
printf("%d\n",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 = + ;
char b[maxn];
int next[maxn];
void getnext()//模板
{
int l=strlen(b);
int i=,j=-;
next[]=-;
while(i<l)
{
if(j==-||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])==)//说明从开始判断到结束有循环节
{ if(l/(l-next[l]) == )
printf("%d\n",l);//循环了几次
else
printf("0\n");
} else
{ int length = l - next[l];
// printf("%d %d",next[l],length);
int add = length - next[l]%length;
printf("%d\n",add);
}
}
return ;
}
G：