首页 > 其他分享 >2022 China Collegiate Programming Contest (CCPC) Guilin Site（持续更新）

2022 China Collegiate Programming Contest (CCPC) Guilin Site（持续更新）

时间：2023-10-14 20:35:18浏览次数：42  
标签：std now const Contest int Guilin Site include define

Preface

由于还有两周就要滚去打区域赛了，这周开始周末每天都训一场吧

这场总体来说打的还可以，虽然E题这个Easy从卡局卡到3h，但由于其它的题都是一遍过所以罚时还尚可跻进Au区

后面一个小时看徐神和祁神苦战K大分类讨论，虽然场下感觉摸了一个B的做法出来，但感觉实现还是太麻烦了就没写，最后K也是没写出来苦露西

由于明天早上9点要再打场VP，而且今晚在给学校趣味赛出题验题，所以就没补BK这两个题，过段时间有空补上吧

A. Lily

签到题，把两把不是L的位置都变成C即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n; char s[N];
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
	if (s[i]=='.'&&s[i-1]!='L'&&s[i+1]!='L') s[i]='C';
	return printf("%s",s+1),0;
}

B. Code With No Forces

每个人拆成三个来状压，细节好多以后再来写

C. Array Concatenation

首先发现当接上这个序列的转置后，后面两种操作就本质相同了，我们可以直接递推求出贡献

然后把贡献的式子写一写会发现最后其实只有两种情况，即要么一直不转置，要么第一步就转置，取其中较大的那个输出即可

#include<bits/stdc++.h>
#define int int64_t
using namespace std;
const int MOD = 1e9+7;

const int N = 1e5+5;
int n, m, sum[N];

int powe(int x, int p){
	int res=1;
	while (p>0){if (p%2) res=res*x%MOD; p/=2, x=x*x%MOD;}	
	return res;
}

signed main(){
	scanf("%lld%lld", &n, &m);
	for (int i=1; i<=n; ++i){
		int a; scanf("%lld", &a);
		sum[i]=(sum[i-1]+a)%MOD;	
	}
	
	int ans1 = sum[n]*powe(2, m-1)%MOD;
	ans1 = ans1*(n*powe(2, m)%MOD + 1)%MOD;
	
	int ans2=0;
	int len=n, S=sum[n], T=0;
	for (int i=1; i<=n; ++i) T=(T+sum[i])%MOD;
	for (int i=1; i<=m; ++i){
		T = (T*2%MOD + S*len%MOD)%MOD;	
		S = S*2%MOD, len=len*2%MOD;
		//printf("i=%lld T=%lld\n", i, T);
	}
	ans2 = T;
	
	//printf("ans1=%lld ans2=%lld\n", ans1, ans2);
	printf("%lld\n", max(ans1, ans2));
	return 0;	
}

D. Alice's Dolls

好神的多项式，做不了一点

E. Draw a triangle

徐神被这题要折磨疯了，不禁让我想起今年ICPC网络赛第二场的那个K，直接把我们队干爆炸了

把式子写出来会发现最小的可能取值就是\(\gcd(x,y)\)，然后求一组合法解就直接用exgcd跑一下即可

比赛的时候不知道怎么脑抽了一直卡着，但我一直在想别的题也没太管，最后能过就行

#include <bits/stdc++.h>

using llsi = long long signed int;
using ld = long double;
using std::abs;

llsi t, a, b, c, d;

void exgcd(llsi a, llsi b, llsi &x, llsi &y) {
	if(!b) x = 1, y = 0;
	else exgcd(b, a % b, y, x), y -= a / b * x;
}

int main() {
	// freopen("1.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	std::cin >> t;
	while(t--) {
		std::cin >> a >> b >> c >> d;
		if(a == c) { std::cout << a + 1 << ' ' << b << char(10); continue; }
		if(b == d) { std::cout << a << ' ' << b + 1 << char(10); continue; }
		
		const llsi A = b - d, B = c - a, C = a * d - b * c;
		
		llsi x, y;
		exgcd(A, B, x, y);
		// const llsi gab = x * A + y * B;
		// std::cerr << "X = " << x << " Y = " << y << char(10);
		
		std::cout << a + x << ' ' << b + y << char(10);
	}
	return 0;
}

F. Union of Circular Sectors

扇形面积并，巨恶心的计算几何神题，直接给我们队两个几何之神干懵了

G. Group Homework

典中典之换根DP，闪总的最爱

这题首先要手玩发现两条路径要么完全不相交，要么只有一个公共点，否则我们可以交换配对情况来得到一组更大的解

考虑只有一个公共点的情况是很简单的，直接把到每个点的路径中前\(4\)大的找出来即可，当然这里复杂度不卡可以直接大力排序

而另一种情况我们可以枚举在哪条边断开，然后在两边的树中分别找直径即可

但我们换根DP求出来的只有强制经过某个点的最长路，但我们现在要求的是一个子树中的最大值，乍一看很不好处理

但仔细一想，我们可以直接定义状态\(F(x,y)\)表示在\(x\)的子树内（不走\(y\)这个点方向的边），能得到的最长路

不难发现有效的状态其实是\(O(n)\)的，那么直接记搜一下就好了

这里为了方便用了sort和map，实际可以做到完全线性

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,x,y,a[N],ans; vector <int> v[N]; vector <pi> l[N]; map <int,int> f[N];
inline void DFS1(CI now=1,CI fa=0)
{
	for (auto to:v[now]) if (to!=fa)
	DFS1(to,now),l[now].push_back(pi((l[to].empty()?0:l[to][0].fi)+a[to],to));
	sort(l[now].begin(),l[now].end(),greater <pi>());
}
inline void DFS2(CI now=1,CI fa=0,CI out=0)
{
	if (fa) l[now].push_back(pi(out+a[fa],fa)),sort(l[now].begin(),l[now].end(),greater <pi>());
	while (l[now].size()<4) l[now].push_back(pi(0,0));
	for (auto to:v[now]) if (to!=fa) DFS2(to,now,to!=l[now][0].se?l[now][0].fi:l[now][1].fi);
}
inline int F(CI now,CI fa)
{
	if (f[now].count(fa)) return f[now][fa];
	int p1=0; while (l[now][p1].se==fa) ++p1;
	int p2=p1+1; while (l[now][p2].se==fa) ++p2;
	int ret=l[now][p1].fi+l[now][p2].fi+a[now];
	for (auto to:v[now]) if (to!=fa) ret=max(ret,F(to,now));
	return f[now][fa]=ret;
}
int main()
{
	//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (DFS1(),DFS2(),i=1;i<=n;++i) ans=max(ans,l[i][0].fi+l[i][1].fi+l[i][2].fi+l[i][3].fi);
	for (i=1;i<=n;++i) for (auto j:v[i]) ans=max(ans,F(i,j)+F(j,i));
	return printf("%d",ans),0;
}

H. Hysteretic Racing

啥玩意根本没人过

I. Invincible Hotwheels

徐神最爱的字符串，但难度有点大写不了一点

J. Permutation Puzzle

很有意思的一个题，感觉随便rush了一个写法就过了

首先我们可以给所有值不确定的位置\(i\)搞出一个取值区间\([l_i,r_i]\)

\(l_i\)的求解就是正向拓扑排序一遍，每次更新\(u\to v\)的时候就令\(l_v=\max(l_v,l_u+1)\)，\(r_i\)的情况同理，在反图上拓扑排序一遍即可

然后我们考虑现在的问题，给出\(n\)个区间和\(n\)个，要求在每个区间内选一个数，使得所有\([1,n]\)中的每个数都被选了恰好一次

这个问题有个经典的贪心做法，我们从小到大枚举每个数，在所有左端点小于它的区间中，我们找右端点最小的那个区间和它配对，不难发现这样一定是最优的

这道题和上面的问题看似有区别，因为它还附带了一些拓扑关系，在符合上述配对的条件下还要满足大小关系

但仔细一想会发现对于图中\(u\to v\)连接的两点，一定有\(l_u<l_v,r_u< r_v\)，而上面的贪心跑出的结果天然满足拓扑序的性质，因此可以直接上

实现的话用个堆模拟一下即可，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,m,p[N],x,y,deg_G[N],deg_R[N],l[N],r[N],ans[N]; vector <int> G[N],R[N]; vector <pi> o[N];
int main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		scanf("%d",&p[i]),G[i].clear(),R[i].clear(),deg_G[i]=deg_R[i]=0;
		for (i=1;i<=m;++i)
		{
			scanf("%d%d",&x,&y);
			G[x].push_back(y); ++deg_G[y];
			R[y].push_back(x); ++deg_R[x];
		}
		queue <int> q; for (i=1;i<=n;++i) if (p[i]) l[i]=r[i]=p[i]; else l[i]=1,r[i]=n;
		for (i=1;i<=n;++i) if (!deg_G[i]) q.push(i);
		int cnt=0; while (!q.empty())
		{
			int now=q.front(); q.pop(); ++cnt;
			for (auto to:G[now]) if (l[to]=max(l[to],l[now]+1),!--deg_G[to]) q.push(to);
		}
		if (cnt!=n) { puts("-1"); continue; }
		for (i=1;i<=n;++i) if (!deg_R[i]) q.push(i);
		while (!q.empty())
		{
			int now=q.front(); q.pop();
			for (auto to:R[now]) if (r[to]=min(r[to],r[now]-1),!--deg_R[to]) q.push(to);
		}
		bool flag=1; for (i=1;i<=n;++i) if (l[i]>r[i]) flag=0;
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i) o[i].clear();
		for (i=1;i<=n;++i) o[l[i]].push_back(pi(r[i],i));
		priority_queue <pi,vector <pi>,greater <pi>> hp;
		for (i=1;i<=n;++i)
		{
			for (auto [pos,id]:o[i]) hp.push(pi(pos,id));
			if (hp.empty()||hp.top().fi<i) { flag=0; break; }
			ans[hp.top().se]=i; hp.pop();
		}
		if (!flag) { puts("-1"); continue; }
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

K. Barrel Theory

大力分类讨论，感觉我们队比赛时候写的做法挺对的但就是过不去，看了题解又只能怀疑人生，留着过两天补吧

L. Largest Unique Wins

我只能说出题人这个数据范围真是神来一笔，差点把我骗去想什么单纯形法这类的东西了

这题其实想通的话非常简单，直接先拉两个人出来以\(100\%\)的概率选\(m\)，然后再拉两个人出来以\(100\%\)的概率选\(m-1\)，一直往前放下去即可

此时手玩不难发现对于任意一个人都达到了纳什均衡态

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=20;
int n,m,l,c[N],a[N][N];
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),l=m,i=1;i<=n;++i)
	{
		if (l>1&&c[l]==2) --l; ++c[l]; a[i][l]=1; 
	}
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) printf("%.10lf%c",(double)a[i][j]," \n"[j==m]);
	return 0;
}

M. Youth Finale

傻逼题，但是我脑抽了写复杂了

首先求出初始逆序对数，考虑每次shift操作带来的影响，不难发现其实就是看后面的数和\(p_1\)的大小关系

而reverse操作就直接拿\(C_n^2\)减去当前答案即可，然后把原来在前面的shift操作改到后面即可

因此直接拿个deque模拟一下，比赛的时候脑抽了拿树状数组去维护了下后面的数，我的评价是脑子被门夹了

#include<cstdio>
#include<iostream>
#include<deque>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=600005;
int n,m,p[N],ret,all,rev; deque <int> dq; char s[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline int get(RI x,int ret=0)
		{
			for (;x<=n;x+=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x;x-=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}A,B;
signed main()
{
	//freopen("M.in","r",stdin); freopen("M.out","w",stdout);
	RI i; for (scanf("%lld%lld",&n,&m),all=n*(n-1)/2LL,i=1;i<=n;++i)
	scanf("%lld",&p[i]),ret+=A.get(p[i]),A.add(p[i],1),dq.push_back(p[i]);
	for (A.add(p[1],-1),i=1;i<n;++i) B.add(p[i],1);
	for (scanf("%s",s+1),printf("%lld\n",ret),i=1;i<=m;++i)
	{
		if (n==1) { putchar('0'); continue; }
		if (s[i]=='R') rev^=1; else
		{
			if (rev)
			{
				int grt=B.get(dq.back()); ret-=grt; ret+=n-1-grt;
				int ed=dq.back(); dq.pop_back(); int sed=dq.back();
				A.add(ed,-1); B.add(sed,-1); A.add(dq.front(),1); B.add(ed,1); dq.push_front(ed);
			} else
			{
				int grt=A.get(dq.front()); ret-=n-1-grt; ret+=grt;
				int fr=dq.front(); dq.pop_front(); int sfr=dq.front();
				A.add(sfr,-1); B.add(fr,-1); A.add(fr,1); B.add(dq.back(),1); dq.push_back(fr);
			}
		}
		putchar((rev?all-ret:ret)%10+'0');
	}
	return 0;
}

Postscript

唉明天还要早起打比赛，冲冲冲

标签：std,now,const,Contest,int,Guilin,Site,include,define
From： https://www.cnblogs.com/cjjsb/p/17764670.html

相关文章

  • AtCoder Beginner Contest 321 C-321-like Searcher
    可以观察到0-9的所有子集都能恰组成一个满足题目条件的数字，所以共有1022个数{除空集和0}方法就是二元枚举，找出所有数然后排序。#include<iostream>#include<cstdio>#include<vector>#include<algorithm>usingnamespacestd;usingll=longlong;vector<ll>v;sig......
  • CF1439D INOI Final Contests
    先总结一些充要条件。一个人\(i\)选不到自己的\(a_i\)的充要条件为：若为左侧，则存在左侧的一个\(j\)满足\(a_k\in[j,i]\)且\(b_k=R\)的\(k\)的个数\(>i-j\)，右侧同理，满足其一即可。一个方案不合法的充要条件为，若对于一个\(b_i=R\)的\(i\)，\(i\)选位置时\([a_i,n]......
  • 2021 China Collegiate Programming Contest (CCPC) Guilin Site
    A.AHeroNamedMagnus#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<int,int>;usingvi=vector<int>;voidsolve(){intx;cin>>x;cout<<2ll*x-1<<"......
  • AtCoder Regular Contest 166
    Preface上周末因为上课而且这天下午还有CF要打，所以就没现场打这场ARC了这两天事情也特别多导致写题的时间很少，摸了好久总算是补了四个题A-ReplaceCorSwapAB感觉是我做法复杂了，怎么A题码量好大首先我们找到所有\(Y\)中为\(C\)的位置，显然对应的\(X\)中的位置也必须为\(C......
  • 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror
    有五种种类的垃圾，数量分别为\(a_1,a_2,a_3,a_4,a_5\)。第一种为纸质垃圾第二种为塑料垃圾第三种双非垃圾第四种基本纸质垃圾第五种基本塑料垃圾有三种垃圾桶，容量分别为\(c_1,c_2,c_3\)。第一种垃圾桶可以放入：纸质垃圾和基本纸质垃圾第二种垃圾桶可以放入：塑料......
  • Qto_SiteBaseQuantities
    Qto_SiteBaseQuantities场地基准工程量：场地所有引用的定义中通用的基准工程量。  NameTypeDescriptionGrossPerimeterQ_LENGTHUmfangUmfangderGrundstücksgrenze,gemesseninhorizontalerProjektion.GrossPerimeterPerimeterofthesiteboundary,......
  • siteMesh原理
    sitemesh是基于filter过滤器的一个请求到服务器后，如果请求需要sitemesh装饰：1.服务器先解释被请求的资源2.然后根据配置文件获得用于该请求的装饰器3.最后用装饰器装饰被请求资源4.将结果一同返回给客户浏览器......
  • Atcoder Grand Contest 016 E - Poor Turkeys
    先思考这样一个问题：对于一只火鸡\(i\)，我们应该如何判断它最后是否能活下来。如果我们正着判断，我们其实并没有足够的证据表明每一次操作我们应该保留哪只火鸡，也就没法判断最终的答案。但是如果我们倒着考虑，我们发现，如果最后一次操作的两个火鸡都不是\(i\)，那么这次操作选啥对答案......
  • April Fools Day Contest 2021 A. Is it rated - 2
    询问若干个问题，每个问题用一段字符串表示，存在空格。每个问题一行，对于每个回答，只需要输出\(NO\)。view1#include<bits/stdc++.h>chars[1000005];voidsolve(){ while(fgets(s,1000005,stdin)!=NULL){ std::cout<<"NO"<<std::endl;//fgets从流中读取，读取失......
  • 2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) gym 104670
    原题容易想到最短路DAG求出来，起初我以为要求最小割，但这是错误的，因为可能有多条边联通了一个点的情况，这时候选择最小割不一定是最优的我们猜想一个思路：答案一定是包含\(1\)号节点的连通块全部填\(N\)，剩下的填\(S\)。发现在最短路DAG中，\(1\rightarrown\)的所有路径......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99