首页 > 代码库 > XVII Open Cup named after E.V. Pankratiev. GP of SPb
XVII Open Cup named after E.V. Pankratiev. GP of SPb
A. Array Factory
将下标按前缀和排序，然后双指针，维护最大的右边界即可。
#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int N=200010;int n,i,j,anslen,ansl,ansr,mr,q[N];ll a[N],lim;inline bool cmp(int x,int y){return a[x]<a[y];}int main(){ freopen("arrayfactory.in","r",stdin); freopen("arrayfactory.out","w",stdout); scanf("%d%lld",&n,&lim); for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1]; for(i=0;i<=n;i++)q[i]=i; sort(q,q+n+1,cmp); for(i=j=0;i<=n;i++){ while(j<=n&&a[q[j]]-a[q[i]]<=lim)mr=max(mr,q[j++]); if(mr>q[i]){ int len=mr-q[i]; if(len>anslen){ anslen=len; ansl=q[i]; ansr=n-mr; }else if(len==anslen&&q[i]<ansl){ ansl=q[i]; ansr=n-mr; } } } if(!anslen)return puts("-1"),0; printf("%d\n%d %d",anslen,ansl,ansr);}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
B. Purchases and Bonuses
$f[i][j]$表示购买了前$i$个物品，目前有$j$积分时最多省多少钱，转移就是要么直接买，要么把积分全用完。
#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;typedef pair<LL,LL>pi;const int Maxn=102,Inf=1e9;int n;int a[Maxn];int pre[102][100020];int pw[102][100020];int rep[102];int dp[2][100020];int main(){ freopen("bonuses.in","r",stdin); freopen("bonuses.out","w",stdout); while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++)scanf("%d",a+i); int cs=0; for(int i=0;i<=n*1000;i++)dp[cs][i]=Inf; dp[cs][0]=0; for(int i=1;i<=n;i++,cs^=1){ for(int j=0;j<=n*1000;j++)dp[cs^1][j]=Inf; for(int j=0;j<=i*1000;j++){ if(dp[cs][j]==Inf)continue; if(dp[cs^1][j+a[i]/100]>dp[cs][j]+a[i]){ dp[cs^1][j+a[i]/100]=dp[cs][j]+a[i]; pre[i][j+a[i]/100]=j; pw[i][j+a[i]/100]=0; } int tmp=min(a[i],j); int tmpv=dp[cs][j]+a[i]-tmp; if(dp[cs^1][j-tmp]>tmpv){ dp[cs^1][j-tmp]=tmpv; pre[i][j-tmp]=j; pw[i][j-tmp]=tmp; } } } int ans=Inf,anscs; for(int i=0;i<=n*1000;i++){ if(ans>dp[cs][i]){ ans=dp[cs][i];anscs=i; } } for(int i=n;i>=1;i--){ rep[i]=pw[i][anscs]; anscs=pre[i][anscs]; } printf("%d\n",ans); for(int i=1;i<=n;i++)printf("%d + %d\n",a[i]-rep[i],rep[i]); }}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
C. Number of Solutions
留坑。
D. Cutting Potatoes
暴力枚举即可。
#include<cstdio>#include<algorithm>using namespace std;typedef long long LL;typedef pair<LL,LL>pi;int n,K;struct Node{ LL x,y; Node(){} Node(LL x,LL y):x(x),y(y){} bool operator <(const Node&a)const{ return x*a.y<=y*a.x; } Node operator /(const Node&a)const{ return Node(x*a.y,y*a.x); }};int cmp(Node a,Node b){ if(a.x*b.y==a.y*b.x)return 0; return a.x*b.y>a.y*b.x?1:-1;}int a[102];int rep[102],tmprep[102];int main(){ freopen("cut-potatoes.in","r",stdin); freopen("cut-potatoes.out","w",stdout); while(scanf("%d%d",&n,&K)!=EOF){ for(int i=1;i<=n;i++)scanf("%d",a+i); Node ans=Node(10000000,1); for(int i=1;i<=n;i++){ for(int j=1;j<=K;j++){ Node minx=Node(a[i],j); Node maxx=Node(1,10000000); bool flag=1; for(int k=1;k<=n;k++){ int x=a[k]*minx.y/minx.x; if(!x){flag=0;break;} x=min(x,K); tmprep[k]=x; maxx=max(Node(a[k],x),maxx); } if(!flag){continue;} Node tans=maxx/minx; if(tans<ans){ ans=tans; for(int k=1;k<=n;k++)rep[k]=tmprep[k]; } } } for(int i=1;i<=n;i++)printf("%d%c",rep[i],i==n?‘\n‘:‘ ‘); }}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
E. Divide and Conquer
DP求出点数为$n$时的划分方案数，然后枚举决策找到第$k$小解即可。
#include<bits/stdc++.h>using namespace std;typedef long long LL;typedef vector<int>vi;struct P{ int x,y; P(){} P(int x,int y):x(x),y(y){} bool operator<(const P&a)const{ if(x!=a.x)return x<a.x; return y<a.y; } P operator -(const P&a)const{ return P(x-a.x,y-a.y); } int operator *(const P&a)const{ return x*a.y-y*a.x; }}a[33];int n;LL Mp[44];int cal(P t1,P t2,P t3){ int tmp=(t2-t1)*(t3-t1); return tmp>0;}bool cmp(int x,int y){return a[x]<a[y];}LL dfs(int n){ if(Mp[n]>=0)return Mp[n]; if(!n){return Mp[n]=1;} LL t=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ int l=j-i-1,r=n-2-l; if((l&1))continue; LL res1=dfs(l); LL res2=dfs(r); t+=res1*res2; } } return Mp[n]=t;}vector<P>rep;void pt(vi cur,LL ned){ if(cur.empty())return; bool flag=1; for(int i=0;i<cur.size()&&flag;i++){ for(int j=i+1;j<cur.size()&&flag;j++){ P t1=a[cur[i]],t2=a[cur[j]]; vi vl,vr; for(int k=0;k<cur.size();k++){ if(k==i||k==j)continue; if(cal(t1,t2,a[cur[k]]))vl.push_back(cur[k]); else vr.push_back(cur[k]); } if(vl.size()&1)continue; sort(vl.begin(),vl.end(),cmp); sort(vr.begin(),vr.end(),cmp); LL res1=Mp[vl.size()]; LL res2=Mp[vr.size()]; if(ned>=res1*res2)ned-=res1*res2; else{ rep.push_back(t1); rep.push_back(t2); pt(vl,ned/res2); pt(vr,ned%res2); flag=0; break; } } }}int main(){ freopen("dnc.in","r",stdin); freopen("dnc.out","w",stdout); //cal(P(0,0),P(2,0),P(2,1)); while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++){ int x,y; scanf("%d%d",&x,&y); a[i]=P(x,y); } vi ori(n,0); for(int i=0;i<n;i++)ori[i]=i; sort(ori.begin(),ori.end(),cmp); memset(Mp,-1,sizeof Mp); dfs(n); // for(int i=1;i<=n;i++)printf("%lld ",Mp[i]);puts(""); rep.clear(); LL k;scanf("%lld",&k); pt(ori,k); for(int i=0;i<rep.size();i++)printf("%d %d\n",rep[i].x,rep[i].y); }}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
F. Doubling
大范围直接$/2$构造，小范围DP求解。
#include<cstdio>#include<algorithm>#include<string>#include<iostream>using namespace std;typedef long long ll;const int N=200010;const int inf=100000000;typedef pair<int,string>P;int n,i,j;P f[111];string cal(int n){ if(n<=100)return f[n].second; if(n&1)return cal(n-1)+"1"; return "["+cal(n/2)+"]";}int main(){ freopen("doubling.in","r",stdin); freopen("doubling.out","w",stdout); scanf("%d",&n); f[0]=P(0,""); f[1]=P(1,"1"); f[2]=P(2,"11"); for(i=3;i<=100;i++){ f[i]=P(inf,""); for(j=1;j<i;j++){ P x=f[j]; x.first+=f[i-j].first; x.second+=f[i-j].second; f[i]=min(f[i],x); } if(i%2==0){ P x(f[i/2].first+2,"["+f[i/2].second+"]"); f[i]=min(f[i],x); } } cout<<cal(n)<<endl; return 0;}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
G. New Collection
随机100轮算出期望集合大小，然后找到差距最近的即可。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define getid( l , r ) l + r | ( l != r )set < string> s ;double magic[7]={10.0,100.0,999.96,6325.61,9517.19,9950.67,9995.01};void solve () { string c ; for ( int i = 1 ; i <= 10000 ; ++ i ) { cout << "+" << endl ; fflush ( stdout ) ; cin >> c ; s.insert(c); } int x = ( int ) s.size () ; double ret=1e9; int ans; for(int i=0;i<7;i++){ double now=fabs(1.0*x-magic[i]); if(now<ret)ret=now,ans=i; } int fin=1; for(int i=0;i<=ans;i++)fin*=10; printf("= %d\n",fin); fflush ( stdout ) ; }int main () { solve () ; return 0 ;}
H. Path or Coloring
贪心染色，如果可以$k$染色，那么就好了，否则必然存在长度为$k$的简单路径。
#include<cstdio>#include<algorithm>#include<string>#include<iostream>#include<cstdlib>using namespace std;typedef long long ll;const int N=1010;const int M=20010;const int inf=100000000;int Case,n,m,K,i,j,x,y,g[N],v[M],nxt[M],ed,vis[N],col[N],pos;inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x){ pos++; for(int i=g[x];i;i=nxt[i])if(col[v[i]])vis[col[v[i]]]=pos; for(int i=1;;i++)if(vis[i]<pos){ col[x]=i; break; } for(int i=g[x];i;i=nxt[i])if(!col[v[i]])dfs(v[i]);}void solve(){ scanf("%d%d%d",&n,&m,&K); for(ed=0,i=1;i<=n;i++)g[i]=col[i]=0; while(m--)scanf("%d%d",&x,&y),add(x,y),add(y,x); for(i=1;i<=n;i++)if(!col[i])dfs(i); bool flag=0; for(i=1;i<=n;i++)if(col[i]>K){flag=1;break;} if(!flag){ printf("coloring"); for(i=1;i<=n;i++)printf(" %d",col[i]); return; } for(i=1;i<=n;i++)if(col[i]==K+1){x=i;break;} printf("path"); for(i=1;i<=K+1;i++){ printf(" %d",x); for(j=g[x];j;j=nxt[j])if(col[v[j]]==col[x]-1){ x=v[j]; break; } }}int main(){ freopen("pathorcoloring.in","r",stdin); freopen("pathorcoloring.out","w",stdout); scanf("%d",&Case); while(Case--){ solve(); puts(""); }}
I. Double Shuffle
留坑。
J. Timer
按题意模拟。
#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 )#define getid( l , r ) l + r | ( l != r )const int MAXN = 100005 ;char s[12][65] ;char a[12][MAXN] ;char digit[10][8][9] = {{".XXXXX..","XX..XXX.","XX.XXXX.","XXXX.XX.","XXX..XX.","XXX..XX.",".XXXXX..","........",},{"...XX...","..XXX...",".XXXX...","...XX...","...XX...","...XX...",".XXXXXX.","........",},{".XXXXX..","XX...XX.",".....XX.","...XXX..",".XXX....","XX......","XXXXXXX.","........",},{".XXXXX..","XX...XX.",".....XX.","..XXXX..",".....XX.","XX...XX.",".XXXXX..","........",},{"...XXX..","..XXXX..",".XX.XX..","XX..XX..","XXXXXXX.","....XX..","...XXXX.","........",},{"XXXXXXX.","XX......","XXXXXX..",".....XX.",".....XX.","XX...XX.",".XXXXX..","........",},{".XXXXX..","XX...XX.","XX......","XXXXXX..","XX...XX.","XX...XX.",".XXXXX..","........",},{"XXXXXXX.","XX...XX.","X....XX.","....XX..","...XX...","..XX....","..XX....","........",},{".XXXXX..","XX...XX.","XX...XX.",".XXXXX..","XX...XX.","XX...XX.",".XXXXX..","........",},{".XXXXX..","XX...XX.","XX...XX.",".XXXXXX.",".....XX.","XX...XX.",".XXXXX..","........",},} ;void paint ( int x , int v ) { for ( int i = 3 ; i < 10 ; ++ i ) { for ( int j = x ; j < x + 8 ; ++ j ) { a[i][j] = digit[v][i - 3][j - x] ; } }} void mark ( int x ) { a[0][x + 3] = a[0][x + 4] = a[1][x + 3] = a[1][x + 4] = ‘X‘ ;}int check ( int x ) { for ( int i = 0 ; i < 12 ; ++ i ) { for ( int j = 0 ; j < 60 ; ++ j ) { if ( s[i][j] == ‘-‘ ) continue ; if ( s[i][j] != a[i][x + j] ) return 0 ; } } return 1 ;}void solve () { for ( int i = 0 ; i < 12 ; ++ i ) { scanf ( "%s" , s[i] ) ; } int ans = 3470 ; for ( int i = 0 ; ; ++ i ) { if ( check ( i ) ) { printf ( "%02d:%02d\n" , ans / 60 , ans % 60 ) ; return ; } ans -= 5 ; if ( ans < 0 ) ans += 3600 ; }}void show ( int l , int r ) { for ( int i = 0 ; i < 12 ; ++ i ) { for ( int j = l ; j < r ; ++ j ) { printf ( "%c" , a[i][j] ) ; } puts ( "" ) ; }}int main () { clr ( a , ‘.‘ ) ; int x = 0 ; for ( int i = 0 ; i < 50000 ; i += 12 ) { if ( x % 5 == 0 ) { if ( x < 10 ) paint ( i , x ) ; else { paint ( i + 4 , x % 10 ) ; paint ( i - 4 , x / 10 ) ; } } mark ( i ) ; x = ( x - 1 + 60 ) % 60 ; } //show ( 0 , 110 ) ; solve () ; /* for ( int i = 0 ; i < 10 ; ++ i ) { scanf ( "%d" , &n ) ; printf ( "{\n" ) ; for ( int j = 0 ; j < 8 ; ++ j ) { scanf ( "%s" , tmp ) ; printf ( "\"%s\",\n", tmp ); } printf ( "},\n" ) ; } */ return 0 ;}
K. Ultraprime Numbers
答案最多只有$9$项。
#include<cstdio>#include<algorithm>#include<string>#include<iostream>using namespace std;typedef long long ll;const int N=2010;const int inf=100000000;int n,i,j,p[N/10],tot;bool is[N],v[N];int q[1111],ans;inline bool check(int x){ if(!is[x])return 0; static int f[100]; int n=0; while(x)f[++n]=x%10,x/=10; for(int i=n;i;i--){ int t=0; for(int j=i;j;j--){ t=t*10+f[j]; if(!is[t])return 0; } } return 1;}int main(){ freopen("ultraprime.in","r",stdin); freopen("ultraprime.out","w",stdout); //scanf("%d",&n); n=2000; for(i=2;i<=n;i++){ if(!v[i])is[i]=1,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=2;i<=n;i++)if(check(i)){ q[++ans]=i; // printf("%d %d\n",ans,i); if(ans==1000)break; } scanf("%d",&n); if(ans<n)puts("-1");else printf("%d",q[n]); return 0;}/*a[r]-a[l]<=limask max ra[r]<=a[l]+lim*/
XVII Open Cup named after E.V. Pankratiev. GP of SPb
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。