SPOJ 726

都说叫分段HASH。。
我觉得还是有点块状数组的感觉。。
用stl写平衡数很方便不过还是块状数组爽。。
可以是负数的阿。。好贱。。。
Code。。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000001,maxv=maxn*2,maxsize=1000,maxL=maxv/maxsize+10;
int C[maxv]={0};
int D[maxL]={0};
int n,Blocks;
void insert(int n)
{
C[n]++;
D[n/maxsize]++;
}
void del(int n)
{
C[n]–;
D[n/maxsize]–;
}
int getMin()
{
int i,j;
for(i=0;i<maxL;i++)
if(D[i]) break;
for(j=i*maxsize;;j++)
if(C[j]) break;
return j;
}
int getMax()
{
int i,j;
for(i=maxL-1;i>=0;i–)
if(D[i]) break;
for(j=(i+1)*maxsize-1;;j–)
if(C[j]) break;
return j;
}
int main()
{
cin>>n;int k,t;
long long ans=0;
while(n–)
{
scanf("%d",&k);
while(k–)
scanf("%d",&t),insert(t+maxn);
int Max=getMax(),Min=getMin();
ans+=Max-Min;
del(Max);del(Min);
}
cout<<ans<<endl;
}

sgu 347-357 部分(2)

356。。。
实际上求的就是N的排列中多少个排列只有K个不在位置上。。
那么答案就是C(N,K)*D(N-K)。。D是错排。。错排不知道者可以google之。。
但是高精十分BT。。实际上我怎么会没时间写模拟题呢?都是栽在这题上了。。555
不过总算是在比赛结束前过了。。
由于输出居然是要用不可约分数。。莫非要写一个高精度欧几里得算法吗?天阿。。
如果你真去写那你就傻了。。。
答案是D(n-k)/((n-k)!(k)!)
换句话说公约数的素因子《=100。。。
那么一个个化就OK了。。
不过程序还是很长。。好羡慕JAVA阿。。自带高精度运算功能的。。
#include<iostream>
#include<cstring>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=110;
int Prime[]=
{2,3,5,7,11,
13,17,19,23,29
,31,37,41,43,47
,53,59,61,67,71
,73,79,83,89,97};
const int ps=25;
int N,K;
struct Num
{
int P;
Num(){memset(P,0,sizeof(P));}
void mult(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]++;
}
}
void divide(int a)
{
for(int i=0;i<ps;i++)
{
if(a==1) break;
while(a%Prime[i]==0)
a/=Prime[i],P[i]–;
}
}
};
const int maxlen=200;
struct BigNum
{
int Q[maxlen],last;
BigNum(int x=0)
{memset(Q,0,sizeof(Q));Q[0]=x;last=0;}
int operator[](int v) const
{return Q[v];}
int& operator[](int v)
{return Q[v];}
BigNum operator+(const BigNum&x)
{
BigNum now;now.last=max(last,x.last);
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=Q[i]+x[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
return now;
}
void operator*=(int x)
{
int d=0;
for(int i=0;i<=last;i++)
{
d+=Q[i]*x;
Q[i]=d%10;
d/=10;
}
while(d>0)
{
Q[++last]=d%10;
d/=10;
}
}
BigNum operator*(const BigNum&x)
{
BigNum now;now.last=x.last+last;
memset(now.Q,0,sizeof(Q));
for(int i=0;i<=last;i++)
for(int j=0;j<=x.last;j++)
now[i+j]+=Q[i]*x[j];
int d=0;
for(int i=0;i<=now.last;i++)
{
d+=now[i];
now[i]=d%10;
d/=10;
}
while(d)
{
now[++now.last]=d%10;
d/=10;
}
}
int Mod(int x)
{
int d=0;
for(int i=last;i>=0;i–)
{
d*=10;
d+=Q[i];
d%=x;
}
return d;
}
void Divide(int x)
{
int rest=0;
for(int i=last;i>=0;i–)
{
rest=rest*10+Q[i];
Q[i]=rest/x;
rest%=x;
}
while(Q[last]==0)
last–;
}
void operator=(const BigNum&x)
{
last=x.last;
memmove(Q,x.Q,sizeof(Q));
}
void show()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
};
BigNum Get(Num x)
{
BigNum now(1);
for(int i=0;i<ps;i++)
{
for(int j=0;j<x.P[i];j++)
now*=Prime[i];
}
return now;
}
BigNum D[maxn];
void CalD(int n)
{
D[0][0]=1;D[1][0]=0;
for(int i=2;i<=n;i++)
{
D[i]=D[i-1]+D[i-2];
D[i]*=(i-1);
}
}
Num C;
int main()
{
cin>>K>>N;
if(N-K==1)
{
cout<<0<<endl;
return 0;
}
CalD(N-K);
for(int i=1;i<=K;i++)
C.mult(i);
for(int i=1;i<=N-K;i++)
C.mult(i);
BigNum left,right;
left=D[N-K];
for(int i=0;i<ps;i++)
{
while(left.Mod(Prime[i])==0&&C.P[i]>0)
left.Divide(Prime[i]),C.P[i]–;
}
right=Get(C);
left.show();cout<<"/";right.show();
}
357。。。好无聊的水题阿。。要是能跳明显一开始就跳。。
然后枚举每个开始UP or DOWN的点算答案。。。
Code。。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>2;
bool Digit[10]={0};
bool UP,DOWN,FLY;
int dist[100],s,t;
void init()
{
cin>>Digit[1]>>Digit[2]>>Digit[3]>>UP>>
Digit[4]>>Digit[5]>>Digit[6]>>DOWN>>
Digit[7]>>Digit[8]>>Digit[9]>>FLY>>Digit[0];
}
void renew(int&x,int c)
{
x=min(x,c);
}
void Fly()
{
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
if(Digit[i]&&Digit[j])
renew(dist[i*10+j],3);
}
void Go(int j)
{
int c=dist[j];
if(UP)
renew(dist[(j+1)%100],c+1);
if(DOWN)
renew(dist[(j+99)%100],c+1);
}
int main()
{
init();cin>>s>>t;
REP(i,100) dist[i]=inf;
dist[s]=0;
if(FLY)
Fly();
for(int i=0;i<10;i++)
if(Digit[i])
renew(dist[i],1);
int ans=dist[t];
for(int i=0;i<100;i++)
if(dist[i]!=inf)
{
if(UP)
renew(ans,(t-i+100)%100+dist[i]);
if(DOWN)
renew(ans,(i-t+100)%100+dist[i]);
}
if(ans==inf)
cout<<-1<<endl;
else
cout<<ans<<endl;
}

sgu 347-357 部分(1)


参加了虚拟比赛11道只做了5道。。SB阿。。
346和353都是模拟的题目。。懒得做了。。
347。。看代码吧。。
Code。。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=100+10;
string A[maxn];
bool cmp(const string&A,const string&B)
{
return (A+B)<(B+A);
}
int main()
{
int N;cin>>N;
for(int i=0;i<N;i++)
cin>>A[i];
sort(A,A+N,cmp);
for(int i=0;i<N;i++)
cout<<A[i];
cout<<endl;
}
350。。
有点意思的题目。。
首先如果有一个解。。那么把这些数全部xor上一个数的话。。还是一个解。。
因为(a xor x) xor (b xor x)=(a xor b) xor (x xor x)= a xor b xor 0= a xor b。。。
所以就当里面有一个0好了。。
然后特判掉M=1的情况。。
那么注意到。。如果B中有两个数A和B。。A xor B=另一个数C。。
那么A和B必然有公共的元素。。
那么就很简单了。。找两个有公共元素的B中的数i,j。。强行将它们的公共元素设为0。。
那么现在就有3个数了0,i,j。。
那么只要找其他的有0的元素就可以求出一个解了。。怎么求找呢?
如果B中数x不是i xor j。。又跟i和j都有公共元素。。那么这个公共元素只能是0了。。那么这个数就属于解了。。。
就这样找数。。。
#include<iostream>

#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int M,B[maxn];
bool HaveCommon(int i,int j,int&k)
{
int now=B[i]^B[j];
for(k=0;k<M;k++)
if(B[k]==now)
return true;
return false;
}
int main()
{
cin>>M;
REP(i,M) cin>>B[i];
if(M==1)
{
cout<<(B[0]-1)<<" "<<(B[0]^(B[0]-1))<<endl;
return 0;
}
int ans[maxn];ans[0]=0;int i,j,k;
bool mark[maxn]={0};
for(i=0;i<M;i++)
for(j=i+1;j<M;j++)
if(HaveCommon(i,j,k))
{
ans[1]=B[i],ans[2]=B[j],mark[i]=mark[j]=mark[k]=true;
goto out;
}
out:
int cnt=3,t;
for(int o=0;o<M;o++) if(!mark[o])
if(HaveCommon(o,i,t)&&HaveCommon(o,j,t))
ans[cnt++]=B[o];
cout<<ans[0];
for(int i=1;i<cnt;i++)
cout<<" "<<ans[i];
cout<<endl;
}355。。。
构造题。。很明显答案是logN+1…
染色的话只要染成素因数个数就OK了。。
#include<iostream>
using namespace std;
int num(int p)
{
int cnt=0;
while(p%2==0)
{cnt++;p/=2;}
while(p%3==0)
{cnt++;p/=3;}
for(int i=5,j=25,k=4;j<=p;i+=(k=6-k),j+=(i*2-k)*k)
{
while(p%i==0)
{cnt++;p/=i;}
}
if(p!=1)
cnt+=2;
else
cnt+=1;
return cnt;
}
int main()
{
int N,x,cnt=0;cin>>N;x=1;
while(x<=N){cnt++;x*=2;}
cout<<cnt<<endl;
for(int i=1;i<N;i++)
cout<<num(i)<<" ";
cout<<num(N)<<endl;
}

SPOJ 2185

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();
}

SPOJ 2747

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);
}
}

sgu 395

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

sgu 327

想了半天。。发现居然是一个最短哈密顿路的模型(注意不是环。。)
首先把被包含的扔掉。。那么建立N个顶点代表字符串。。
两点的距离就是这两个字符串接起来增加的字符数*2。。
图是完全的。。边是有向的。。
那么用集合DP就可以搞定了。。先要枚举开始的顶点。。
复杂度就是(N^3*2^N)。。也能过。。
。。正在写。。
写了半天。。弄了个半成品。。路径实在不想写了。。只能算个答案
注意一下。。连接的话有4种方式(T表示正的放。。R表示反着放)
T<- T R -> R
R<- R T -> T
T<- R T -> R
R<- T R -> T
。。。BT。。。
这么搞的话再构造方案岂不是要死人阿。。
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();
}

SPOJ 297

。。。传送门。。。
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;
}

sgu 200

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

USACO NOV 2009

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

Page 3 of 512345