Preface

久违地VP一场，由于CCPC桂林在即因此最近就自主VP一下去年的CCPC

这场打的时候全队不在状态，签完到后我就因为A题一个corner case没考虑到卡了快两个小时

然后好不容易搞过去徐神上来有狂WA E题，最后也是喜提+11

后面写的D题也是需要特判，好家伙又是快到比赛结束才看出来

最后祁神写的线性的J做法也是细节写挂，我看要没时间了马上抢键盘上机去写了个二分，堪堪卡过下班

后面一看榜好家伙喜提8题倒一，赛后把感觉不难的L补了，感觉赛场上如果能腾一个多小时的话还是可以写出来的

A. Ban or Pick, What's the Trick

这题思路其实很简单，我们注意到\(k\)的范围很小，因此不妨将其放到状态里

设\(f_{i,j,k}\)表示双方操作\(i\)轮后，第一个队选了\(j\)个数，第二个队选了\(k\)个数时的答案

考虑每个队每回合的策略要么是选择自己没被ban的最大的数，要么是ban掉对面的没选没ban的最大的数

把两个数组分别从大到小排序后，不难发现其实每个队接下来要选的数的下标都是可以算出来的

然后要注意下第一个队转移时取\(\max\)，第二个队转移时取\(\min\)即可，还有转移顺序需要注意下，刚开始正着推WA了后才发现要倒着推

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e17;
int n,m,a[N],b[N],f[N<<1][12][12]; bool vis[N<<1][12][12];
inline int DP(CI x,CI y,CI z)
{
	if (x>2*n) return 0; if (vis[x][y][z]) return f[x][y][z];
	if (x%2==1)
	{
		int ret=-INF; if (y<m&&y+x/2-z+1<=n)
		ret=max(ret,DP(x+1,y+1,z)+a[y+x/2-z+1]);
		ret=max(ret,DP(x+1,y,z)); f[x][y][z]=ret;
	} else
	{
		int ret=INF; if (z<m&&z+(x+1)/2-y+1<=n)
		ret=min(ret,DP(x+1,y,z+1)-b[z+(x+1)/2-y+1]);
		ret=min(ret,DP(x+1,y,z)); f[x][y][z]=ret;
	}
	return vis[x][y][z]=1,f[x][y][z];
}
signed main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	RI i,j,k; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (i=1;i<=n;++i) scanf("%lld",&b[i]);
	sort(a+1,a+n+1,greater <int>()); sort(b+1,b+n+1,greater <int>());
	return printf("%lld",DP(1,0,0)),0;
}

B. Call Me Call Me

题目都没看，一眼做不来

C. Catch You Catch Me

签到题，对于\(1\)的每个儿子求出它子树中深度最大的点即可

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,x,y,mxd,ans; vector <int> v[N];
inline void DFS(CI now,CI fa=1,CI d=1)
{
	mxd=max(mxd,d); for (auto to:v[now]) if (to!=fa) DFS(to,now,d+1);
}
int main()
{
	//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (auto x:v[1]) mxd=0,DFS(x),ans+=mxd;
	return printf("%d",ans),0;
}

D. Gambler's Ruin

这题感觉比E简单多了，但不知道为什么过的人反而比E少

首先我们可以把所有人按照\(p_i\)从大到小排序，此时发现当第\(i\)个人选择下注BU时，第\(i'(i'<i)\)个人也一定会选择下注BU

同理当第\(j\)个人选择下注BC时，第\(j'(j'>j)\)个人也一定会选择下注BC

因此我们发现其实下注的一定是某段前缀和后缀，因此很容易通过确定端点来求出\(x=\frac{1}{p_i},y=\frac{1}{1-p_i}\)

然后把贡献的式子写出来会发现如果我们枚举\(j\)的位置，\(i\)的取值具有单峰性，因此可以三分求解最优的\(i\)

（刚开始列了枚举\(i\)的式子发现符号对不上，改为枚举\(j\)后发现就有性质了）

但是如果直接这么写的话会因为有很多相同的\(p_i\)导致单峰性失效，因此需要处理下把所有\(p_i\)相同的人合并成一个即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
typedef long double LDB;
const int N=1e6+5;
struct ifo
{
	int c; LDB p;
	friend inline bool operator < (const ifo& A,const ifo& B)
	{
		return A.p>B.p;
	}
}o[N],t[N]; int n,m,pfx[N],sfx[N]; LDB ans;
signed main()
{
	//freopen("D.in","r",stdin); freopen("D.out","w",stdout);
	RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%Lf%lld",&o[i].p,&o[i].c);
	for (sort(o+1,o+n+1),t[m=1]=o[1],i=2;i<=n;++i)
	if (o[i].p==t[m].p) t[m].c+=o[i].c; else t[++m]=o[i];
	for (i=1;i<=m;++i) pfx[i]=pfx[i-1]+t[i].c;
	for (i=m;i>=1;--i) sfx[i]=sfx[i+1]+t[i].c;
	for (i=1;i<=m;++i) if (t[i].p!=1.0L)
	{
		LDB y=1.0L/(1.0L-t[i].p); ans=max(ans,sfx[i]*(1.0L-y));
		auto calc=[&](CI j)
		{
			if (t[j].p==0.0L) return -1e18L; LDB x=1.0L/t[j].p;
			return pfx[j]+sfx[i]-max(pfx[j]*x,sfx[i]*y);
		};
		int l=1,r=i-1; while (r-l>2)
		{
			int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
			if (calc(lmid)>=calc(rmid)) r=rmid; else l=lmid;
		}
		int pos=l; for (j=l+1;j<=r;++j) if (calc(j)>calc(pos)) pos=j;
		ans=max(ans,calc(pos));
	}
	return printf("%.12Lf",ans),0;
}

E. Hammer to Fall

ORZ徐神

不难发现可以从后往前DP，求出从每个地方开始每个人逃跑需要的代价\(f_i\)，那么最后的答案就是\(\sum f_i\times a_i\)

把转移的式子写出来会发现其实每次转移就是单点修改，但每次修改会影响一个点所有相邻点

考虑用经典的根号分治来解决，度数小的点就直接暴力更新，否则把更新存起来，每过一段时间暴力遍历更新所有信息

但实际实现的时候需要用堆，因此复杂度是\(O(n\sqrt{n\log n})\)的（设\(n,m,q\)同阶），后面看了题解发现可以用nth_element做到严格\(O(n\sqrt n)\)，我只能呃呃

#include <bits/stdc++.h>

using llsi = __int128_t;

constexpr llsi mod = 998244353;

const int Q = 700;

int n, m, q;

struct edge {
	int to, w;
	inline friend bool operator < (const edge& a, const edge& b) {
		return a.to == b.to
			? a.w  < b.w
			: a.to < b.to;
	}
};

struct info {
	llsi val;
	int to, tt;
	inline friend operator <(const info &a, const info &b) {
		return a.val > b.val;
	}
};

int a[100010];
llsi dp[100010];
std::vector<edge> out[100010];
int timeTag[100010];

int b[100010];

std::priority_queue<info> upd[100010];
std::vector<int> ss;

void rebuild() {
	ss.clear();
	for(int i = 1; i <= n; ++i) {
		if(out[i].size() <= Q) continue;
		upd[i] = {};
		for(auto [to, w]: out[i]) upd[i].push({dp[to] + w, to, timeTag[to]});
	}
	return ;
}

void update(int now) {
	timeTag[now] += 1;
	ss.push_back(now);
	dp[now] = 1e18;
	if(out[now].size() <= Q) {
		for(auto [to, w]: out[now]) dp[now] = std::min(dp[now], dp[to] + w);
		return ;
	}
	while(upd[now].size()) {
		auto [val, to, tt] = upd[now].top();
		if(tt != timeTag[to]) { upd[now].pop(); continue; }
		dp[now] = val; break;
	}
	for(auto s: ss) {
		auto it = std::lower_bound(out[now].begin(), out[now].end(), edge{s, 0});
		if(it == out[now].end() || it->to != s) continue;
		dp[now] = std::min(dp[now], it->w + dp[s]);
	}
}

int32_t main() {
	// freopen("2.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	std::cin >> n >> m >> q;
	for(int i = 1; i <= n; ++i) out[i].clear(), dp[i] = 0ll, std::cin >> a[i];
	for(int i = 1, f, t, w; i <= m; ++i) {
		std::cin >> f >> t >> w;
		out[f].push_back({t, w});
		out[t].push_back({f, w});
	}
	for(int i = 1; i <= n; ++i)
		std::sort(out[i].begin(), out[i].end());
	for(int i = 1; i <= q; ++i) std::cin >> b[i];
	
	int cc = Q - 1;
	for(int i = q; i; --i) {
		if(b[i] == b[i + 1]) continue;
		if(++cc == Q) rebuild(), cc = 0;
		update(b[i]);
		// for(int j = 1; j <= n; ++j) std::cout << dp[j] << char(j == n ? 10 : 32);
	}
	llsi ans = 0;
	for(int i = 1; i <= n; ++i) ans = (ans + dp[i] * a[i]) % mod;
	std::cout << int(ans % mod) << std::endl;
	return 0;
}

F. Infinite Strife

什么神仙题到现在CF上也没人过，查询jiangly状态

G. Let Them Eat Cake

签到题，不难发现每次相邻两个数中至少有一个数要被删掉，因此直接模拟的复杂度是正确的

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
int n; vector <int> a;
int main()
{
	//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
	RI i; for (scanf("%d",&n),a.resize(n),i=0;i<n;++i) scanf("%d",&a[i]);
	int ans=0; while (a.size()>1) 
	{
		vector <int> b; ++ans;
		if (a[0]>=a[1]) b.push_back(a[0]);
		for (i=1;i<a.size()-1;++i)
		if (a[i]>=a[i-1]&&a[i]>=a[i+1]) b.push_back(a[i]);
		if (a.back()>=a[a.size()-2]) b.push_back(a.back());
		a=b;
	}
	return printf("%d",ans),0;
}

H. Life is Hard and Undecidable, but...

题目巨长，但构造方法很简单，直接搞一个长为\(2k+1\)的斜线即可

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	int n;
	std::cin >> n;
	n = 2 * n - 1;
	std::cout << n << '\n';
	for(int i = 1; i <= n; ++i) std::cout << i << ' ' << i << '\n';
	return 0;
}

I. Mental Abuse To Humans

数论，做不了一点

J. Middle Race

伪交互题，其实是个传统题的说

不妨尝试找出三元组\((x,y,z)\)，使得\(x+y+z=n\)且使得\(|Ax+By+Cz-\frac{n\times (A+B+C)}{3}|\)的值最小

不难发现当最后恰取\(x\)个\(A\)，\(y\)个\(B\)，\(z\)个\(C\)时一定获胜、

证明的话考虑设此时玩家的得分为\(\frac{n\times (A+B+C)}{3}+\Delta\)，不妨设\(\Delta>0\)，则另外两个人的得分一定为\(\frac{n\times (A+B+C)}{3}+\Delta',\frac{n\times (A+B+C)}{3}-\Delta-\Delta'(\Delta'>\Delta)\)，满足题意

实现的话可以枚举\(x\)的值，然后二分\(y\)的取值，当然也可以像祁神一样直接推\(O(1)\)的式子

以下代码是比赛时写的二分，由于是直接在祁深代码上改的，风格会不太同意

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t, n, a, b, c;
int na, nb, nc;
int sum;



signed main() {
//	ios::sync_with_stdio(false);
	cin >> t;
	while(t--) {
		cin >> n >> a >> b >> c;
		
		a*=3; b*=3; c*=3;
		
		int sum=(a+b+c)*n;
		
		int t[3]={a,b,c}; sort(t,t+3);
		a=t[0]; b=t[1]; c=t[2];
		na=n; nb=0; nc=0; int ans=abs(sum/3-na*a);
		for (int i=0;i<=n;++i)
		{
			int left=sum/3-i*a; if (left<0) continue;
			auto calc=[&](const int& x)
			{
				return x*b+(n-i-x)*c;
			};
			int l=0,r=n-i,mid,LB,RB;
			while (l<=r) if (calc(mid=l+r>>1)<=left) LB=mid,r=mid-1; else l=mid+1;
			l=0; r=n-i;
			while (l<=r) if (calc(mid=l+r>>1)>=left) RB=mid,l=mid+1; else r=mid-1;
			if (abs(sum/3-(i*a+LB*b+(n-i-LB)*c))<ans) ans=abs(sum/3-(i*a+LB*b+(n-i-LB)*c)),na=i,nb=LB,nc=n-i-LB;
			if (abs(sum/3-(i*a+RB*b+(n-i-RB)*c))<ans) ans=abs(sum/3-(i*a+RB*b+(n-i-RB)*c)),na=i,nb=RB,nc=n-i-RB;
		}
		
		//printf("na=%d nb=%d nc=%d\n", na, nb, nc);

		a/=3; b/=3; c/=3;
		
		for (int i=1; i<=na; ++i){
			int x, y;
			cout << a << endl;
			cin >> x >> y;
		}
		for (int i=1; i<=nb; ++i){
			int x, y;
			cout << b << endl;
			cin >> x >> y;
		}
		for (int i=1; i<=nc; ++i){
			int x, y;
			cout << c << endl;
			cin >> x >> y;
		}
	}
	return 0;
}

K. Pattern Matching in A Minor “Low Space”

什么论文题，我要是会做我就去发Paper了

L. Por Una Cabeza

题意很长，但搞清楚后就不难了的说

不难发现对于任意一个机器，设它的输入有\(2k+1\)个，而限制要求它的前\(2k\)个输入中\(0,1\)的个数要相等

而最晚的那个输入的内容和时间就决定了这个机器的输出内容和时间，因此我们可以直接用这个输入来替换掉这个机器

不难发现最后所有编号不为\(n\)的人一定唯一对应一个机器产生贡献，而每个机器此时一定有\(2k\)个输入

一个trivial的想法就是对于每个点开权值线段树维护\(0/1\)对于的代价，假设此时\(0\)的个数\(x>k\)，则我们要取权值最小的\(x-k\)个\(0\)，在线段树上二分查询即可

但实际上有一种更好的实现方法，以维护\(0\)为例，当它的个数不超过\(k\)时，我们把权值扔进小根堆里

而超过\(k\)后我们每次把小根堆的堆顶扔进一个大根堆中，大根堆中的权值和就是修改的代价

每次删除时讨论下这个数的位置，如果在大根堆中就直接删，否则就删去小根堆中对应的数后，把大根堆的堆顶扔回小根堆即可

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

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,m,q,a[N],b[N],dt[N],bel[N],x,y,z,tp[N],ans;
struct DS
{
	set <pi> gt,ls; int lim;
	inline void insert(CI id,CI x)
	{
		ls.insert(pi(x,id)); tp[id]=0;
		if (ls.size()>lim)
		{
			pi tmp=*ls.begin(); ls.erase(tmp);
			ans+=tmp.fi; tp[tmp.se]=1; gt.insert(tmp);
		}
	}
	inline void erase(CI id,CI x)
	{
		if (tp[id]) ans-=x,gt.erase(pi(x,id)); else
		{
			ls.erase(pi(x,id)); if (gt.empty()) return;
			pi tmp=*gt.rbegin(); gt.erase(tmp);
			ans-=tmp.fi; tp[tmp.se]=0; ls.insert(tmp);
		}
	}
}S[N][2];
signed main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	RI i,j; for (scanf("%lld%lld%lld",&n,&m,&q),i=1;i<=n;++i)
	scanf("%lld%lld",&a[i],&b[i]),dt[i]=i;
	for (i=1;i<=m;++i)
	{
		scanf("%lld",&x); vector <int> son;
		for (j=0;j<x;++j) 
		{
			if (scanf("%lld",&y),y<0) y=n-y;
			son.push_back(y);
		}
		auto cmp=[&](CI x,CI y)
		{
			return dt[x]<dt[y];
		};
		sort(son.begin(),son.end(),cmp);
		for (j=0;j<x-1;++j) bel[dt[son[j]]]=i;
		S[i][0].lim=S[i][1].lim=(x-1)/2; dt[n+i]=dt[son.back()];
	}
	for (i=1;i<n;++i) S[bel[i]][a[i]].insert(i,b[i]);
	for (i=1;i<=q;++i)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		if (x!=n)
		{
			S[bel[x]][a[x]].erase(x,b[x]);
			S[bel[x]][a[x]=y].insert(x,b[x]=z);
		} 
		printf("%lld\n",ans);
	}
	return 0;
}

M. Rock-Paper-Scissors Pyramid

ORZ徐神一眼秒了此题

考虑用一个栈来从左到右维护，若当前元素可以战胜或打平栈顶的话就直接弹出栈顶，否则就把它压入栈中，最后栈底的元素就是答案

证明的话可以用类似于归纳法的方式，当然题解中给了中更妙的做法甚至可以处理单点修改和区间询问，只能说确实牛逼

#include <bits/stdc++.h>

char sta[1000001];
int t, top = 0;

char ko[128][128];

int main() {
	// freopen("1.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	ko['S']['P'] = ko['S']['S'] = 1;
	ko['P']['R'] = ko['P']['P'] = 1;
	ko['R']['S'] = ko['S']['S'] = 1;
	std::cin >> t; while(t--) {
		std::string s;
		std::cin >> s;
		top = 0;
		for(char c: s) {
			while(top && ko[c][sta[top]]) top -= 1;
			sta[++top] = c;
		}
		std::cout << sta[1] << '\n';
	}
	return 0;
}