这是一道很经典的题目了。。题目在：http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
USACO上面的那次我是用DP过的，现在不能DP了。我学了一下SA。过掉了。不过又想到了一个用Hash的做法比较NB。。
首先把原系列换成差系列。。
方法还是二分，因为长度为l的重复字串存在那么l-1的肯定也存在，所以问题变成判断所有长度为l的字串中有没有相同且不相交的，这可以用Hash来解决，算出每个字串的Hash值然后用一个Hash表来保存，有点类似Rabin-Karp算法。。然后二分就OK了。。为了调试我还去USACO了一下。。好久没去了。有点怀念饿。。
Code：

/* PROG: theme LANG: C++ ID: Tom Chen*/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef unsigned int uint;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=20000,seed[]={131,1331,10007,133331},size=17771;int A[maxn],n,Len;struct Hash{ struct node { node*next; uint h[4]; int Max,Min; void Renew(int x) { Max=max(Max,x); Min=min(Min,x); } bool Legal() { return Max-Min>Len; } bool equals(uint _h[4])const { for(int i=0;i<4;i++) if(h[i]!=_h[i])return false; return true; } }Data[maxn],*Now,*H[size]; void Clear() { Now=Data; rep(i,size) H[i]=0; } node* new_node(uint h[4],int start,node*next) { memcpy(Now->h,h,sizeof(Now->h)); Now->Max=Now->Min=start; Now->next=next; return Now++; } bool Insert(uint h[4],int start) { int t=h[0]%size; for(node*i=H[t];i;i=i->next) if(i->equals(h)) { i->Renew(start); return i->Legal(); } H[t]=new_node(h,start,H[t]); return false; }}H;bool Check(int l){ H.Clear(); Len=l;uint e[4]={1,1,1,1}; rep(i,4)rep(j,l-1)e[i]*=seed[i]; uint h[4]={0}; rep(i,l)rep(j,4) h[j]*=seed[j],h[j]+=A[i]; H.Insert(h,0); for(int i=1;i+l<=n;i++) { rep(j,4) { h[j]-=A[i-1]*e[j]; h[j]*=seed[j]; h[j]+=A[i+l-1]; } if(H.Insert(h,i)) return true; } return false;}bool Init(){ cin>>n;if(!n)return false;rep(i,n)scanf("%d",A+i); rep(i,n-1) A[i]=A[i+1]-A[i]+90; –n; return true;}void Work(){ int l=0,r=n/2+2; while(l+1<r) { int m=(l+r)/2; if(Check(m))l=m; else r=m; } ++l; if(l<5)cout<<0<<endl; else cout<<l<<endl;}bool Solve(){ if(!Init())return false; Work(); return true;}int main(){ //freopen("in","r",stdin); //freopen("theme.in","r",stdin); //freopen("theme.out","w",stdout); while(Solve());}

这道题目很显然是强连通的题目，用Tarjan算法求出强连通分量之后，要注意一些细节，
单个人不算爱心天使！靠靠靠。。所以强连通分量要特判的。
很显然如果入度为0的强连通分量有2个或以上，就不行了。
而且如果这个分量是一个人的话，还是-1囧。。我基本靠STL。。真爽饿(*^__^*)
幸好样例很强大，1AC了(*^__^*)
Code：

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int inf=~0U>>1,maxn=1000;int n,m;vvi E;vi ord,low,inStack,Stack,id;int cnt=0,snt=0;int dfs(int x){ ord[x]=low[x]=++cnt; inStack[x]=true;Stack.pb(x); tr(i,E[x]) if(!ord[*i]) low[x]=min(low[x],dfs(*i)); else if(inStack[*i]) low[x]=min(low[x],ord[*i]); if(ord[x]==low[x]) { int u;do{u=Stack.back();Stack.pop_back();id[u]=snt;inStack[u]=false;}while(u!=x); snt++; } return low[x];}void Init(){ cin>>n>>m;int s,t; E.resize(n); while(m–) { scanf("%d %d",&s,&t); E[t-1].pb(s-1); }}void Work(){ vi In,Num; ord=low=inStack=id=vi(n,0); rep(i,n)if(!ord[i])dfs(i); In=Num=vi(snt,0); rep(i,n)tr(e,E[i]) if(id[i]!=id[*e]) In[id[*e]]++; rep(i,n) Num[id[i]]++; int t=0; rep(i,snt)if(Num[i]>1) ++t; cout<<t<<endl; if(count(all(In),0)>1) cout<<-1<<endl; else { int ans=find(all(In),0)-In.begin(); if(Num[ans]==1){cout<<-1<<endl;return;} rep(i,n)if(id[i]==ans)cout<<i+1<<" "; cout<<endl; }}int main(){ //freopen("in","r",stdin); Init(); Work();}

为了方便编程，我打了个Marco头文件，以后就方便了。。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int inf=~0U>>1;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;

这个是次小生成树，我用的是n^2的算法，先算出最小生成树，然后算出每一条路径中最大的边，然后枚举每一条不再树上的边。。
代码写的巨丑。。悲剧囧。
Code：
#include<cstdio>#include<vector>#include<algorithm>#include<iostream>#define all(x) x.begin(),x.end()using namespace std;typedef pair<int,int> ii;typedef pair<int,ii> Edge;typedef vector<ii> vii;typedef vii::iterator vit;typedef vector<vii> vvii;vector<Edge> E,NotOnTree;vector<int> F;const int maxn=500;int n,m;void setF(){ for(int i=0;i<n;i++)F.push_back(i);}int Find(int x){ if(x==F[x]) return x; return F[x]=Find(F[x]);}void Union(int a,int b){ F[b]=a;}void Init(){ scanf("%d %d",&n,&m);int s,t,c; while(m–) { scanf("%d %d %d",&s,&t,&c);–s;–t; E.push_back(Edge(c,ii(s,t))); }}vii edge[maxn];int Total=0;void Ins_Edge(int s,int t,int c){ edge[s].push_back(ii(t,c)); edge[t].push_back(ii(s,c));}void dealEdge(const Edge&e){ ii t=e.second; int i=Find(t.first),j=Find(t.second); if(i!=j) { Union(i,j); Ins_Edge(t.first,t.second,e.first); Total+=e.first; } else { NotOnTree.push_back(e); }}void CalMST(){ sort(all(E)); setF(); for_each(all(E),dealEdge);}int Max_Edge[maxn][maxn];int s;void dfs(int x,int f,int Max){ Max_Edge[s][x]=Max; for(vit e=edge[x].begin();e!=edge[x].end();++e) if(e->first!=f) dfs(e->first,x,max(Max,e->second));}int Ans;void dealEdge2(const Edge&e){ int Now=Total-Max_Edge[e.second.first][e.second.second]+e.first; //cout<<e.second.first<<" "<<e.second.second<<" "<<e.first<<endl; //cout<<Now<<endl; if(Ans==-1||Now<Ans) Ans=Now;}void Work(){ CalMST();Ans=-1; for(int i=0;i<n;i++)s=i,dfs(i,-1,0); for_each(all(NotOnTree),dealEdge2); cout<<"Cost:"<<Total<<endl; cout<<"Cost:"<<Ans<<endl;}int main(){ //freopen("in","r",stdin); Init(); Work();}

额。。拿了0分







纯属发泄。。

[ZJOI2008]骑士

Time Limit:10000MS  Memory Limit:165536K
Total Submit:62 Accepted:30
Case Time Limit:2000MS

Description

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军 队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝 对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛 盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

Input

第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

Output

应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

Sample Input

3
10 2
20 3
30 1

Sample Output

30
【数据规模】
对于30%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 100；
对于80%的测试数据，满足N ≤ 10 000。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

Source

啊啊啊。总算A掉了。。
61.187.179.132:8080/JudgeOnline/showproblem
注意到这样形成的图的每个联通块顶上必然是一堆树根组成的环，那么对每个树用树形DP算出选根和不选根的最大收入，然后就变成环上的问题了，就比较简单了。。
自己画的图，好悲剧囧。。

不过感觉我这个方法还不错，就是不是用树形DP去算，而是从底往上更新，每一种状态和规则都写一个类来表示更不容易出错(*^__^*) 。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000000;
struct StateTree
{
long long A[2];
long long operator()(int v)const{return A[v];}
StateTree(int val=0)
{
A[0]=0;A[1]=val;
}
void Renew(const StateTree&son)
{
A[0]+=max(son(0),son(1));
A[1]+=son(0);
}
}Dp[maxn];
struct StateCircle
{
long long A[2][2];
long long operator()(int l,int r){return A[l][r];}
StateCircle(const StateTree&x)
{
memset(A,0,sizeof(A));
A[0][0]=x(0);
A[1][1]=x(1);
}
void Renew(const StateTree&x)
{
long long Ans[2][2];
rep(i,2)
{
Ans[i][0]=max(A[i][0],A[i][1])+x(0);
Ans[i][1]=A[i][0]+x(1);
}
memcpy(A,Ans,sizeof(A));
}
};
int In[maxn],P[maxn],C[maxn],n;
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);
rep(i,n) scanf("%d %d",C+i,P+i),In[–P[i]]++,Dp[i]=StateTree(C[i]);
queue<int> Q;
rep(i,n)if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();
Dp[P[t]].Renew(Dp[t]);
if(–In[P[t]]==0) Q.push(P[t]);
}
long long Ans=0;
rep(i,n)if(In[i]>0)
{
In[i]=0;int t=i;
StateCircle now=StateCircle(Dp[t]);
t=P[t];
while(t!=i)
{
now.Renew(Dp[t]);In[t]=0;
t=P[t];
}
Ans+=max(now(1,0),max(now(0,0),now(0,1)));
}
cout<<Ans<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem
额。。这是很老的强联通题目了。刚刚弄懂了Tarjan算法。。就像实践一下。。结果WA了
很久。。最后发现原来是Stack搞错了。。真是悲剧。。
就是求出每个强联通分量，然后如果入度为0的分量只有一个，答案就是这个分量的大小，否则就是0
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
vector<int> E[maxn];
typedef vector<int>::iterator it;
int ord[maxn],low[maxn],cnt=0,id[maxn],snt=0,n,m;
bool inStack[maxn]={0};
stack<int> Stack;
void dfs(int x)
{
ord[x]=low[x]=cnt++;
inStack[x]=true;Stack.push(x);
for(it i=E[x].begin();i!=E[x].end();++i)
{
if(ord[*i]==-1)
dfs(*i),low[x]=min(low[x],low[*i]);
else if(inStack[*i]) low[x]=min(low[x],ord[*i]);
}
if(ord[x]==low[x])
{
int u;do{u=Stack.top();Stack.pop();id[u]=snt;inStack[u]=false;}while(u!=x);
snt++;
}
}
int Num[maxn]={0},In[maxn]={0};
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int s,t;
while(m–) scanf("%d %d",&s,&t),E[t-1].pb(s-1);
rep(i,n) ord[i]=-1;
rep(i,n)if(ord[i]==-1) dfs(i);
rep(i,n){
int own=id[i];for(it e=E[i].begin();e!=E[i].end();++e)if(id[*e]!=own) In[id[*e]]++;
Num[own]++;
}
t=0;int ans=0;rep(i,snt)if(In[i]==0) ++t,ans+=Num[i];
if(t>1)cout<<0<<endl;
else cout<<ans<<endl;
}

[ZJOI2008]生日聚会Party

Time Limit:10000MS  Memory Limit:165536K
Total Submit:35 Accepted:20
Case Time Limit:1000MS

Description

今天是hidadz小朋友的生日，她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件：
对于任意连续的一段，男孩与女孩的数目之差不超过k。
很快，小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种， 那么到底有多少种呢？热爱数学的hidadz和她的朋友们开始思考这个问题……
假设参加party的人中共有n个男孩与m个女孩，你是否能解答Susie和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目 除以12345678的余数。

Input

仅包含一行共3个整数，分别为男孩数目n, 女孩数目m, 常数k。

Output

应包含一行，为题中要求的答案。

Sample Input

1 2 1

Sample Output

1

Hint

对于30%的数据，n , m ≤ 20；
对于100%的数据, n , m ≤ 150，k ≤ 20。

Source

61.187.179.132:8080/JudgeOnline/showproblem
额。就是DP不知道有没有什么公式的。
设dp(i,j,k1,k2)是有i个人，j个男的，右端最多男生比女生多k1个，最多女生比男生多k2个，
跟算最大连续子序列的线段树差不多。。
然后就可以直接DP了。。由于空间不够，要用滚动数组额。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=150+1,maxk=20+1,mod=12345678;
int n,m,k;
int dp[2][maxn][maxk][maxk];
void add(int&a,int x)
{
a+=x;a%=mod;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>k;
int now=0,old=1;
dp[now][0][0][0]=1;
for(int i=0;i<n+m;++i)
{
swap(now,old);
memset(dp[now],0,sizeof(dp[now]));
for(int j=0;j<=min(i,n);++j)
for(int k1=0;k1<=min(j,k);++k1)
for(int k2=0;k2<=min(i-j,k);++k2)
{
int x=dp[old][j][k1][k2];
if(k1<k&&j<n) add(dp[now][j+1][k1+1][max(k2-1,0)],x);
if(k2<k&&i-j<m) add(dp[now][j][max(k1-1,0)][k2+1],x);
}
}
int ans=0;
rep(k1,k+1)rep(k2,k+1) ans+=dp[now][n][k1][k2],ans%=mod;
cout<<ans<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem
额。。水题直接上矩阵乘法。。
由于m比较小实际上没必要用KMP算法算出原始矩阵的，不过我乘机学习了一下KMP算法囧。。
还有就是我昨天一直在调我那个QTREE的程序。。到现在都没有调好。。我真是太菜了555.
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxm=20;
int n,m,mod,A[maxm],next[maxm+1];
struct Mat
{
int M[maxm][maxm];
Mat(){memset(M,0,sizeof(M));}
void operator=(const Mat&o)
{memcpy(M,o.M,sizeof(M));}
int& operator()(int i,int j){return M[i][j];}
Mat operator*(Mat&o)
{
Mat T;
rep(i,m)rep(j,m)rep(k,m)T(i,j)+=M[i][k]*o(k,j),T(i,j)%=mod;
return T;
}
}orig;
Mat Power(int n)
{
if(n==1) return orig;
Mat tmp=Power(n/2);
tmp=tmp*tmp;
if(n&1) tmp=tmp*orig;
return tmp;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m>>mod;char x;
rep(i,m) cin>>x,A[i+1]=x-‘0’;
next[1]=0;int t=0;
for(int i=2;i<=m;i++)
{
while(t>0&&A[t+1]!=A[i]) t=next[t];
if(A[t+1]==A[i])++t;
next[i]=t;
}
for(int i=0;i<m;++i)
{
rep(j,10)
{
int t=i;
while(t>0&&A[t+1]!=j)t=next[t];
if(A[t+1]==j)++t;
orig(t,i)++;
}
}
Mat ans=Power(n);int Ans=0;
rep(i,m) Ans+=ans(i,0),Ans%=mod;
cout<<Ans<<endl;
}

61.187.179.132:8080/JudgeOnline/showproblem
这道题很有意思啊。。就是说一棵树对一些顶点的度数有要求一些没有，让你求这样的树的度数。
我一开始想DP脑子都爆了也没想出来。。最后想到Prufer Code。。然后就明白了。。
Prufer Code是把每棵n点的树对应到长度为n-2，数在1-n之间的数列。。其中一个度数为d的点出现d-1次。。
wiki上的说明:en.wikipedia.org/wiki/Prufer_code
这就是关键。所以问题就转化成求这样的数列的数目了。。这用多重集的公式很方便，就不多说了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000;
int n;
vector<int> Prime;
typedef vector<int>::iterator it;
int D[maxn],S=0,noLimit=0;
bool isPrime(int x)
{
if(x==2) return true;
if(x/2==0) return false;
for(int i=3;i*i<=x;i+=2)
if(x%i==0) return false;
return true;
}
void getPrime()
{
for(int i=2;i<=n;i++)
if(isPrime(i)) Prime.pb(i);
}
void init()
{
cin>>n;
rep(i,n)
{
cin>>D[i];
if(D[i]>0)
S+=D[i]-1;
else
noLimit++;
}
}
struct BigInt
{
int H[400];
BigInt(){memset(H,0,sizeof(H));}
void mul(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x/=Prime[i],H[i]++;
}
void div(int x)
{
rep(i,Prime.size())
while(x%Prime[i]==0) x/=Prime[i],H[i]–;
}
};
ostream& operator<<(ostream&out,const BigInt&x)
{
static int Hp[100000],last;
memset(Hp,0,sizeof(Hp));Hp[last=0]=1;
rep(i,Prime.size())
{
rep(j,x.H[i])
{
int o=Prime[i],d=0;
rep(k,last+1)
{
d+=Hp[k]*o;
Hp[k]=d%10;
d/=10;
}
while(d) Hp[++last]=d%10,d/=10;
}
}
for(int i=last;i>=0;–i)out<<Hp[i];
return out;
}
void work()
{
if(S>n-2){cout<<0<<endl;return;}
if(noLimit==0&&S<n-2){cout<<0<<endl;return;}
getPrime();
BigInt ans;
for(int i=1;i<=n-2;i++)
ans.mul(i);
rep(i,n)
{
if(D[i]>0)
for(int j=1;j<=D[i]-1;j++)
ans.div(j);
}
for(int i=1;i<=n-2-S;i++)
ans.div(i);
rep(i,n-2-S) ans.mul(noLimit);
cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
init();
work();
}
PS。。o(︶︿︶)o 这个OJ不能用Java。还得自己写高精度囧。。