526互联

Codeforces Round 866 (Div. 2)（持续更新）

发布时间 2023-04-17 00:01:15作者: 空気力学の詩

Preface

不知道为什么现在对不想打游戏刷B站什么的一点兴趣都没有，打开HBR就只想清下体力下线去写题

但学校的DS专题能抢一血的题都被抢的七七八八了，剩下几个难得要死都是些我OI时期都不会的东西（吉司机线段树、划分树之类的）

然后突然想起来昨天这场CF还没写博客，E明天再抽个时间想一下然后写吧

这场本来比赛时让ztc给我截个CDE的图片然后我先从C开始看，如果感觉有思路就用大号打Div1，不然就用小号打Div2

然后C时一眼丁真了，但是D刚开始没注意到重要性质没太多想法，E一眼也没啥想法就跑回去打Div2了

总结一下还是太菜了，这样下去什么时候能上2100啊，得上点强度了的说

A. Yura's New Name

傻逼题，从左到右考虑每个_，先保证它们的左边都要有^，然后考虑对结尾的_的右边进行补全即可

注意特判\(n\)较小的情况

#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
int T,n; string s,t;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (cin>>T;T;--T)
	{
		RI i; cin>>s; t="";
		if (s.size()==1&&s[0]=='_') { puts("2"); continue; }
		if (s.size()==1&&s[0]=='^') { puts("1"); continue; }
		if (s.size()==2)
		{
			if (s[0]=='_'&&s[1]=='_') { puts("3"); continue; }
			if (s[0]=='^'&&s[1]=='^') { puts("0"); continue; }
			puts("1"); continue;
		}
		for (i=0;i<s.size();++i)
		if (s[i]=='_') { if (i==0||s[i-1]=='_') t=t+"^"+s[i]; else t+=s[i]; } else t+=s[i];
		if (t[t.size()-1]=='_') t+="_"; cout<<t.size()-s.size()<<endl;
	}
	return 0;
}

B. JoJo's Incredible Adventures

丁真题，很显然我们如果设串中最长的连续的\(1\)的长度为\(m\)，则现在就要考虑对\(m+1\)进行划分，使得\(x+y=m+1\)时\(xy\)的值最大

显然根据均值不等式令\(x=\lfloor\frac{m+1}{2}\rfloor,y=x=m+1-\lfloor\frac{m+1}{2}\rfloor\)即可，注意到我们在找最长的\(m\)时时可以从最后接到前面去的

但注意一个Corner Case，当\(m=n\)，即所有数都是\(1\)时要特判输出\(n\times n\)

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
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 i; int lst=0,mx=0; for (scanf("%s",s+1),n=strlen(s+1),i=1;i<=2*n-1;++i)
		if (s[(i-1)%n+1]=='0') mx=max(mx,i-lst-1),lst=i; mx=max(mx,2*n-1-lst); ++mx;
		printf("%lld\n",mx>n?1LL*n*n:1LL*(mx/2)*(mx-mx/2));
	}
	return 0;
}

C. Constructive Problem

刚开始心态太浮躁都没细心想，其实很简单的一个题

首先我们求出原序列的\(\operatorname{MEX}(a)=t\)，显然由于\(\operatorname{MEX}\)的性质若\(t=n\)则必然无解

否则我们可以把修改的\(k\)定为\(t\)，然后考虑在修改后\(a\)中不能出现\(t+1\)

因此我们找出原来的序列中包含所有\(t+1\)的最小区间，然后把这段区间赋值成\(t\)后再检验一遍即可

#include<cstdio>
#include<iostream>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],L,R,mex; set <int> s;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),s.clear(),i=1;i<=n;++i)
		scanf("%d",&a[i]),s.insert(a[i]);
		for (mex=0;s.count(mex);++mex);
		if (mex==n) { puts("No"); continue; }
		for (L=n+1,R=0,i=1;i<=n;++i)
		if (a[i]==mex+1) L=min(L,i),R=max(R,i);
		if (L>R) { puts("Yes"); continue; }
		for (s.clear(),i=L;i<=R;++i) a[i]=mex;
		for (i=1;i<=n;++i) s.insert(a[i]);
		int tmp=mex; for (mex=0;s.count(mex);++mex);
		if (mex==tmp+1) puts("Yes"); else puts("No");
	}
	return 0;
}

D. The Butcher

有点意思的题，感觉是最近做到的最有意思的思博题了

首先我们考虑对于原来最大的矩形，第一刀切下去时一定会有某一维中保留下了原来的最大的那条边

换句话说，我们记\(mxh=\max a_i,mxw=\max b_i\)，则显然最后答案只可能是\(h=mxh\)和\(w=mxw\)两种情况

同时我们发现由于所有矩形的面积之和是可以求出来的，因此我们也很容易推出原来的矩形的另一维是多少

那么现在问题就是给定了\(h,w\)后怎么检验它是否合法，显然根据前面的思路我们发现如果在剩下的碎片中存在\(\max a_i=h\)的，则这些碎片一定是在保留\(h\)这一维的基础上在另一维上切割得出来的

当然另一位也同理，因此就很好模拟这个切割过程了，总复杂度\(O(n\log n)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,M=1e6+5;
int t,n,a[N],b[N],ans[5][2],cnt,mxa,mxb;
bool vis[N]; long long area; vector <int> A[M],B[M]; multiset <int> LA;
inline bool check(int h,int w)
{
	RI i; for (LA.clear(),i=1;i<=n;++i) A[a[i]].clear(),B[b[i]].clear(),vis[i]=0;
	for (i=1;i<=n;++i) A[a[i]].push_back(i),B[b[i]].push_back(i),LA.insert(a[i]);
	while (h>0&&w>0)
	{
		bool is_remove=0;
		if (h==*(--LA.end()))
		{
			for (int id:A[h]) if (!vis[id]&&w>=b[id])
			vis[id]=1,w-=b[id],is_remove=1,LA.erase(LA.find(a[id]));
		} else
		{
			for (int id:B[w]) if (!vis[id]&&h>=a[id])
			vis[id]=1,h-=a[id],is_remove=1,LA.erase(LA.find(a[id]));
		}
		if (!is_remove) return 0;
	}
	return 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),area=cnt=mxa=mxb=0,i=1;i<=n;++i)
		scanf("%lld%lld",&a[i],&b[i]),mxa=max(mxa,a[i]),mxb=max(mxb,b[i]),area+=a[i]*b[i];
		if (area%mxa==0&&check(mxa,area/mxa)) ++cnt,ans[cnt][0]=mxa,ans[cnt][1]=area/mxa;
		if (area%mxb==0&&mxa!=area/mxb&&check(area/mxb,mxb)) ++cnt,ans[cnt][0]=area/mxb,ans[cnt][1]=mxb;
		for (printf("%lld\n",cnt),i=1;i<=cnt;++i) printf("%lld %lld\n",ans[i][0],ans[i][1]);
	}
	return 0;
}