题解#3
感觉自己弱得没救了。。。求神犇解救T_T
7
2597: [Wc2007]剪刀石头布
补集转化之后就是费用流了。我比较逗方案WA了两发。
1 int n,m,k,mincost,tot=1,cnt,s,t,win[maxn],a[maxn][maxn],b[maxn][maxn],head[maxm],d[maxm],from[2*maxm]; 2 3 bool v[maxm]; 4 5 queue<int>q; 6 7 struct edge{int from,go,next,v,c;}e[2*maxm]; 8 9 void add(int x,int y,int v,int c) 10 11 { 12 13 e[++tot]=(edge){x,y,head[x],v,c};head[x]=tot; 14 15 e[++tot]=(edge){y,x,head[y],0,-c};head[y]=tot; 16 17 } 18 19 bool spfa() 20 21 { 22 23 for (int i=0;i<=cnt;i++){v[i]=0;d[i]=inf;} 24 25 q.push(s);d[s]=0;v[s]=1; 26 27 while(!q.empty()) 28 29 { 30 31 int x=q.front();q.pop();v[x]=0; 32 33 for (int i=head[x],y;i;i=e[i].next) 34 35 if(e[i].v&&d[x]+e[i].c<d[y=e[i].go]) 36 37 { 38 39 d[y]=d[x]+e[i].c;from[y]=i; 40 41 if(!v[y]){v[y]=1;q.push(y);} 42 43 } 44 45 } 46 47 return d[t]!=inf; 48 49 } 50 51 void mcf() 52 53 { 54 55 while(spfa()) 56 57 { 58 59 int tmp=inf; 60 61 for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v); 62 63 mincost+=d[t]*tmp; 64 65 for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;} 66 67 } 68 69 } 70 71 int main() 72 73 { 74 n=read();s=0;t=n+1;cnt=t; 75 for5(n,n)a[i][j]=read(),win[i]+=(a[i][j]==1); 76 for1(i,n)for1(j,i-1)if(a[i][j]==2) 77 { 78 add(s,++cnt,1,0); 79 b[i][j]=tot+1; 80 add(cnt,i,1,0); 81 add(cnt,j,1,0); 82 } 83 for1(i,n) 84 { 85 mincost+=win[i]*(win[i]-1)/2; 86 for2(j,win[i],n-2)add(i,t,1,j); 87 } 88 mcf(); 89 cout<<(n*(n-1)*(n-2)/6-mincost)<<endl; 90 for1(i,n)for1(j,i-1)if(a[i][j]==2)a[i][j]=!e[b[i][j]].v,a[j][i]=!a[i][j]; 91 for1(i,n)for1(j,n)printf("%d%c",a[i][j],j==n?' ':' '); 92 93 return 0; 94 95 }
3813: 奇数国
果真良心送分题,随便写个线段树就可以过了。
1 const int p[60]={2,3,5,7,11,13,17,19,23,29, 2 31,37,41,43,47,53,59,61,67, 3 71,73,79,83,89,97,101,103, 4 107,109,113,127,131,137,139, 5 149,151,157,163,167,173,179, 6 181,191,193,197,199,211,223, 7 227,229,233,239,241,251,257, 8 263,269,271,277,281}; 9 struct seg{int s[60];}t[4*maxn]; 10 int n=100000,ret,ans[60]; 11 inline void build(int k,int l,int r) 12 { 13 int mid=(l+r)>>1;t[k].s[1]=r-l+1; 14 if(l==r)return; 15 build(lch);build(rch); 16 } 17 inline void query(int k,int l,int r,int x,int y) 18 { 19 if(l==x&&r==y){for0(i,59)ans[i]+=t[k].s[i];return;} 20 int mid=(l+r)>>1; 21 if(y<=mid)query(lch,x,y); 22 else if(x>mid)query(rch,x,y); 23 else query(lch,x,mid),query(rch,mid+1,y); 24 } 25 inline void pushup(int k) 26 { 27 for0(i,59)t[k].s[i]=t[k<<1].s[i]+t[k<<1|1].s[i]; 28 } 29 inline void change(int k,int l,int r,int x) 30 { 31 if(l==r){for0(i,59)t[k].s[i]=ans[i];return;} 32 int mid=(l+r)>>1; 33 if(x<=mid)change(lch,x);else change(rch,x); 34 pushup(k); 35 } 36 inline int power(int x,int y) 37 { 38 int t=1; 39 for(;y;y>>=1,x=(ll)x*x%mod) 40 if(y&1)t=(ll)t*x%mod; 41 return t; 42 } 43 44 int main() 45 46 { 47 48 freopen("input.txt","r",stdin); 49 50 freopen("output.txt","w",stdout); 51 52 build(1,1,n); 53 int T=read(); 54 while(T--) 55 { 56 int ch=read(),x=read(),y=read(),ret=1; 57 memset(ans,0,sizeof(ans)); 58 if(ch==0) 59 { 60 query(1,1,n,x,y); 61 for0(i,59)if(ans[i])ret=(ll)ret*(p[i]-1)%mod*power(p[i],ans[i]-1)%mod; 62 printf("%d ",ret); 63 }else 64 { 65 for0(i,59) 66 { 67 while(y%p[i]==0)ans[i]++,y/=p[i]; 68 } 69 change(1,1,n,x); 70 } 71 } 72 73 return 0; 74 75 }