首页 > 其他分享 >Educational Codeforces Round 163 (Rated for Div. 2)

Educational Codeforces Round 163 (Rated for Div. 2)

时间：2024-03-21 14:55:51浏览次数：22  
标签：Educational Rated const int typedef long Codeforces include define

Preface

这周很奇怪，连着计网、数据库、组合数学的课都莫名其妙不上了，突然变得很空闲了的说

正好有空赶紧补补题，不然接下来有很多造题/比赛的任务搁置着就忘记了

A. Special Characters

签到，\(n\)是偶数才有解，构造的话注意到一个AAB可以产生\(2\)的贡献，把\(\frac{n}{2}\)个AAB拼起来即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d",&n),n%2) { puts("NO"); continue; }
		puts("YES"); for (RI i=1;i<=n/2;++i) printf("AAB"); putchar('\n');
	}
	return 0;
}

B. Array Fix

从前往后贪心，能分裂就尽量分裂

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=55;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=1; int pre=0; for (i=1;i<=n;++i)
		{
			if (a[i]<pre) { flag=0; break; }
			if (a[i]>9&&a[i]/10<=a[i]%10&&pre<=a[i]/10)	pre=a[i]%10; else pre=a[i];
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

C. Arrow Path

直接在上面跑个BFS看看哪些点能走到即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int t,n,vis[2][N]; char s[2][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) vis[0][i]=vis[1][i]=0;
		scanf("%s%s",s[0]+1,s[1]+1); vis[0][1]=1;
		queue <pi> q; q.push({0,1});
		while (!q.empty())
		{
			auto [x,y]=q.front(); q.pop();
			for (i=0;i<4;++i)
			{
				int nx=x+dx[i],ny=y+dy[i];
				if (nx<0||nx>1||ny<1||ny>n) continue;
				if (s[nx][ny]=='<') --ny; else ++ny;
				if (!vis[nx][ny]) vis[nx][ny]=1,q.push({nx,ny});
			}
		}
		puts(vis[1][n]?"YES":"NO");
	}
	return 0;
}

D. Tandem Repeats?

首先枚举答案的一半长度\(len\)，如果位置\(i\)上的字符可以与位置\(i+len\)上的字符匹配，则我们令位置\(i\)的权值为\(1\)；否则为\(0\)

不难发现此时要有长度为\(2\times len\)的答案串，当且仅当存在长度为\(len\)的连续一段权值为\(1\)的区间，然后就可以\(O(n^2)\)做完这道题了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005;
int t,n; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI len,i; scanf("%s",s+1); n=strlen(s+1);
		for (len=n/2;len>=0;--len)
		{
			int cur=0,mx=0;
			auto cmp=[&](const char& a,const char& b)
			{
		    	return a==b||a=='?'||b=='?';
			};
			for (i=1;i+len<=n;++i)
			if (cmp(s[i],s[i+len])) ++cur; else mx=max(mx,cur),cur=0;
			mx=max(mx,cur);
			if (mx>=len) { printf("%d\n",len*2); break; }
		}
	}
	return 0;
}

E. Clique Partition

一眼构造题

稍微手玩一下会发现，对于固定的某个\(k\)，它最多只能bound住大小为\(k\)的Clique

而构造方法也很简单，假设当前存在编号为\(1\sim n\)的Clique需要被bound在一起

且我们存在以下构造方式：先设\(a_i=i\)，令\(m=\lfloor\frac{1+n}{2}\rfloor\)，然后翻转区间\([1,m],[m+1,n]\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=45;
int t,n,k,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) a[i]=i;
		for (i=1;i<=n;i+=k)
		{
			int l=i,r=min(i+k-1,n),mid=l+r>>1;
			reverse(a+i,a+mid+1); reverse(a+mid+1,a+r+1);
		}
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
		for (printf("%d\n",(n+k-1)/k),i=1;i<=n;++i)
		printf("%d%c",(i-1)/k+1," \n"[i==n]);
	}
	return 0;
}

F. Rare Coins

唉又是TM的组合数化简，感觉我的组合数学课再上一次课就能讲到这些组合恒等式了（然而这周课没了）

首先假设区间内有\(g_1\)枚金币，\(s_1\)枚银币；区间外有\(g_2\)枚金币，\(s_2\)​枚银币

不妨假设区间内有\(a\)枚银币变成\(1\)，区间外有\(b\)枚银币变成\(0\)（这样定义的好处是防止下标出负数）

则需要满足\(g_1+a>g_2+(s_2-b)\)，即\(a+b\ge g_2+s_2-g_1+1\)，令\(M=g_2+s_2-g_1+1\)

因此答案的表达式就很简单了：\(\frac{1}{2^{s_1+s_2}}\times \sum_{a+b\ge M} C_{s_1}^a\times C_{s_2}^b\)，然后又遇到经典的组合数相乘了

根据范德蒙德卷积，上面的式子等价于\(\frac{1}{2^{s_1+s_2}}\times \sum_{x\ge M} C_{s_1+s_2}^x\)，因此给\(C_{s_1+s_2}^x\)预处理一个后缀和即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5,mod=998244353;
int n,q,m,pfx[2][N],fact[N],ifac[N],g[N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&q),j=0;j<2;++j)
	for (i=1;i<=n;++i) scanf("%d",&pfx[j][i]),pfx[j][i]+=pfx[j][i-1];
	for (init(m=pfx[1][n]),i=0;i<=m;++i) g[i]=C(m,i);
	for (i=m-1;i>=0;--i) (g[i]+=g[i+1])%=mod;
	int prob=quick_pow(quick_pow(2,m));
	for (i=1;i<=q;++i)
	{
		int l,r; scanf("%d%d",&l,&r);
		int g1=pfx[0][r]-pfx[0][l-1],g2=pfx[0][n]-g1;
		int s1=pfx[1][r]-pfx[1][l-1],s2=pfx[1][n]-s1;
		printf("%d ",1LL*prob*g[min(m+1,max(0,g2+s2-g1+1))]%mod);
	}
	return 0;
}

G. MST with Matching

刚开始没看数据范围以为是个什么玄学奇妙题，后面发现妈的\(n\le 20\)

提到匹配会想到什么，对于二分图来说，匹配和点覆盖是等价的，而巧了树也是一种二分图（没有环当然没有奇环咯）

因此不妨直接\(2^n\)大力枚举生成树的一个点覆盖，根据规约方式我们知道，此时能用的边只有那些两端有至少一个在点覆盖解集里的

然后再对合法的边跑一个MST即可，注意用克鲁斯卡尔实现的话要注意常数，先在外面把边排序好不然可能会T

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=25;
int n,c,w[N][N],fa[N],ans=1e9;
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	vector <array<int,3>> edges;
	RI i,j; for (scanf("%d%d",&n,&c),i=0;i<n;++i)
	for (j=0;j<n;++j) scanf("%d",&w[i][j]);
	for (i=0;i<n;++i) for (j=i+1;j<n;++j)
	if (w[i][j]) edges.push_back({w[i][j],i,j});
	sort(edges.begin(),edges.end());
	for (RI mask=0;mask<(1<<n);++mask)
	{
		for (i=0;i<n;++i) fa[i]=i; int cs=0,val=0;
		for (auto [w,x,y]:edges)
		{
			if (cs==n-1) break;
			if (!(((mask>>x)&1)||((mask>>y)&1))) continue;
			if (getfa(x)!=getfa(y)) fa[getfa(x)]=getfa(y),++cs,val+=w;
		}
		if (cs==n-1) ans=min(ans,val+c*__builtin_popcount(mask));
	}
	return printf("%d",ans),0;
}

Postscript

你说的对但是今天云顶S11更新了，牢闪不得不回归云顶一段时间力

标签：Educational,Rated,const,int,typedef,long,Codeforces,include,define
From： https://www.cnblogs.com/cjjsb/p/18087382

相关文章

  • Tree Compass Codeforces Round 934 (Div. 2) 1944E
    Problem-E-Codeforces题目大意：有一棵n个点的树，初始状态下所有点都是白色的，每次操作可以选择一个点u和一个距离dis，使得距离点u所有长度为dis的点变为黑色，问最少需要多少次操作能使所有点变成黑色，输出所有操作1<=n<=2000思路：要想操作数最少，就要使每次操作涂黑的点的数量尽......
  • Codeforces Round 935 (Div. 3) A-G
    A传送门  先考虑无解情况，外在人的数量如果%3之后还剩下x人，只能靠第三类综合性人y来补充进去，如果x+y小于3则无解，有解只需要向上取整即可。#include<bits/stdc++.h>usingll=longlong;typedefstd::pair<int,int>PII;typedefstd::array<int,4>ay;constintN=......
  • CodeForces 1945H GCD is Greater
    洛谷传送门CF传送门感觉是这场唯一比较有趣的题？首先明确一点：先手只会选\(2\)个数，因为数多了\(\gcd\)会变小，而且对方的\(\text{and}\)会变大。所以对于某一位，若\(0\)的个数\(\ge3\)那么对方的按位与这一位一定是\(0\)。所以若\(0\)的个数\(\le2\)，那么可能会......
  • Codeforces Round 923 (Div. 3) D. Find the Different Ones!
    写点简单的思维题https://codeforces.com/problemset/problem/1927/D思路：用两个数组，一个存储原始数据，一个用nex存该位置第一次不一样的下标#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<str......
  • 1948.Educational Codeforces Round 163 - sol
    202403补题效率低下。场上发挥并不是很好，A~E都是简单的，而场上没有去推F的式子，只是找了找规律，然后发现是一个不可做的东西就下播了。如果直接推式子就会很快地做出来，还是非常可惜。A.SpecialCharactersYouaregivenaninteger\(n\).Yourtaskistobuildast......
  • Codeforces Round 920 (Div. 3)-----＞E. Eat the Chip
    一，思路：1.这是一道博弈论的题目（两个人都绝顶聪明，所以每个人都会按最优方案进行）。这题你会发现，两个人从一开始就已经确定了结局。2.如假如他们俩的棋子在竖直方向上距离相差的值是偶数，那么一定就两个结果Alice赢或者平局，反之奇数则是Bob赢或者平局（仔细分析一下就能得知）。3.所......
  • Codeforces Round 918 (Div. 4)-----＞E. Romantic Glasses
    一，思路：这题是一道前缀和的扩展题。题目要我们求是否有一个区间内的奇偶之和是否相等，我们可以对数组重新赋值，奇数位赋值为负数，偶数位不变。这样我们后面求前缀和，只要看有没有一段区间和为零的。二，代码：#include<iostream>#include<cstring>#include<algorithm>#include<vec......
  • CodeForces 1943D2 Counting Is Fun (Hard Version)
    洛谷传送门CF传送门被自己的赛时智障操作气笑了。谁告诉你容斥钦定了几个要记到状态里面的。。。/tuu显然先找“好数组”的充要条件。对原数组\(a\)差分，设\(b_i=a_i-a_{i-1}\)。那么一次可以选择一对\((i,j)\)满足\(i\lej-2\)，然后给\(b_i\)减\(1\)，给\(b_......
  • Codeforces Round 933 G. Rudolf and Subway
    原题链接：Problem-G-Codeforces思路：根据题意可知相同颜色的边一定是联通的，那么就可以设置虚点，例如1-2，2-3，3-4边的颜色都是相同的，那么就可以设置一个特殊的点例如设置为10，那么这三条边就可以改成1-10，10-2，2-10，10-3，3-10，10-4，从点到虚点需要1的代价，但是从虚点到其他点不需要代价，......
  • CodeForces 1943C Tree Compass
    洛谷传送门CF传送门发现对于一条链，一次操作最多能染黑这条链上的\(2\)个点。所以我们把直径拎出来，设直径长度为\(d\)。考虑一条长度为\(d\)的链至少要多少次能全染黑。若\(d\)为奇数，显然从直径中点\(u\)开始做\((u,0),(u,1),\ldots,(u,\frac{d-1}{2})\)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99