首页 > 代码库 > XVI Open Cup named after E.V. Pankratiev. GP of Siberia
XVI Open Cup named after E.V. Pankratiev. GP of Siberia
A. Passage
枚举两个点，看看删掉之后剩下的图是否是二分图。
#include <bits/stdc++.h>using namespace std ;const int MAXN = 205 ;vector < int > G[MAXN] ;int vis[MAXN] , col[MAXN] ;int n ;int dfs ( int u ) { for ( int i = 0 ; i < G[u].size () ; ++ i ) { int v = G[u][i] ; if ( vis[v] == 0 ) continue ; if ( !col[v] ) { col[v] = 3 - col[u] ; if ( !dfs ( v ) ) return 0 ; } if ( col[u] + col[v] != 3 ) return 0 ; } return 1 ;}int check () { for ( int i = 1 ; i <= n ; ++ i ) { col[i] = 0 ; } for ( int i = 1 ; i <= n ; ++ i ) { if ( col[i] || !vis[i] ) continue ; col[i] = 1 ; if ( !dfs ( i ) ) return 0 ; } return 1 ;}void solve () { for ( int i = 1 ; i <= n ; ++ i ) { int x , y ; scanf ( "%d" , &x ) ; for ( int j = 0 ; j < x ; ++ j ) { scanf ( "%d" , &y ) ; G[i].push_back ( y ) ; G[y].push_back ( i ) ; } vis[i] = 1 ; } if ( n <= 3 ) { printf ( "Hurrah!\n" ) ; return ; } for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = i + 1 ; j <= n ; ++ j ) { vis[i] = vis[j] = 0 ; if ( check () ) { printf ( "Hurrah!\n" ) ; return ; } vis[i] = vis[j] = 1 ; } } printf ( "Fired.\n" ) ;}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ;}
B. Files list
按题意模拟。
#include <bits/stdc++.h>using namespace std ;const int MAXN = 10005 ;map < string , int > mp ;map < int , string > mp2 ;char s[MAXN] , p[MAXN] ;int n ;void solve () { mp.clear () ; mp2.clear () ; int cnt = 0 ; for ( int i = 0 ; i < n ; ++ i ) { scanf ( "%s" , s ) ; int t = 0 , f = 0 ; for ( int j = 0 ; s[j] ; ++ j ) { if ( f ) p[t ++] = s[j] ; else if ( s[j] == ‘.‘ ) f = 1 ; } p[t] = 0 ; if ( mp.count ( p ) ) mp[p] ++ ; else { mp[p] ++ ; mp2[++ cnt] = p ; } } for ( int i = 1 ; i <= cnt ; ++ i ) { cout << mp2[i] << ": " << mp[mp2[i]] << endl ; }}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ;}
C. Graph optimization
将所有1类限制的边加入，分块bitset判定限制2是否都满足即可。
时间复杂度$O(\frac{nm}{64})$。
#include<algorithm>#include<cstdio>#include<bitset>#include<set>#include<ctime>using namespace std;typedef bitset<4096>B;typedef unsigned long long ll;const int N=300010;int n,m,i,j,k,x,y,z,ans[N][2],quailty;int g[N],G[N],v[N],nxt[N],ed;int vis[N],q[N],h,t,cnt,f[N],d[N];B dp[100010];//dp[x] : this can reach xset<int>SET[100010];struct E{int x,y,z;}e[N];const int BUF=5000000;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 bool cmp(const E&a,const E&b){return a.z<b.z;}inline void add(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void add2(int x,int y){ v[++ed]=y;nxt[ed]=G[x];G[x]=ed;}void dfs1(int x){ vis[x]=1; for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])dfs1(v[i]); q[++t]=x;}void dfs2(int x,int y){ vis[x]=0;f[x]=y; for(int i=G[x];i;i=nxt[i])if(vis[v[i]])dfs2(v[i],y);}inline bool solve(int L,int R){ if ( clock () > 2.95 * CLOCKS_PER_SEC ) return 1 ; int z=e[L].z; int i; for(i=1;i<=cnt;i++){ dp[i].reset(); //if ( clock () > 2.95 * CLOCKS_PER_SEC ) return 1 ; } for(i=max(z<<12,1);(i>>12)==z;i++){ dp[f[i]][i&4095]=1; } for(i=1;i<=cnt;i++){ int x=q[i]; for(int j=g[x];j;j=nxt[j]){ dp[v[j]]|=dp[x]; //if ( clock () > 2.95 * CLOCKS_PER_SEC ) return 1 ; } } for(i=L;i<=R;i++){ int x=e[i].x,y=e[i].y; //printf("-> %d %d %d %llu\n",x,y,z,dp[f[y]]); if(dp[f[y]][x&4095])return 0; } return 1;}int main (){ freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; fread(Buf,1,BUF,stdin); read(n),read(m); for(i=1;i<=m;i++){ //x=i,y=i+1; read(x),read(y); ans[i][0]=x,ans[i][1]=y; add(x,y); add2(y,x); } for(i=1;i<=n;i++)if(!vis[i])dfs1(i); for(i=n;i;i--)if(vis[q[i]])dfs2(q[i],++cnt); for(ed=0,i=1;i<=cnt;i++)g[i]=0; for(i=1;i<=m;i++){ x=ans[i][0],y=ans[i][1]; if(f[x]==f[y])continue; if(SET[f[x]].find(f[y])!=SET[f[x]].end())continue; SET[f[x]].insert(f[y]); add(f[x],f[y]); d[f[y]]++; } for(h=1,t=0,i=1;i<=cnt;i++)if(!d[i])q[++t]=i; while(h<=t)for(i=g[q[h++]];i;i=nxt[i])if(!(--d[v[i]]))q[++t]=v[i]; //now q is topo sequence of SCC read(quailty); for(i=1;i<=quailty;i++){ //e[i].x=i+1; //e[i].y=i; read(e[i].x),read(e[i].y); e[i].z=e[i].x>>12; } sort(e+1,e+quailty+1,cmp); for(i=1;i<=quailty;i=j){ for(j=i;j<=quailty&&e[i].z==e[j].z;j++); if(!solve(i,j-1))return puts("NO"),0; } puts("YES"); printf("%d\n",m); for(i=1;i<=m;i++)printf("%d %d\n",ans[i][0],ans[i][1]); return 0 ;}
D. Housing payments
设$f[i]$表示前$i$个月付清，且第$i$个月进行了交易的最小代价，那么因为债务指数级增长，所以可用决策只有$O(\log n)$项。
#include <bits/stdc++.h>using namespace std ;typedef pair < int , int > pii ;const int MAXN = 100005 ;const int INF = 0x3f3f3f3f ;int s[MAXN] , x[MAXN] , p[MAXN] ;double dp[MAXN] ;int n ;void solve () { for ( int i = 1 ; i <= n ; ++ i ) { scanf ( "%d%d%d" , &s[i] , &x[i] , &p[i] ) ; dp[i] = 1e18 ; } dp[0] = 0 ; for ( int i = 0 ; i <= n ; ++ i ) { double sum1 = 0 ; for ( int j = i + 1 ; j <= i + 100 && j <= n ; ++ j ) { dp[j] = min ( dp[j] , dp[i] + sum1 + s[j] + x[j] ) ; sum1 = ( sum1 + s[j] ) * ( 1 + 0.01 * p[j] ) ; } } printf ( "%.10f\n" , dp[n] ) ;}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ;}
E. Arithmetic expressions
$f[i][j]$表示长度为$i$的值为$j$的表达式个数，然后枚举后面接上什么转移即可。
#include <bits/stdc++.h>using namespace std ;const int mod=1e9+7;int n,m,p;int dp[55][222];int len[333];void up(int &x,int y){x+=y;if(x>=mod)x-=mod;}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; while(scanf("%d%d%d",&n,&m,&p)!=EOF){ memset(dp,0,sizeof dp); for(int i=0;i<m;i++){ int x=i; if(!x){len[i]=1;continue;} int l=0; while(x)l++,x/=10; len[i]=l; } for(int i=1;i<=n;i++){ for(int j=0;j<m;j++){ if(len[j]==i)up(dp[i][j],1); if(i>=3)up(dp[i][j],dp[i-2][j]); } //if(i==2)up(dp[i][0],1); for(int j=0;j<m;j++){ for(int k=1;k+1<i;k++){ int nj,ni=i-k-1; for(int nm=0;nm<m;nm++){ for(int ty=0;ty<2;ty++){ if(!ty)nj=(j+nm)%m; else nj=(j-nm+m)%m; if(ni>2)up(dp[i][nj],1LL*dp[k][j]*dp[ni-2][nm]%mod); if(len[nm]==ni)up(dp[i][nj],dp[k][j]); } } } } } printf("%d\n",dp[n][p]); } return 0;}
F. Sputnik
留坑。
G. Voting
设$f[i][j]$表示$i$的子树里选举情况为$j$的最小代价，转移则用另一个$dp[i][a][b][c]$表示考虑了前$i$个儿子，三个人选票各自为$a,b,c$的最小代价来转移。
#include <bits/stdc++.h>using namespace std ;const int mod=1e9+7;const int Maxn=10050,M=10,Inf=1e9;typedef pair<int,int>pi;int n,m,K;vector<int>G[Maxn];int f[Maxn][4];int g[23][23][23][23];int ori[Maxn];vector<pi>ans;vector<pi>res[Maxn][4];pi pre[23][23][23][23];void init(int cs){ for(int i=0;i<21;i++){ for(int j=0;j<21;j++){ for(int k=0;k<21;k++) g[cs][i][j][k]=Inf; } }}struct State{ int x,y,z; State(){} State(int x,int y,int z):x(x),y(y),z(z){}}st[Maxn][4];int get(int a,int b,int c){ vector<pi>v; v.push_back(pi(a,1)); v.push_back(pi(b,2)); v.push_back(pi(c,3)); sort(v.begin(),v.end()); reverse(v.begin(),v.end()); if(v[0].first==v[1].first)return 0; return v[0].second;}void dfs(int u){ if(u>m){ for(int i=0;i<4;i++){ if(i>K)f[u][i]=Inf; else { res[u][i].push_back(pi(u,i)); f[u][i]=i==ori[u]?0:1; } } return ; } for(int i=0;i<G[u].size();i++){ int v=G[u][i]; dfs(v); } int n=G[u].size(); init(0); g[0][0][0][0]=0; for(int i=0;i<n;i++){ int v=G[u][i]; init(i+1); int it[4]; for(it[0]=0;it[0]<=20;it[0]++) for(it[1]=0;it[1]<=20;it[1]++) for(it[2]=0;it[2]<=20;it[2]++){ if(g[i][it[0]][it[1]][it[2]]==Inf)continue; int w=g[i][it[0]][it[1]][it[2]]; for(int ty=0;ty<4;ty++){ if(f[v][ty]==Inf)continue; if(ty)it[ty-1]++; int nw=w+f[v][ty]; int &t=g[i+1][it[0]][it[1]][it[2]]; if(nw<t){ t=nw; pre[i+1][it[0]][it[1]][it[2]]=pi(v,ty); } if(ty)it[ty-1]--; } } } for(int i=0;i<4;i++)f[u][i]=Inf; for(int i=0;i<=20;i++){ for(int j=0;j<=20;j++){ for(int k=0;k<=20;k++){ if(g[n][i][j][k]==Inf)continue; int ty=get(i,j,k); if(f[u][ty]>g[n][i][j][k]){ f[u][ty]=g[n][i][j][k]; st[u][ty]=State(i,j,k); } } } } for(int i=0;i<4;i++){ if(f[u][i]==Inf)continue; res[u][i].clear(); State tmp=st[u][i]; for(int cur=n;cur>=1;cur--){ res[u][i].push_back(pre[cur][tmp.x][tmp.y][tmp.z]); int ty=pre[cur][tmp.x][tmp.y][tmp.z].second; if(ty==1)tmp.x--; if(ty==2)tmp.y--; if(ty==3)tmp.z--; } reverse(res[u][i].begin(),res[u][i].end()); } //printf("u=%d\n",u); //for(int i=0;i<4;i++)printf("%d ",f[u][i]);puts("");}void dfs2(int u,int ty){ //printf("u=%d ty=%d\n",u,ty); if(u>m){ if(ori[u]!=ty)ans.push_back(pi(u,ty)); return; } //printf("sz=%d\n",(int)res[u][1].size()); for(int i=0;i<G[u].size();i++){ //printf("v=%d\n",G[u][i]); dfs2(G[u][i],res[u][ty][i].second); }}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; scanf("%d%d%d",&n,&m,&K); for(int i=1;i<=n;i++)scanf("%d",&ori[i+m]); for(int i=1;i<=m;i++){ int k;scanf("%d",&k); for(int j=0;j<k;j++){ int x;scanf("%d",&x); if(x<0)x=-x; else x=m+x; G[i].push_back(x); } } dfs(1); //puts("ok1"); dfs2(1,1); printf("%d\n",(int)ans.size()); for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first-m,ans[i].second); return 0;}
H. Novice urbanist
枚举每个点和每个区间，那么它能贡献的距离是一段区间，差分前缀和即可。
#include <bits/stdc++.h>using namespace std ;int n,m,l,r,cnt,i,j;int a[11111],f[4444444];struct P{int l,r;P(){}P(int _l,int _r){l=_l,r=_r;}}b[1111],c[1111];inline bool cmp(const P&a,const P&b){return a.l<b.l;}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=m;i++)scanf("%d%d",&b[i].l,&b[i].r); sort(b+1,b+m+1,cmp); l=1e9; r=-l; for(i=1;i<=m;i++){ if(b[i].l>r+1){ if(l<=r)c[++cnt]=P(l,r); l=b[i].l; } r=max(r,b[i].r); } if(l<=r)c[++cnt]=P(l,r); for(i=1;i<=n;i++){ for(j=1;j<=cnt;j++){ f[c[j].l-a[i]+2000000]++; f[c[j].r-a[i]+2000000+1]--; } } for(i=1;i<4000000;i++)f[i]+=f[i-1]; int ans=-1,ans2; for(i=0;i<2000000;i++){ int t=max(f[2000000+i],f[2000000-i]); if(t>ans)ans=t,ans2=i; } printf("%d %d",ans2,ans); return 0 ;}
I. Rangefinder
留坑。
J. Hive
求出方向向量$(x,y)$，顺时针旋转$60$°后是$(x+y,-x)$。
#include <bits/stdc++.h>using namespace std ;const int Maxn=100020;int n,x,y,a,b;int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; scanf("%d%d%d",&n,&x,&y); while(n--){ scanf("%d%d",&a,&b); a-=x,b-=y; printf("%d %d\n",x+a+b,y-a); } return 0;}
K. Side effects
每次加入一条边之后暴力染色，然后将经过的边删掉，均摊复杂度$O(n+m)$。
#include <bits/stdc++.h>using namespace std ;const int Maxn=100020;int n,m,q,ans;set<int>G[Maxn];int col[Maxn];void dfs(int u){ //printf("u=%d\n",u); col[u]=1; for(set<int>::iterator it=G[u].begin();it!=G[u].end();){ //printf("iv=%d\n",*it); if(!col[*it]){ dfs(*it); ans++; } G[u].erase(it++); }}void solve(){ ans=0; for(int i=1;i<=m;i++){ int x;scanf("%d",&x); col[x]=1; ans++; } while(q--){ //puts("ok"); int u,v;scanf("%d%d",&u,&v); if(u!=v)G[v].insert(u); if(col[v]==1)dfs(v); printf("%d\n",ans); }}int main () { freopen ( "input.txt" , "r" , stdin ) ; freopen ( "output.txt" , "w" , stdout ) ; while ( ~scanf ( "%d%d%d" , &n,&m,&q ) ) solve () ; return 0 ;}
L. Cypher
留坑。
总结：
- 在分块bitset时，应尽量设大bitset的大小，减少bitset的操作次数，这样常数反而小。
XVI Open Cup named after E.V. Pankratiev. GP of Siberia
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。