A. Automat

$m$超過$1600$是沒用的。

從后往前考慮，設(shè)$f[i][j][k]$表示考慮$[i,n]$這些物品，一共花費$j$元錢，買了$k$個物品的最大收益。

時間復(fù)雜度$O(n^5)$。

#include<cstdio> const int N=45,M=1605; int n,m,lim,A,B,i,j,k,x,y,z,o,a[N],b[N],f[2][M][N],ans; inline void up(int&a,int b){a<b?(a=b):0;} inline int min(int a,int b){return a<b?a:b;} int main(){scanf("%d%d",&n,&m);m=min(m,M-5);lim=40;for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++)scanf("%d",&b[i]);for(o=0;o<2;o++)for(i=0;i<=m;i++)for(j=0;j<=lim;j++)f[o][i][j]=-1;o=0;f[0][0][0]=0;for(i=n;i;i--,o^=1){A=a[i],B=b[i];for(j=0;j<=m;j++)for(k=0;k<=lim;k++)f[o^1][j][k]=-1;for(j=0;j<=m;j++)for(x=0;x<=B&&j+x*A<=m;x++)for(k=0;k<=lim;k++)if(~f[o][j][k])up(f[o^1][j+x*A][min(k+x,lim)],f[o][j][k]+min(k+x,B)*A);}for(i=0;i<=m;i++)for(j=0;j<=lim;j++)up(ans,f[o][i][j]);printf("%d",ans); }

　　

B. Touristic Bureau

將所有景點按照有趣度從小到大排序，設(shè)$f[i]$表示走到$i$的最大獲利，則$f[i]=\max(f[j]+manhattan(i,j))+c[i](j<i)$。

枚舉曼哈頓距離里$x$和$y$的符號，分別維護最大值即可。

時間復(fù)雜度$O(nm)$。

#include<cstdio> #include<algorithm> #include<vector> using namespace std; typedef pair<int,int>P; typedef long long ll; const int N=1010,M=N*N; const ll inf=1LL<<60; int n,m,i,j,x,c[N][N];vector<P>v[M]; ll g[4],f[N][N],ans; inline void up(ll&a,ll b){a<b?(a=b):0;} inline void cal(int x,int y){ll t=0;up(t,x+y+g[0]);//-x-yup(t,x-y+g[1]);//-x+yup(t,-x+y+g[2]);//x-yup(t,-x-y+g[3]);//x+yup(ans,f[x][y]=t+c[x][y]); } inline void ins(int x,int y){ll t=f[x][y];up(g[0],t-x-y);up(g[1],t-x+y);up(g[2],t+x-y);up(g[3],t+x+y); } int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)for(j=1;j<=m;j++){scanf("%d",&x);if(x)v[x].push_back(P(i,j));}for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&c[i][j]);g[0]=g[1]=g[2]=g[3]=-inf;for(i=1;i<M;i++){for(j=0;j<v[i].size();j++)cal(v[i][j].first,v[i][j].second);for(j=0;j<v[i].size();j++)ins(v[i][j].first,v[i][j].second);}printf("%lld",ans); }

　　

C. Sequence

下標模$k$相同的位置最后要一樣，故直接將序列長度壓縮成$k$然后DP即可。

#include<cstdio> const int N=1000010; int n,k,i,j,x,cnt[N][2],f[N][2]; inline void up(int&a,int b){a>b?(a=b):0;} int main(){scanf("%d%d",&n,&k);for(i=1;i<=n;i++){scanf("%d",&x);cnt[i%k][x&1]++;}for(i=0;i<=k;i++)f[i][0]=f[i][1]=N;f[0][0]=0;for(i=0;i<k;i++)for(j=0;j<2;j++){up(f[i+1][j],f[i][j]+cnt[i][1]);up(f[i+1][j^1],f[i][j]+cnt[i][0]);}printf("%d",f[k][0]); }

　　

D. DNA

字符集$=1$最優(yōu)。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100010; int n,i,b[N];char a[N],ans; int main(){scanf("%d%s",&n,a+1);for(i=1;i<=n;i++)b[a[i]]++;ans='A';if(b['C']<b[ans])ans='C';if(b['T']<b[ans])ans='T';if(b['G']<b[ans])ans='G';printf("%d\n",b[ans]);for(i=1;i<=n;i++)putchar(ans); }

　　

E. Evaluation

對表達式遞歸建樹，設(shè)$f[i][j]$表示$i$子樹內(nèi)運算結(jié)果為$j$的方案數(shù)。

對于求冪直接計算。

對于加法可以FFT。

對于乘法可以求出原根后取指標然后轉(zhuǎn)化為加法FFT。

時間復(fù)雜度$O(nP\log P)$。

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; typedef vector<int>V; const int N=70000,MO=30011; int P,n,i,j,len,po[MO][10],pos[N],A[N],B[N],C[N]; int ind[N],gen[N],G; char a[310]; namespace FFT{ typedef long double ld; const ld pi=acos(-1.0); struct comp{ld r,i;comp(ld _r=0,ld _i=0){r=_r,i=_i;}comp operator+(const comp&x){return comp(r+x.r,i+x.i);}comp operator-(const comp&x){return comp(r-x.r,i-x.i);}comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}comp conj(){return comp(r,-i);} }A[N],B[N]; inline void FFT(comp a[],int n,int t){for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]);for(int d=0;(1<<d)<n;d++){int m=1<<d,m2=m<<1;ld o=pi*2/m2*t;comp _w(cos(o),sin(o));for(int i=0;i<n;i+=m2){comp w(1,0);for(int j=0;j<m;j++){comp&A=a[i+j+m],&B=a[i+j],t=w*A;A=B-t;B=B+t;w=w*_w;}}}if(t==-1)for(int i=0;i<n;i++)a[i].r/=n; } inline void mul(int*a,int*b,int*c){int i,j;for(i=0;i<len;i++)A[i]=comp(a[i],b[i]);FFT(A,len,1);for(i=0;i<len;i++){j=(len-i)&(len-1);B[i]=(A[i]*A[i]-(A[j]*A[j]).conj())*comp(0,-0.25);}FFT(B,len,-1);for(i=0;i<len;i++)c[i]=((long long)(B[i].r+0.5))%MO; } } V dfs(int l,int r){if(l==r){V v;v.resize(P);for(int i=0;i<P;i++)v[i]=0;if(a[l]>='0'&&a[l]<='9')v[(a[l]-'0')%P]=1;if(a[l]>='a'&&a[l]<='z')for(int i=0;i<P;i++)v[i]=1;return v;}l++,r--;int al=-1,ar,bl,br,op;if(a[l]!='('){al=ar=l;bl=l+2;br=r;op=a[l+1];}else for(int i=l,t=0;i<=r;i++){if(a[i]=='(')t++;if(a[i]==')'){t--;if(!t){al=l;ar=i;bl=i+2;br=r;op=a[i+1];break;}}}V vl=dfs(al,ar),vr,v;v.resize(P);for(int i=0;i<P;i++)v[i]=0;if(op!='^')vr=dfs(bl,br);if(op=='^'){int k=a[bl]-'0';//printf("[%d,%d]^%d\n",al,ar,k);for(int i=0;i<P;i++)(v[po[i][k]]+=vl[i])%=MO;}if(op=='+'){//printf("[%d,%d]+[%d,%d]\n",al,ar,bl,br);for(int i=0;i<len;i++)A[i]=B[i]=C[i]=0;for(int i=0;i<P;i++)A[i]=vl[i],B[i]=vr[i];FFT::mul(A,B,C);for(int i=0;i<len;i++)(v[i%P]+=C[i])%=MO;}if(op=='*'){//printf("[%d,%d]*[%d,%d]\n",al,ar,bl,br);for(int i=0;i<P;i++)v[0]=(1LL*vl[0]*vr[i]+v[0])%MO;for(int i=1;i<P;i++)v[0]=(1LL*vl[i]*vr[0]+v[0])%MO;for(int i=0;i<len;i++)A[i]=B[i]=C[i]=0;for(int i=1;i<P;i++)A[ind[i]]=vl[i],B[ind[i]]=vr[i];FFT::mul(A,B,C);for(int i=0;i<len;i++)(v[gen[i%(P-1)]]+=C[i])%=MO;}//for(int i=0;i<P;i++)printf("->%d %d\n",i,v[i]);return v; } inline int powmod(int a,int b,int P){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t; } int getG(int n){if(n==2)return 1;int i,j,t=0;static int q[N];for(i=2;1LL*i*i<=n-1;i++)if((n-1)%i==0)q[t++]=i,q[t++]=(n-1)/i;for(i=2;;i++){for(j=0;j<t;j++)if(powmod(i,q[j],n)==1)break;if(j==t)return i;} } int main(){scanf("%d%s",&P,a+1);n=strlen(a+1);if(n==1){if(a[1]=='0')return puts("1"),0;if(a[1]>='a'&&a[1]<='z')return puts("1"),0;return puts("0"),0;}for(len=1;len<P*2;len<<=1);j=__builtin_ctz(len)-1;for(i=0;i<len;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j);for(i=0;i<MO;i++)for(po[i][0]=j=1;j<10;j++)po[i][j]=1LL*po[i][j-1]*i%P;G=getG(P);for(i=0,j=1;i<P-1;i++){gen[i]=j;ind[j]=i;j=1LL*j*G%P;}V ret=dfs(1,n);printf("%d",ret[0]); }

　　

F. Formula-1

設(shè)$s[k]$為第$k$輛車最多能進行的超車次數(shù)，$A[k]$表示它前面那些車給$s[k]$的貢獻，$B[k]$為后面的，則$A[k]=\sum_{i=1}^{k-1}(a[i]+1)$。

設(shè)$b[i]$為第$i$輛車為了到$k+1$這個位置最少需要的超車次數(shù)，則$b[k+1]=0,b[i+1]=b[i]+[a[i]\leq b[i]]$，且$B[k]=\sum_{i=k+1}^n \max(a[i]-b[i],0)$。

若對于每個$k$都有$s[k]\geq a[k]$，則可行。

找出最大的$m$滿足$A[m]\leq a[m]$，則除了$m$之外所有車都可行，暴力檢查$m$即可。

時間復(fù)雜度$O(n)$。

#include<cstdio> const int N=1000010,BUF=30000000; int Case,n,i,k,a[N],b[N];long long s[N];char Buf[BUF],*buf=Buf; inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} int main(){fread(Buf,1,BUF,stdin);read(Case);while(Case--){read(n);for(i=1;i<=n;i++)read(a[i]);for(s[1]=0,i=2;i<=n;i++)s[i]=s[i-1]+a[i-1]+1;for(i=1;i<=n;i++)if(s[i]<=a[i])k=i;for(b[i=k+1]=0;i<n;i++)b[i+1]=b[i]+(a[i]<=b[i]);for(i=k+1;i<=n;i++)if(a[i]>b[i])s[k]+=a[i]-b[i];puts(s[k]>=a[k]?"TAK":"NIE");}return 0; }

　　

G. General

如果凸包大小$\leq 2$，那么特判即可。

否則凸包大小至少為$3$，對于每個詢問，首先在凸包上按極角二分出一條邊，看看是否在凸包內(nèi)或者邊上。

如果不在，那么往左往右二分出兩條切線的位置，然后用叉積前綴和回答詢問即可。

時間復(fù)雜度$O((n+m)\log n)$。

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=100010; int n,m,ce,i,j,x,y,z,ca,cb,cnt;ll f[N<<1]; struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}P operator-(const P&b){return P(x-b.x,y-b.y);}void operator-=(const P&b){*this=*this-b;}bool operator==(const P&b){return x==b.x&&y==b.y;}bool operator!=(const P&b){return x!=b.x||y!=b.y;} }a[N],b,c[N<<1],O; inline bool cmp(const P&a,const P&b){return a.x==b.x?a.y<b.y:a.x<b.x;} inline ll cross(const P&a,const P&b){return 1LL*a.x*b.y-1LL*a.y*b.x;} inline void read(int&a){char c;bool f=0;a=0;while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));if(c!='-')a=c-'0';else f=1;while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';if(f)a=-a; } int convexhull(P*p,int n,P*q){int i,k,m;for(i=m=0;i<n;q[m++]=p[i++])while(m>1&&cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0)m--;k=m;for(i=n-2;i>=0;q[m++]=p[i--])while(m>k&&cross(q[m-1]-q[m-2],p[i]-q[m-2])<=0)m--;return --m; } inline bool point_on_segment(P p,P a,P b){return !cross(b-a,p-a)&&1LL*(p.x-a.x)*(p.x-b.x)+1LL*(p.y-a.y)*(p.y-b.y)<=0; } inline int askl(int l,int r,P p){int t=l++,mid;while(l<=r){mid=(l+r)>>1;if(cross(c[mid]-p,c[(mid-1+n)%n]-c[mid])<=0)l=(t=mid)+1;else r=mid-1;}return t; } inline int askr(int l,int r,P p){int t=r--,mid;while(l<=r){mid=(l+r)>>1;if(cross(c[mid]-p,c[(mid+1)%n]-c[mid])>=0)r=(t=mid)-1;else l=mid+1;}return t; } inline ll solve(P p){if(n<2)return 0;if(n==2)return abs(f[0]+cross(c[1],p)+cross(p,c[0]));if(point_on_segment(p,c[0],c[n-1]))return f[n-1];int o=0;if(p.x>0){int l=1,r=n-1,mid;while(l<=r)if(cross(c[mid=(l+r)>>1],p)>=0)l=(o=mid)+1;else r=mid-1;}else if(p.y>0)o=n-1;if(p.x>=0&&cross(p-c[o],c[o+1]-p)<0)return f[n-1];if(p.x>=0&&point_on_segment(p,c[o],c[o+1]))return f[n-1];int l,r;if(p.x>0)l=askl(0,o,p),r=askr(o,n,p);else l=askl(m,n,p),r=askr(0,m,p);if(l>r)r+=n;return f[n-1]+cross(c[l],p)+cross(p,c[r])-f[r-1]+f[l-1]; } int main(){read(ca),read(cb);for(i=1;i<=ca;i++)read(a[i].x),read(a[i].y);cnt=ca;sort(a+1,a+ca+1,cmp);for(ca=0,i=1;i<=cnt;i++)if(i==1||a[i]!=a[i-1])a[++ca]=a[i];n=convexhull(a+1,ca,c);for(O=c[0],i=0;i<n;i++)c[i]-=O;for(i=0;i<n;i++)if(c[i].x>=c[m].x)m=i;for(i=0;i<n;i++)c[i+n]=c[i];for(i=0;i<n+n;i++){f[i]=cross(c[i],c[i+1]);if(i)f[i]+=f[i-1];}while(cb--){read(b.x),read(b.y);ll tmp=solve(b-O);printf("%lld.%lld\n",tmp/2,tmp%2*5);}return 0; }

　　

H. Hydra

設(shè)$f[x]$為擊殺$x$的最小代價，則$f[x]=\min(k[x],s[x]+\sum(f[x的后繼]))$，用SPFA來循環(huán)更新即可。

#include<cstdio> typedef long long ll; const int N=200010,M=1000010,P=1048575,BUF=20000000; int n,i,j,x,g[N],v[M],nxt[M],ed,in[N],h,t,q[P+1];ll f[N],f2[N];char Buf[BUF],*buf=Buf; inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} inline void read(ll&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;} int main(){for(fread(Buf,1,BUF,stdin),read(n),i=1;i<=n;i++)for(read(f2[i]),read(f[i]),read(j);j--;add(x,i))read(x);for(i=1;i<=n;i++)for(j=g[i];j;j=nxt[j])f2[v[j]]+=f[i];for(i=h=1;i<=n;i++)in[q[++t]=i]=1;while(h!=((t+1)&P)){x=q[h++],h&=P;if(f[x]>f2[x]){for(i=g[x];i;i=nxt[i]){f2[j=v[i]]-=f[x]-f2[x];if(!in[j]){in[j]=1;q[h=(h-1+P)&P]=j;}}f[x]=f2[x];}in[x]=0;}return printf("%lld",f[1]),0; }

　　

I. Inversions

線段樹優(yōu)化BFS。

#include<cstdio> #include<algorithm> using namespace std; const int N=1000010,M=2222222; int n,i,j,a[N],vmi[M],vma[M],mx,tot,e[N][2]; int q[N],h,t; bool vis[N]; inline void up(int x){vmi[x]=min(vmi[x<<1],vmi[x<<1|1]);vma[x]=max(vma[x<<1],vma[x<<1|1]); } void build(int x,int a,int b){if(a==b){vmi[x]=vma[x]=::a[a];return;}int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b);up(x); } void clear(int x,int a,int b,int c){if(a==b){vis[q[++t]=a]=1;vmi[x]=N,vma[x]=0;return;}int mid=(a+b)>>1;if(c<=mid)clear(x<<1,a,mid,c);else clear(x<<1|1,mid+1,b,c);up(x); } void bigger(int x,int a,int b,int c,int d,int p){if(vma[x]<p)return;if(a==b){vis[q[++t]=a]=1;vmi[x]=N,vma[x]=0;return;}int mid=(a+b)>>1;if(c<=mid)bigger(x<<1,a,mid,c,d,p);if(d>mid)bigger(x<<1|1,mid+1,b,c,d,p);up(x); } void smaller(int x,int a,int b,int c,int d,int p){if(vmi[x]>p)return;if(a==b){vis[q[++t]=a]=1;vmi[x]=N,vma[x]=0;return;}int mid=(a+b)>>1;if(c<=mid)smaller(x<<1,a,mid,c,d,p);if(d>mid)smaller(x<<1|1,mid+1,b,c,d,p);up(x); } inline void bfs(int S){mx=S;h=1,t=0;clear(1,1,n,S);while(h<=t){int x=q[h++];if(x>mx)mx=x;if(x>1)bigger(1,1,n,1,x-1,a[x]);if(x<n)smaller(1,1,n,x+1,n,a[x]);} } int main(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);for(i=1;i<=n;i++)if(!vis[i]){bfs(i);tot++;e[tot][0]=i;e[tot][1]=mx;}printf("%d\n",tot);for(i=1;i<=tot;i++){printf("%d",e[i][1]-e[i][0]+1);for(j=e[i][0];j<=e[i][1];j++)printf(" %d",j);puts("");} }

　　

J. Procrastination

按時間從后往前貪心安排任務(wù)。

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=1000010; int n,i;ll cur; struct P{int d,t;}a[N]; inline bool cmp(const P&a,const P&b){return a.t>b.t;} int main(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&a[i].d,&a[i].t);sort(a+1,a+n+1,cmp);cur=1LL<<60;for(i=1;i<=n;i++){if(cur>a[i].t)cur=a[i].t-a[i].d+1;else cur-=a[i].d;}printf("%lld",cur-1); }

　　

K. Rabbits

若$n=3$，那么貪心取最大的$k$個即可。

否則打槍順序無關(guān)，要么第一槍打$1$，要么第一槍打$2$，要么打$3..n$。

第一槍打$1$和$2$時，模擬出變化后的情況，并將次數(shù)減$1$，將環(huán)當(dāng)成序列考慮，那么不能在相鄰兩個位置打槍，若$i$和$i-2$都打槍，那么可以同時打到$i-1$，DP即可。

第一槍打$3..n$時，可以直接將環(huán)當(dāng)成鏈DP。

時間復(fù)雜度$O(nk)$。

#include<cstdio> #include<algorithm> const int N=4010,M=2010; int n,m,K,i,j,a[N*2],b[N],f[2][M][2][2],ans; inline void up(int&a,int b){a<b?(a=b):0;} inline int dp(int flag){if(!K)return 0;if(flag){b[2]+=b[1],b[m-1]+=b[m];b[1]=b[m]=0;}int i,j,x,y,o=0,ret=0;for(j=0;j<=K;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)f[o][j][x][y]=-1;f[o][0][0][0]=0;for(i=0;i<m;i++,o^=1){for(j=0;j<=K;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)f[o^1][j][x][y]=-1;for(j=0;j<=K;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)if(~f[o][j][x][y]){up(f[o^1][j][y][0],f[o][j][x][y]);if(!y&&j<K){if(x)up(f[o^1][j+1][y][1],f[o][j][x][y]+b[i]+b[i+1]);else up(f[o^1][j+1][y][1],f[o][j][x][y]+b[i+1]);}}}for(j=0;j<=K;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)up(ret,f[o][j][x][y]);return ret; } int main(){scanf("%d%d",&n,&K);if(!K)return puts("0"),0;for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];if(n==3){std::sort(a+1,a+n+1);for(i=n;i&&K;i--)ans+=a[i],K--;return printf("%d",ans),0;}K=std::min(K,n/2+5);K--;for(i=1;i<=2;i++){for(m=0,j=i+1;j<i+n;j++)b[++m]=a[j];up(ans,dp(1)+a[i]);}K++;for(m=0,i=3;i<=n;i++)b[++m]=a[i];up(ans,dp(0));return printf("%d",ans),0; }

　　

總結(jié)

以上是生活随笔為你收集整理的XII Open Cup named after E.V. Pankratiev. GP of Eastern Europe (AMPPZ-2012)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。