。。这道题目模线性方程组的模型很好想。。关键是高斯消元。。我搞的累死就是因为很多地方写错了。。。
幸好还是过了。。
Code。。注意。。消元找主元的时候一定要考虑所有没被消过的元素。。。
#include<iostream>
using namespace std;
const int maxn=100+10;
int A[maxn][maxn]={0};
int P[maxn];
int n,m;
void add(string& a,string b,string c)
{
int d=0,t=max(b.length(),c.length());a="";
for(int i=0;i<t;i++)
{
d+=b[i]+c[i]-2*’0′;
a+=char(d%10+’0′);
d/=10;
}   
if(d)
a+=’1′;
}
void sub(string&a)
{       
a[0]-=1;       
}
void print(const string&a)
{
for(int i=a.length()-1;i>=0;i–)
cout<<a[i];
}
bool isprime(int p)
{
if(p==2) return true;
if(p%2==0) return false;
for(int i=3;i*i<=p;i+=2)
if(p%i==0) return false;
return true;
}
void swap(int&x,int&y)
{int t=x;x=y;y=t;}
int main()
{
cin>>n>>m;
int now=2;
for(int i=0;i<n;i++)
{
while(!isprime(now))
now++;
P[i]=now++;
}
for(int i=0;i<m;i++)
{
int p,t=0;
cin>>p;
for(int j=0;j<n;j++)
{
t=0;
while(p%P[j]==0)
p/=P[j],t++;
A[j][i]=t%2;
}
}
int i;
for(i=0;i<min(n,m);i++)
{
int p,q;
for(p=i;p<n;p++)
for(q=i;q<m;q++)
if(A[p][q]) goto out;
out:
if(p==n)break;
for(int o=0;o<n;o++)
swap(A[o][i],A[o][q]);
for(int o=0;o<=m;o++)
swap(A[i][o],A[p][o]);
for(int o=0;o<n;o++)if(o!=i&&A[o][i])
for(int j=0;j<=m;j++)
A[o][j]^=A[i][j];
}
i=m-i;
string ans="1";
while(i–)
{
add(ans,ans,ans);
}
sub(ans);
print(ans);
}

。。。题目真是比较水阿。。。连我都得了1000。。。
– – – – – – – – – – – – – – – – 45384401 – – – – – – – – – – – – – – – –
– – – – – – – – – – – – – – – USACO NOV09 – – – – – – – – – – – – – – –

Tom Chen / CHN / Grad: 9999 / Div: Gold
As an observer, YOUR RESULTS MIGHT NOT APPEAR ON THE FINAL WEB LISTINGS

Below are the results of grading your submissions against the test data for
the contest.

============================== SUMMARY =============================

— case number —
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
cookie * * * * * * * * * *
lights * * * * * * * * * * * * * * * * *
rescue * * * * * * * * * *

. = no entry t = time exceeded * = correct answer
x = wrong s = signal e = bad exit status/…..1…./
很明显是一个解模线性方程的模型。。但是很可能有多解。。
但实际上可以自由取值的变量的数量不会超过N/2。。
所以只要暴力枚举就可以了。。中途还可以剪枝。。。
Code。。
/*
PROG: lights
LANG: C++
ID: Tom Chen
*/
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=40;
int A[maxn][maxn]={0};
int N[maxn];
void init();
void solve();
int n,m;
void swap(int&x,int&y)
{int t=x;x=y;y=t;}
void init()
{   
freopen("lights.in","r",stdin);
freopen("lights.out","w",stdout);   
cin>>n>>m;
for(int i=1;i<=n;i++)   
A[i][n+1]=A[i][i]=1,N[i]=i;   
while(m–)
{
int s,t;cin>>s>>t;
A[s][t]=A[t][s]=1;
}
}
int Frees[maxn]={0},cnt=0;
bool Free[maxn]={0};
void solve()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
if(A[i][j]) break;
if(j==n+1) continue;
swap(N[i],N[j]);   
for(int k=1;k<=n;k++)
swap(A[k][i],A[k][j]);
for(int j=1;j<=n;j++) if(j!=i)
if(A[j][i])
for(int k=1;k<=n+1;k++)
A[j][k]=A[j][k] xor A[i][k];
}
for(int i=1;i<=n;i++)
if(A[i][i]==0)
Frees[cnt++]=N[i],Free[N[i]]=true;
}
int ans=~0U>>1;
int C[maxn]={0};
void dfs(int pos,int now)
{
if(now>ans)
return;
if(pos==cnt)
{
for(int i=1;i<=n;i++)
if(A[i][i])
{
C[N[i]]=0;
for(int j=1;j<=n;j++)if(Free[N[j]]&&A[i][j])
C[N[i]]^=C[N[j]];
C[N[i]]^=A[i][n+1];
}
int t=count(C+1,C+n+1,1);       
ans=min(ans,t);
return;
}
C[Frees[pos]]=0;dfs(pos+1,now);
C[Frees[pos]]=1;dfs(pos+1,now+1);
}
int main()
{
init();
solve();
dfs(0,0);
cout<<ans<<endl;
}
/…..2…../
越看越裸的网络流阿。。没什么话说。。。
Code。。
/*
PROG: cookie
LANG: C++
ID: Tom Chen
*/
#include<iostream>
#include<math.h>
using namespace std;
const int maxn=1000+10,maxm=100+10,maxV=1500,inf=~0U>>2;
inline int Cow(int s){return s;}
inline int Group(int s){return maxn+s;}
struct edge
{
int t,c;
edge*next,*op;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxV];
void addedge(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int H[maxV]={0};
double Can[maxn]={0};
int Num[maxm]={0},N,M,vs=0,vt=maxn+maxm,V;
void init();
void solve();
int MaxFlow();
void Impossible();
void Print();
void init()
{
freopen("cookie.in","r",stdin);
freopen("cookie.out","w",stdout);
cin>>N>>M;V=N+M+2;
for(int i=1;i<=M;i++)
{
cin>>Num[i];int s;
for(int j=0;j<Num[i];j++)
{
cin>>s;
addedge(Cow(s),Group(i),1);
Can[s]+=1/(double)Num[i];
}
}
for(int i=1;i<=N;i++)
addedge(vs,Cow(i),ceil(Can[i]));
for(int i=1;i<=M;i++)
addedge(Group(i),vt,1);
}
int aug(int no,int m)
{
if(no==vt)
return m;
int l=m;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[no]==H[i->t]+1)
{
int d=aug(i->t,min(i->c,l));
l-=d,i->c-=d,i->op->c+=d;
if(l==0||H[vs]>=V) return m-l;
}
int minh=maxV;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[i->t]<minh)
minh=H[i->t];
H[no]=minh+1;return m-l;   
}
int MaxFlow()
{
int flow=0;
while(H[vs]<V)
flow+=aug(vs,inf);
return flow;
}
void solve()
{
int t=MaxFlow();
if(t<M)
Impossible();
else
Print();
}
void Impossible()
{
cout<<-1<<endl;
}
void Print()
{
for(int i=1;i<=M;i++)
{
int t=Group(i);
for(edge*i=E[t];i;i=i->next)
if(i->t!=vt&&i->c)
{
cout<<i->t<<endl;
break;
}
}
}
int main()
{
init();
solve();
}
/….3…./
这是一道陈题阿。。06年WY的论文有提到过。。我恰好看过。。
可以去看WY的论文阿。。我就不说了。。。
Code。。。
/*
PROG: rescue
LANG: C++
ID: Tom Chen
*/
#include<iostream>
using namespace std;
int n,m;
struct point
{
int i,j,x,y,z;
void read()
{
cin>>i>>j;
x=i;
y=i-j/2;
z=(j+1)/2;
}
void show()
{
cout<<i<<" "<<j<<endl;
}
int operator-(const point&o) const
{return abs(x-o.x)+abs(y-o.y)+abs(z-o.z);}
};
int main()
{
freopen("rescue.in","r",stdin);
freopen("rescue.out","w",stdout);
cin>>n>>m;point now,ans;
now.read();int min=~0U>>1;
for(int i=0;i<m;i++)
{
point out;out.read();
if(now-out<min)
{
min=now-out;
ans=out;
}
}
ans.show();
cout<<min+1<<endl;
}
/…总结…/
1是很基本的解方程+枚举。。USACO的分析好像是枚举的。。毕竟N太小了。。但是不会高斯消元还是不会做的。。。
2太暴力的网络流了。。。
3数学问题。。WY的论文中提过。。否则比赛的时候我还不一定做的出来。。。

传送门http://acm.sgu.ru/problem.php?contest=0&problem=339。。
看上去好像要用到线段树。。想了半天不知道怎么搞。。于是暴力。。居然过了。。

不过很满哎。。要2.5秒多。。
才200+的人过阿。。估计都被吓住了。。。
#include<cstdio>
using namespace std;
const int maxn=1000+10;
struct seg
{
int L,R;
}S[maxn];
int main()
{
char t;int L,R,cnt=0;
while(scanf("%c %d %dn",&t,&L,&R)==3)
{
if(t==’+’)
{
S[cnt].L=L;S[cnt].R=R;int ans=0;
for(int i=0;i<cnt;i++)
if(S[i].L>=S[cnt].L&&S[i].R<=S[cnt].R)
ans++;
cnt++;
printf("%dn",ans);
}
if(t==’-‘)
{
for(int i=cnt-1;i>=0;i–)
if(S[i].L==L&&S[i].R==R)
{
cnt–;
for(int k=i;k<cnt;k++)
S[k]=S[k+1];               
break;
}
}
}
}

水题。。绝对的水题。。暴力模拟就OK了。。
PS实现的时候可以对墙使用哨兵。。
Code。。
#include<iostream>
#define REP(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=102;
char map[maxn][maxn]={0};
int main()
{
int n,m,nowx,nowy;
cin>>n>>m;
REP(i,1,n) REP(j,1,m)
{
cin>>map[i][j];   
if(map[i][j]==’P’)
nowx=i,nowy=j;
}
char old=’P’;   
bool fall=false;
while(true)
{               
if(nowx==n+1)
{
cout<<nowy;
break;
}
char t=map[nowx][nowy];
map[nowx][nowy]=0;
if(!t)
{
cout<<-1;
break;
}           
if(t==old&&!fall)
nowx++,fall=true;
else if(t==’/’)
nowy–,fall=false;
else if(t==’\’)
nowy++,fall=false;
else nowx++,fall=true;
old=t;
}   
}
遇见水题太激动居然交错了题号。。还连交了3边。。我的AC率阿。。      

好好好水的题目。。Catalan数或者暴力DP都可以阿。。
好短的代码。。。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int K,P;
long long H[40]={0};
cin>>K;
P=K+1;
H[0]=1;
for(int i=1;i<=K;i++)
for(int j=0;j<i;j++)
H[i]+=H[j]*H[i-j-1];
cout<<H[K]<<" "<<P<<endl;
}

比较简单的题目。。。不过有几个地方不细心也是要错的。。
主要思想当然是用stack。。维护两个stack
遇到<DOWN>或<UP>就push进这个符号的位置。。遇到另外两种就pop
然后输出的时候比较最近的UP或DOWN的位置（肯定在stack顶上）。。
万一两个stack都空的话要按原样输出。。开头结尾也要按原样输出。。。
P.S 大小写转换可以用ctype.h里面的tolower或toupper。。。
今天看到了wy的照片。。pretty阿。。。
Code。。
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;
const int maxn=1000;
template<typename T>
struct stack
{
T Q[maxn];
int top;
stack(){top=0;}   
bool Empty(){return top==0;}
const T& Top()
{
if(Empty()) return -1;
return Q[top-1];
}
void Pop(){top–;}
void Push(T a)
{Q[top++]=a;}
};
stack<int> U,D;
char t;
string NOW;
char a[50];
bool first=true;
int main()
{
freopen("z.in","r",stdin);
int now=0;
while(scanf("%c",&t)!=EOF)
{
now++;
if(t=='<‘)
{
if(first){cout<<NOW;first=false;goto next;}
if(D.Empty()&&U.Empty())
{cout<<NOW;goto next;}
if(D.Top()>U.Top())
{               
for(int i=0;i<NOW.length();i++)
printf("%c",tolower( NOW[i] ) );
}
else
{
for(int i=0;i<NOW.length();i++)
printf("%c",toupper( NOW[i] ));
}
next:
NOW="";
scanf("%[^>]s",a);now++;
if(a[0]==’/’)
{
if(a[1]==’D’)
D.Pop();
else
U.Pop();
}
else
{
if(a[0]==’D’)
D.Push(now);
else
U.Push(now);
}
scanf(">");
}
else
NOW+=t;
}
cout<<NOW<<endl;
}   

有点小难的数论问题哦。。
aX＝b（mod n）很好求吧。。
怎么才能把这个问题化成这种呢？
首先序列A可以mod P。。
因为a和b可以组成gcd（a，b）的任何倍数。。反之也是。。
因为可以用扩展欧几里得算出ax+by=gcd(a,b)嘛。。
故可以把a和b换成gcd（a，b）。。。
然后就一个个处理。。
若k是之前的所有数的gcd。。当前处理t。。
得出kx+ty=gcd(k,t)。。
那么之前所有数的系数全部*x（然后再modP）。。t的系数就是y
就可以使系数没有问题了。。
无解就是gcd（all包括n）无法整除b。。
然后直接输出系数就可以了。。
P.S为了方便可以把P也带入方程写成…..+PXn+1=b..
Code。。。
#include<stdio.h>
#include<iostream>
using namespace std;
const int maxn=200;
long long N,P,B;
long long A[maxn];
long long X[maxn];
long long gcd(long long a,long long b)
{
while(b){int t=a;a=b;b=t%b;}
return a;
}
void get(long long a,long long b,long long&x,long long&y)
{
if(b==0)
{
x=1;y=0;
return;
}
get(b,a%b,y,x);
y-=(a/b)*x;
}
int main()
{
cin>>N>>P>>B;
cin>>A[0];long long k=A[0];
for(int i=1;i<N;i++)
{
cin>>A[i];   
A[i]%=P;
k=gcd(k,A[i]);
}
A[N]=P;
k=gcd(k,A[N]);
if(B%k!=0)
{
cout<<"NO"<<endl;
return 0;
}   
k=gcd(A[0],A[1]);
get(A[0],A[1],X[0],X[1]);
for(int i=2;i<=N;i++)
{
long long x;
get(k,A[i],x,X[i]);
for(int j=0;j<i;j++)
{
X[j]*=x;
X[j]%=P;
while(X[j]<0)
X[j]+=P;
}
k=gcd(k,A[i]);
}
cout<<"YES"<<endl;
for(int i=0;i<N;i++)
{
X[i]*=(B/k);
X[i]%=P;
while(X[i]<0) X[i]+=P;
cout<<X[i]<<" ";
}
}

首先可以发现选中的序列无论S还是B（SB。。寒阿。。）都不能有任何逆序（也就是全递增阿。。）。。DP不就是要有一个序么。。
于是先按S排序。。那么选中的S一定就是递增的了。。然后发现就是标准LIS了。。
不过N太大。。要用nlogn的算法并且还要注意不能选S或B一样的。。
P.S
sort和binary就是好用阿。。。
不过比赛的时候不能用。。
别到时候脸qsort都不会了就四定了。。。
Code找不到了。。

很SB的完全背包问题阿。。。
P.S
由于我沙茶。。素数判定居然写错了。。还调了半天。。
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1000;
int Q,Ps[maxn],cnt=0,snt=0;
bool isprime(int p)
{
if(p==2) return true;
if(p%2==0) return false;
for(int i=3,j=9;j<=p;i+=2,j=i*i)
if(p%i==0) return false;
return true;
}
void init()
{
cin>>Q;
cnt=1;
for(int i=3;i<=Q;i++)
if( isprime(i) )
{
cnt++;
if(isprime(cnt))
{
Ps[snt++]=i;
}
}
}
bool G[maxn*10]={0};
int F[maxn*10]={0};
int P[maxn*10]={0};
int DP(int x)
{   
if(G[x]) return F[x];
G[x]=true;
for(int i=0;i<snt;i++) if(x>=Ps[i])
if(DP(x-Ps[i])<F[x])
{
F[x]=F[x-Ps[i]];
P[x]=Ps[i];
}
F[x]++;return F[x];
}
bool cmp(const int& x,const int& y)
{ return x>y;}
void print(int x)
{
int ans[maxn],cnt=0;
if(P[x]==0) {return;}
while(x)
{
ans[cnt++]=P[x];
x-=P[x];
}
sort(ans,ans+cnt,cmp);
cout<<ans[0];
for(int i=1;i<cnt;i++)
cout<<" "<<ans[i];
}
int main()
{
init();for(int i=0;i<=Q;i++) F[i]=~0U>>3;
F[0]=0;G[0]=true;
if( DP(Q)>10000 )
{
cout<<0<<endl;
}else
{
cout<<DP(Q)<<endl;
print(Q);
}
}

经典的有点水的树DP了。。
设S[x]为以节点x为跟的子树的大小。。
画个图便可知去掉x可割出的最大块是他的全体减去他自己的大小和他的最大子树的最大值。。。
P.S
一定要用前向星阿。。
我一直是邻接表的忠实拥护者。。不过这次我受挫了。。
我真不明白，前向星是要排序的。。我用stl是nlogn。。邻接表再怎么垃圾也是O（n）的阿！！。。
怎么一个52ms一个1600+ms。。天阿！！！！
Code。。。
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=16000;
int N,cnt=0;
int H[maxn+2]={0};
//graph
struct edge
{
int s,t;
}E[maxn*2];
bool cmp(const edge&x,const edge&y)
{ return x.s<y.s;}
void add(int s,int t)
{
E[cnt].s=s;E[cnt].t=t;cnt++;
E[cnt].s=t;E[cnt].t=s;cnt++;
}
void init()
{
scanf("%d",&N);
int s,t;
for(int i=1;i<N;i++)
{
scanf("%d %d",&s,&t);
add(s,t);
}
sort(E,E+cnt,cmp);
for(int i=0;i<cnt;i++)
H[E[i].s+1]++;
for(int i=2;i<=N+1;i++)
H[i]+=H[i-1];
}
//solve
int ans=maxn+1,acnt=0;
int Ans[maxn+1];
int S[maxn+1]={0};
bool Vis[maxn+1]={0};
int dfs(int x)
{
Vis[x]=true;int Max=0;
for(int i=H[x];i<H[x+1];i++)
{
int o=E[i].t;
if(!Vis[o])
{
S[x]+=dfs(o);
Max=max(Max,S[o]);
}
}   
S[x]++;
Max=max(Max,N-S[x]);
if(Max<ans)   
ans=Max,Ans[0]=x,acnt=1;
else if(Max==ans)
Ans[acnt++]=x;
return S[x];   
}
int main()
{
init();
dfs(1);
cout<<ans<<" "<<acnt<<endl;
sort(Ans,Ans+acnt);
cout<<Ans[0];
for(int i=1;i<acnt;i++)
cout<<" "<<Ans[i];
cout<<endl;
}