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]<=lim
ask max r
a[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]<=lim
ask max r
a[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]<=lim
ask max r
a[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]<=lim
ask max r
a[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]<=lim
ask max r
a[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]<=lim
ask max r
a[r]<=a[l]+lim
*/