送信卒

Subtask1, 2

首先我们将一条路径用 $(w, h)$ 表示，意为这条路径有 $w$ 次水平移动，$h$ 次垂直移动。

考虑将所有从 $S$ 至 $T$ 的可能形成最短路径的路（即找不到另一条路 $w, h$ 都不大于它）都找出来。计算每条路为最短路时的 $k$ 值，取最大的即可。

Subtask3

注意到 $k$ 越大，最短路的长度肯定不减，所以 $k$ 值可以二分。每次二分一个 $k$，跑最短路 (Dijkstra) 检验即可。时间复杂度为 $O((n+m) \log n \cdot \log s)$。

#include <cstdio>
#include <queue>
#include <tuple>
#include <algorithm>
#define eps (1e-4)
#define mp std::make_tuple
#define ld double
using std::tuple;
using std::priority_queue;
const int N=105;
int n, m, sx, sy, tx, ty;
ld s, k, dis[N][N];
int a[N][N];
priority_queue<tuple<ld, int, int> > q;
inline void upt(int x, int y, ld f)
{
	if(a[x][y]||!x|!y||x>n||y>m||dis[x][y]<=f+eps) return;
	dis[x][y]=f;
	q.push(mp(-f, x, y));
}
void dij(void)
{
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) dis[i][j]=1e9;
	dis[sx][sy]=0;
	q.push(mp(0, sx, sy));
	while(!q.empty())
	{
		auto t=q.top();
		q.pop();
		int x=std::get<1>(t), y=std::get<2>(t);
		if(-std::get<0>(t)!=dis[x][y]) continue;
		ld d=dis[x][y];
		upt(x, y-1, d+1);
		upt(x, y+1, d+1);
		upt(x-1, y, d+k);
		upt(x+1, y, d+k);
	}
}
bool chk(ld c)
{
	k=c;
	dij();
	return s<=dis[tx][ty]+eps;
}
int main()
{
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%d", a[i]+j);
	scanf("%lf", &s);
	ld l=0, r=s;
	while(r-l>eps)
	{
		ld mid=(l+r)/2;
		if(chk(mid)) r=mid;
		else l=mid;
	}
	printf("%.3lf\n", l+(5e-5));
	return 0;
}

星际联邦

做法比较多，可以直接用 Prim 来做，但最简单的做法仍然是考虑 Borůvka 算法，我们在每一轮需要找到这个点向外到另一个联通块内的最小边。注意到当 $i$ 固定时，最小边要么是前缀 $[1, i)$ 的最大值取到的，要么是 $(i, n]$ 内的最小值取到的。我们只需要对每个前缀维护最大值，以及和最大值不在同一个联通块内的最大值，就可以快速求出该联通块向外的最小边。总的时间复杂度为 $O(n \log n)$。

#include <bits/stdc++.h>

const int N = 3e5 + 50;

int x[N], f[N], pre[N][2], suf[N][2];

inline int find(int x) {
	while (x != f[x])
		x = f[x] = f[f[x]];
	return x;
}

void push(int *A, int i, const auto &cmp) {
	if (!i) return;
	int fA0 = find(A[0]);
	int fA1 = find(A[1]);
	int fi = find(i);
	assert(A[0] == 0 || A[1] == 0 || fA0 != fA1);
	if (A[0] == 0 || cmp(x[A[0]], x[i])) {
		if (fi == fA0) {
			A[0] = i;
		}
		else {
			A[1] = A[0];
			A[0] = i;
		}
	}
	else if (A[1] == 0 || cmp(x[A[1]], x[i])) {
		if (fi != fA0) {
			A[1] = i;
		}
	}
}


void push_max(int *A, int i) {
	push(A, i, std::less<int>());
}
void push_min(int *A, int i) {
	push(A, i, std::greater<int>());
}
int take(int *A, int i) {
	if (find(i) != find(A[0]))
		return A[0];
	return A[1];
}
int val(int i, int j) {
	if (i > j) std::swap(i, j);
	return x[j] - x[i];
}

int to[N], to_v[N];
int64_t solve() {
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i) {
		std::cin >> x[i];
		f[i] = i;
	}
	int comp = n;
	int64_t ans = 0;
	while (comp > 1) {
		for (int i = 0; i <= n + 1; ++i) {
			pre[i][1] = pre[i][0] = suf[i][0] = suf[i][1] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			if (i != 1) {
				push_max(pre[i], pre[i - 1][0]);
				push_max(pre[i], pre[i - 1][1]);
			}
			push_max(pre[i], i);
		}
		for (int i = n; i >= 1; --i) {
			if (i != n) {
				push_min(suf[i], suf[i + 1][0]);
				push_min(suf[i], suf[i + 1][1]);
			}
			push_min(suf[i], i);
		}
		for (int i = 1; i <= n; ++i) {
			to[i] = 0;
			to_v[i] = 2e9 + 50;
		}
		for (int i = 1; i <= n; ++i) {
			int pre_max = take(pre[i], i), pv = val(pre_max, i);
			int suf_min = take(suf[i], i), sv = val(suf_min, i);
			int o = find(i);
			assert(find(pre_max) != i);
			assert(find(suf_min) != i);
			if (pre_max && pv < to_v[o]) {
				to_v[o] = pv;
				to[o] = pre_max;
			}
			if (suf_min && sv < to_v[o]) {
				to_v[o] = sv;
				to[o] = suf_min;
			}
		}
		for (int i = 1; i <= n; ++i)
			if (i == find(i) && find(i) != find(to[i])) {
				--comp;
				ans += to_v[i];
				f[find(i)] = find(to[i]);
			}
	}
	return ans;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t=1;
	while (t--) {
		std::cout << solve() << '\n';
	}
}

对称旅行者

考虑先求旅行者 $i$ 的期望位置，设为 $f_i$，那么答案就为 $f_i * 2^{m K}$。

当旅行者 $i$ 旅行时时，由于期望的线性性，$f_i \longleftarrow \frac{1}{2}\left(2 f_{i-1}-f_i+2 f_{i+1}-f_i\right)=f_{i-1}+f_{i+1}-f_i$，考虑其几何含义，发现是把 $f_i$ 关于 $f_{i-1}$ 和 $f_{i+1}$ 的中点对称，如果设 $g_i=f_{i+1}-f_i$，那么跳第 $i$ 枚棋子相当于交换 $g_{i-1}$ 和 $g_i$。

因此一轮旅行就对应一个 $1 \sim n-1$ 的置换，用类似快速幂的方法就可以求出 $K$ 轮旅行后的 $\left\{g_i\right\}$，再注意到 $f_1$ 始终不变，就可以求出所有棋子的期望位置，时间复杂度为 $O(n \log K)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e5+10,iv=(mod+1)/2;
inline int ksm(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
	return ret;
}
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;} 
int n,x[N],f[N],m,id[N],vis[N],stk[N],pos[N];
ll k;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&x[i]),f[i]=dec(x[i],x[i-1]),id[i]=i;
	scanf("%d%lld",&m,&k);
	for(int i=1,x;i<=m;++i) scanf("%d",&x),swap(id[x],id[x+1]);
	int del=ksm(2,1ll*m*(k%(mod-1))%(mod-1));
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			int now=i,top=0;
			while(!vis[now]){
				vis[now]=1;stk[top++]=now;
				now=id[now];
			}
			for(int i=0;i<top;++i) x[stk[i]]=f[stk[(i+k)%top]];
		}
	}
	for(int i=1;i<=n;++i) x[i]=add(x[i-1],x[i]),printf("%d ",1ll*x[i]*del%mod);
	return 0;
}

和平精英

首先考虑枚举按位与和按位或的值，假设结果是 $val$，那么显然所有 $a_i<val$ 都应该放到 or 集合里，所有 $a_i>val$ 都应该放到 and 集合里，如果暴力 check 可以做到 $O(nQ)$，大概有 50pts。

考虑再发掘一些性质，考虑枚举 $val$ 的 popcount，设为 $p$，那么显然所有 $popcount(a_i)<p$ 都应该放到 or 集合里，所有 $popcount(a_i)>p$ 都应该放到 and 集合里，$popcount(a_i)=p$ 的把上面的结论拉下来发现这些数应当全部相等，如果暴力 check 可以做到 $O(nQ \log v)$，大概有 25pts。

然后考虑直接离线分治回答询问，可以轻松做到 $O(n\log^2 n)$，如果你不幸写了一个根号复杂度，也可以获得多于暴力的分数。

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
inline char nc(){
	static char buf[500005],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,500000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	char ch=nc(); int sum=0;
	for(;ch<'0'||ch>'9';ch=nc());
	while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
	return sum;
}
int n,Q,a[maxn],pc[maxn]; bool ans[maxn];
struct node { int l,r,id; } q[maxn],T[maxn];
int A[maxn][31],O[maxn][31],c[maxn][31];
int ad[31],o[31],C[31];
void solve(int l,int r,int x,int y) {
	if(l>=r||x>y) return ; int mid=l+r>>1;
	for(int i=l;i<=r;i++) for(int j=0;j<=30;j++) A[i][j]=0x3fffffff,O[i][j]=c[i][j]=0;
	for(int i=mid+1;i<=r;i++) A[i][pc[i]]&=a[i],O[i][pc[i]]|=a[i],c[i][pc[i]]++,memcpy(A[i+1],A[i],124),memcpy(O[i+1],O[i],124),memcpy(c[i+1],c[i],124);
	for(int i=mid;i>=l;i--) A[i][pc[i]]&=a[i],O[i][pc[i]]|=a[i],c[i][pc[i]]++,memcpy(A[i-1],A[i],124),memcpy(O[i-1],O[i],124),memcpy(c[i-1],c[i],124);
	int pl=x-1,pr=y+1;
	for(int _=x;_<=y;_++) {
		if(q[_].r<=mid) T[++pl]=q[_]; else if(q[_].l>mid) T[--pr]=q[_];
		else {
			for(int i=0;i<=30;i++) ad[i]=A[q[_].l][i]&A[q[_].r][i],o[i]=O[q[_].r][i]|O[q[_].l][i],C[i]=c[q[_].l][i]+c[q[_].r][i];
			for(int i=0;i<=30;i++) if(ad[i]>=o[i]) {
				int L=0,R=0x3fffffff,cl=0,cr=0; for(int j=0;j<i;j++) L|=o[j],cl+=C[j]; for(int j=30;j>i;j--) R&=ad[j],cr+=C[j];
				ans[q[_].id]|=(C[i]==0)?(cl&&cr&&L==R):((C[i]==1)?((cl&&(L==(R&o[i])))||(cr&&(R==(L|o[i])))):((L|o[i])==(R&o[i])));
			}
		}
	} for(int i=x;i<=pl;i++) q[i]=T[i]; for(int i=pr;i<=y;i++) q[i]=T[i]; solve(l,mid,x,pl); solve(mid+1,r,pr,y);
}
int main() {
	n=read(),Q=read();
	for(int i=1;i<=n;i++) pc[i]=__builtin_popcount(a[i]=read());
	for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
	solve(1,n,1,Q);
	for(int i=1;i<=Q;i++) puts(ans[i]?"YES":"NO");
}