。。。题目真是比较水阿。。。连我都得了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的论文中提过。。否则比赛的时候我还不一定做的出来。。。