Preface

沉迷Galgame不打CF懒狗闪总出列！

这场在大物课上口胡了前四个题，回去写了也都很顺，然后E题本来做不来的，看了眼昨天校队群里的消息就会做了

F题什么东西直接弃

A. Sum of Three

当\(n\bmod 3\ne 0\)时，用\((1,2,z)\)来凑；否则当\(n\bmod 3=0\)时，用\((1,4,z)\)来凑

#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_set>
#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;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d",&n),n%3)
		{
			int left=n-1-2;
			if (left<=0||left==1||left==2) { puts("NO"); continue; }
			printf("YES\n1 2 %d\n",left);
		} else
		{
			int left=n-1-4;
			if (left<=0||left==1||left==4) { puts("NO"); continue; }
			printf("YES\n1 4 %d\n",left);
		}
	}
	return 0;
}

B. Fear of the Dark

简单讨论下会发现可能的走法只有四种，\(O\to A \to P;O\to B\to P;O\to A\to B\to P;O\to B\to A\to P\)，取最短的那个即可

#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_set>
#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 pi O=mp(0,0);
int t; pi P,A,B;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d%d%d%d",&P.fi,&P.se,&A.fi,&A.se,&B.fi,&B.se);
		auto dist=[&](const pi& A,const pi& B)
		{
			return sqrt((A.fi-B.fi)*(A.fi-B.fi)+(A.se-B.se)*(A.se-B.se));
		};
		double OA=dist(O,A),OB=dist(O,B),AP=dist(A,P),BP=dist(B,P),AB=dist(A,B);
		printf("%.10lf\n",min({max(OA,AP),max(OB,BP),max({OA,AB/2.0,BP}),max({OB,AB/2.0,AP})}));
	}
	return 0;
}

C. Decreasing String

首先考虑对于一个给定的字符串\(s\)，删去哪个字符能使得其字典序最小

简单手玩一下会发现其实就是第一个满足\(s_{i+1}<s_i\)的位置\(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_set>
#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=1e6+5;
int t,n,pos,vis[N],ers[N],stk[N],top,cnt; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; scanf("%s%lld",s+1,&pos); n=strlen(s+1);
		for (top=cnt=0,i=1;i<=n;++i)
		{
			while (top&&s[i]<s[stk[top]]) ers[++cnt]=stk[top--];
			stk[++top]=i;
		}
		while (top) ers[++cnt]=stk[top--];
		if (pos<=n) { putchar(s[pos]); continue; }
		int sum=n; for (i=1;i<=n;++i)
		if (pos<=sum+(n-i))
		{
			vis[ers[i]]=1; pos-=sum;
			for (j=1;j<=n;++j) if (!vis[j])
			if (!--pos) { putchar(s[j]); break; }
			break;
		} else sum+=(n-i),vis[ers[i]]=1;
		for (i=1;i<=n;++i) vis[i]=0;
	}
	return 0;
}

D. Monocarp and the Set

刚开始想了好多假算法，后面冷静思考发现原来是个丁真题

首先发现若\(s_1=?\)的话答案一定为\(0\)，否则对于这种排列计数我们有很经典的增量法

考虑已经处理了前\(i\)个数，我们可以把这些数之间的大小关系看作一个长为\(i\)的排列

此时考虑加入第\(i+1\)个数，不难发现如果此时的符号是\(<\)或\(>\)的话，新加入的数只有一种取法

否则这个数可以取中间任意一个位置的值，即有\(i+1-2=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_set>
#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=300005,mod=998244353;
int n,m,x,ans=1,inv[N]; char s[N],opt[10];
inline void init(CI n)
{
	inv[1]=1; for (RI i=2;i<=n;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%s",&n,&m,s+1),init(n),i=2;i<n;++i) ans=1LL*ans*(s[i]=='?'?i-1:1)%mod;
	if (s[1]=='?') puts("0"); else printf("%d\n",ans);
	for (i=1;i<=m;++i)
	{
		if (scanf("%d%s",&x,opt),x!=1)
		{
			ans=1LL*ans*(s[x]=='?'?inv[x-1]:1)%mod;
			ans=1LL*ans*(opt[0]=='?'?x-1:1)%mod;
		}
		if (s[x]=opt[0],s[1]=='?') puts("0"); else printf("%d\n",ans);
	}
	return 0;
}

E. I Wanna be the Team Leader

这个题还是出的挺好的，虽然我是纯靠学长的点拨才会的

考虑如果我们把所有人按照\(a_i\)从大到小排序，考虑最后被拉去写程序的人一定是某段前缀

证明的话很简单，如果最后选的人不是前缀的话，我们总可以通过将区间向前平移来得到仍然满足要求的解

同时进一步挖掘一下性质会发现此时去做某个项目的一定是一段连续区间的人，因为此时做一个项目需要的人数仅由其中\(a_i\)最小的那个人决定，因此肯定连续地选是最优的

有了这几点后再结合题目中的\(m\le 20\)的限制，很容易想到用状压DP求解（实际上朴素的想法就是枚举长为\(m\)的排列，然后很容易发现这东西就跟哈密顿通路一样显然可以状压优化）

具体地，我们设\(f_{mask}\)表示以及处理了状态为\(mask\)的项目后，最少要用多少长的前缀

为了优化转移我们还需要求出对于每个项目，从某个位置开始向后最少要多少个数才能满足要求，这个可以通过双指针预处理出来

最后要输出方案就记录下每个状态的转移点即可，总复杂度\(O(nm+m\times 2^m)\)

#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_set>
#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,M=20;
int n,m,a[N],b[M+5],id[N],nxt[M+5][N],f[(1<<M)+5],pre[(1<<M)+5]; vector <int> ans[M+5];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; if (scanf("%lld%lld",&n,&m),n<m) return puts("NO"),0;
	for (i=1;i<=n;++i) scanf("%lld",&a[i]),id[i]=i;
	for (i=0;i<m;++i) scanf("%lld",&b[i]);
	auto cmp=[&](CI x,CI y)
	{
		return a[x]>a[y];
	};
	for (sort(id+1,id+n+1,cmp),i=0;i<m;++i)
	{
		for (j=k=1;j<=n;++j)
		{
			while (k<=n&&b[i]>a[id[k]]*(k-j+1)) ++k;
			nxt[i][j]=k;
		}
	}
	for (i=1;i<(1<<m);++i) f[i]=n+1;
	for (i=0;i<(1<<m);++i) if (f[i]<n)
	{
		for (j=0;j<m;++j) if (!((i>>j)&1))
		if (nxt[j][f[i]+1]<f[i|(1<<j)])
		f[i|(1<<j)]=nxt[j][f[i]+1],pre[i|(1<<j)]=j;
	}
	if (f[(1<<m)-1]>n) return puts("NO"),0;
	for (int cur=(1<<m)-1;cur;)
	{
		int lst=cur^(1<<pre[cur]);
		for (i=f[lst]+1;i<=f[cur];++i) ans[pre[cur]].push_back(id[i]);
		cur=lst;
	}
	for (puts("YES"),i=0;i<m;++i)
	{
		printf("%d ",ans[i].size());
		for (auto x:ans[i]) printf("%d ",x); putchar('\n');
	}
	return 0;
}