做了SDOI第一輪的一試題，差點(diǎn)被完虐。。。
內(nèi)存限制竟然全部是2MB！！而且linux下arbiter，2MB竟然無(wú)法檢測(cè)，全部判定為Wrong Answers！！
浪費(fèi)了我好多時(shí)間。
第一題，遞推+高精度，類似于AHOI2010的送分題。
我自以為聰明，用了和遞推一樣復(fù)雜度的模擬，結(jié)果90分。
原來(lái)，我那種算法對(duì)于n==1是不成立。。。。
（前幾名中好像只有一個(gè)人AC了，其他和我一樣90）
第二題，真的是模擬了，但需要一定的技巧，果斷AC。
然后發(fā)現(xiàn)這個(gè)題我虐爆全場(chǎng)了，可能是因?yàn)槲矣胏pp的原因。
第三題，最小路徑覆蓋。沒(méi)有思路，本想寫(xiě)搜索，顯然沒(méi)有時(shí)間。
于是想貪心，考慮到答案可能會(huì)根據(jù)數(shù)據(jù)規(guī)模呈對(duì)數(shù)級(jí)增長(zhǎng)，于是直接輸出
2*int(log(n+m)/log(3.141592653*2))
【常數(shù)全是瞎編的，唯一的確定的是那個(gè)n+m,技巧就是隨便弄幾個(gè)小數(shù)據(jù)，都滿足即可】
結(jié)果過(guò)了2個(gè)點(diǎn)。
后來(lái)看了題解，是轉(zhuǎn)化成二分圖做，正在研究中。
最后90+100+20=210，SD第4，考慮到最后一題爆0的概率，SD第5還有的
（NO3,4,5都是最后一題偏分的。。。最強(qiáng)的騙了30分）
（NO1,2 AC了最后一題，結(jié)果第二題。。。。）
第一題AC代碼（M=1時(shí)輸出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;
}
第二題模擬鏈表水掉（手寫(xiě)的萬(wàn)能線性表傳說(shuō)）
#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;
}
第三題是這樣構(gòu)圖的：原邊數(shù)n，構(gòu)建一個(gè)X,Y集合各有n個(gè)節(jié)點(diǎn)的二分圖，X表示發(fā)出，Y表示接受，
原圖中a->b的有向邊轉(zhuǎn)化成二分圖中x[a]與y[b]之間的無(wú)向邊（目前見(jiàn)過(guò)的二分圖都是無(wú)向的）
然后求出最大匹配數(shù)M 。 最終結(jié)果為n-M。我只有記結(jié)論的水平，證明略。
第三題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;
}