首页 > 其他分享 >2017 China Collegiate Programming Contest Final (CCPC-Final 2017)

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

时间：2023-10-03 20:56:58浏览次数：60  
标签：CI const Contest int Final 2017 include id define

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

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

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

标签：CI,const,Contest,int,Final,2017,include,id,define
From： https://www.cnblogs.com/cjjsb/p/17741629.html

相关文章

  • AtCoder Beginner Contest 288 Ex A Nameless Counting Problem
    洛谷传送门AtCoder传送门考虑到规定单调不降比较难搞。先设\(g_t\)为长度为\(t\)的满足条件的序列个数（可重且有顺序）。求这个可以设个dp，\(f_{d,i}\)表示考虑到从高到低第\(d\)位，当前\(t\)个数中有\(i\)个仍然顶上界，并且之前的位都满足异或分别等于\(X\)的限制。......
  • P3956 [NOIP2017 普及组] 棋盘
    传送门P3956[NOIP2017普及组]棋盘不清楚曾师为什么把这个神奇的题目放在搜索\(search\)专栏，反正我用\(dijkstra\)水过去了，虽然\(dijkstra\)严格来说也是一种能够解决一般性最短路问题的算法。然后考虑这道题的建图。这道题来看首先是去除魔法的部分，一般地，任意一个点只......
  • Final Cut Pro最新中文版下载-FCPX软件下载 安装包下载方式
    FinalCutProX 是mac客户端最专业的视频剪辑软件，拥有最完善的视频处理功能，可以编辑不同分辨率的视频，搭配本站的FCPX插件使用效果更佳。新版的FinalCutProXforMac新增模糊、光晕等360°效果让后期制作的速度得以提升，帮助用户创作出令人赞叹的作品。本站提供 Final......
  • fcpx视频剪辑工具：Final Cut Pro for Mac下载 安装包下载
    FinalCutPro是一款专业级的视频编辑软件，为用户提供了强大的编辑工具和功能，广泛应用于电影、电视和广告制作等领域。作为苹果公司开发的软件，FinalCutPro在Mac平台上运行，并为专业编辑人员提供了一流的视频编辑体验。软件地址：看置顶贴FinalCutProXMac新增功能ProRes输出快5......
  • AtCoder Grand Contest 056 D Subset Sum Game
    洛谷传送门AtCoder传送门考虑若\(n\)是奇数怎么做。枚举Alice第一次选的数\(a_i\)，然后考虑把剩下的数两两结成一个匹配，若Bob选了其中一个，Alice就选另一个。容易发现排序后奇数位和它右边的偶数位匹配最优。那么设奇数位的和为\(A\)，偶数位的和为\(B\)，此时Alice获胜......
  • AtCoder Beginner Contest 178 E
    AtCoderBeginnerContest178EE-DistMax曼哈顿距离最大点对\(ans=max(|x_i-x_j|+|y_i-y_j|)\)考虑去绝对值，4种情况。sort一下取max即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+10;intx[N],y[N];intp[4][N];......
  • 2022 China Collegiate Programming Contest (CCPC) Weihai Site
    PrefaceVP到自己学校出的题了可海星，不得不说学长们出的题比起昨天VP的CCPC2022广州做起来要舒服地多这场前面写题都很顺基本都是一发过，中期的medium也没怎么卡思路和卡机子，一道一道地慢慢出最后一个小时徐神RushF可惜没Rush出来，然后我和祁神坐在下面把B的做法给搞出来了，但不知......
  • The 2022 ICPC Asia Shenyang Regional Contest
    C.ClampedSequence因为\(n\)的范围不大，并且可以猜到\(l,r\)中应该至少有一个在\(a_i，a_i-1,a_i+1\)上。所以直接暴力枚举\(l\)或\(r\)然后暴力的计算一下#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;int32_tmain(){......
  • AtCoder Beginner Contest 322
    A-FirstABC2解题思路签到Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;voidsolve(){ intn; cin>>n; strings; cin>>s; intp=s.find("ABC"); if(p==-1)cout<<p<<'\n&......
  • 2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite
    Preface好难啊这场广州站，不愧是5题金4题铜的超恶劣站，中档题普遍难度较高但我感觉主要原因还是题目出的太偏向于DP了，AI是本质差不多的树上换根DP，M又是个数位DP，导致像我这种不擅长DP的人直接中期坐牢但好在祁神大力切出了medium~hard的K题，然后最后一小时我把一直在想的A题丢给徐......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99