做了SDOI第一輪的一試題，差點被完虐。。。
內存限制竟然全部是2MB??！而且linux下arbiter，2MB竟然無法檢測，全部判定為Wrong Answers??！
浪費了我好多時間。
第一題，遞推+高精度，類似于AHOI2010的送分題。
我自以為聰明，用了和遞推一樣復雜度的模擬，結果90分。
原來，我那種算法對于n==1是不成立。。。。
（前幾名中好像只有一個人AC了，其他和我一樣90）
第二題，真的是模擬了，但需要一定的技巧，果斷AC。
然后發(fā)現(xiàn)這個題我虐爆全場了，可能是因為我用cpp的原因。
第三題，最小路徑覆蓋。沒有思路，本想寫搜索，顯然沒有時間。
于是想貪心，考慮到答案可能會根據(jù)數(shù)據(jù)規(guī)模呈對數(shù)級增長，于是直接輸出
2*int(log(n+m)/log(3.141592653*2))
【常數(shù)全是瞎編的，唯一的確定的是那個n+m,技巧就是隨便弄幾個小數(shù)據(jù)，都滿足即可】
結果過了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;
}
第三題是這樣構圖的：原邊數(shù)n，構建一個X,Y集合各有n個節(jié)點的二分圖，X表示發(fā)出，Y表示接受，
原圖中a->b的有向邊轉化成二分圖中x[a]與y[b]之間的無向邊（目前見過的二分圖都是無向的）
然后求出最大匹配數(shù)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;
}