Preface

补题，本来这场想现场打的，但是玩《Island》玩的有点上头就没打了~~（逸一时，误一世~~

然后今天发现2h30min就没啥难度的全写了，早知道昨天现场打给大号涨波分了

不过现场打以我的尿性也不知道会整出什么逆天操作，等下一个细节写挂心态一崩就开始坐牢（乐

A. Grasshopper on a Line

当\(k\nmid x\)时就直接跳过去即可，否则枚举第一步跳多少两步跳过去即可，不难发现一定有解

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

B. Comparison String

刚开始很naive地上来一个贪心，把每次<都看作后一个数比前一个数大\(1\)，>看作后一个数比前一个数小\(1\)

令第一个位置出现的数为\(0\)，然后直接统计总共出现的数个数

但是这样会有一点问题，因为我们可能在某次选择\(\pm k\)的时会更优

然后画画图发现其实就是找最长的连续的相同字符长度\(t\)，然后加\(1\)就是答案

因为我们以这一段为基准定下\(t+1\)个值后，其它的数的取值总可以落在这个范围内

因此代码就很简单了

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=205;
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; scanf("%d%s",&n,s+1); s[n+1]='#';
		int ret=0,lst=0; for (i=1;i<=n;++i)
		if (s[i]!=s[i+1]) ret=max(ret,i-lst),lst=i;
		printf("%d\n",ret+1);
	}
	return 0;
}

C. Best Binary String

感觉比B题简单的说

首先操作次数最短的串肯定满足其中连续的\(01\)段数量最少

因此很容易想到把每个?位置都和前后的某种字符变成一样的即可

注意初始时全部都是?的情况

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

D. Bracket Coloring

趣题，首先发现当左右括号个数不相同时一定无解，否则一定有解

然后就是本题最关键的一个性质，答案要么为\(1\)要么为\(2\)

答案为\(1\)的情况很好判断，从前往后和从后往前分别扫一遍看看整个串是不是合法的括号序列即可

否则考虑如何构造答案为\(2\)的情况，以从左往右为例，我们用一个栈维护所有的左括号的位置

当遇到右括号时，将栈顶和当前右括号一起染成颜色\(1\)，而特别之处在于如果此时栈中没有左括号，则直接无视这个右括号

扫一遍之后剩下没被染色的就是颜色\(2\)了，手玩一下不难发现这样得出的一定是合法的解

#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,stk[N],top,ans[N]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s",&n,s+1); top=0; int cnt[2]={0,0};
		for (i=1;i<=n;++i) ans[i]=2,++cnt[s[i]=='('];
		if (cnt[0]!=cnt[1]) { puts("-1"); continue; }
		int cur=0; for (i=1;i<=n;++i) if (s[i]==')')
		{
			if (top) ans[i]=ans[stk[top]]=1,cur+=2,--top;
		} else stk[++top]=i;
		if (cur==n)
		{
			for (puts("1"),i=1;i<=n;++i)
			printf("%d%c",ans[i]," \n"[i==n]); continue;
		}
		for (i=1;i<=n;++i) ans[i]=2;
		for (cur=top=0,i=n;i>=1;--i) if (s[i]==')')
		{
			if (top) ans[i]=ans[stk[top]]=1,cur+=2,--top;
		} else stk[++top]=i;
		if (cur==n)
		{
			for (puts("1"),i=1;i<=n;++i)
			printf("%d%c",ans[i]," \n"[i==n]); continue;
		}
		for (puts("2"),i=1;i<=n;++i)
		printf("%d%c",ans[i]," \n"[i==n]); 
	}
	return 0;
}

E. Playoff Fixing

什么模拟题也混到E题的位置来了，而且也没啥细节的说

考虑从编号从大到小考虑每组同一轮淘汰的人，以\(k=4\)的情况为例

第一轮淘汰的是编号为\([9,16]\)，不难发现对于按种子序号形成的最终排列中，区间\([1,2],[3,4]\cdots,[15,16]\)中每个区间都要有且仅有一个\([9,16]\)的数

然后无解的情况就很好判掉，然后考虑设\([9,16]\)中还未分配的个数为\(left\)，同时区间\([2k-1,2k]\)中有两个空位的区间个数为\(coef\)，则这一轮的数的放置方案数为\(left!\times 2^{coef}\)

然后不难发现这一轮的具体填法对接下来的轮次是没有影响的，我们随便搞一组合法的填法然后递归下一轮即可

不过要注意对于第二轮淘汰的\([5,8]\)，要求的区间就变成了\([1,4],[5,8],[9,12],[13,16]\)，后面的也是同理

直到做到只剩两个数\([1,2]\)没有分配时退出即可，注意特判下这两个数都没被分配的情况要多乘上一个\(2\)

具体实现的话可以递归也可以像我一样用类似于FFT的枚举区间方式来写，复杂度是\(O(k\times 2^k)\)

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1<<20,mod=998244353;
int n,m,a[N],fact[N],pw[N],ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%d",&m),n=1<<m,i=0;i<n;++i)
	if (scanf("%d",&a[i]),~a[i]) --a[i];
	if (m==0) return puts("1"),0;
	for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
	for (ans=k=1;k<m;++k)
	{
		int L=1<<m-k,R=(1<<m-k+1)-1,left=R-L+1,coef=0;
		for (i=0;i<n;i+=(1<<k))
		{
			int cur=0,space=0;
			for (j=0;j<(1<<k);++j)
			if (a[i+j]>=L&&a[i+j]<=R) ++cur;
			else if (!~a[i+j]) ++space;
			if (cur>1) ans=0; else if (cur) --left;
			if (!space&&!cur) ans=0;
			if (space==2) ++coef;
			if (!cur)
			{
				for (j=0;j<(1<<k);++j)
				if (!~a[i+j]) { a[i+j]=L; break; }
			}
		}
		ans=1LL*ans*fact[left]%mod*pw[coef]%mod;
	}
	int cur=0; for (i=0;i<n;++i) if (!~a[i]) ++cur;
	return printf("%d",1LL*ans*fact[cur]%mod),0;
}

F. Editorial for Two

什么一眼题，首先不难发现一种暴力的想法，枚举分界点\(i\)，再枚举第一个人取走的数的个数\(j\)

则求出\([1,i]\)中前\(j\)小的数之和，和\([i+1,n]\)中前\(k-j\)小的数之和取\(\max\)即可，正确性显然

然后直觉告诉我们当\(i\)固定时，随着\(j\)的取值变化，两边的\(\max\)是一个单峰函数，因此直接三分\(j\)的最优取值即可

然后求区间内前\(k\)大的问题方法也很多，这题可以直接离散化之后在权值线段树上二分，代码也是十分好写

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

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,k,a[N],rst[N],cnt; long long ans;
class Segment_Tree
{
	private:
		int num[N<<2]; long long sum[N<<2];
	public:
		#define TN CI now=1,CI l=1,CI r=cnt
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			sum[now]=num[now]=0; if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
		}
		inline void update(CI pos,CI mv,TN)
		{
			num[now]+=mv; sum[now]+=mv*rst[pos]; if (l==r) return; int mid=l+r>>1;
			if (pos<=mid) update(pos,mv,LS); else update(pos,mv,RS);
		}
		inline long long query(CI rk,TN)
		{
			if (l==r) return 1LL*rst[l]*rk; int mid=l+r>>1;
			if (rk<=num[now<<1]) return query(rk,LS);
			else return query(rk-num[now<<1],RS)+sum[now<<1];
		}
		#undef TN
		#undef LS
		#undef RS
}A,B;
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",&n,&k),i=1;i<=n;++i)
		scanf("%d",&a[i]),rst[i]=a[i];
		sort(rst+1,rst+n+1); cnt=unique(rst+1,rst+n+1)-rst-1;
		for (i=1;i<=n;++i) a[i]=lower_bound(rst+1,rst+cnt+1,a[i])-rst;
		for (A.build(),B.build(),i=1;i<=n;++i) B.update(a[i],1);
		for (ans=B.query(k),i=1;i<=n;++i)
		{
			A.update(a[i],1); B.update(a[i],-1);
			int l=max(0,k-(n-i)),r=min(i,k),lmid,rmid;
			while (r-l>2)
			{
				lmid=l+(r-l)/3; rmid=r-(r-l)/3;
				if (max(A.query(lmid),B.query(k-lmid))<max(A.query(rmid),B.query(k-rmid))) r=rmid; else l=lmid;
			}
			for (j=l;j<=r;++j) ans=min(ans,max(A.query(j),B.query(k-j)));
		}
		printf("%lld\n",ans);
	}
}

当然这题还有个更好写的做法，考虑直接二分答案\(x\)，思考如何check

不难发现我们可以贪心地令\(L_i\)表示\([1,i]\)中最多可以选几个数使得它们的和不超过\(x\)，\(R_i\)同理表示\([i,n]\)中最多可以选几个数使得它们的和不超过\(x\)

维护\(L_i,R_i\)的过程显然直接用堆维护下当前选择的元素，然后如果和超过\(x\)就弹出最大的即可

最后只要验证是否存在\(L_i+R_{i+1}\ge k\)即可，总复杂度也是两个\(\log n\)的，不过比前一个好写

#include<cstdio>
#include<iostream>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,k,a[N],L[N],R[N]; long long sum;
inline bool check(const long long& x)
{
	RI i; long long pfx=0; priority_queue <int> hp;
	for (i=1;i<=n;++i)
	{
		hp.push(a[i]); pfx+=a[i];
		while (pfx>x) pfx-=hp.top(),hp.pop();
		L[i]=hp.size();
	}
	while (!hp.empty()) hp.pop();
	for (pfx=0,i=n;i>=1;--i)
	{
		hp.push(a[i]); pfx+=a[i];
		while (pfx>x) pfx-=hp.top(),hp.pop();
		R[i]=hp.size();
	}
	for (i=1;i<=n;++i) if (L[i-1]+R[i]>=k) return 1;
	return 0;
}
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",&n,&k),i=1;i<=n;++i)
		scanf("%d",&a[i]),sum+=a[i];
		long long l=0,r=sum,mid,ret=0;
		while (l<=r) if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
		printf("%lld\n",ret);
	}
	return 0;
}