526互联

Codeforces Round 885 (Div. 2)

发布时间 2023-07-19 21:04:36作者: 空気力学の詩

Preface

打的就是依托答辩居然也能上分，看来手稳还是重要的说

D题半场开香槟以为随便写，然后没想到怎么处理这个局部没有三分性的函数，直接GG

后面听学长一说其实分成四种函数分别求最值即可直接恍然大悟，只能说还是太菜太菜

而且F好像是个蓝桥杯的某个题的弱化版，我说比赛的时候怎么那么多人艹过去

A. Vika and Her Friends

这场的题面简直就是灾难级别的，A题搞懂题意都快5min了

不难发现可以对格子进行黑白染色，如果有一个朋友和Vika在同色格子内最后就一定能捉到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105;
int t,n,m,k,X0,Y0,x,y,s[2];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d%d%d",&n,&m,&k,&X0,&Y0),s[0]=s[1]=0,i=1;i<=k;++i) scanf("%d%d",&x,&y),++s[(x+y)&1];
		puts(s[(X0+Y0)&1]?"NO":"YES");
	}
	return 0;
}

B. Vika and the Bridge

又是题面杀，做法其实很简单

刚开始最大值最小一眼二分，后面发现不需要

直接枚举最后走的是哪种颜色，然后扫一遍求一下相邻元素的最大值与次大值

考虑修改的话就是把最大值的贡献减半，再和之前的次大值取较大的一个更新答案即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e9;
int t,n,k,c; vector <int> pos[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) scanf("%d",&c),pos[c].push_back(i);
		int ans=INF; for (i=1;i<=k;++i) if (pos[i].size())
		{
			int mx=0,smx=0,lst=0; for (int x:pos[i])
			{
				if (x-lst-1>mx) smx=mx,mx=x-lst-1;
				else if (x-lst>smx) smx=x-lst-1; lst=x;
			}
			if (n-lst>mx) smx=mx,mx=n-lst;
			else if (n-lst>smx) smx=n-lst;
			ans=min(ans,max(smx,mx/2)); pos[i].clear();
		}
		printf("%d\n",ans);
	}
	return 0;
}

C. Vika and Price Tags

刚开始搞错了最后\((0,x)\)后的循环节，以为是以\(2\)为循环然后一直跑不过样例，后面发现后真想抽自己大耳光子

首先不难发现我们只要求出每组位置\((a_i,b_i)\)第一次变成\((0,x)\)这种形式所需要的步数，最后如果要让所有数都为\(0\)就需要所有的步数对\(3\)取模的值相同

而怎么求这个东西，直接暴力辗转相减显然不可取，但我们可以找一手规律

不妨设\(n>m\)，则在\(3\)次操作后\((n,m)\)会变成\((n,n-2\times m)\)，利用这个可以快速缩减数据规模

最后单组的次数求解大概是\(O(\log a_i)\)级别的，总之可以跑过

注意特判两个数都是\(0\)的情况

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int t,n,a[N],b[N];
inline int calc(int n,int m)
{
	//printf("%d %d\n",n,m);
	if (!n) return 0; if (!m) return 1;
	if (n<m) return calc(m,m-n)+1;
	int t=(n/m)/2,step=t*3; n-=t*2*m;
	if (!n) return step;
	if (n<m) return step+calc(n,m);
	return step+calc(m,n-m)+1; 
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
		for (i=1;i<=n;++i) scanf("%lld",&b[i]); int s[3]={0,0,0};
		for (i=1;i<=n;++i)
		{
			if (!a[i]&&!b[i]) continue;
			++s[calc(a[i],b[i])%3LL];
		}
		if (!s[0]&&!s[1]&&!s[2]) { puts("YES"); continue; }
		if (s[0]&&!s[1]&&!s[2]) { puts("YES"); continue; }
		if (s[1]&&!s[0]&&!s[2]) { puts("YES"); continue; }
		if (s[2]&&!s[0]&&!s[1]) { puts("YES"); continue; }
		puts("NO"); 
	}
	return 0;
}

D. Vika and Bonuses

这个题一眼看上去实在是太板了，考虑对于做了\(x\)次加数操作的情况，一定是先把\(x\)次加数都加了然后再乘上\(k-x\)

然后这个东西一眼看上去实在太像个单峰函数了，所以感觉直接三分\(x\)，而加数的过程很容易发现除了\(0,5\)外都有长度为\(4\)的循环节，随便搞一下就好了

但是飞速写完发现怎么连样例都过不了，后面一想其实是因为这是个多个单峰函数复合的函数，只有整体的单峰性，但局部可能会有偏差

处理方法大致有两种，一种是三分的时候每次取分点的左右各\(10\)各点左右，取最大值来作为比较的依据

不过注意这样最后区间长度要保证是一个较大的数，最后再暴力扫一遍区间即可，感觉是个很好用的trick以后有机会可以试试

另一种比较科学的方法就是做四次三分，每次三分规定后面加数操作一定是\(4\)的倍数，这样得到的一定是一个二次函数的形式，显然是可以三分的

这里的代码写的是后面的做法

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
int t,s,k,num[10],d[10],cnt;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; scanf("%lld%lld",&s,&k); memset(num,-1,sizeof(num));
		int len,st; for (num[s%10]=0,d[cnt=0]=s;;)
		{
			s+=s%10; if (~num[s%10])
			{
				len=cnt+1-num[s%10]; st=num[s%10];
				d[++cnt]=s; break;
			} else num[s%10]=cnt+1,d[++cnt]=s;
		}
		int ans=0; for (i=0;i<=min(st,k);++i) ans=max(ans,d[i]*(k-i));
		int dlt=d[cnt]-d[st];
		if (k>=st)
		{
			auto calc=[&](int x)
			{
				x-=st; int c=d[st]+x/len*dlt;
				c+=d[st+x%len]-d[st]; return (k-x-st)*c;
			};
			for (i=st;i<=min(st+len-1,k);++i)
			{
				int l=0,r=(k-i)/len;
				while (r-l>2)
				{
					int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
					if (calc(lmid*len+i)<=calc(rmid*len+i)) l=lmid; else r=rmid;
				}
				for (j=l;j<=r;++j) ans=max(ans,calc(j*len+i));
			}
		}
		printf("%lld\n",ans);
	}
}

E. Vika and Stone Skipping

搞不懂出题人为什么喜欢搞不定模数，就是给题徒增难度是吧

对于等差数列求和，不妨设求和的区间为\([l,r]\)，最后得到的数为\(t\)，则\(\sum_{i=l}^ r i=\frac{(l+r)\times (r-l+1)}{2}=t\)，等价于\((l+r)\times (r-l+1)=2t\)

稍加讨论一下会发现左边的两个式子的奇偶性一定不同，因此我们可以想到把\(2t\)分成奇偶性不同的两个因子，同时我们惊喜地发现这种划分方案和\([l,r]\)的取法一一对应

那么现在问题就很简单了，我们对于\(2t\)做一遍质因数分解，所有的\(2\)必须放在某一边，而其它的质因子都可以随便放

方案数其实就是一个数的约数个数的式子的变形，即\(\prod_{p_i\ne 2} (c_i+1)\)

然后实现的时候要注意一个坑点，由于\((c_i+1)\)可能是模数的倍数，因此直接搞会出现某些数没有逆元的情况

这种问题的处理方法也比较经典了，考虑记录一下此时整个式子乘上\(0\)的个数，输出的时候判断下即可，具体看代码吧

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=1e6+5;
int x,q,mod,cnt[N],ans=1,cnt0;
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 calc(int x)
{
	for (RI i=2;i*i<=x;++i) if (x%i==0)
	{
		if (i!=2)
		{
			if ((cnt[i]+1)%mod) ans=1LL*ans*quick_pow(cnt[i]+1)%mod; else --cnt0;
		}
		while (x%i==0) x/=i,++cnt[i];
		if (i!=2)
		{
			if ((cnt[i]+1)%mod) ans=1LL*ans*(cnt[i]+1)%mod; else ++cnt0;
		}
	}
	if (x>1)
	{
		if (x>1000000) return (void)(ans=2LL*ans%mod);
		if (x!=2)
		{
			if ((cnt[x]+1)%mod) ans=1LL*ans*quick_pow(cnt[x]+1)%mod; else --cnt0;
		}
		++cnt[x];
		if (x!=2)
		{
			if ((cnt[x]+1)%mod) ans=1LL*ans*(cnt[x]+1)%mod; else ++cnt0;
		}
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&x,&q,&mod),calc(x),i=1;i<=q;++i)
	scanf("%d",&x),calc(x),printf("%d\n",cnt0?0:ans);
	return 0;
}

F. Vika and Wiki

额蓝桥杯某题究极弱化版来了，当时那题我记得\(n\)还不是\(2\)的幂次，所以写起来还有些细节

这题其实就是利用一个关键性质，在操作\(2^t\)次后\(a'_i=a_i\oplus a_{(i+2^t)\bmod 2^k}\)，我记得当时我做蓝桥杯那题的时候是找规律发现的，其实归纳一下很好证明

有了这个我们会发现在操作\(2^k\)序列一定会变成全\(0\)，那么有没有更少的次数可能呢

考虑分治，对于当前长度为\(n\)的序列，不妨分成前面\(\frac{n}{2}\)和后面\(\frac{n}{2}\)来考虑

如果对于\(\forall i\in[0,\frac{n}{2}),a_i=a_{i+\frac{n}{2}}\)，则操作\(\frac{n}{2}\)就是完全没有必要的，否则我们必须进行这次操作

很容易发现可以把上面的东西写成一个分治的形式，具体实现看代码

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=20;
int n,a[1<<N];
inline int solve(CI n)
{
	if (n==1) return a[0]!=0;
	RI i; bool flag=1; for (i=0;i<n/2&&flag;++i)
	if (a[i]!=a[i+n/2]) flag=0;
	if (flag) return solve(n/2);
	for (i=0;i<n/2;++i) a[i]^=a[i+n/2];
	return n/2+solve(n/2);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=0;i<n;++i) scanf("%d",&a[i]);
	return printf("%d",solve(n)),0;
}

Postscript

好好好不掉分就算成功