首页 > 代码库 > XIV Open Cup named after E.V. Pankratiev. GP of SPb
XIV Open Cup named after E.V. Pankratiev. GP of SPb
A. Bracket Expression
直接按题意模拟即可。
时间复杂度$O(n)$。
#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;char s[Maxn];int ls;LL sta[Maxn];int top=0;int main(){ freopen("bracket-expression.in","r",stdin); freopen("bracket-expression.out","w",stdout); fgets(s,sizeof s,stdin); for(int i=0;(s[i]==‘(‘)||(s[i]==‘)‘);i++){//-1,-2 if(s[i]==‘(‘)sta[top++]=-1; else{ LL cur=1; while(top&&sta[top-1]!=-1){ cur=cur*sta[top-1]; top--; } sta[top-1]=cur+1; } } LL ret=1; while(top)ret=1LL*ret*sta[top-1],top--; printf("%lld\n",ret); return 0;}
B. Checkers
暴力搜索所有对战情况，然后模拟。
时间复杂度$O(2^nk)$。
#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;int n,k;string s[22];int ans=0;int jud(vector<int>&V,string &s){ for(int i=V.size()-1,j=s.size()-1;i>=0&&j>=0;i--,j--){ if(V[i]==(s[j]==‘W‘))continue; if(V[i])return 0; else return 1; } return 1;}void dfs(int cur,int op,int win,vector<int>V){ if(cur>=k){ ans=max(ans,win); return; } for(int i=1;i+cur<=k&&i<=2;i++){ string tmp=s[op]; vector<int>nxt=V; int tmpwin=win; for(int j=0;j<i;j++){ int res=jud(nxt,s[op]); nxt.push_back(res); if(res)tmpwin++; s[op].push_back(res?‘B‘:‘W‘);//res==1:w } dfs(cur+i,(op+1)%n,tmpwin,nxt); s[op]=tmp; }}int main(){ freopen("checkers.in","r",stdin); freopen("checkers.out","w",stdout); scanf("%d%d",&n,&k); for(int i=0;i<n;i++)cin>>s[i]; vector<int>V; dfs(0,0,0,V); printf("%d\n",ans); return 0;}
C. Convex and Compact
枚举起点，设$f[i][j][k]$表示当前凸包转到了$i$点，凸包上和内部有$j$个点，凸包上有$k$个点时凸包的最小周长，然后DP即可。
时间复杂度$O(n^4k)$。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 65 ;const double INF = 1e60 ;const double eps = 1e-8 ;const double pi = acos ( -1.0 ) ;int dcmp ( double x ) { return ( x > eps ) - ( x < -eps ) ;}struct Point { int x , y ; Point () {} Point ( int x , int y ) : x ( x ) , y ( y ) {} bool operator < ( const Point& a ) const { return x != a.x ? x < a.x : y < a.y ; } Point operator + ( const Point& a ) const { return Point ( x + a.x , y + a.y ) ; } Point operator - ( const Point& a ) const { return Point ( x - a.x , y - a.y ) ; } int operator * ( const Point& a ) const { return x * a.y - y * a.x ; } double angle () { return atan2 ( y , x ) ; } double len () { return sqrt ( 0.0 + x * x + y * y ) ; }} ;struct Node { double r ; int idx ; bool operator < ( const Node& a ) const { return r < a.r ; }} ;struct Pre { int x , y , z ; Pre () {} Pre ( int x , int y , int z ) : x ( x ) , y ( y ) , z ( z ) {}} ;Node a[MAXN] ;Point p[MAXN] ;int n , K ;int in[MAXN][MAXN] ;Pre pre[MAXN][MAXN][17] ;double len2[MAXN][MAXN] ;double dp[MAXN][MAXN][17] ;double ans ;int S[MAXN] , top ;int vis[MAXN] ;int id[MAXN] ;int cmp ( const int&a , const int& b ) { return p[a].x != p[b].x ? p[a].x < p[b].x : p[a].y < p[b].y ;}bool PointInTri ( int i , int j , int k , int l ) { LL a = ( p[i] - p[l] ) * ( p[j] - p[l] ) ; LL b = ( p[j] - p[l] ) * ( p[k] - p[l] ) ; LL c = ( p[k] - p[l] ) * ( p[i] - p[l] ) ; return a * b > 0 && b * c > 0 && c * a > 0 ;}void insert ( int x , int y , int z ) { Pre t = pre[x][y][z] ; if ( t.x ) insert ( t.x , t.y , t.z ) ; S[top ++] = a[x].idx ;}void calc ( int m ) { for ( int i = 0 ; i <= m ; ++ i ) { for ( int j = 0 ; j <= m + 1 ; ++ j ) { for ( int k = 0 ; k <= K ; ++ k ) { dp[i][j][k] = INF ; pre[i][j][k] = Pre ( 0 , 0 , 0 ) ; } } for ( int j = 0 ; j <= m ; ++ j ) { len2[i][j] = ( p[a[i].idx] - p[a[j].idx] ).len () ; } } for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = i + 1 ; j <= m ; ++ j ) { in[i][j] = 3 ; for ( int l = 1 ; l <= m ; ++ l ) if ( l != i && l != j ) { if ( PointInTri ( a[0].idx , a[i].idx , a[j].idx , a[l].idx ) ) { in[i][j] ++ ; } } } } for ( int i = 1 ; i <= m ; ++ i ) { dp[i][2][2] = len2[0][i] * 2 ; pre[i][2][2] = Pre ( 0 , 0 , 0 ) ; for ( int j = 2 ; j <= m ; ++ j ) { for ( int k = 3 ; k <= min ( i + 1 , K ) ; ++ k ) { for ( int l = 1 ; l < i ; ++ l ) if ( dp[l][j][k - 1] < 1e50 ) { int num = j + in[l][i] - 2 ; double tmp = dp[l][j][k - 1] - len2[0][l] + len2[0][i] + len2[i][l] ; if ( dp[i][num][k] > tmp ) { dp[i][num][k] = tmp ; //printf ( "%d %d %d %.5f\n" , i , num , k , dp[i][num][k] ) ; pre[i][num][k] = Pre ( l , j , k - 1 ) ; } } } } } int x = -1 , y , z ; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = K ; j <= m + 1 ; ++ j ) { for ( int k = 3 ; k <= K ; ++ k ) if ( dp[i][j][k] < 1e50 ) { //printf ( "dp[%d][%d][%d] = %.5f\n" , i , j , k , dp[i][j][k] ) ; if ( dcmp ( dp[i][j][k] - ans ) < 0 ) { ans = dp[i][j][k] ; x = i ; y = j ; z = k ; } } } } if ( ~x ) { top = 0 ; insert ( x , y , z ) ; S[top ++] = a[0].idx ; }}int check ( int x ) { LL f = ( p[x] - p[S[0]] ) * ( p[x] - p[S[1]] ) ; for ( int i = 0 ; i < top ; ++ i ) { LL ff = ( p[x] - p[S[i]] ) * ( p[x] - p[S[( i + 1 ) % top]] ) ; if ( f * ff < 0 ) return 0 ; } return 1 ;}void solve () { ans = INF ; for ( int i = 1 ; i <= n ; ++ i ) { scanf ( "%d%d" , &p[i].x , &p[i].y ) ; } if ( K == 1 ) { printf ( "%d\n" , 0 ) ; printf ( "%d\n" , 1 ) ; return ; } if ( K == 2 ) { int x , y ; for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = i + 1 ; j <= n ; ++ j ) { double tmp = ( p[i] - p[j] ).len () ; if ( tmp < ans ) { ans = tmp ; x = i ; y = j ; } } } printf ( "%.8f\n" , ans ) ; printf ( "%d %d\n" , x , y ) ; return ; } for ( int i = 1 ; i <= n ; ++ i ) { id[i] = i ; } sort ( id + 1 , id + n + 1 , cmp ) ; a[0].r = -INF ; for ( int i = 1 ; i <= n ; ++ i ) { int m = 0 ; for ( int j = i + 1 ; j <= n ; ++ j ) { ++ m ; a[m].idx = id[j] ; a[m].r = ( p[id[j]] - p[id[i]] ).angle () ; //if ( dcmp ( a[j].r ) < 0 ) a[j].r = 2 * pi + a[j].r ; } a[0].idx = id[i] ; sort ( a + 1 , a + m + 1 ) ; if ( m + 1 >= K ) calc ( m ) ; } printf ( "%.8f\n" , ans ) ; int flag = 0 ; clr ( vis , 0 ) ; for ( int i = 0 ; i < top ; ++ i ) { if ( flag ) printf ( " " ) ; flag = 1 ; printf ( "%d" , S[i] ) ; vis[S[i]] = 1 ; } for ( int i = top + 1 ; i <= K ; ++ i ) { for ( int j = 1 ; j <= n ; ++ j ) if ( !vis[j] ) { if ( check ( j ) ) { printf ( " %d" , j ) ; vis[j] = 1 ; break ; } } } puts ( "" ) ;}int main () { freopen ( "convexset.in" , "r" , stdin ) ; freopen ( "convexset.out" , "w" , stdout ) ; while ( ~scanf ( "%d%d" , &n , &K ) ) solve () ; return 0 ;}
D. Forbidden Words
留坑。
E. Four Prime Numbers
设$f[i]$表示用两个质数能拼出$i$的方案数，可以通过暴力枚举两个质数求出，则$ans=\sum f[i]f[n-i]$。
时间复杂度$O(\frac{n^2}{\ln^2n})$。
#include<cstdio>const int N=100010;int n,i,j,tot,v[N],p[N],f[N];long long ans;int main(){ freopen("fourprimes.in","r",stdin); freopen("fourprimes.out","w",stdout); scanf("%d",&n); for(i=2;i<=n;i++){ if(!v[i])p[tot++]=i; for(j=0;j<tot;j++){ if(i*p[j]>n)break; v[i*p[j]]=1; if(i%p[j]==0)break; } } for(i=0;i<tot;i++){ if(p[i]+p[i]<=n)f[p[i]+p[i]]++; for(j=0;j<i;j++){ if(p[i]+p[j]>n)break; f[p[i]+p[j]]+=2; } } for(i=1;i<=n;i++)ans+=1LL*f[i]*f[n-i]; printf("%lld",ans); return 0;}
F. Set Intersection
随机化找出规律：$ans=\lfloor\frac{LM}{N}\rfloor$。
#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;int LIM=1000;int a[1000020],b[1000020];int n,l,m;int c[1000020],ans[1000020];int main(){ freopen("intset.in","r",stdin); freopen("intset.out","w",stdout); while(scanf("%d%d%d",&n,&l,&m)!=EOF){ long long now=1LL*m*l/n; printf("%lld",now);/* for(int i=0;i<n;i++)b[i]=i; for(int i=0;i<LIM;i++){ random_shuffle(b,b+n); int cur=0; for(int j=0;j<m;j++){ if(b[j]<l)cur++; } ans[cur]++; } for(int i=n-1;i>=0;i--)ans[i]+=ans[i+1]; int rep=0; for(int i=n;i>=0;i--){ if(ans[i]>=LIM/2){ rep=i; break; } } printf("%d\n",rep);*/ } return 0;}
G. Medals
将第$x$名的费用设置为$1001^{10-x}$，那么答案就是二分图最大权匹配，费用流求解即可，需要用__int128存储。
#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 __int128 LL;typedef pair<int,int>pi;const int Maxn=2020,Maxe=200020;LL Inf=1LL<<60;LL pw[15];int ne;int n,s,t;vector<int>G[Maxn];struct E{ int v,c; LL w; E(){} E(int v,int c,LL w):v(v),c(c),w(w){}}e[Maxe];void add(int u,int v,int c,LL w){ e[ne]=E(v,c,w); G[u].push_back(ne++); e[ne]=E(u,0,-w); G[v].push_back(ne++);}int pre[Maxn],pe[Maxn],inq[Maxn];LL d[Maxn];bool spfa(){ for(int i=0;i<=t;i++)d[i]=Inf,inq[i]=0; d[s]=0; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<G[u].size();i++){ int id=G[u][i]; int v=e[id].v; LL w=e[id].w; int c=e[id].c; if(!c)continue; if(d[v]>d[u]+w){ pre[v]=u; pe[v]=id; d[v]=d[u]+w; if(!inq[v]){q.push(v);inq[v]=1;} } } inq[u]=0; } return d[t]<0;}int rep[100];int cho[Maxn];void costflow(){ LL ans=0; while(spfa()){ ans-=d[t]; for(int i=t;i!=s;i=pre[i]){ e[pe[i]].c--; e[pe[i]^1].c++; } } for(int i=0;i<10;i++)rep[10-i]=ans%1001,ans/=1001; for(int i=1;i<=10;i++)printf("%d%c",rep[i],i==10?‘\n‘:‘ ‘); for(int i=1;i<=n;i++){ cho[i]=0; for(int j=0;j<G[i].size();j++){ int id=G[i][j]; if(e[id].v!=s&&(!e[id].c)){ cho[i]=e[id].v-n; } } } for(int i=1;i<=n;i++)printf("%d%c",cho[i],i==n?‘\n‘:‘ ‘);}int main(){ freopen("medals.in","r",stdin); freopen("medals.out","w",stdout); pw[0]=1; Inf*=Inf; for(int i=1;i<=11;i++)pw[i]=pw[i-1]*1001; scanf("%d",&n); for(int i=1;i<=n;i++){ int k;scanf("%d",&k); for(int j=0;j<k;j++){ int id,rk; scanf("%d%d",&id,&rk); add(i,id+n,1,-pw[10-rk]); } add(s,i,1,0); } s=0;t=n+1000+1; for(int i=n+1;i<t;i++)add(i,t,1,0); costflow(); return 0;}
H. Reachability
对于每个询问，压位记忆化搜索即可。
时间复杂度$O(\frac{qn^3}{64})$。
#include<cstdio>#include<bitset>using namespace std;typedef unsigned int U;const int N=405;typedef bitset<N>DS;int n,m,i,A,B;bool g[N][N],v[N];U pa[N],pb[N];DS f[N];void dfs(int x){ if(v[x])return; v[x]=1; for(int i=1;i<=n;i++)if(g[x][i]){ dfs(i); f[x]|=f[i]; }}inline void vio(){ int i,j; for(i=1;i<=n;i++){ v[i]=0,f[i].reset(); f[i][i]=1; } for(i=1;i<=n;i++)if(!v[i])dfs(i); U ret=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(f[i][j]==1&&i!=j){// printf("%d->%d\n",i,j); ret+=pa[i-1]*pb[j-1]; } printf("%u\n",ret);}int main(){ freopen("reachability.in","r",stdin); freopen("reachability.out","w",stdout); scanf("%d%d%d%d",&n,&m,&A,&B); for(pa[0]=i=1;i<=n;i++)pa[i]=pa[i-1]*A; for(pb[0]=i=1;i<=n;i++)pb[i]=pb[i-1]*B; for(i=1;i<=m;i++){ char op1[5],op2[5]; int x,k,y; scanf("%s%s%d%d",op1,op2,&x,&k); if(op2[0]==‘o‘){ while(k--)scanf("%d",&y),g[x][y]^=1; }else{ while(k--)scanf("%d",&y),g[y][x]^=1; } vio(); } return 0;}
I. Revolving Lasers
留坑。
J. Snakes on the Stone
从蛇头开始走，每次碰到交点就往上走即可，这样一定可以保证不打结。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 30 ;int a[MAXN][MAXN] , n , m[3] ;int vis[MAXN][MAXN] ;int x[3][MAXN * MAXN] , y[3][MAXN * MAXN] ;void solve () { clr ( a , 0 ) ; clr ( vis , 0 ) ; for ( int i = 0 ; i < n ; ++ i ) { scanf ( "%d" , &m[i] ) ; for ( int j = 1 ; j <= m[i] ; ++ j ) { scanf ( "%d%d" , &x[i][j] , &y[i][j] ) ; vis[x[i][j]][y[i][j]] ++ ; } } for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 1 ; j <= m[i] ; ++ j ) { int r = x[i][j] , c = y[i][j] ; if ( vis[r][c] == 2 ) { if ( !a[r][c] ) { ++ a[r][c] ; putchar ( ‘-‘ ) ; } else { putchar ( ‘+‘ ) ; } } } puts ( "" ) ; }}int main () { freopen ( "snakes2.in" , "r" , stdin ) ; freopen ( "snakes2.out" , "w" , stdout ) ; while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ;}
K. Dependent Subsets
选出的这些向量的秩只能是$1$或$2$，枚举一个基向量，用它去对其它向量进行消元，约分之后排序，首先被消完的向量都可以选入，然后再选若干个约分后完全相等的向量即可。
时间复杂度$O(n^2d)$。
#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=1020;int n,d;vector<int> a[Maxn];vector<int> b[Maxn];int id[Maxn];int use[Maxn];int st[Maxn];bool cmp(int t1,int t2){ return b[t1]<b[t2];}int xiao(vector<int>&x){//return first nonzero loc int fst=x.size(); for(int i=0;i<x.size();i++){ if(x[i]!=0){fst=i;break;} } if(fst>=x.size())return fst; int gc=abs(x[fst]); for(int i=fst+1;i<x.size();i++){ if(x[i]!=0){ gc=__gcd(abs(x[i]),gc); } } int tmp=x[fst]<0?(-gc):gc; for(int i=fst;i<x.size();i++){ if(x[i]!=0)x[i]=x[i]/tmp; } return fst;}vector<int> dec(vector<int>&x,vector<int>&y,int st1,int st2){ if(!y[st1])return y; vector<int>ret=x; int lcm=x[st1]*abs(y[st1])/__gcd(x[st1],abs(y[st1])); int be1=lcm/x[st1],be2=lcm/y[st1]; for(int i=0;i<x.size();i++)ret[i]=x[i]*be1-y[i]*be2; return ret;}void pt(vector<int>&x){ for(int i=0;i<x.size();i++)printf("%d ",x[i]);puts("");}bool iszero(vector<int>&x){ for(int i=0;i<x.size();i++)if(x[i])return 0; return 1;}int main(){ freopen("subset.in","r",stdin); freopen("subset.out","w",stdout); scanf("%d%d",&n,&d); for(int i=1;i<=n;i++){ for(int j=0;j<d;j++){ int x;scanf("%d",&x); a[i].push_back(x); } } for(int i=1;i<=n;i++)st[i]=xiao(a[i]); vector<int>rep; for(int i=1;i<=n;i++){ int cnt=0; for(int j=i+1;j<=n;j++){ b[cnt]=dec(a[i],a[j],st[i],st[j]); xiao(b[cnt]); use[cnt]=cnt; id[cnt]=j; cnt++; } sort(use,use+cnt,cmp); int sel=-1,sr; int now=0; vector<int>tmp; tmp.push_back(i); for(;now<cnt&&iszero(b[use[now]]);now++)tmp.push_back(id[use[now]]); int tmpans=0; for(int j=now,k;j<cnt;j=k){ for(k=j+1;k<cnt&&b[use[k]]==b[use[j]];k++); if((k-j)>tmpans){ sel=j; sr=k; tmpans=k-j; } } if(sel>=0){ for(int j=sel;j<sr;j++)tmp.push_back(id[use[j]]); } if(tmp.size()>rep.size())swap(tmp,rep); } printf("%d\n",(int)rep.size()); for(int i=0;i<rep.size();i++)printf("%d%c",rep[i],i==rep.size()-1?‘\n‘:‘ ‘); return 0;}
XIV Open Cup named after E.V. Pankratiev. GP of SPb
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。