昨天晚上做了一下，結(jié)果真的被虐爆了，考完之后毫無(wú)感覺(jué)，直接睡覺(jué)。。。
第一題超惡心，不僅要輸出結(jié)果還要輸出方案，打了半個(gè)小時(shí)草稿，
連計(jì)算方案的算法也沒(méi)搞出來(lái)，只以為是搜索了，但因?yàn)楹竺鎯商鞗](méi)時(shí)間寫(xiě)了。。。
最后手算1~16輸出，10分。。。
第二題：二進(jìn)制的高精度Stein算法，一開(kāi)始以為數(shù)字只會(huì)變小，就按照讀入順序存的
結(jié)果掛掉。。重寫(xiě)，因各種原因掛掉。。50
第三題，并查集，做過(guò)的，AC。
結(jié)果160，勉強(qiáng)第四。
如果第三題沒(méi)有做過(guò)，就要100-，10+了。。。
PS:神奇地發(fā)現(xiàn)總分上升到第二。。。幾個(gè)只會(huì)做水題的同學(xué)悲劇了。可以見(jiàn)得，多試對(duì)于選拔選手是有一定好處的。
好吧，總結(jié)一下。
首先是考試策略問(wèn)題。
第一題的確是搜索，裸的ID-DFS就可以AC（寫(xiě)了不超過(guò)10分鐘。。），完全不需要數(shù)學(xué)方法。。。
當(dāng)然我看到了一個(gè)比我的程序10多倍的搜索程序，正在研究中。
裸的ID-DFS
#include<cstdio>
#include<bitset>
#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])
int ans[16],depth,n,p;
void dfs(int i);
ifstream fin("shulie.in");
ofstream fout("shulie.out");
int main()
{
fin>>n;
NFOR(depth,1,15)p=ans[1]=1,dfs(2);
}
void dfs(int i){
if(ans[p]==n){
fout<<p<<"\n";
FOR(i,1,p-1)fout<<ans[i]<<" ";
fout<<n,exit(0);
}
if(i>depth)return;
DFOR(k,p,1)//下一項(xiàng)是由最后一項(xiàng)和前p項(xiàng)中的任意一項(xiàng)構(gòu)成的，易證其正確性
p++,ans[p]=ans[p-1]+ans[k],dfs(i+1),p--;
}
快我10的代碼（pas）
program shulie;
var
a:array[1..20] of longint;
i,j,k,n:longint;
procedure CloseFile;
begin
close(input); close(output); halt;
end;
procedure dfs(step:longint);
var
i,j:longint;
begin
for i:=step-1 downto 1 do
for j:=step-1 downto i do
begin
a[step]:=a[i]+a[j];
if a[step]>n then continue;
if (a[step]<a[step-1]) or (a[step] shl (k-step)<n) then break;
if a[step]=n then
begin
writeln(k);
for k:=1 to step-1 do
write(a[k],' ');
writeln(a[step]);
CloseFile;
end;
if step<k then dfs(step+1);
end;
end;
begin
assign(input,'shulie.in'); reset(input);
assign(output,'shulie.out'); rewrite(output);
readln(n);
case n of
1:begin
writeln(1); writeln(1); CloseFile;
end;
2:begin
writeln(2); writeln(1,' ',2); CloseFile;
end;
end;
k:=2; a[1]:=1; a[2]:=2;
repeat
inc(k); dfs(3);
until false;
end.第二題，一者是算法不全面（有可能就是錯(cuò)的），使代碼過(guò)長(zhǎng)。
二者比較函數(shù)，寫(xiě)錯(cuò)了。。。
stein算法核心代碼：
int t=equal(a,b);
if(t==2){gcd(b,a);return;}
else if(t==0){copy(ans,b);return;}
if(b[0]==1&&b[1]==1){copy(ans,b);return;}
if((b[0]==1||b[0]==0)&&b[1]==0){copy(ans,a);return;}
//
if(!(b[1]&1)&&!(a[1]&1)){div2(a),div2(b),gcd(a,b),tim2(ans);return;}
if((b[1]&1)&&(a[1]&1)){sub(a,b),gcd(a,b);return;}
//這一類(lèi)有兩種方法gcd(a,b)=gcd((a+b)/2,(a-b)/2) 或 gcd(a,b)=gcd(a-b,b)實(shí)現(xiàn)起來(lái)差距巨大
if(!(b[1]&1)&&(a[1]&1)){div2(b),gcd(a,b);return;}
if((b[1]&1)&&!(a[1]&1)){div2(a),gcd(a,b);return;}
完整代碼
#include<cstdio>
#include<bitset>
#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=1005;
typedef long long int64;
//
int L[maxn],R[maxn];
int ans[maxn];
int S1[maxn],S2[maxn];
char c;
void gcd(int a[],int b[]);
int equal(int a[],int b[]);
void sub(int a[],int b[]);//c=a-b
void copy(int a[],int b[]){DFOR(i,a[0],0)a[i]=0;FOR(i,0,b[0])a[i]=b[i];}//a=b
void div2(int a[]);//a/=2
void tim2(int a[]);//a*=2;
int main(){
freopen("bian.in","r",stdin);
freopen("bian.out","w",stdout);
int a[10],b[10];
MM(ans,0),MM(L,0),MM(R,0),MM(a,0),MM(b,0);
for(;;){
scanf("%c",&c);
if(48<=c&&c<=49)L[0]++,L[L[0]]=c-48;
else break;
}
FOR(i,1,L[0]/2)swap(L[i],L[L[0]-i+1]);
for(;scanf("%c",&c)!=EOF;){
if(48<=c&&c<=49)R[0]++,R[R[0]]=c-48;
else break;
}
FOR(i,1,R[0]/2)swap(R[i],R[R[0]-i+1]);
gcd(L,R);
DFOR(i,ans[0],1)printf("%d",ans[i]);
}
void show(int a[]){DFOR(i,a[0],1)printf("%d",a[i]);}
void gcd(int a[],int b[]){//a>=b
int t=equal(a,b);
if(t==2){gcd(b,a);return;}
else if(t==0){copy(ans,b);return;}
if(b[0]==1&&b[1]==1){copy(ans,b);return;}
if((b[0]==1||b[0]==0)&&b[1]==0){copy(ans,a);return;}
//
if(!(b[1]&1)&&!(a[1]&1)){div2(a),div2(b),gcd(a,b),tim2(ans);return;}
if((b[1]&1)&&(a[1]&1)){sub(a,b),gcd(a,b);return;}
if(!(b[1]&1)&&(a[1]&1)){div2(b),gcd(a,b);return;}
if((b[1]&1)&&!(a[1]&1)){div2(a),gcd(a,b);return;}
//
}
void sub(int a[],int b[]){
FOR(i,1,b[0]){
a[i]-=b[i];
while(a[i]<0)a[i]+=2,a[i+1]--;
}
FOR(i,1,a[0])while(a[i]<0)a[i]+=2,a[i+1]--;
while(a[a[0]]<=0)a[0]--;
}
void div2(int a[]){
FOR(i,1,a[0]-1)
a[i]=a[i+1];
a[0]--;
}
void tim2(int a[]){
DFOR(i,a[0]+1,2)
a[i]=a[i-1];
a[1]=0;
a[0]++;
}
int equal(int a[],int b[]){//1:a>b 2:a<b 0:a==b
if(a[0]>b[0])return 1;
else if(a[0]<b[0])return 2;
DFOR(i,a[0],1)
if(a[i]>b[i])return 1;
else if(a[i]<b[i])return 2;
return 0;
}
第三題，并查集，運(yùn)用拆點(diǎn)法，把它拆成，本身的集合和相對(duì)的集合兩個(gè)部分。然后很水的。。
第二題不會(huì)fin的讀入，所以用freopen，這個(gè)復(fù)制過(guò)來(lái)的。。。
#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=50005;
typedef long long int64;
int n,m;
int par[maxn*2],rank[maxn*2];
int ans=0;
int x,y,z;
int Getpar(int a){if(par[a]!=a)par[a]=Getpar(par[a]);return par[a];}
void Makeset(int a){par[a]=a;rank[a]=0;}
void Union(int a,int b){
a=Getpar(a),b=Getpar(b);
if(rank[a]>rank[b])par[b]=a;
else {par[a]=b;
if (rank[a]==rank[b])rank[b]++;}
}
int main(){
freopen("str.in","r",stdin);
freopen("str.out","w",stdout);
scanf("%d %d",&n,&m);
FOR(i,0,maxn*2-1)Makeset(i);
FOR(i,1,m){
scanf("%d %d %d",&x,&y,&z);
if(z==0){
if(Getpar(x-1)==Getpar(y+maxn)){ans++;continue;}
Union(x-1,y);
Union(x-1+maxn,y+maxn);
}
else{
if(Getpar(x-1)==Getpar(y)){++ans;continue;}
Union(x-1,y+maxn);
Union(x-1+maxn,y);
}
}
printf("%d\n",ans);
return 0;
}