526互联

2017 China Collegiate Programming Contest Final (CCPC-Final 2017)

发布时间 2023-10-03 20:48:15作者: 空気力学の詩

Preface

今天打学校统一要求的这场CCPC2017Final，直接被打爆了，各种数学题搞得人生活不能自理

主要是H徐神开场就秒出了正确的思路，然后一心认准高斯消元然后一直想+写+调到结束都没卡过去

比赛最后20min的时候祁神想到了更好写的基于施密特正交化的方法，可以碍于时间有限没调出来

不过由于这场前面的题都过的挺快的，而且写挂的也挺少，因此罚时还比较可观

不过yysy每次大家一起打比赛的时候可以尽享其他队的成果，今天偷听旁边银牌爷队的做法爽飞了

A. Dogs and Cages

签到，每只狗的错排概率是\(\frac{n-1}{n}\)，因此总答案就是\(n-1\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i; for (scanf("%d",&t),i=1;i<=t;++i)
	scanf("%d",&n),printf("Case #%d: %.10lf\n",i,(double)(n-1));
	return 0;
}

B. Same Digit

防AK题，正解好像是个搜索+打表，评价是完全没时间看题

C. Rich Game

本来尝试单独签到的结果失败了，后面和祁神一讲题意马上补了两个漏洞改过了

首先不难发现把要输的场次都放在前面，先赚取最多的钱，然后后面在考虑打赢

但是要注意到当\(X>Y\)时显然有全胜的策略，即通过不停地和对手轮流打平来把钱刷到无限多，然后接下来直接全胜即可

排除掉这种情况后我们发现如果要输就0：11输的干脆点，否则要赢的话就赢11：9，并且先输9场

最后枚举胜利的场数可以\(O(1)\)判断答案，如果数据范围的\(k\)更大的话也可以二分答案求解

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int t,id,x,y,k;
signed main()
{
	//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
	for (scanf("%lld",&t),id=1;id<=t;++id)
	{
		RI i; scanf("%lld%lld%lld",&x,&y,&k);
		if (x>y) { printf("Case #%lld: %lld\n",id,k); continue; }
		int lose=11LL*x,win=11LL*y-9LL*x,ans=0;
		for (i=1;i<=k;++i) if (lose*(k-i)-win*(i-1)+9LL*x>=11LL*y) ans=i;
		printf("Case #%lld: %lld\n",id,ans);
	}
	return 0;
}

D. Mr. Panda and Circles

好劲的数数题，完全不会，被银牌爷薄纱了

E. Evil Forest

纯签到题

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,id,n,a[N];
int main()
{
	//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
	for (scanf("%d",&t),id=1;id<=t;++id)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ans=0; for (i=1;i<=n;++i) ans+=a[i]+(a[i]+9)/10;
		printf("Case #%d: %d\n",id,ans);
	}
	return 0;
}

F. Fair Lottery

比赛的时候听到了过的队讲的单纯形法，但铸币闪总已经把这个全部忘光光了

这题的做法其实很trivial，因为\(n\)的范围很小因此可以直接爆枚\(2^n\)种情况，如果这个子集合法的话就尝试给它赋值一个概率

考虑到这题的约束是对于所有种族的获胜概率相同，那么我们可以将其转化成第\(2,3,\cdots,n\)个种族获胜的概率和第一个种族相同，然后再把等号放缩成两个不等号

同时还有一个约束就是所有状态的概率之和\(\le 1\)，而最后我们的目标函数就是最大化第一个种族获胜的概率，直接上单纯形法即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
const int N=10;
int t,id,n,m,a[N],rst[(1<<N)+5];
namespace LP
{
	const double EPS=1e-10;
	inline int sgn(const double& x)
	{
		if (fabs(x)<EPS) return 0; return x<0?-1:1;
	}
	inline void pivot(vector <vector <double>>& A,int l,int e,vector <int> id)
	{
		int m=A.size(),n=A[0].size(); double tmp=-1.0/A[l][e]; A[l][e]=-1;
		RI i,j; for (auto& x:A[l]) x*=tmp;
		for (i=0;i<m;++i) if (i!=l)
		{
			tmp=A[i][e]; A[i][e]=0;
			for (j=0;j<n;++j) A[i][j]+=tmp*A[l][j];
		}
		swap(id[e],id[l+n-1]);
	}
	inline int simplex(vector <vector <double>> A,vector <double> b,vector <double> c,vector <double>& res)
	{
		RI i,j; int m=A.size(),n=A[0].size(); vector <int> id(n+m);
		for (i=0;i<n+m;++i) id[i]=i;
		vector <vector <double>> T(m+1,vector <double>(n+1));
		for (i=0;i<m;++i) for (j=0;j<n;++j) T[i][j]=-A[i][j];
		for (i=0;i<m;++i) T[i][n]=b[i];
		for (j=0;j<n;++j) T[m][j]=c[j];
		for (;;)
		{
			int e=0; for (i=1;i<n;++i) if (T[m][i]>T[m][e]) e=i;
			if (sgn(T[m][e])<=0) break;
			int l=-1; double tmp=-1;
			for (i=0;i<m;++i) if (sgn(T[i][e])<0)
			{
				double x=-T[i][n]/T[i][e];
				if (l==-1||sgn(x-tmp)<0||sgn(x-tmp)==0&&id[i]>id[l]) tmp=x,l=i;
			}
			if (l==-1) return -1;
			pivot(T,l,e,id);
		}
		res=vector <double>(n+1); res[n]=T[m][n];
		for (i=0;i<m;++i) if (id[n+i]<n) res[id[n+i]]=T[i][n];
		return 0;
	}
};
int main()
{
	//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
	for (scanf("%d",&t),id=1;id<=t;++id)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=0;i<n;++i) scanf("%d",&a[i]);
		int cnt=0; for (i=1;i<(1<<n);++i)
		{
			int sz=0; for (j=0;j<n;++j) if ((i>>j)&1) sz+=a[j];
			if (sz<=m) rst[i]=cnt++; else rst[i]=-1;
		}
		vector <vector <double>> A; vector <double> b,c(cnt);
		for (i=1;i<n;++i)
		{
			vector <double> t1(cnt,0),t2(cnt,0);
			for (j=1;j<(1<<n);++j) if (~rst[j])
			{
				if ((j>>i)&1) t1[rst[j]]+=1.0,t2[rst[j]]-=1.0;
				if (j&1) t1[rst[j]]-=1.0,t2[rst[j]]+=1.0;
			}
			A.push_back(t1); b.push_back(0);
			A.push_back(t2); b.push_back(0);
		}
		A.push_back(vector <double>(cnt,1.0)); b.push_back(1.0);
		for (j=1;j<(1<<n);++j) if (~rst[j]) c[rst[j]]=j&1;
		vector <double> res; LP::simplex(A,b,c,res);
		printf("Case #%d: %.10lf\n",id,res.back());
	}
	return 0;
}

G. Alice’s Stamps

很经典的题了，可能是因为这场比赛比较久远了所以感觉这道题之前都做过来着

考虑DP，设\(f_{i,j}\)表示从左到右考虑到第\(i\)个位置，且钦定\([i,n]\)均未覆盖，用了\(k\)个区间的最大覆盖位置数

转移的话很trivial，如果选择不覆盖\(i\)就转移\(f_{i,j}\to f_{i+1,j}\)

否则肯定贪心地找一个能覆盖\(i\)且最远的区间，设所有能覆盖\(i\)的区间中最远的右端点为\(rpos_i\)，则转移\(f_{i,j}+rpos_i-i+1\to f_{rpos_i+1,j+1}\)

复杂度\(O(nm)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
int t,id,n,m,k,l,r,rpos[N],f[N][N];
int main()
{
	//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	for (scanf("%d",&t),id=1;id<=t;++id)
	{
		RI i,j; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=n;++i) rpos[i]=0;
		for (i=1;i<=m;++i) for (scanf("%d%d",&l,&r),j=l;j<=r;++j) rpos[j]=max(rpos[j],r);
		for (i=0;i<=n+1;++i) for (j=0;j<=k;++j) f[i][j]=0;
		int ans=0; for (i=1;i<=n;++i) for (j=0;j<=k;++j)
		{
			ans=max(ans,f[i][j]); f[i+1][j]=max(f[i+1][j],f[i][j]);
			f[rpos[i]+1][j+1]=max(f[rpos[i]+1][j+1],f[i][j]+rpos[i]-i+1);
		}
		for (j=0;j<=k;++j) ans=max(ans,f[n+1][j]);
		printf("Case #%d: %d\n",id,ans);
	}
	return 0;
}

H. Equidistance

ORZ徐神、祁神，线代废物表示这题完全做不来的说

考虑增量法每次添加一个点，很容易发现添加的点与添加点之前的重心的连线与之前添加的点所构成的子空间正交，同时添加点后重心移动的距离也很好求

因此本题的难点在于如何将\(n\)维空间中的一组正交基扩展到满秩，刚开始徐神想的是用高斯消元，通过保留上一步消元得到的行阶梯形矩阵来优化复杂度，后面还是一直T

但最后祁神发现这个东西其实就是施密特正交化那一套流程，赛后写出了代码复杂度和常数都更优秀的做法，我只能ORZ

单组数据复杂度\(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;
#define LD long double

const int N = 105;
const LD eps = 1e-10;
int t, n, m;

int sgn(LD x){return fabs(x)<eps ? 0 : (x>eps ? 1 : -1);}
struct Pt{
	LD x[N];
	Pt operator*(LD b)const{
		Pt tmp;
		for (int i=0; i<n; ++i) tmp.x[i] = x[i]*b;
		return tmp;
	}
	Pt operator-(Pt b)const{
		Pt tmp;
		for (int i=0; i<n; ++i) tmp.x[i] = x[i]-b.x[i];
		return tmp;
	}
	Pt operator+(Pt b)const{
		Pt tmp;
		for (int i=0; i<n; ++i) tmp.x[i] = x[i]+b.x[i];
		return tmp;
	}
	LD dot(Pt b)const{
		LD res=0.0L;
		for (int i=0; i<n; ++i) res+=x[i]*b.x[i];
		return res;
	}
};

vector<Pt> pt, v;
bool vis[N*2];
LD R[N];

void calc(vector<Pt> &vec){
	int sz=vec.size();
	for (int i=0; i<sz; ++i) vis[i]=false;
	for (int i=1; i<sz; ++i){
		for (int j=0; j<i; ++j)if (!vis[j]){
			vec[i] = vec[i]-vec[j]*(vec[i].dot(vec[j])/vec[j].dot(vec[j]));
		}
		bool zero=true;
		for (int j=0; j<n; ++j){
			if (sgn(vec[i].x[j])!=0){zero=false; break;}
		}
		if (zero) vis[i]=true;
	}
	
	int cur=1;
	for (int i=1; i<sz; ++i){
		if (!vis[i]) vec[cur++] = vec[i]*(1.0L/sqrtl(vec[i].dot(vec[i])));	
	}
	vec.erase(vec.begin()+cur, vec.end());
//	printf("sz=%d vec:\n", vec.size());
//	for (auto p : vec){
//		for (int i=0; i<n; ++i) printf("%.3Lf ", p.x[i]); puts("");	
//	}
}

int main(){
	R[1]=0.5L;
	for (int i=2; i<N; ++i) R[i] = 0.5L/(sqrtl(1-R[i-1]*R[i-1]));
//	printf("R:"); for (int i=1; i<5; ++i) printf("%.4Lf ", R[i]); puts("");
	
	scanf("%d", &t);
	for (int cas=1; cas<=t; ++cas){
		scanf("%d%d\n", &n, &m);
		pt.clear(); v.clear();
		pt.resize(m);
		for (int i=0; i<m; ++i){
			for (int j=0; j<n; ++j) scanf("%Lf", &pt[i].x[j]);
		}
		
		for (int i=1; i<m; ++i) v.push_back(pt[i]-pt[0]);
		for (int i=0; i<n; ++i){
			Pt tmp;
			for (int j=0; j<n; ++j) tmp.x[j]=0;
			tmp.x[i]=1;
			v.push_back(tmp);
		}
		calc(v);
		
		Pt cir;
		for (int i=0; i<n; ++i) cir.x[i]=0.0L;
		for (int i=0; i<n; ++i){
			for (int j=0; j<m; ++j) cir.x[i]+=pt[j].x[i];
			cir.x[i] /= m;
		}
		
//		printf("cir:"); for (int j=0; j<n; ++j) printf("%.3Lf ", cir.x[j]); puts("");
		for (int i=m-1; i<n; ++i){
			pt.push_back(cir+v[i]*sqrtl(1-R[i]*R[i]));
			cir = cir+v[i]*(sqrtl(0.25L/(1-R[i]*R[i])-R[i]*R[i]));
//			printf("cir:"); for (int j=0; j<n; ++j) printf("%.3Lf ", cir.x[j]); puts("");
		}
		
		printf("Case #%d: %d\n", cas, n+1-m);
		for (int i=m; i<=n; ++i){
			for (int j=0; j<n; ++j) printf("%.10Lf%c", pt[i].x[j], char(j==n-1 ? '\n' : ' '));
		}
	}
	return 0;	
}

I. Inkopolis

本来一眼感觉不可做的，后面发现大家都会做仔细一想发现是个傻逼题

首先考虑树的情况怎么做，首先可以发现对于某个点，如果它连接的边中同色的边有\(k\)条的话，最后可以使得连通块数量减去\(k-1\)

那么再转化一步就可以得到另外一个好统计的式子，不妨设点\(i\)连接的边中的颜色数为\(f_i\)，则最后的答案就是\(\sum f_i-(n-1)\)

那么对于基环树的情况手玩一下会发现其实就是\(\sum f_i-n\)，只不过存在一种特殊情况就是当环上的所有边颜色相同时，最后的答案需要加一，注意特判这条即可

实现的时候直接暴力开个map，复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,id,n,m,x,y,c,all,cyc,pre[N],bkt[N]; bool flag;
vector <int> v[N]; map <int,int> f[N]; map <pi,int> col; set <pi> on_cyc;
inline void DFS(CI now=1,CI lst=0)
{
	if (flag) return;
	for (auto to:v[now]) if (to!=lst)
	{
		if (flag) return;
		if (!pre[to]) pre[to]=now,DFS(to,now); else
		{
			for (int x=now;x!=to;x=pre[x])
			on_cyc.insert(pi(min(x,pre[x]),max(x,pre[x])));
			on_cyc.insert(pi(min(now,to),max(now,to)));
			return (void)(flag=1);
		}
	}
}
inline void add(CI x,CI y)
{
	if (++f[x][y]==1) ++all;
}
inline void del(CI x,CI y)
{
	if (--f[x][y]==0) --all;
}
inline void add_cyc(CI c)
{
	if (++bkt[c]==1) ++cyc;
}
inline void del_cyc(CI c)
{
	if (--bkt[c]==0) --cyc;
}
int main()
{
	//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
	for (scanf("%d",&t),id=1;id<=t;++id)
	{
		printf("Case #%d:\n",id);
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) bkt[i]=0,v[i].clear(),f[i].clear();
		for (on_cyc.clear(),col.clear(),all=cyc=0,i=1;i<=n;++i)
		{
			scanf("%d%d%d",&x,&y,&c); v[x].push_back(y); v[y].push_back(x);
			col[pi(min(x,y),max(x,y))]=c; add(x,c); add(y,c);
		}
		for (i=1;i<=n;++i) pre[i]=0; flag=0; DFS();
		//for (auto [x,y]:on_cyc) printf("(%d,%d)\n",x,y);
		for (auto it:on_cyc) add_cyc(col[it]);
		for (i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x,&y,&c); if (x>y) swap(x,y);
			del(x,col[pi(x,y)]); del(y,col[pi(x,y)]);
			if (on_cyc.count(pi(x,y))) del_cyc(col[pi(x,y)]);
			col[pi(x,y)]=c;	add(x,c); add(y,c);
			if (on_cyc.count(pi(x,y))) add_cyc(c);
			printf("%d\n",all-n+(cyc==1));
		}
	}
	return 0;
}

J. Subway Chasing

这题题目还没看的时候就被边数的银牌爷队剧透了差分约束的做法了，遂不得不滚去看

模型啥的都很自然想到，不妨设\(s_i\)表示从起点到第\(i\)站所需的时间，最后的答案就是\(s_{i+1}-s_i\)

考虑对于每组约束条件，根据\(A,B/C,D\)的等于/不等于情况可以讨论出连边，但后面写完发现原来可以统一起来

最后再加上\(s_{i+1}-s_i\ge 1\)的限制即可，然后跑个最长路的SPFA就能得到答案了

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=2005;
int t,id,n,m,x,A,B,C,D,s[N],c[N],vis[N]; vector <pi> v[N];
inline void addedge(CI x,CI y,CI z)
{
	//printf("%d -> %d (%d)\n",x,y,z);
	v[x].push_back(pi(y,z));
}
signed main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	for (scanf("%lld",&t),id=1;id<=t;++id)
	{
		RI i; for (scanf("%lld%lld%lld",&n,&m,&x),i=0;i<=n;++i) s[i]=vis[i]=c[i]=0,v[i].clear();
		for (i=1;i<=m;++i)
		{
			scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
			/*if (A==B&&C==D) addedge(A,C,x),addedge(C,A,-x);
			if (A==B&&C!=D) addedge(A,D,x+1),addedge(C,A,-(x-1));
			if (A!=B&&C==D) addedge(A,C,x+1),addedge(C,B,-(x-1));
			if (A!=B&&C!=D) addedge(B,C,x+1),addedge(D,A,-(x-1));*/
			addedge(A,D,x+(A!=B||C!=D)); addedge(C,B,-(x-(A!=B||C!=D)));
		}
		for (i=0;i<n;++i) addedge(i,i+1,1);
		queue <int> q; q.push(0); vis[0]=1;
		bool flag=1; while (!q.empty())
		{
			int now=q.front(); q.pop(); vis[now]=0;
			if (++c[now]>n) { flag=0; break; }
			for (auto [to,w]:v[now]) if (s[to]<s[now]+w)
			{
				s[to]=s[now]+w;
				if (!vis[to]) vis[to]=1,q.push(to);
			}
		}
		if (!flag) { printf("Case #%lld: IMPOSSIBLE\n",id); continue; }
		for (printf("Case #%lld: ",id),i=1;i<n;++i) printf("%lld%c",s[i+1]-s[i]," \n"[i==n-1]);
	}
	return 0;
}

K. Knightmare

这题上来讨论一波无果后我提议既然空机了那就打表找规律吧

然后序列输出来后徐神就说让我顺便把一阶差分和二阶差分输一下，我一写好家伙当\(n\ge 6\)时二阶差分全是\(28\)

那么说明最后的答案一定是关于\(n\)的二次多项式，然后把\(n=6,7,8\)的情况扔给徐神人力算出系数后得到通项公式为\(14n^2-6n+5\)

注意最后答案会爆long long，因此记得开__int128

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int ans[6]={1,9,41,109,205,325};
int t,id,n;
//14*i*i-6*i+5
inline void print(__int128 x)
{
	if (x>9) print(x/10); putchar(x%10+'0');
}
int main()
{
	//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
	for (scanf("%d",&t),id=1;id<=t;++id)
	{
		if (scanf("%d",&n),n<=5) printf("Case #%d: %d\n",id,ans[n]);
		else printf("Case #%d: ",id),print(__int128(14)*n*n-6LL*n+5LL),putchar('\n');
	}
	return 0;
}

Postscript

这场感觉偏数学的成分好多，不过总体难度好像并不大，可能因为是老题的缘故了吧，很多当时很新的科技放在今天都成套路了

所以为什么我比赛的时候还是不会单纯形法啊，苦露西