CF1715.

A. Crossmarket

钦定 \(n \ge m\)。

不难发现，最优操作方式一定是一个先走完 \((n-1) + (m-1)\) 的路程，另一个只需要走 \((m-1)\) 的路程加上 \(1\) 的传送即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t, n, m;
void solve() {
	n=read(), m=read();
	if(n==1&&m==1) { puts("0"); return; }
	if(n<m) swap(n,m);
	printf("%lld\n",(n-1)+(m-1)+(m-1)+1);
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Beautiful Array

既然是构造题，那么我们可以乱搞。

考虑如果 \(a_i < k\)，那么不会对序列的 beauty 产生贡献。

由于存在向下取整，所以序列的和最小是 \(k \cdot b\)，如果 \(k \cdot b > s\)，那么无解。

让 \(a_1\) 为 \(\min(k \cdot (b+1)-1,s)\)，如果 \(s - a_1\) 之后还有剩余，那么就贪心地在后面放上不超过 \(k\) 的数字就行了。

如果没有位置可以放的时候，\(s\) 仍然大于 \(0\)，那么无解。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, k, b, s, a[N];
void solve() {
	n=read(), k=read(), b=read(), s=read();
	if(k*b>s) { puts("-1"); return; }
	for(int i=1;i<=n;++i) a[i]=0;
	int t=k*(b+1)-1;
	if(t>s) t-=t-s;
	a[1]=t;
	s-=t;
	for(int i=2;i<=n;++i) {
		if(!s) break;
		if(s>=k-1) a[i]=k-1, s-=(k-1);
		else if(s>0) a[i]=s, s=0;
	}
	if(s!=0) { puts("-1"); return; }
	for(int i=1;i<=n;++i) printf("%lld%c",a[i]," \n"[i==n]);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Monoblock

先求出原序列的值，考虑每个数的贡献。

不太好想，举个例子。假设 \(1,2\) 的贡献已经计算完毕，现在要在后面加入一个 \(3\)。不难发现，所有以 \(3\) 结尾的前缀，\(1,2,3\)，\(2,3\)，\(3\) 中都存在 \(3\) 的 \(1\) 个贡献，所以这部分的贡献是 \(3\)。而由于这 \(3\) 段都是新加入的，所以也要计算 \(1\) 和 \(2\) 的贡献。不难发现这就是一个相同的问题，以 \(2\) 结尾的前缀的个数加上以 \(1\) 结尾的前缀的个数。

而如果加入的是 \(2\) 呢？则只会让以 \(2\) 结尾的前缀个数增加 \(1\)，其他是相同的。

形式化地，设 \(pre\) 为所有 \(k \in [1,i-1]\)，以 \(k\) 结尾的前缀的数量，\(ans\) 为 \([1,i-1]\) 的贡献。加入 \(a_i\)

假设 \(a_1,\ldots a_{i-1}\) 的贡献已经计算完毕，那么插入 \(a_i\) 时，如果 \(a_{i} \neq a_{i-1}\)，那么令 \(pre + i\)，\(ans + pre\)。否则令 \(pre+1\)，\(ans + pre\)。

对于修改操作，如果 \(a_i \neq a_{i-1}\) 且 \(x = a_{i-1}\)，那么左端点在 \([1,i-1]\)，右端点在 \([i,n]\) 中的区间，其贡献都会减少 \(1\)，所以要减去 \((i-1) \cdot (n-i+1)\)。同理，如果 \(a_i \neq a_{i+1}\) 且 \(x = a_{i+1}\)，那么就要减去 \(i \cdot (n-i)\)。

反过来，如果 \(a_i = a_{i-1}\) 且 \(x \neq a_{i-1}\) 或者 \(a_i = a_{i+1}\) 且 \(x \neq a_{i+1}\)，那么就要加上对应的值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, m, cnt, a[N], b[N];
void solve() {
	n=read(), m=read();
	int ans=1, pre=1;
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=2;i<=n;++i) {
		if(a[i]!=a[i-1]) pre+=i, ans+=pre;
		else ++pre, ans+=pre;
	}
	while(m--) {
		int i=read(), x=read();
		if(a[i]==x) { printf("%lld\n",ans); continue; }
		if(x==a[i-1]&&a[i]!=a[i-1]) ans-=(i-1)*(n-i+1);
		else if(x!=a[i-1]&&a[i]==a[i-1]) ans+=(i-1)*(n-i+1);
		if(x==a[i+1]&&a[i]!=a[i+1]) ans-=i*(n-i);
		else if(x!=a[i+1]&&a[i]==a[i+1]) ans+=i*(n-i);
		a[i]=x;
		printf("%lld\n",ans);
	}
}
signed main() {
	solve();
}

D. 2+ doors

设 \(g(k,x)\) 为 \(x\) 二进制中的第 \(k\) 位。

如果 \(a_i | a_j = x\)，那么如果 \(g(k,x)=0\)，那么一定有 \(g(k,a_i) = g(k,a_j) = 0\)。

考虑反着构造，先将每个 \(a_i\) 赋值为 \(2^{30} - 1\)。

对于一组 \((i,j,x)\)，如果 \(i \neq j\)，那么就执行上述操作。

执行完之后，\(a_i | a_j\) 必然等于 \(k\)，下面着手减小它的字典序。

对于一个 \(i\)，枚举其为 \(1\) 的位 \(k\)，找到所有与 \(i\) 有关的 \((j,x)\)，如果上满足存在一组 \((j,x)\)，满足 \(g(k,a_j) = 1\) 且 \(g(k,x) = 0\)，那么就将 \(g(k,a_1)\) 改为 \(0\)。

这样做会导致其他的 \((j,x)\) 不满足条件，但为什么是最优解呢？因为数据保证有解，由于枚举 \(i\) 是从前往后，所以减小靠前的数要优于减小靠后的数，且可以通过修改 \(a_j\) 的方式重新满足条件。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int n, q, a[N];
bool v[N];
vector<pair<int,int> > w[N];
signed main() {
	n=read(), q=read();
	for(int i=1;i<=n;++i) a[i]=(1<<30)-1;
	while(q--) {
		int i=read(), j=read(), x=read();
		if(i==j) {
			a[i]=x, v[i]=1;
			continue;
		}
		for(int k=29;~k;--k) {
			if(x>>k&1) continue;
			if(a[i]>>k&1) a[i]^=1<<k;
			if(a[j]>>k&1) a[j]^=1<<k;
		}
		w[i].push_back({j,x});
		w[j].push_back({i,x});
	}
	for(int i=1;i<=n;++i) if(!v[i]) {
		for(int j=29;~j;--j) {
			if(!(a[i]>>j&1)) continue;
			bool fg=1;
			for(auto p:w[i]) {
				#define x first
				#define y second
				if((p.y>>j&1)&&!(a[p.x]>>j&1)) { fg=0; break; }
			}
			if(fg) a[i]^=1<<j;
		}
	}
	for(int i=1;i<=n;++i) printf("%lld%c",a[i]," \n"[i==n]);
}