标签：CODE const int Codeforces freopen Div include 821 RI

Preface

唉LOL打到一半被迫营业开打，感觉这算是第一次自己认真的在线打CF，以我的老年人手速感觉要罚时飞起了

10：35开始打到12：10顶不住了睡觉去了，E大概看了个题感觉挺有意思的，但D2写了太久了没时间了

晚上还要上课先把前5题写一下，E的话下次再补

A. Consecutive Sum

对于每个下标对\(k\)取模后相同的位置取个\(\max\)再加起来即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,k,x,c[N]; long long ans;
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=0;i<k;++i) c[i]=0;
		for (i=0;i<n;++i) scanf("%d",&x),c[i%k]=max(c[i%k],x);
		for (ans=i=0;i<k;++i) ans+=c[i]; printf("%lld\n",ans);
	}
	return 0;
}

B. Rule of League

首先发现，若\(x,y\)均不为\(0\)则一定不合法，因为一共就\(n-1\)场比赛不可能做到每个人都赢

同时显然若\(x,y\)均等于\(0\)也不合法，此时设\(x\ne 0,y=0\)，若\(n-1\)不是\(x\)的倍数也不合法

否则一定合法，让顺次轮到的人连续赢\(x\)场，稍微构造一下即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,y,cur;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d%d",&n,&x,&y);
		if ((x&&y)||(!x&&!y)) { puts("-1"); continue; }
		if (!x) x=y; if ((n-1)%x) { puts("-1"); continue; }
		for (i=j=cur=1;i<=n-1;i+=x)
		{
			for (j=1;j<=x;++j) printf("%d ",cur);
			if (cur==1) cur+=x+1; else cur+=x;
		}
		putchar('\n');
	}
	return 0;
}

C. Parity Shuffle Sorting

又是构造题好耶

首先不难发现次数的限制很宽松，我们不妨直接把所有数都变成一样的

考虑到两个数奇偶性相同时是后面的传递给前面，反之则是前面的传递给后面，我们以此下手：

首先先对\((1,n)\)进行一次操作把两个数变成一样的
考虑\([2,n-1]\)中的每个数\(a_i\)，若\(a_i\)和\(a_1\)的奇偶性不同，则进行操作\((1,i)\)
考虑\([2,n-1]\)中的每个数\(a_i\)，由于\(a_1=a_n\)，且此时若\(a_i\ne a_n\)则它与\(a_n\)的奇偶性一定相同，进行操作\((i,n)\)即可

总操作次数是小于等于\(n-1\)的，满足题目要求

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],l[N],r[N],tot;
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]);
		if (n==1) { puts("0"); continue; }
		l[tot=1]=1; r[1]=n;	if ((a[1]&1)!=(a[n]&1)) a[n]=a[1]; else a[1]=a[n];
		for (i=2;i<n;++i) if ((a[i]&1)!=(a[1]&1)) l[++tot]=1,r[tot]=i,a[i]=a[1];
		for (i=2;i<n;++i) if (a[i]!=a[n]) l[++tot]=i,r[tot]=n,a[i]=a[n];
		for (printf("%d\n",tot),i=1;i<=tot;++i) printf("%d %d\n",l[i],r[i]);
	}
	return 0;
}

D1. Zero-One (Easy Version)

为什么这题这么简单值1500分，后面的D2才750分捏

首先找出所有需要翻转的下标\(pos_i\)，设共有\(cnt\)个，显然若\(cnt\)为奇数则一定无解

考虑当\(cnt>2\)的情况，由于\(y\le x\)，因此我们总可以找到一种方案，使得每次操作的两个位置不相邻（比如把前\(\frac{cnt}{2}\)个位置和后\(\frac{cnt}{2}\)个位置一一配对）

若\(cnt=2\)，且\(pos_1+1=pos_2\)，则考虑\(x\)和\(2y\)的大小关系即可

#include<cstdio>
#include<iostream>
#include<cctype>
#define RI register int
#define CI const int&
using namespace std;
const int N=3005;
int t,n,cnt,x,y,pos[N]; char a[N],b[N];
inline char get_dight(void)
{
	char ch; while (ch=getchar(),!isdigit(ch)); return ch;
}
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",&n,&x,&y),i=1;i<=n;++i)
		a[i]=get_dight(); for (i=1;i<=n;++i) b[i]=get_dight();
		for (cnt=0,i=1;i<=n;++i) if (a[i]!=b[i]) pos[++cnt]=i;
		if (cnt&1) { puts("-1"); continue; }
		if (cnt==2)
		{
			if (pos[1]+1==pos[2]) printf("%lld\n",min(1LL*x,2LL*y)); 
			else printf("%lld\n",1LL*y);
		} else printf("%lld\n",1LL*y*cnt/2LL);
	}
	return 0;
}

D2. Zero-One (Hard Version)

首先特判掉\(y\le x\)的情况，然后考虑\(x>y\)的情形

首先我们发现可以把\(pos_i\)分成若干个连续段，每个段内部可以进行\(x\)操作，不同的段之间可以进行\(y\)操作，同时相邻的两个段之间还可以进行多次\(x\)操作

刚开始naive的想用贪心，但想了下感觉有点假，遂开始大力DP（写完Locked之后看下Room里别的过的人代码好简略，感觉我可以忽略了什么性质）

设\(f_{i,j,0/1}\)表示处理完了前\(i\)个连续段，一共有\(j\)个没处理的数（最后用\(y\)操作处理），且第\(i\)段的末尾有无预留元素与\(i+1\)段匹配（这个不算在\(j\)里面）

转移的话就细分几种情况讨论下即可，注意一个重要性质，一个连续段内不能出现超过两个称为未处理的数，这样显然不是最优的，具体实现可以看代码

单组数据复杂度\(O(n^2)\)

#include<cstdio>
#include<iostream>
#include<cctype>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
const long long INF=1e18;
int t,n,cnt,x,y,pos[N],l[N],r[N],sz[N],tot,cur; char a[N],b[N]; long long f[N][N][2],tmp,ans;
inline char get_dight(void)
{
	char ch; while (ch=getchar(),!isdigit(ch)); return ch;
}
inline void chkmin(long long& x,const long long& y)
{
	if (y<x) x=y;
}
inline long long link(CI p,CI q)
{
	if (p<1||q>tot) return INF; return 1LL*(l[q]-r[p])*x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d%d",&n,&x,&y),i=1;i<=n;++i)
		a[i]=get_dight(); for (i=1;i<=n;++i) b[i]=get_dight();
		for (cnt=0,i=1;i<=n;++i) if (a[i]!=b[i]) pos[++cnt]=i;
		if (cnt&1) { puts("-1"); continue; }
		if (y<=x)
		{
			if (cnt==2)
			{
				if (pos[1]+1==pos[2]) printf("%lld\n",min(1LL*x,2LL*y)); 
				else printf("%lld\n",1LL*y);
			} else printf("%lld\n",1LL*y*cnt/2LL);
		} else
		{
			for (cur=tot=0,i=1;i<=cnt;i=j+1)
			{
				j=i; while (j<cnt&&pos[j]+1==pos[j+1]) ++j;
				l[++tot]=pos[i]; r[tot]=pos[j]; sz[tot]=j-i+1;
			}
			for (i=0;i<=n;++i) for (j=0;j<=n;++j) f[i][j][0]=f[i][j][1]=INF;
			for (f[0][0][0]=0,i=0;i<tot;++i) for (j=0;j<=cnt;++j)
			{
				if ((tmp=f[i][j][0])!=INF)
				{
					if (sz[i+1]&1)
					{
						chkmin(f[i+1][j][1],tmp+1LL*(sz[i+1]-1)/2LL*x);
						chkmin(f[i+1][j+1][0],tmp+1LL*(sz[i+1]-1)/2LL*x);
					} else
					{
						chkmin(f[i+1][j][0],tmp+1LL*sz[i+1]/2LL*x);
						chkmin(f[i+1][j+1][1],tmp+1LL*(sz[i+1]/2LL-1)*x);
					}
				}
				if ((tmp=f[i][j][1])!=INF)
				{
					if (sz[i+1]&1)
					{
						chkmin(f[i+1][j][0],tmp+1LL*(sz[i+1]-1)/2LL*x+link(i,i+1));
						if (sz[i+1]>=3) chkmin(f[i+1][j+1][1],tmp+1LL*(sz[i+1]-3)/2LL*x+link(i,i+1));
					} else
					{
						chkmin(f[i+1][j][1],tmp+1LL*(sz[i+1]/2LL-1)*x+link(i,i+1));
						chkmin(f[i+1][j+1][0],tmp+1LL*(sz[i+1]/2LL-1)*x+link(i,i+1));
					}
				}
			}
			for (ans=INF,j=0;j<=cnt;j+=2) chkmin(ans,f[tot][j][0]+1LL*j/2LL*y);
			for (j=1;j<=cnt;j+=2) chkmin(ans,f[tot][j][1]+1LL*(j+1)/2LL*y);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

Postscript

手感不错前5题都没有挂PT，而且最后也没有FST，苟了个不错的排名上了一大波分（Rank101，+161Rating）

标签：CODE,const,int,Codeforces,freopen,Div,include,821,RI
From： https://www.cnblogs.com/cjjsb/p/16712161.html

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