做了SDOI第一轮的一试题，差点被完虐。。。
内存限制竟然全部是2MB！！而且linux下arbiter，2MB竟然无法检测，全部判定为Wrong Answers！！
浪费了我好多时间。
第一题，递推+高精度，类似于AHOI2010的送分题。
我自以为聪明，用了和递推一样复杂度的模拟，结果90分。
原来，我那种算法对于n==1是不成立。。。。
（前几名中好像只有一个人AC了，其他和我一样90）
第二题，真的是模拟了，但需要一定的技巧，果断AC。
然后发现这个题我虐爆全场了，可能是因为我用cpp的原因。
第三题，最小路径覆盖。没有思路，本想写搜索，显然没有时间。
于是想贪心，考虑到答案可能会根据数据规模呈对数级增长，于是直接输出
2*int(log(n+m)/log(3.141592653*2))
【常数全是瞎编的，唯一的确定的是那个n+m,技巧就是随便弄几个小数据，都满足即可】
结果过了2个点。
后来看了题解，是转化成二分图做，正在研究中。
最后90+100+20=210，SD第4，考虑到最后一题爆0的概率，SD第5还有的
（NO3,4,5都是最后一题偏分的。。。最强的骗了30分）
（NO1,2 AC了最后一题，结果第二题。。。。）
第一题AC代码（M=1时输出2^D）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define NFOR(i,a,b) for(i=a;i<=b;i++)
#define DFOR(i,b,a) for(int i=b;i>=a;i--)
#define NDFOR(i,b,a) for(i=b;i>=a;i--)
#define PFOR(p,head,next) for(int p=head;p;p=next[p])
#define NPFOR(p,head,next) for(p=head;p;p=next[p])
const int INF=~0U>>2;
const int maxn=105;
typedef long long int64;
//
ifstream fin("rabbit.in");
ofstream fout("rabbit.out");
int A[maxn][maxn];
int ans[maxn];
int main()
{
int M,D;
MM(A,0),MM(ans,0);
fin>>M>>D;
if(M==1){
ans[0]=1,ans[1]=1;
FOR(i,1,D){
FOR(k,1,ans[0])ans[k]*=2;
FOR(k,1,ans[0])ans[k+1]+=ans[k]/10,ans[k]%=10;
if(ans[ans[0]+1])ans[0]++;
}
DFOR(i,ans[0],1)fout<<ans[i];
fin.close();
fout.close();
return 0;
}
A[M][0]=1,A[M][1]=1;
FOR(i,1,D){
FOR(k,0,A[M][0])
A[M+1][k]=A[M][k];
FOR(k,1,A[M-1][0]){
A[M][k]+=A[M-1][k];
A[M][k+1]+=A[M][k]/10;
A[M][k]%=10;
A[M-1][k]=0;
}
if(A[M][A[M][0]+1]>0)A[M][0]++;
DFOR(j,M-2,1)
FOR(k,0,A[j][0])
A[j+1][k]=A[j][k];
FOR(k,0,A[M+1][0])
A[1][k]=A[M+1][k];
//FOR(j,1,M)printf("%d ",A[j][1]);printf("\n");
}
FOR(k,0,A[M][0])
ans[k]=A[M][k];
FOR(j,1,M-1){
FOR(k,1,A[j][0]){
ans[k]+=A[j][k];
ans[k+1]+=ans[k]/10;
ans[k]%=10;
}
if(ans[ans[0]+1]>0)ans[0]++;
}
DFOR(i,ans[0],1)
fout<<ans[i];
fin.close();
fout.close();
return 0;
}
第二题模拟链表水掉（手写的万能线性表传说）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define NFOR(i,a,b) for(i=a;i<=b;i++)
#define DFOR(i,b,a) for(int i=b;i>=a;i--)
#define NDFOR(i,b,a) for(i=b;i>=a;i--)
#define PFOR(p,head,next) for(int p=head;p;p=next[p])
#define NPFOR(p,head,next) for(p=head;p;p=next[p])
const int INF=~0U>>2;
const int maxn=100001;
typedef long long int64;
//
ifstream fin("team.in");
ofstream fout("team.out");
short int team[maxn];
int last[301];
int next[maxn];
int head=-1,tail=-1;
string s,aa="ENQUEUE",bb="DEQUEUE",cc="STOP";
int main(){
int m,k,t;
MM(last,0xff),MM(next,0xff),MM(team,0);
fin>>m;
FOR(i,1,m){
fin>>k;
FOR(j,1,k)
fin>>t,team[t]=i;
}
s.clear();
for(;;){
fin>>s;
if(s==cc)break;
else if(s==aa){
fin>>t;
if(tail==-1){
head=tail=t;
last[team[t]]=t;
next[t]=-1;
}
else if(last[team[t]]!=-1){
if(next[last[team[t]]]!=-1)
next[t]=next[last[team[t]]];
else
tail=t,next[t]=-1;
next[last[team[t]]]=t;
last[team[t]]=t;
}
else {
last[team[t]]=t;
next[tail]=t;
tail=t;
next[t]=-1;
}
}
else {
fout<<head<<"\n";
if(last[team[head]]==head)last[team[head]]=-1;
if(head==tail)head=tail=-1;
else head=next[head];
}
s.clear();
}
fin.close();
fout.close();
return 0;
}
第三题是这样构图的：原边数n，构建一个X,Y集合各有n个节点的二分图，X表示发出，Y表示接受，
原图中a->b的有向边转化成二分图中x[a]与y[b]之间的无向边（目前见过的二分图都是无向的）
然后求出最大匹配数M 。 最终结果为n-M。我只有记结论的水平，证明略。
第三题AC代码（DINIC求最大匹配）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define NFOR(i,a,b) for(i=a;i<=b;i++)
#define DFOR(i,b,a) for(int i=b;i>=a;i--)
#define NDFOR(i,b,a) for(i=b;i>=a;i--)
#define PFOR(p,head,next) for(int p=head;p;p=next[p])
#define NPFOR(p,head,next) for(p=head;p;p=next[p])
const int INF=~0U>>2;
const int maxn=2001;
const int maxm=20001;
//
ifstream fin("trip.in");
ofstream fout("trip.out");
int Q[maxm],H,T;
//
int to[maxm],next[maxm],sc[maxm],snum=0;
int level[maxn],head[maxn],out[maxn];
//
void init(){snum=1;MM(head,0);}
void insert(int x,int y,int c);
int max_flow(int n,int s,int t);
//
int main(){
int n,m,a,b;
fin>>n>>m;init();
FOR(i,1,m)fin>>a>>b,insert(a+1,b+1+n,1);
FOR(i,1,n)insert(n+n+1,i,1),insert(i+n,n+n+2,1);
fout<<n-max_flow(n+n+2,n+n+1,n+n+2);
fin.close();
fout.close();
return 0;
}
void insert(int x,int y,int c){
snum++,to[snum]=y,sc[snum]=c,next[snum]=head[x],head[x]=snum;
snum++,to[snum]=x,sc[snum]=0,next[snum]=head[y],head[y]=snum;}
int max_flow(int n,int s,int t){
int flow=0,cur;
for(;;){MM(level,0);
H=T=1,level[s]=1,Q[H]=s;
for(;H<=T;H++){int &t=Q[H];
PFOR(p,head[t],next)
if(sc[p]&&!level[to[p]])
T++,level[to[p]]=level[t]+1,Q[T]=to[p];}
if(!level[t])break;
FOR(i,1,n)out[i]=head[i];
for(int q=0;;){
if(!q){
NPFOR(cur,out[s],next)
if(sc[cur]&&out[to[cur]]&&level[to[cur]]==2)
break;
if(cur)q++,Q[q]=cur,out[s]=next[cur];
else break;
}
int u=to[Q[q]];
if(u==t){int dd=INF,ddl=0;
FOR(i,1,q)if(sc[Q[i]]<dd)dd=sc[Q[i]],ddl=i;
flow+=dd;
FOR(i,1,q)sc[Q[i]]-=dd,sc[Q[i]^1]+=dd;
FOR(i,1,q)if(!sc[Q[i]]){q=ddl-1;break;}
}
else {
NPFOR(cur,out[u],next)
if(sc[cur]&&out[to[cur]]&&level[u]+1==level[to[cur]])break;
if(cur)q++,Q[q]=cur,out[u]=next[cur];
else out[u]=0,q--;
}
}
}
return flow;
}