[SCOI2009]迷路

Time Limit:10000MS  Memory Limit:165536K
Total Submit:40 Accepted:24
Case Time Limit:1000MS

Description

windy在有向图中迷路了。
该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？
注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

Input

第一行包含两个整数，N T。
接下来有 N 行，每行一个长度为 N 的字符串。
第i行第j列为’0’表示从节点i到节点j没有边。
为’1’到’9’表示从节点i到节点j需要耗费的时间。

Output

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

Sample Input

【输入样例一】
2 2
11
00

【输入样例二】
5 30
12045
07105
47805
12024
12345

Sample Output

【输出样例一】
1

【样例解释一】
0->0->1

【输出样例二】
852

Hint

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

Source

Day2

我擦啊！61.187.179.132:8080/JudgeOnline/showproblem
我一开始没想出来怎么做，很明显要用矩阵乘法，所以我就想怎么搞。。
我想了半天没有什么头绪，感觉这个长度很麻烦，感觉矩阵乘法就是从一个推出下一个，推不出下面很多个额。。很头疼。
过了一天发现由于长度最长是9。。。所以把每9个打包起来就再递推就OK了。。
可是我：

晕死了。。那几个WA是我故意写return 0查出错点的。。
最后发现原来因为矩阵有点大，导致如果我直接在乘法里写临时变量的话会MLE。。
靠靠靠。。我本来就没什么AC率的。。现在悲剧大发了。。
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 maxt=9,maxv=90,maxn=10,mod=2009;
int n,v;
inline int node(int time,int pos)
{
return time*n+pos;
}
int tmp[maxv][maxv];
struct Mat
{
int M[maxv][maxv];
int&operator()(int i,int j){return M[i][j];}
Mat(){memset(M,0,sizeof(M));}
void operator*=(Mat&o)
{
memset(tmp,0,sizeof(tmp));
rep(i,v)rep(j,v)rep(k,v)
tmp[i][j]+=M[i][k]*o(k,j),tmp[i][j]%=mod;
memcpy(M,tmp,sizeof(M));
}
void operator=(const Mat&o)
{
memcpy(M,o.M,sizeof(M));
}
}orig;
int Map[maxn][maxn];
void Power(int n,Mat&ret)
{
if(n==1){ret=orig;return;}
Power(n/2,ret);
ret*=ret;
if(n&1)ret*=orig;
}
int main()
{
//freopen("in","r",stdin);
//freopen("road.in","r",stdin);
//freopen("road.out","w",stdout);
int T;
scanf("%d %d",&n,&T);char x;v=n*9;
rep(i,n)
{
scanf("n");
rep(j,n)scanf("%c",&x),Map[i][j]=x-‘0’;
}
rep(i,n)for(int t=0;t<8;t++)
orig(node(t,i),node(t+1,i))++;
rep(i,n)rep(j,n)if(Map[j][i])
orig(node(8,i),node(9-Map[j][i],j))++;
Mat Ans;Power(T,Ans);
int dp[maxn][maxt]={0};
dp[0][0]=1;
for(int t=1;t<maxt;t++)
{
rep(i,n)rep(j,n)
if(Map[j][i])
if(t-Map[j][i]>=0)
{
dp[i][t]+=dp[j][t-Map[j][i]];
dp[i][t]%=mod;
}
}
int ans=0;
rep(i,n)rep(t,maxt)
{
ans+=Ans(node(0,n-1),node(t,i))*dp[i][t];
ans%=mod;
}
cout<<ans<<endl;
}

靠。。刚想出这道题Vijos居然奔溃了。。我哭啊。。
题目是说给你n个数，都小于10^5，然后让你求出其中一个子序列（连不连续无所谓，只要顺序是原序列的顺序就OK）。。相邻两个数不互质。。让你求这个序列的最大长度。。n<=100000
很明显暴力DP是会悲剧的，如果你用Dpi表示第i个数结尾的最长长度然后O(n)枚举前一个的话是O(n^2)的。关键是利用题目的性质。
注意到不互质的数一定有一个公共的质因子，就简单了。首先算出10^5一下每个质数，然后开个数组保存每个当前以第i个质数的倍数结尾的数列的最长值，然后对于每个数枚举他的每个质因子计算并更新一下就可以了。。
关键是一个数的质因子数目显然是O(logn)级别的，并且预先处理也可以大大降低枚举量。。程序还是很快的。。
不过VJ挂了。没法测了囧。。

这是一道很经典的题目了。。题目在：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;
}