T1 基因序列
死磕，搞不懂为啥超时。（我只打了这一题，嘻嘻）
#include
using namespace std;
const int maxn = 1001000;
char x[maxn];
int n,k,maxx=-1,i,t=0,sum=0,ans=0,idol=0;
int v[maxn];
struct yjy {
int ccc;
int id;
} a[maxn];
bool cmp(yjy a,yjy b) {
return a.ccc>b.ccc;
}
int main() {
freopen("dna.in","r",stdin);
freopen("dna.out","w",stdout);
scanf("%s",x);
n=strlen(x);
for(i=0;i<n;i++) {
maxx=max(maxx,int(x[i]));
v[x[i]]++;
}
for(i=1;i<=maxx;i++) {
if(v[i]!=0) {
a[t].ccc=v[i];
a[t].id=i;
t++;
}
}
sort(a,a+t,cmp);
for(i=0;i<t;i++){
sum+=a[i].ccc;
if(ansans){
idol=i;
ans=sum/k;
}
}
cout<<ans;
}
求助。
T2 质数查询
与线性筛的实现基本类似。
显然，L到R之间喜欢的数的个数，等于1到R之间喜欢的数的个数减去1到L-1之间喜欢的数的个数，这样，本题就可以运用线性筛解决。
如果是朴素的分解质因数做法，时间复杂度为O(N* \sqrt{N}+Q)，可以拿到 65pts 。
替换为下文的线性筛做法，时间复杂度为O(N+Q)，可以通过本题。
T3 最短路径
这道题最麻烦的地方就是最终搞成的图有可能有很多个联通块，考虑怎么将它们整合在一起而不会对最后结果产生影响。
因此考虑增加一个点：S点，让 S点连接所有的黑点，边权为0；
处理从S出发到每个点的最短距离，将每个在最短路上的边留下来，形成一个新图，做一遍最小生成树即可。
难点主要是如何保留最短路上的边。
T4 奇偶游戏
出题人真是太良心啦！
题目名字里已经暗示了一个结论：无解的情况，当且仅当原图不是二分图，换句话说，不能有奇环。
先考虑连通图的情况。 首先如果原图不是二分图，显然无解。因为对于一个长度大于3的奇环，如果合并环上任意两个不相邻的点，一定会生成一个更小的奇环，最终会剩下一个三元环，无法继续合并。
对于任意联通的二分图，我们可以选定一个点S，然后将所有与S距离相同的点合并。由于原图是二分图，所有与距离相同的点必然在同一侧，也就一定不相邻，这样就可以构造出一条链。因此只需要找出两个点，使得它们间的最短路径最长，然后从任意一个点出发，将所有距离相同的点合并。显然这样构造是最优的，而每一个连通块的最优解就是这个连通块中最长的最短路径长度。
考虑有多个连通分量的情况， 我们对于每一个连通分量都构造了一条链，而对于任意两条链，我们显然可以通过一次合并操作将它们并成一条，长度为它们的长度之和。因此，答案就是所有连通块中最长的最短路径之和。
使用 BFS 求出最短路，时间复杂度为 O(nm)。