http://www.spoj.pl/problems/MUSIC/
USACO不知那年那月的月赛题。。。
看上去很BT。。但如果看一下部分和的话。。
会发现搞那么多也就是交换Sx-1于Sy。。
要让条件满足。。必须要把部分和顺序排序。。并且S1>0以及没有相同的部分和。。
那么最小交换数就是n-轮换数。。很好求。。
Code。。。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
const int maxn=100000;
using namespace std;
int S[maxn],P[maxn],n;
bool cmp(const int&x,const int&y)
{
return S[x]<S[y];
}
void Judge()
{
if(S[P[0]]<=0)
cout<<-1<<endl,exit(0);
for(int i=1;i<n;i++)
if(S[P[i]]==S[P[i-1]])
cout<<-1<<endl,exit(0);
}
void init()
{
scanf("%d",&n);
scanf("%d",S);P[0]=0;
for(int i=1;i<n;i++)
{
scanf("%d",S+i);
S[i]+=S[i-1];
P[i]=i;
}
sort(P,P+n,cmp);
Judge();
}
void solve()
{
bool mark[maxn]={0};int ans=n;
for(int i=0;i<n;i++) if(!mark[i])
{
int t=i;
while(!mark[t])
mark[t]=true,t=P[t];
ans–;
}
cout<<ans<<endl;
}
int main()
{
init();
solve();
}

http://www.spoj.pl/problems/SUMSUMS/
最近在做USACO以前的月赛题备战NOIP哎。。。
这道是2007 CHN的。。
琢磨一下可以发现对于每个人来说。。S是所有Ci的总和
任何次数下他的值都是A*S+B*Ci。。且这个A和B只要给定了次数，跟i是无关的。。
可以导出A和B的递推式：
A’=(n-1)*A+B;
B’=-B;
。。但是T太大了。。只好用矩阵乘法加速了。。。
矩阵为
n-1 1
0    -1
Code。。。
#include<iostream>
#include<cstring>
#include<cstdio>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long Board[2][2];
const int maxn=50000;
const long long Mod=98765431;
int N;
long long T;
int C[maxn];
struct Matrix
{
Board own;       
Matrix(){memset(own,0,sizeof(own));}
Matrix operator*(const Matrix&x)
{
Matrix now;
REP(i,2) REP(j,2)
{
REP(k,2)now.own[i][j]+=(own[i][k]*x.own[k][j])%Mod;
now.own[i][j]%=Mod;if(now.own[i][j]<0) now.own[i][j]+=Mod;
}
return now;
}
long long* cal(int A[])
{
long long* ans=new long long[2];
ans[0]=ans[1]=0;
REP(i,2) REP(j,2)
ans[i]+=own[i][j]*A[j];
return ans;
}
void operator=(const Matrix&x)
{
memmove(own,x.own,sizeof(own));
}
}ans,orig;
Matrix power(long long t)
{
if(t==1)   
{
return orig;
}
Matrix now;   
now=power(t/2);
now=now*now;
if(t%2==1)
now=now*orig;
return now;
}
int main()
{
cin>>N>>T;int S=0;
REP(i,N) {scanf("%d",C+i);S+=C[i];S%=Mod;}
orig.own[0][0]=N-1;orig.own[0][1]=1;
orig.own[1][0]=0;orig.own[1][1]=-1;
ans=power(T);
int A[2]={0,1};
long long*get=ans.cal(A);
REP(i,N)
{
long long t=get[0]*S+get[1]*C[i];
t%=Mod;
printf("%lldn",t);
}
}

这道题我居然想出来了。。只有11个人AC哎。。好激动。。
一下就看出可以用有上下界的最小费用可行流。。
就是对增加的处理有些BT。。
每个人分开讨论
如果把来了看成+号，走了看成-号。。那么对于相邻的两个。。
1++。。中间肯定要加个-。。
2+-。。可以不加。。也可以在中间加-+。。
3–。。中间肯定要加个+。。
当然可以狂加+-+-+-之类的。。但是可以看成一个新人来简化问题。。
于是分别处理以上三种情况。。具体太繁琐。。简单说一下。。
1和3好处理。。加个顶点就OK了。。
2很BT。。要加2个顶点。。我想了半天突然明悟了。。。
新人的话只需要用容量无限费用为1的边就可以了。。
不过我不会写有上下界的最小费用可行流。。无语。。。
去学学再去AC这题吧。。。
N不大时间应该够。。
P.S似乎运用了网络流中配“零件”的思想。。配“零件”。。真好玩。。。

想了半天。。发现居然是一个最短哈密顿路的模型（注意不是环。。）
首先把被包含的扔掉。。那么建立N个顶点代表字符串。。
两点的距离就是这两个字符串接起来增加的字符数*2。。
图是完全的。。边是有向的。。
那么用集合DP就可以搞定了。。先要枚举开始的顶点。。
复杂度就是（N^3*2^N）。。也能过。。
。。正在写。。
写了半天。。弄了个半成品。。路径实在不想写了。。只能算个答案
注意一下。。连接的话有４种方式(Ｔ表示正的放。。Ｒ表示反着放)
T<- T R -> R
R<- R T -> T
T<- R T -> R
R<- T R -> T
。。。ＢＴ。。。
这么搞的话再构造方案岂不是要死人阿。。
Code。。
#include<string>
#include<iostream>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=14,inf=~0U>>1;
int N=0,ans=~0U>>1;
string B[maxn];
int dist[maxn][maxn];
string Reverse(string tmp)
{
for(int s=0,t=tmp.length()-1;s<t;s++,t–) swap(tmp[s],tmp[t]);
return tmp;
}
int maxcommon(const string&x,const string&y)
{
int ans=0;
for(int i=1;i<=min(x.length(),y.length());i++)
if(x.substr(x.length()-i,i)==y.substr(0,i))
ans=i;
return ans;
}
void init()
{
int cnt;cin>>cnt;
string A[maxn];
for(int i=0;i<cnt;i++)
cin>>A[i];
for(int i=0;i<cnt;i++)
{
bool find=false;
for(int j=0;j<cnt;j++) if(j!=i)
if(A[j].find(A[i])!=string::npos)
{find=true;break;}
if(!find)
B[N++]=A[i];
}
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) if(i!=j)
{
int a=B[j].length()*2-maxcommon(B[j],B[i])*2;
int b=B[j].length()*2-maxcommon(Reverse(B[j]),B[i])*2;
int c=B[j].length()*2-maxcommon(B[j],Reverse(B[i]))*2;
int d=B[j].length()*2-maxcommon(Reverse(B[j]),Reverse(B[i])))*2;
dist[i][j]=min(min(min(a,b),c),d);
}
}
int DP[1<<maxn][maxn];
struct node
{
int state,pos;
node(int s,int p):state(s),pos(p){}
};
void start(int i)
{
string tmp=Reverse(B[i]);
REP(j,1<<N) REP(k,N) DP[j][k]=inf;
DP[1<<i][i]=B[i].length()*2-maxcommon(B[i],tmp);
queue<node> Q;
Q.push(node(1<<i,i));
while(Q.size())
{
node cur=Q.front();Q.pop();
int s=cur.state,p=cur.pos;
for(int j=0;j<N;j++) if(s^(1<<j))
{
int ns=s^(1<<j),get=DP[s][p]+dist[p][j];
if(DP[ns][j]>get)
DP[ns][j]=get,Q.push(node(ns,j));
}
}
REP(j,N) if(DP[(1<<N)-1][j]<ans)
ans=DP[(1<<N)-1][j];
}
void solve()
{
for(int i=0;i<N;i++)
start(i);
cout<<ans<<endl;
}
int main()
{
init();
solve();
}

。。。传送门。。。
http://www.spoj.pl/problems/AGGRCOW/。。。
二分+贪心麻。。很明显如果知道答案越往钱放越好嘛。。。
代码太短了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;int N,C,X[maxn];
bool Can(int limit)
{
int old=0,now=1;
for(int i=1;i<C;i++)
{
while(X[now]-X[old]<limit&&now<N)
now++;
if(now>=N)
return false;
old=now;now++;
}
return true;
}
void solve();
int main()
{
int t;cin>>t;
while(t–)
{       
solve();
}
}
void solve()
{
cin>>N>>C;
for(int i=0;i<N;i++)
scanf("%d",X+i);
sort(X,X+N);
int l=1,r=X[N-1];
while(l+1<r)
{
int mid=(l+r)/2;
if(Can(mid))
l=mid;
else
r=mid;
}
cout<<l<<endl;
}

。。这道题目模线性方程组的模型很好想。。关键是高斯消元。。我搞的累死就是因为很多地方写错了。。。
幸好还是过了。。
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;
}