2012杭州网络赛赛后【缺ACDI】
A Boomerang (HDU 4410)
B Arrest (HDU 4411)最小费用流，建-inf边保证n个点都被访问到
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=222,M=111111; const int inf=0x3f3f3f3f; MinCostMaxFlow mc; int d[N][N]; int main() { //freopen("in.txt","r",stdin); int n,m,k; while(scanf("%d%d%d",&n,&m,&k),n||m||k) { int s=0,ss=n*2+1,t=n*2+2; memset(d,63,sizeof(d)); for(int i=0;i<m;i++) { int x,y,len; scanf("%d%d%d",&x,&y,&len); d[x][y]=d[y][x]=min(d[x][y],len); } for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); mc.init(); mc.addedge(s,ss,k,0); for(int i=1;i<=n;i++) mc.addedge(ss,i,1,d[i][0]); for(int i=1;i<=n;i++) mc.addedge(i,i+n,1,-0xfffff); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) mc.addedge(i+n,j,1,d[i][j]); for(int i=1;i<=n;i++) mc.addedge(i+n,t,1,d[i][0]); mc.addedge(ss,t,k,0); int f,c; mc.mincost(s,t,n*2+3,f,c); printf("%d\n",c+0xfffff*n); } return 0; }C Sky Soldiers (HDU 4412)
D Logical Expression (HDU 4413)
n^3四个方向搜最长
#include<cstdio> char s[100][100]; int main() { //freopen("in","r",stdin); int n; while(scanf("%d",&n),n) { for(int i=0;i<n;i++) scanf("%s",s[i]); int ans=0; for(int x=1;x<n-1;x++) for(int y=1;y<n-1;y++) { if(s[x][y]!='#') continue; int up=0,down=0,left=0,right=0,fg=1; for(int i=x-1;i>=0;i--) { if(s[i][y]!='#') break; up++; if(s[i][y+1]=='#'||s[i][y-1]=='#') fg=0; } for(int i=x+1;i<n;i++) { if(s[i][y]!='#') break; down++; if(s[i][y+1]=='#'||s[i][y-1]=='#') fg=0; } for(int i=y-1;i>=0;i--) { if(s[x][i]!='#') break; left++; if(s[x-1][i]=='#'||s[x+1][i]=='#') fg=0; } for(int i=y+1;i<n;i++) { if(s[x][i]!='#') break; right++; if(s[x-1][i]=='#'||s[x+1][i]=='#') fg=0; } if(fg&&up==down&&down==left&&left==right&&up) ans++; } printf("%d\n",ans); } return 0; }贪心 若可能则先杀了bi非0且ai最小的那个，然后算出所有bi.second之和为cnt，杀cnt个ai最大的。再用自己的刀杀ai尽量小的剩余人
#include <cstdio> #include <algorithm> using namespace std; const int N=100010; pair<int,int>a[N]; int main() { int n,m,t,cas=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second); sort(a,a+n); int cst=0,cnt=0,id; for(int i=0;i<n;i++) if(a[i].second){ id=i;break;} if(m<a[id].first) id=-1; else{ cst=a[id].first,cnt=1; for(int i=0;i<n;i++) cnt+=a[i].second; } if(cnt>n) cnt=n; for(int i=0;i<n&&cnt<n&&a[i].first+cst<=m;i++) if(i!=id) cst+=a[i].first,cnt++; printf("Case %d: %d %d\n",cas++,cnt,cst); } return 0; }G Good Article Good sentence (HDU 4416)
后缀数组，ans=总数-重复。s的每一个后缀与非s中串的lcp为对应重复子串个数。s串自身重复则只保留第一个串的cnt不变，其他视为重复删去。
可以利用性质lcp(i,j)=min(height[k]){i<k<=j}，正反分别扫一遍求出cnt[k]=min(min(height[w]){i<w<=k},height[w]{k<w<=j})。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010*3; const int inf=0x3f3f3f3f; int ua[N],ub[N],us[N]; int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];} void da(int *r,int *sa,int n,int m) { int i,j,p,*x=ua,*y=ub,*t; for(i=0;i<m;i++) us[i]=0; for(i=0;i<n;i++) us[x[i]=r[i]]++; for(i=1;i<m;i++) us[i]+=us[i-1]; for(i=n-1;i>=0;i--) sa[--us[x[i]]]=i; for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<m;i++) us[i]=0; for(i=0;i<n;i++) us[x[i]]++; for(i=1;i<m;i++) us[i]+=us[i-1]; for(i=n-1;i>=0;i--) sa[--us[x[y[i]]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } } int rank[N],hei[N]; void calhei(int *r,int *sa,int n) { int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;hei[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); } char s[N]; int r[N],sa[N],cnt[N]; int main() { int t,n,cas=1; scanf("%d",&t); while(t--) { scanf("%d%s",&n,s); int len=strlen(s),m=0,k=28; for(int i=0;i<len;i++) r[m++]=s[i]-96; for(int i=0;i<n;i++) { r[m++]=k++; scanf("%s",s); for(int j=0;s[j];j++) r[m++]=s[j]-96; } r[m]=0; da(r,sa,m+1,k); calhei(r,sa,m); memset(cnt,0,sizeof(cnt)); int lcp=inf; for(int i=1;i<=m;i++) { if(sa[i]<len) { lcp=min(lcp,hei[i]); cnt[sa[i]]=max(lcp,cnt[sa[i]]); } else lcp=inf; } lcp=inf; for(int i=m;i;i--) { if(sa[i-1]<len) { lcp=min(lcp,hei[i]); cnt[sa[i-1]]=max(lcp,cnt[sa[i-1]]); } else lcp=inf; } for(int i=1;i<=m;i++) if(sa[i]<len&&sa[i-1]<len) cnt[sa[i-1]]=max(cnt[sa[i-1]],hei[i]); long long ans=(long long)len*(len+1)/2; for(int i=0;i<len;i++) ans-=cnt[i]; printf("Case %d: %I64d\n",cas++,ans); } return 0; }H Super Mario (HDU 4417)
离散化+树状数组 在树状数组中对应插入删除的数离散化后的位置加1或减1，求sum(hz[k])即为比它小的数的个数。区间询问则计算ans[r]-ans[l-1]即可。
此题亦可用划分树+二分答案。
#include<map> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; const int inf=0x3f3f3f3f; int bin[N],num[N],arr[N]; struct Query { int l,r,h,i,ans; void init(int i){scanf("%d%d%d",&l,&r,&h);ans=0;this->i=i;l--;} }q[N]; bool cmp1(Query a,Query b){return a.l<b.l;} bool cmp2(Query a,Query b){return a.r<b.r;} bool cmp3(Query a,Query b){return a.i<b.i;} void init(){memset(arr,0,sizeof(arr));} void add(int k,int v){while(k<N) arr[k]+=v,k+=k&-k;} int sum(int k){int ans=0;while(k) ans+=arr[k],k-=k&-k;return ans;} int main() { //freopen("in.txt","r",stdin); int t,n,m,cas=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",num+i),bin[i]=num[i]; for(int i=0;i<m;i++) q[i].init(i); printf("Case %d:\n",cas++); bin[n]=inf; sort(bin,bin+n+1); map<int,int>hz; int len=unique(bin,bin+n+1)-bin; for(int i=0;i<len;i++) hz[bin[i]]=i+1; sort(q,q+m,cmp1);init(); for(int i=0,j=0;i<=n;i++) { while(j<m&&q[j].l<i) q[j].ans-=sum(upper_bound(bin,bin+len,q[j].h)-bin),j++; if(i==n) break; add(hz[num[i]],1); } sort(q,q+m,cmp2);init(); for(int i=0,j=0;i<=n;i++) { while(j<m&&q[j].r<i) q[j].ans+=sum(upper_bound(bin,bin+len,q[j].h)-bin),j++; if(i==n) break; add(hz[num[i]],1); } sort(q,q+m,cmp3); for(int i=0;i<m;i++) printf("%d\n",q[i].ans); } return 0; }I Time travel (HDU 4418)
矩形面积并（模板）+容斥关系
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010*2; typedef long long ll; typedef ll type; type bin[N]; struct line { type x,y0,y1; int d; line(){} line(type x,type y0,type y1,int d):x(x),y0(y0),y1(y1),d(d){} bool operator < (const line &u) const { if(x!=u.x) return x<u.x; return d>u.d; } }lin[N]; struct node { int l,r,c; type m; int mid(){return (l+r)>>1;} void update(int); }tree[N*4]; void node::update(int rt) { if(c) m=bin[r]-bin[l]; else if(l+1==r) m=0; else m=tree[rt<<1].m+tree[rt<<1|1].m; } void build(int rt,int l,int r) { tree[rt].l=l;tree[rt].r=r; tree[rt].c=0;tree[rt].m=0; if(l+1==r) return; int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid,r); } void insert(int rt,int l,int r,int d) { if(l<=tree[rt].l&&tree[rt].r<=r) { tree[rt].c+=d; tree[rt].update(rt); return; } int mid=tree[rt].mid(); if(l<mid) insert(rt<<1,l,r,d); if(mid<r) insert(rt<<1|1,l,r,d); tree[rt].update(rt); } struct Rect { int n,x0[N],x1[N],y0[N],y1[N]; ll ans; void init(){n=ans=0;} void insert(int a,int b,int c,int d){x0[n]=a,y0[n]=b,x1[n]=c,y1[n++]=d;} }rect[8]; ll solve(Rect &r) { if(r.n==0) return 0; if(r.n==1) return ll(r.x1[0]-r.x0[0])*(r.y1[0]-r.y0[0]); int tot=0,n=r.n; for(int i=0;i<n;i++) { bin[tot]=r.y0[i];lin[tot++]=line(r.x0[i],r.y0[i],r.y1[i], 1); bin[tot]=r.y1[i];lin[tot++]=line(r.x1[i],r.y0[i],r.y1[i],-1); } sort(lin,lin+tot); sort(bin,bin+tot); tot=unique(bin,bin+tot)-bin; build(1,0,tot-1); ll ans=0; for(int i=0;i<n*2;i++) { int lft=lower_bound(bin,bin+tot,lin[i].y0)-bin; int rht=lower_bound(bin,bin+tot,lin[i].y1)-bin; if(lft!=rht) insert(1,lft,rht,lin[i].d); ans+=tree[1].m*(lin[i+1].x-lin[i].x); } return ans; } int main() { int n,t,cas=1; scanf("%d",&t); while(t--) { scanf("%d",&n); char op[2]; for(int i=0;i<8;i++) rect[i].init(); for(int i=0; i<n; i++) { int a,b,c,d; scanf("%s%d%d%d%d",op,&a,&b,&c,&d); if(op[0]=='R') for(int i=0;i<8;i++) if(i&4) rect[i].insert(a,b,c,d); if(op[0]=='G') for(int i=0;i<8;i++) if(i&2) rect[i].insert(a,b,c,d); if(op[0]=='B') for(int i=0;i<8;i++) if(i&1) rect[i].insert(a,b,c,d); } ll ans[8]; for(int i=0;i<8;i++) ans[i]=solve(rect[i]); ll rgb=ans[1]+ans[2]+ans[4]-ans[3]-ans[5]-ans[6]+ans[7]; printf("Case %d:\n",cas++); printf("%I64d\n",ans[7]-ans[3]); printf("%I64d\n",ans[7]-ans[5]); printf("%I64d\n",ans[7]-ans[6]); printf("%I64d\n",ans[4]+ans[2]-ans[6]-rgb); printf("%I64d\n",ans[4]+ans[1]-ans[5]-rgb); printf("%I64d\n",ans[2]+ans[1]-ans[3]-rgb); printf("%I64d\n",rgb); } return 0; }