首页 > 代码库 > XVII Open Cup named after E.V. Pankratiev. Grand Prix of America (NAIPC-2017)
XVII Open Cup named after E.V. Pankratiev. Grand Prix of America (NAIPC-2017)
A. Pieces of Parentheses
将括号串排序，先处理会使左括号数增加的串，这里面先处理减少的值少的串；再处理会使左括号数减少的串，这里面先处理差值较大的串。确定顺序之后就可以DP了。
时间复杂度$O(n^3)$。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=310,inf=1000000;int n,i,j,m,all,f[N*N],g[N*N];char s[N];struct P{ int x,y,w; int type,p; void cal(){ if(y>=0){ type=1; p=-x; }else{ type=0; p=y-x; } }}a[N];inline bool cmp(const P&a,const P&b){ if(a.type!=b.type)return a.type>b.type; if(a.type==1)return a.p<b.p; return a.p>b.p;}int main(){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%s",s); m=strlen(s); for(j=0;j<m;j++){ if(s[j]==‘(‘)a[i].y++;else a[i].y--; a[i].x=min(a[i].x,a[i].y); } a[i].w=m; a[i].cal(); all+=m; } sort(a+1,a+n+1,cmp); for(i=1;i<=all;i++)f[i]=-inf; for(i=1;i<=n;i++){ for(j=0;j<=all;j++)g[j]=f[j]; for(j=0;j<=all;j++)if(j+a[i].x>=0&&f[j]>=0)g[j+a[i].y]=max(g[j+a[i].y],f[j]+a[i].w); for(j=0;j<=all;j++)f[j]=g[j]; } printf("%d",f[0]);}
B. Stars in a Can
求出三维凸包，枚举一个面，求出距离这个面最远的点作为圆柱体的高，然后将所有点投影到平面上求最小圆覆盖作为底面即可。
时间复杂度$O(n^2)$。
C. Stretching Streamers
$f[i][j][k]$表示$[i,j]$区间，$(i,j)$这条边存在情况为$k$时的生成树个数，然后区间DP即可。
时间复杂度$O(n^3)$。
#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=313,mod=1e9+7;int n;int g0[Maxn][Maxn][2];int g1[Maxn][Maxn][2];int a[Maxn];int ok[Maxn][Maxn];inline void up(int &x,int y){ x+=y;if(x>=mod)x-=mod;}int main(){ scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",a+i); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ok[i][j]=__gcd(a[i],a[j])>1; } } for(int i=0;i<n;i++)g0[i][i][0]=g1[i][i][0]=1; for(int len=2;len<=n;len++){ for(int l=0;l<n;l++){ int r=l+len-1; if(r>=n)break; g0[l][r][0]=g0[l][r][1]=0; for(int br=l;br<r;br++){ up(g0[l][r][0],1LL*g0[l][br][1]*g0[br][r][0]%mod); if(ok[l][r])up(g0[l][r][1],1LL*g0[l][br][0]*g1[br+1][r][0]%mod); /* if(l==0&&r==1){ printf("br=%d %d %d\n",br,g0[l][r][0],g0[l][r][1]); } */ } up(g0[l][r][0],g0[l][r][1]); /* if(l==0&&r==2){ printf("%d %d\n",g0[l][r][0],g0[l][r][1]); } */ g1[l][r][0]=g1[l][r][1]=0; for(int bl=r;bl>l;bl--){ up(g1[l][r][0],1LL*g1[bl][r][1]*g1[l][bl][0]%mod); if(ok[l][r])up(g1[l][r][1],1LL*g1[bl][r][0]*g0[l][bl-1][0]%mod); } up(g1[l][r][0],g1[l][r][1]); //printf("l=%d r=%d g=%d\n",l,r,g0[l][r][0]); } } printf("%d\n",g0[0][n-1][0]); return 0;}
D. Heaps from Trees
$f[i][j]$表示$i$的子树内选择点集的权值最大值为$j$时最多选几个点，用dsu on tree配合线段树转移即可。
时间复杂度$O(n\log^2n)$。
#include<cstdio>#include<algorithm>using namespace std;const int N=200010,M=N*20;int n,i,x,g[N],nxt[N],size[N],son[N],a[N],b[N],q[N],cnt;int l[M],r[M],v[M],tag[M],root[N];int rub[M],cur;void clear(int x){ if(!x)return; clear(l[x]); clear(r[x]); rub[++cur]=x;}inline int newnode(){ int x=rub[cur--]; l[x]=r[x]=v[x]=tag[x]=0; return x;}inline void tag1(int x,int p){ if(!x)return; tag[x]+=p; v[x]+=p;}inline void pb(int x){ if(tag[x])tag1(l[x],tag[x]),tag1(r[x],tag[x]),tag[x]=0;}inline void up(int x){ v[x]=max(v[l[x]],v[r[x]]);}void ins(int&x,int a,int b,int c,int d){ if(!x)x=newnode(); pb(x); if(a==b){ v[x]=max(v[x],d); return; } int mid=(a+b)>>1; if(c<=mid)ins(l[x],a,mid,c,d); else ins(r[x],mid+1,b,c,d); up(x);}int ask(int x,int a,int b,int c,int d){ if(!x)return 0; if(c<=a&&b<=d)return v[x]; pb(x); int mid=(a+b)>>1,t=0; if(c<=mid)t=ask(l[x],a,mid,c,d); if(d>mid)t=max(t,ask(r[x],mid+1,b,c,d)); return t;}void add(int x,int a,int b,int c,int d,int p){ if(!x)return; if(c<=a&&b<=d){tag1(x,p);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)add(l[x],a,mid,c,d,p); if(d>mid)add(r[x],mid+1,b,c,d,p); up(x);}inline int lower(int x){ int l=1,r=n,mid,t; while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1; return t;}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i]){ dfs(i); size[x]+=size[i]; if(size[i]>size[son[x]])son[x]=i; }}void go(int x){ q[++cnt]=a[x]; for(int i=g[x];i;i=nxt[i])go(i);}inline void merge(int x,int y){ cnt=0; go(y); sort(q+1,q+cnt+1); q[cnt+1]=n+1; static int A[N],B[N]; for(int i=1;i<=cnt;i++){ int o=q[i]; A[i]=ask(root[y],1,n,o,o); B[i]=ask(root[x],1,n,1,o); } for(int i=1,t=0;i<=cnt;i++){ int o=q[i]; t=max(t,A[i]); if(o!=q[i+1])add(root[x],1,n,o,q[i+1]-1,t); } clear(root[y]); for(int i=1;i<=cnt;i++){ ins(root[x],1,n,q[i],A[i]+B[i]); }}void dfs2(int x){ if(son[x]){ dfs2(son[x]); root[x]=root[son[x]]; } for(int i=g[x];i;i=nxt[i])if(i!=son[x]){ dfs2(i); merge(x,i); } int o=0; if(a[x]>1)o=ask(root[x],1,n,1,a[x]-1); ins(root[x],1,n,a[x],o+1);}int main(){ cur=M-1; for(i=1;i<=cur;i++)rub[i]=i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d",&a[i],&x); if(x){ nxt[i]=g[x]; g[x]=i; } b[i]=a[i]; } sort(b+1,b+n+1); for(i=1;i<=n;i++)a[i]=lower(a[i]); dfs(1); dfs2(1); printf("%d",ask(root[1],1,n,1,n));}
E. Blazing New Trails
二分参数$mid$，将所有特殊边的权值加上$mid$求MST，使得得到的生成树恰好有$K$条特殊边即可。
时间复杂度$O(n\log^2n)$。
F. Incremental Double Free Strings
留坑。
G. Apple Market
二维ST表优化建图的网络流。
#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=55;const int MAXN = 1000005 ;const int MAXE = 3000005 ;const LL INF = 1LL<<60 ;struct Edge { int v , n ; LL c; Edge () {} Edge ( int v , LL c , int n ) : v ( v ) , c ( c ) , n ( n ) {}} ;Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , cur[MAXN] , gap[MAXN] , pre[MAXN] ;int Q[MAXN] , head , tail ;int s , t , nv ;LL flow ;int a[55][55][6][6];int ori[55][55];int cl[66];int idx;void init () { memset ( H , -1 , sizeof H ) ; cntE = 0 ;}void add ( int u , int v , LL c ) { if(v==0)while(1); E[cntE] = Edge ( v , c , H[u] ) ; H[u] = cntE ++ ; E[cntE] = Edge ( u , 0 , H[v] ) ; H[v] = cntE ++ ;}void rev_bfs () { memset ( d , -1 , sizeof d ) ; memset ( gap , 0 , sizeof gap ) ; d[t] = 0 ; gap[d[t]] = 1 ; head = tail = 0 ; Q[tail ++] = t ; while ( head != tail ) { int u = Q[head ++] ; for ( int i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( d[v] == -1 ) { d[v] = d[u] + 1 ; gap[d[v]] ++ ; Q[tail ++] = v ; } } }}int isap () { flow = 0 ; rev_bfs () ; memcpy ( cur , H , sizeof cur ) ; int u = pre[s] = s , i , mv ; while ( d[s] < nv ) { if ( u == t ) { LL f = INF ; for ( i = s ; i != t ; i = E[cur[i]].v ) { if ( f > E[cur[i]].c ) { f = E[cur[i]].c ; u = i ; } } flow += f ; for ( i = s ; i != t ; i = E[cur[i]].v ) { E[cur[i]].c -= f ; E[cur[i] ^ 1].c += f ; } } for ( i = cur[u] ; ~i ; i = E[i].n ) { if ( E[i].c && d[u] == d[E[i].v] + 1 ) break ; } if ( ~i ) { cur[u] = i ; pre[E[i].v] = u ; u = E[i].v ; } else { if ( 0 == -- gap[d[u]] ) break ; mv = nv ; for ( i = H[u] ; ~i ; i = E[i].n ) { int v = E[i].v ; if ( E[i].c && mv > d[v] ) { cur[u] = i ; mv = d[v] ; } } d[u] = mv + 1 ; gap[d[u]] ++ ; u = pre[u] ; } } return flow ;}void precal(int n,int m){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ a[i][j][0][0]=++idx; //a[i][j][0][0]=ori[i][j]; } } for(int i=0;(1<<i)<=n;i++){ for(int j=0;(1<<j)<=m;j++){ if(!i&&!j)continue; for(int x=0;x+(1<<i)<=n;x++){ for(int y=0;y+(1<<j)<=m;y++){ a[x][y][i][j]=++idx; if(!j){ add(a[x][y][i][j],a[x][y][i-1][j],INF); add(a[x][y][i][j],a[x+(1<<(i-1))][y][i-1][j],INF); //a[x][y][i][j]=max(a[x][y][i-1][j],a[x+(1<<(i-1))][y][i-1][j]); } else{ add(a[x][y][i][j],a[x][y][i][j-1],INF); add(a[x][y][i][j],a[x][y+(1<<j-1)][i][j-1],INF); //a[x][y][i][j]=max(a[x][y][i][j-1],a[x][y+(1<<(j-1))][i][j-1]); } } } } }}void ask(int o,int x1,int y1,int x2,int y2){ int len1=x2-x1+1,len2=y2-y1+1; int tx=cl[len1],ty=cl[len2]; len1=tx;len2=ty; add(o,a[x1][y1][tx][ty],INF); add(o,a[x2-(1<<len1)+1][y1][tx][ty],INF); add(o,a[x1][y2-(1<<len2)+1][tx][ty],INF); add(o,a[x2-(1<<len1)+1][y2-(1<<len2)+1][tx][ty],INF);}int check(int x1,int y1,int x2,int y2){ int ret=0; for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++){ ret=max(ret,ori[i][j]); } return ret;}int main(){ init () ; for(int i=2;i<55;i++){ cl[i]=cl[i>>1]+1; } int n , m , k ; scanf ( "%d%d%d" , &n , &m , &k ) ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { scanf ( "%d" , &ori[i][j] ) ; } } precal ( n , m ) ; s = 0 ; for ( int i = 1 ; i <= k ; ++ i ) { int x1 , x2 , y1 , y2 , val ; scanf ( "%d%d%d%d%d" , &x1 , &x2 , &y1 , &y2 , &val ) ; if ( x1 > x2 ) swap ( x1 , x2 ) ; if ( y1 > y2 ) swap ( y1 , y2 ) ; -- x1 ; -- y1 ; -- x2 ; -- y2 ; ++ idx ; add ( s , idx , val ) ; ask ( idx , x1 , y1 , x2 , y2 ) ; } t = ++ idx ; nv = t + 1 ; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ add ( a[i][j][0][0] , t , ori[i][j] ) ; //a[i][j][0][0]=ori[i][j]; } } isap () ; //printf("%d %d\n",idx,cntE); printf ( "%lld\n" , flow ) ; if ( scanf ( "%d%d%d" , &n , &m , &k ) != -1 ) while ( 1 ) ; /* int q=100; while(q--){ int x1=rand()%n,y1=rand()%m,x2=rand()%n,y2=rand()%m; if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); int ans1=ask(x1,y1,x2,y2); int ans2=check(x1,y1,x2,y2); if(ans1!=ans2){ printf("%d %d %d %d ans=%d %d\n",x1,y1,x2,y2,ans1,ans2); } else puts("ok"); } */ return 0;}
H. Maximum Color Clique
留坑。
I. Ski Resort
留坑。
J. Yin and Yang Stones
按题意模拟。
#include <bits/stdc++.h>using namespace std ;const int MAXN = 100005 ;char s[MAXN] ;void solve () { int x = 0 , y = 0 ; for ( int i = 0 ; s[i] ; ++ i ) { if ( s[i] == ‘W‘ ) ++ x ; else ++ y ; } printf ( "%d\n" , x == y ) ;}int main () { while ( ~scanf ( "%s" , s ) ) solve () ; return 0 ;}
K. Unbalanced Parentheses
留坑。
XVII Open Cup named after E.V. Pankratiev. Grand Prix of America (NAIPC-2017)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。