首页 > 其他分享 >Codeforces Round 896 (Div. 1)

Codeforces Round 896 (Div. 1)

时间：2023-09-11 20:11:37浏览次数：38  
标签：typedef 896 int Codeforces long Div include c1 define

Preface

不管怎么说，最后还是被我苟上橙名了（虽然刚好2100整，不多不少）

感觉我在1900~2100之间卡了好久好久，反观我的队友都是打上紫名后随便两三场就打上橙了，狠狠地羞辱我这个铁混子

由于暑假集训打的校内排名比较高，作为新队伍也拿到了今年的一场CCPC+一场ICPC的名额，虽然要自费出行但还是让人很期待的说

这场其实也没啥亮点，就中规中矩地把A~B2写完，剩下一个小时对着C发呆就结束了

比赛最后几分钟徐神点醒我C题的正解，但我是完全没往那方面想，看来计数这么久了还是一点不会的说

A. Fill in the Matrix

简单构造题，首先特判掉\(m=1\)的情况

考虑要让\(\operatorname{MEX}\)尽量大，相当于要贪心地先让\(0\)出现，再让\(1\)出现，依此类推

那我们就像这样贪心地构造列，稍微手玩一下很容易发现可以用如下的构造方法（以\(n=8,m=5\)为例）：

5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2
2 3 4 5 0 1
1 2 3 4 5 0
1 2 3 4 5 0
1 2 3 4 5 0
1 2 3 4 5 0

即我们可以用\(m-1\)行构造出最后答案为\(m\)的情况，然后要注意下如果\(n\ge m\)那么多出来的行不能乱填，随便复制前面的某一行即可

而如果行数比较少的话就只能构造出答案为\(n+1\)的情况

#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_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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m; vector <int>  a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; if (scanf("%d%d",&n,&m),m==1)
		{
			for (puts("0"),i=1;i<=n;++i) puts("0"); continue;
		}
		for (i=1;i<=n;++i) a[i].resize(m+1);
		for (i=1;i<=min(n,m-1);++i)
		{
			for (j=1;j<=i;++j) a[i][j]=j+m-1-i;
			for (j=i+1;j<=m;++j) a[i][j]=j-(i+1);
		}
		for (i=m;i<=n;++i) a[i]=a[m-1];
		for (printf("%d\n",min(n+1,m)),i=1;i<=n;++i) for (j=1;j<=m;++j)
		printf("%d%c",a[i][j]," \n"[j==m]);
	}
	return 0;
}

B1. Candy Party (Easy Version)

首先排除掉显然无解的情况，然后求出序列的平均数\(avg\)

考虑枚举每个数\(a_i\)，因为所有数都要给出一次并收入一次，因此每个数都可以枚举一个二元组\((j,k)\)，表示\(a_i+2^j-2^k=avg\)

显然如果某个数找不到这个合法的二元组就直接无解了，不然可以证明这样的二元组一定是唯一的

那么我们只要按位把加上的数和减去的数扔进桶里，然后看下是否每一位对应的都相同即可

注意对于那些初始时就有\(a_i=avg\)的数我们可以直接忽略，因为我们可以把它们当作类似于中转站一样的作用，扔进去什么然后吐出来什么到原来想去的地方即可

而至于最后从哪个点开始以及具体怎么操作可以完成这个过程，感性体会一下会发现一定是存在一种构造方法的

总复杂度\(O(n\log^2 a_i)\)

#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_map>
#define int long long
#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],c1[35],c2[35];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j,k; int avg=0; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),avg+=a[i];
		if (avg%n) { puts("No"); continue; } else avg/=n;
		for (i=0;i<=32;++i) c1[i]=c2[i]=0;
		bool flag=1; for (i=1;i<=n&&flag;++i) if (a[i]!=avg)
		{
			bool sign=0; for (j=0;j<=32&&!sign;++j) for (k=0;k<=32&&!sign;++k)
			if (a[i]+(1LL<<j)-(1LL<<k)==avg) ++c1[j],++c2[k],sign=1;
			if (!sign) flag=0;
		}
		for (i=0;i<=32&&flag;++i) if (c1[i]!=c2[i]) flag=0;
		puts(flag?"Yes":"No");
	}
	return 0;
}

B2. Candy Party (Hard Version)

B2和B1的区别就在于B1强制每个数只能分成两份，而B2允许某个数只分出一份

显然这样的数只有满足\(|a_i-avg|=2^k\)的那些数，并且这些数最后可以选择保留贡献到第\(k\)位或者拆成\(\pm2^{k+1}\mp2^k\)的形式

我们可以把这样的数的个数（正负分开）单独记录下来，而那些只能拆成两位的数还是和之前一样先统计好

贪心地从高位到低位处理，在处理第\(i\)位时先看第\(i+1\)位确定的是否相等，如果不等的话就分裂这一位保证\(i+1\)位相等，不难证明这样一定是最优的

#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_map>
#define int long long
#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],c1[35],c2[35],d1[35],d2[35];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j,k; int avg=0; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),avg+=a[i];
		if (avg%n) { puts("No"); continue; } else avg/=n;
		for (i=0;i<=32;++i) c1[i]=c2[i]=d1[i]=d2[i]=0;
		bool flag=1; for (i=1;i<=n&&flag;++i) if (a[i]!=avg)
		{
			bool sign=0; for (j=0;j<=32&&!sign;++j)
			{
				if (a[i]+(1LL<<j)==avg) ++d1[j],sign=1;
				if (a[i]-(1LL<<j)==avg) ++d2[j],sign=1;
			}
			for (j=0;j<=32&&!sign;++j) for (k=0;k<=32&&!sign;++k)
			if (a[i]+(1LL<<j)-(1LL<<k)==avg) ++c1[j],++c2[k],sign=1;
			if (!sign) flag=0;
		}
		for (i=31;i>=0&&flag;--i)
		{
			if (c1[i+1]==c2[i+1])
			{
				c1[i]+=d1[i]; c2[i]+=d2[i]; continue;
			}
			if (c1[i+1]<c2[i+1])
			{
				int dlt=c2[i+1]-c1[i+1];
				if (dlt>d1[i]) { flag=0; continue; }
				d1[i]-=dlt; c1[i+1]+=dlt; c2[i]+=dlt; c1[i]+=d1[i]; c2[i]+=d2[i];
			}
			if (c1[i+1]>c2[i+1])
			{
				int dlt=c1[i+1]-c2[i+1];
				if (dlt>d2[i]) { flag=0; continue; }
				d2[i]-=dlt; c2[i+1]+=dlt; c1[i]+=dlt; c1[i]+=d1[i]; c2[i]+=d2[i];
			}
		}
		for (i=0;i<=32&&flag;++i) if (c1[i]!=c2[i]) flag=0;
		puts(flag?"Yes":"No");
	}
	return 0;
}

C. Travel Plan

唉铸币了并没有想到有用的状态只有\(O(\log n)\)种，失策失策

首先考虑转换题意，假设我们知道了二叉树中长度为\(i\)的路径的条数\(c_i\)（由于这个是平衡二叉树所以路径长度是\(\log n\)级别的），那么可以直接枚举路径上的最大值\(k\)，则贡献为：

\[k\times [k^i-(k-1)^i]\times m^{n-i} \]

显然如果已知\(\{c_i\}\)就可以\(O(m\log n)\)地计算答案了，很容易想到DP，设\(f_{i,j}\)表示以\(i\)为端点，长度为\(j\)的路径条数，\(g_{i,j}\)表示经过\(i\)（排除以\(i\)为端点的情况），长度为\(j\)的路径条数，显然转移就是合并两个子树，但我们不可能像这样显式地遍历整棵树

稍作思考会发现其实我们根本不关心树根的编号是什么，只要知道子树的大小那么它的贡献就已经确定了

同时很容易证明其实合法的子树大小只有\(O(\log n)\)种，因此直接写个记搜就可以通过了，这部分的复杂度是\(O(\log^3 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_map>
#define int long long
#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int M=100005,mod=998244353;
int t,n,m,coef[130],pw[M][130]; map <int,int> f;
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 m)
{
	for (RI i=1,j;i<=m;++i)
	for (pw[i][0]=1,j=1;j<130;++j)
	pw[i][j]=1LL*pw[i][j-1]*i%mod;
}
inline int DP(int n)
{
	if (!n) return 0; if (n==1) return coef[1];
	if (f.count(n)) return f[n];
	static int c1[65],c2[65]; RI i,j; int tmp=n,ret=0;
	memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2));
	for (c1[0]=c2[0]=1,--n,i=0;n;++i)
	{
		int dlt=min(n,1LL<<i); c1[i+1]+=dlt; n-=dlt;
		dlt=min(n,1LL<<i); c2[i+1]+=dlt; n-=dlt;
	}
	for (i=0;i<65;++i) for (j=0;j<65;++j)
	(ret+=coef[i+j+1]*(c1[i]%mod)%mod*(c2[j]%mod)%mod)%=mod;
	int sum1=-1,sum2=-1; for (i=0;i<65;++i) sum1+=c1[i],sum2+=c2[i];
	return f[tmp]=(ret+DP(sum1)+DP(sum2))%mod;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t),init(100000);t;--t)
	{
		RI i,j; for (scanf("%lld%lld",&n,&m),i=1;i<=min(n,129LL);++i)
		{
			for (coef[i]=0,j=1;j<=m;++j)
			(coef[i]+=(pw[j][i]-pw[j-1][i]+mod)*j%mod)%=mod;
			(coef[i]*=quick_pow(m,n-i))%=mod;
		}
		f.clear(); printf("%lld\n",DP(n));
	}
	return 0;
}

Postscript

打上橙后可以安心小号摆烂了，咱也没那个实力和精力冲红名的说

标签：typedef,896,int,Codeforces,long,Div,include,c1,define
From： https://www.cnblogs.com/cjjsb/p/17694388.html

相关文章

  • Codeforces Round 101 (Div. 2) C - E
    C.Queue(思维、排序、构造、*1800)题意：$n$个人排队,为他们构造一组身高,使得$x$的前面有$a_i$个人比他高。如果无法构造满足所有条件的身高序列,输出-1。思路：首先考虑,对于$a_i$较大的人,肯定尽可能地将其往队伍后面放,然后从后往前构造,因为只有$......
  • abc288F - Integer Division
    F-IntegerDivision挺有意思的一道题，贪心的做法就是排序之后，逐个加入，如果不能被之前的表示则加入题解证明的话大概是这样考虑第i个数选不选首先加入前面选的数，如果能够表示当前的数，则必然不选否则前面的数不能表示当前的数，假如我们不选\(p_i\)假设最后得到一个合法序列，则......
  • 【题解】Educational Codeforces Round 142（CF1792）
    没有手速，再加上被E卡了，废掉了。A.GamingForces题目描述：Monocarp正在玩电脑游戏。他打算杀死\(n\)个怪兽，第\(i\)个的血量为\(h_i\)。Monocarp的角色有两个魔法咒语如下，都可以以任意顺序用任意次（可以不用），每次使用相当于一次操作。选择两个怪兽并各扣一滴血。选择......
  • Codeforces Global Round 21 B. NIT Destroys the Universe
    给一个长为\(n\)的数组，可以执行以下操作任意次：选择\(l,r(1\leql<r\leqn)\)，让\(\foralli(l\leqi\leqr),a_i=mex(\{a_l,a_{l+1},\cdots,a_{r}\})\)。问最小操作数使得\(\foralli,a_i=0\)。观察：答案\(\leq2\)，因为对\([1,n]\)操作不超过两次......
  • Codeforces Round 804 (Div. 2) B. Almost Ternary Matrix
    给两个偶数\(n\)和\(m\)。任务是构造任意一个二进制矩阵，\(n\timesm\)。对于任意\((i,j)\)，有且仅有两个邻居的颜色与\(a_{i,j}\)不同。邻居的定义为\(|x-x'|+|y-y'|=1\)。观察：任何\(n\timesm\)的矩阵若作为一个大型矩阵的子矩阵不会受到限制。于是构造......
  • Codeforces Round 807 (Div. 2) B. Mark the Dust Sweeper
    需要打扫\(n\)个房间，第\(i\)个房间有\(a_i\)的积灰。只能使用如下魔法打扫：选择\(i,j,(1\leqi<j\leqn,\min_{k=i}^{j}a_i>0)\)。执行\(a_i=a_i-1,a_j=a_j+1\)。需要将\(1\simn-1\)号房间的积灰全部清空，最少使用多少次魔法。观察一：显......
  • Codeforces Round 811 (Div. 3) A. Everyone Loves to Sleep
    闹钟设有\(n\)个时间点，第\(i\)个时间为\((H_i,M_i)\)。在\(h,m\)时刻入睡，响铃必须起床，问能睡多久。使用\(set<pair<int,int>>\)存储闹铃时刻，然后在其中\(lower_{bound}\)到\(<first\geqh,second\geqm>\)的迭代器\(it\)。若\(it=end\)，则\(it=begin......
  • Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    给一个长为\(n\)的正整数数组，执行以下操作严格一次。选择\(l,r,(1\leql<r\leqn)\)，任意一个正整数\(k\)。重复\(k\)次：让\([l,r]\)的数组成环，按顺时针走一次。希望\(a_n-a_1\)最大，找到这个数。分类讨论题。先判断\(n\)为\(1\)时\(a_n-a_1\)......
  • Codeforces Round 830 (Div. 2) B. Ugu
    给一个\(01\)字符串，需要使它变为非降的，可以执行以下操作：选择一个下标\(i,(1\leqi\leqn)\)，\(\forallj\geqi\)的数位翻转。经典的按无后效性翻转问题。考虑从前往后，得到一个全\(0\)串。若开始存在\(1\)，则答案减\(1\)。如果存在\(1\)，遇到\(1\)便翻转后......
  • $Codeforces Round 891 (Div. 3)$
    \(A.ArrayColoring\)显然需要奇数个偶数即可满足题目。voidsolve(){intn=read(),res=0;for(inti=1;i<=n;i++){intx=read();if(x%2)res++;}puts(res%2==0?"YES":"NO");//puts(ans>0?"Yes":"No&......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99