Round 1

E

题意

已知a，b求 $|a^2-b^2|$ 在所有平方之差的绝对值集合中的位次。

解

通过 $(a+1)^2-a^2=2a+1$ 可知集合中包含所有的除1以外的奇数。再通过 $(a+2)^2-a^2=4a+4$ 可知集合包含所有4的倍数。那么集合中所有的数都被考虑到了吗？显然是的。因为我们发现当 $(a+b)^2-a^2$ 中 $b>2$ 时，若b为奇数则结果为奇数，b为偶数则结果一定能被4整除，所以集合中所有的数已经被表示完全。

G

题意

给定字符串S，求字符串T在S中连续的位置上能取多少个区间 $[u,v]$ 保证 $S[u,v]=T[u,v]$ 。

解

求位置上连续相同的的长度 $len$ ,可知 $ans=\sum \binom{len}{2}$

I

题意

切割铁棒将其分为 $a_1,a_2,a_3...a_n$ 的块，每次切割时将产生 $\min(l_1,l_2)*\lceil{\log_2(l_1+l_2)}\rceil$ 的代价，并且保证每次切割时不平衡度 $|l_1-l_2|$ 要不大于上次切割。求最小代价。

观察

首先，可以推出只要保证当前切割的不平衡度大于于左右两段下一次切割的不平衡度就可以保证最终不平衡度满足条件。因为切割类似于归并排序，我们可以将左右子树的切割排列的不平衡度从小到大排序，就可以保证最后的切割排列的不平衡度递减。其次，数组长度n很小可以满足 $n^3$ 的做法，想到区间DP。

解

用 $F_{l,r,i}$ 表示切割区间 $[l,r]$ 切割位置为 i 时的最小代价。朴素地想，转移为： $F_{l,r,i}=\min(\left\{F_{l,i,j}|l\le j\le i\right\})+\min(\left\{F_{i+1,r,j}|i+1\le j\le r\right\})+cost$ 上述中的 F 需要满足不平衡度的条件, $cost$ 表示代价。这样直接去转移的时间复杂度为 $n^4$ 的，无法通过。考虑是否可以进一步优化时间复杂度。

一种优化思路是对于可选的每一个方案按照其不平衡度排序，再维护前缀最小值，二分查询满足限制的最大位置就好了。这样优化的时间复杂度是 $n^3\log n$ 比较极限。值得注意的是如果直接开空间会超出内存限制，可以考虑优化不必要的空间来通过。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<ll,ll> PII;
const ll N = 430, INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

ll a[N];
vector<ll> f[N][N];
vector<PII> v[N][N];

ll Log(ll x) {
	ll res = 0, t = 1;
	while(t<x) res ++, t<<=1;
	return res;
}

void solve() {
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin>>a[i], a[i]+=a[i-1];
	for(int len=2;len<=n;len++) {
		for(int l=1;l+len-1<=n;l++) {
			int r = l+len-1;
			ll plus = Log(a[r]-a[l-1]);
			f[l][r].clear(); v[l][r].clear();
			f[l][r].resize(r,INF);
			for(int i=l;i<r;i++) {
				ll limit = abs(2*a[i]-a[l-1]-a[r]), sum = 0;
				int p = upper_bound(v[l][i].begin(),v[l][i].end(),(PII){limit,INF})-v[l][i].begin();
				if(i==l) ;
				else if(!p) continue;
				else sum += v[l][i][p-1].sec;
				int pp = upper_bound(v[i+1][r].begin(),v[i+1][r].end(),(PII){limit,INF})-v[i+1][r].begin();
				if(i==r-1) ;
				else if(!pp) continue;
				else sum += v[i+1][r][pp-1].sec;
				f[l][r][i] = sum+plus*min(a[r]-a[i],a[i]-a[l-1]);
				if(len<n) v[l][r].push_back({limit,f[l][r][i]});
			}
			sort(v[l][r].begin(),v[l][r].end());
			ll mn = INF;
			for(PII &p : v[l][r]) mn=min(mn,p.sec), p.sec=mn;
		}
	}
	for(int i=1;i<n;i++) {
		if(f[1][n][i] >= INF) cout << "-1 ";
		else cout << f[1][n][i] << ' ';
	}
	cout << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

K

题意

图上给每个节点连接的边标号，求从每个节点标号为1的边出发按照如下规则走过所有不同边的数量。

如果从编号为 $i$ 的边走到当前节点且边个数为t，那么就沿着编号为 $i\bmod t+1$ 的边走到下一个节点

解

如果我们将每一个节点内的每一种走法边视作单独的节点，无向边视作两个有向边，我们发现这样节点的入度等于出度等于 1。因此无论从什么节点出发最终的路径始终为一个环。我们统计环上不同边的数量就可以了。

L

题意

有 n 个数，q次查询，每次查询将编号为 p 的数增加 v 后有多少数满足比除自己以外一半及以上的数小。

解

我们需要一个数据结构支持查询区间和，单点修改，还能快速地查询中位数。我们想到可以使用树状数组（也可以是线段树）。由于数的范围在 $[1,10^9]$ ，因此需要先离散化。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 1000010, INF = 0x3f3f3f3f, mod = 998244353;

ll a[N], X[N], tt;
ll tree[N];
PII query[N];

int lowBit(int x) {return x&-x;}

void add(int x, int v) {
	while(x<N) tree[x]+=v, x+=lowBit(x);
}

ll count(int x) {
	ll res = 0;
	while(x) res+=tree[x], x-=lowBit(x);
	return res;
}

void solve() {
	int n, q; cin >> n >> q;
	tt = 0;
	for(int i=1;i<=n;i++) cin >> a[i], X[++tt] = a[i];
	for(int i=1;i<=q;i++) cin>>query[i].fir>>query[i].sec;
	for(int i=1;i<=q;i++) {
		X[++tt] = X[query[i].fir];
		X[query[i].fir] += query[i].sec;
	}
	sort(X+1,X+1+tt);
	tt = unique(X+1,X+1+tt)-X-1;
	for(int i=1;i<=tt;i++) tree[i] = 0;
	for(int i=1;i<=n;i++) {
		int p = lower_bound(X+1,X+1+tt,a[i])-X;
		add(p,1);
	}
	for(int i=1;i<=q;i++) {
		int k = query[i].sec;
		int p = lower_bound(X+1,X+1+tt,a[query[i].fir])-X;
		add(p,-1);
		a[query[i].fir] += k;
		p = lower_bound(X+1,X+1+tt,a[query[i].fir])-X;
		add(p,1);
		int l = 1, r = tt;
		while(l <= r) {
			int mid = (l+r) >> 1;
			if(count(mid) <= (n+1)/2) l = mid + 1;
			else r = mid - 1;
		}
		cout << count(r) << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

Round 2

A

题意

给定数组a，包含-1，0，1。求将-1替换成0或1后每种方案的连续1的段数之和。

解

我们在a[1]前添加一个0，一种确定方案的贡献为[0,1]的数量之和。也就是除了[0,0],[1,0],[1,1]其他情况都有贡献。我们定义cnt为-1的总数，cc为已经确定的-1的个数，那么 $ans=\sum_{i=0}^{i < n} 2^{cnt-cc}$

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 500010, INF = 0x3f3f3f3f, mod = 998244353;

int a[N];

ll qmi(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = res*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return res;
}

void solve() {
	int n; cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	int cnt = 0;
	for(int i=1;i<=n;i++) cnt += a[i]==-1;
	ll ans = 0;
	for(int i=0;i<n;i++) {
		if(a[i] == 1 || !a[i+1]) continue;
		int cc = (a[i]==-1)+(a[i+1]==-1);
		ans = (ans + qmi(2,cnt-cc))%mod;
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

B

题意

判断数组a中是否存在两个数异或后的值比两数之和小。

解

我们只用关注较小数的最高位。当较大数这一位为1时结果一定变小，否则一定变大或不变。排序后从大到小判断最高位是否已经有标记。然后将该数的每一位1的位置标记。

D

题意

在考虑未填满的空间会对物品造成损失下的背包问题。

Step 1

当填装的空间确定时，每包薯片的损失就确定了。我们可以考虑枚举空间。

Step 2

空间确定的情况下，题目转变为传统背包问题，但需要注意的是必须保证体积刚好为V，没有空。设空间为V,当前填如v体积的物品，每个物品的贡献为 $w_i = h_i-d_i*(V-v)$

Step 3

设 $F_{i,j}$ 表示当体积为 i 时，当前装了 j 体积的物品的最大价值。直接转移的时间复杂度为 $NV^2$ 通过不了。考虑优化。

解

当装入体积为 i 时，体积为 j 的物品最多放入 $\lfloor \frac{i}{j} \rfloor$ 个，我们可以使用 nth_element 函数得到最大的前 $\lfloor \frac{i}{j} \rfloor$ 个物品。这样时间复杂度显著提高。注意转移时要将初值赋成-INF因为有物品的贡献为负但也许要填入的情况。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const ll N = 600, INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;


ll f[N][N];
vector<PII> a[N];

void solve() {
	int n, v; cin >> n >> v;
	for(int i=1;i<=v;i++) a[i].clear();
	for(int i=1;i<=n;i++) {
		int h, s, d; cin >> h >> s >> d;
		a[s].push_back({h,d});
	}
	for(int i=1;i<=v;i++)
		for(int j=1;j<=v;j++) f[i][j] = -INF;
	for(int i=1;i<=v;i++) {
		for(int j=1;j<=i;j++) {
			vector<ll> w;
			for(PII p : a[j]) w.push_back(-p.fir+(ll)p.sec*(v-i));
			int k = min((int)w.size(),i/j);
			nth_element(w.begin(),w.begin()+k-1,w.end());
			for(int l=0;l<k;l++) {
				for(int m=v;m>=j;m--) {
					f[i][m] = max(f[i][m],f[i][m-j]-w[l]);
				}
			}
		}
	}
	ll ans = 0;
	for(int i=1;i<=v;i++) ans = max(ans, f[i][i]);
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

F

题意

懒得解释了

解

观察到首尾相接成环，因此任意一连串的区域将从两头开始着火。我们只能选择一个区域。贪心地想，选择更长的区域更好。因为这样才能保住更多的区域。而当区域长度超过 $2t$ 时能保住的区域将不再增大。可以先算出不做出操作每一个连续区域的一定能保住的区域，和做出操作后能多保的区域数量。

G

题意

一个多边形绕着点转，求最少旋转多少弧度多边形将不再覆盖新的点。

解

分类讨论。

如果旋转点在多边形外，那么答案就是 $2\pi$ ，因为多边形上有且只有一个点距离旋转点的距离最短。
如果旋转点在多边形内，先计算出所有顶点到旋转点的距离，取最远的顶点与旋转点相连，分割成若干旋转角，最大的旋转角 $(\le\pi)$ 为答案。

H

题意

q次询问，每次询问给出k，求在可以选择一条边的路程降低 $k*w[i]$ 情况下的最短路。

Step 1

一条边降低路程后，最短路一定要经过这条边，如果不经过，那么选择最短路上的边一定更优。我们考虑对每条边求从节点 1 到节点 n 经过这条边的最短路。

Step 2

预处理出经过一条边的最短路后，那么经过这条边的路程为 $S_i=sum_i+t_i-w_i*k$ 未知数为 k，由询问给出。

Step 3

我们在坐标系中画出 S-k 函数图象，发现答案取最底下的边围成的凸包。当询问 k 时，我们只需二分求出 k 在凸包上哪条边下面。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
const ll N = 200010, INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int n, m;

void Dijkstra(vector<vector<PII>> &h, vector<ll> &dis, vector<PLL> &edge, int st) {
	priority_queue<PLL,vector<PLL>,greater<PLL>> heap;
	vector<bool> vis(n+1);
	dis[st] = 0;
	heap.push({0,st});
	while(heap.size()) {
		auto t = heap.top(); heap.pop();
		if(vis[t.sec]) continue;
		vis[t.sec] = 1;
		for(PII v : h[t.sec]) {
			if(vis[v.fir]) continue;
			ll cost = edge[v.sec].fir;
			if(t.fir + cost < dis[v.fir]) {
				dis[v.fir] = t.fir + cost;
				heap.push({dis[v.fir],v.fir});
			}
		}
	}
}

void solve() {
	cin >> n >> m;
	vector<vector<PII>> h(n+1), g(n+1);
	vector<PLL> edge(m+1);
	vector<ll> dis1(n+1,INF), dis2(n+1,INF);
	for(int i=1;i<=m;i++) {
		ll u, v, t, w; cin >> u >> v >> t >> w; // 读入的时候别忘开long long
		h[u].push_back({v,i});
		g[v].push_back({u,i});
		edge[i] = {t,w};
	}
	Dijkstra(h,dis1,edge,1);
	Dijkstra(g,dis2,edge,n);
	vector<PLL> line;
	for(int u=1;u<=n;u++)
		for(PII v : h[u])
			line.push_back({edge[v.sec].fir+dis1[u]+dis2[v.fir],edge[v.sec].sec});

	sort(line.begin(),line.end(),[](PLL a, PLL b){return a.sec==b.sec?a.fir<b.fir:a.sec<b.sec;});
	
	vector<PLL> convex;
	convex.push_back({dis1[n],0});
	for(auto l : line) {
		while(convex.size()>1) {
			PLL p = convex[convex.size()-2], q = convex[convex.size()-1];
			if((__int128_t)(l.fir-q.fir)*(q.sec-p.sec)<=(__int128_t)(q.fir-p.fir)*(l.sec-q.sec)) convex.pop_back();
			else break;
		}
		convex.push_back(l);
	}
	auto f = [&convex](int i, ll k) {
		if(i < convex.size() && i > 0) return convex[i].fir-k*convex[i].sec;
		return INF;
	};
	int q; cin >> q;
	while(q--) {
		ll k; cin >> k;
		int l = 0, r = convex.size()-2;
		while(l<=r) {
			int mid = (l+r) >> 1;
			if(f(mid,k) > f(mid+1,k)) l = mid + 1;
			else r = mid - 1;
		}
		cout << f(l,k) << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

I

题意

给定 x，y $(x\ne y)$ ，和 $H(x) = (x\bmod k)+(k\bmod x)$ ，找到 k 使得 $H(x) = H(y)$ 。

解

我们假设 $x<y$ ， $k<x$ 那么 $x\bmod k = y\bmod k$ 。

$x\ne 1$ 时， $k = 1$ 是一种解。
$x=1$ 时，无论 k 取什么值都没有解。

L

题意

给出关系，在随机固定两个点不能配对的情况下求出其他点两两配对的总方案数。满足

除了固定点，都属于某一对。
两个点之间没有关系不能配对。
任意两点的关系对象不同。

解

不难发现在关系图中没有链，只有环。我们考虑有多少个奇环和偶环。

若奇环的个数大于2，则无解。
若奇环的个数等于2，则只能固定这两个奇环上的点，并且一个环上固定一个。
若没有奇环，不固定偶环上的点。长度大于2，则该个环有两种配对情况。否则只有一种。
若要固定一个偶环上的点，则需要将两个点都固定在该偶环上。保证两个点之间的距离为奇数边。所以贡献为 $\frac{n^2}{4}$ 。

M

题意

求满足条件的三元组 $(a,b,c)$ 数量

$1 \le a,b,c \le s$
$a+b>c,a+c>b,b+c>a$
$a\oplus b\oplus c \le l$
$(a,b,c)$ 构成的三角形若通过旋转相同则视为一个三角形

Step 1

观察数据s,l很大，考虑数位DP。

Step 2

我们先考虑 $a\le b\le c\le s$ 的情况。从高位向低位，需要满足

$a\oplus b\oplus c \le l$

当遍历到第i位时，有4种情况

$a_i=b_i$ or $a_i<b_i$
$b_i=c_i$ or $b_i<c_i$
$c_i=s_i$ or $c_i<s_i$
$a_i\oplus b_i\oplus c_i = l$ or $a_i\oplus b_i\oplus c_i < l$

Step 3

我们还需要满足 $a+b<c$ 。考虑当前位上和以前位上的情况。

如果前面出现 $a_{i-1}+b_{i-1}-c_{i-1} \le -2$ 此时无论后面的位是什么，始终 $a+b<c$ ，不满足条件
如果出现 $a_{i-1}+b_{i-1}-c_{i-1} = -1$ 则当前位
- $a_i+b_i-c_i=2$ 则对后续无贡献
- $a_i+b_i-c_i=1$ 则对后续贡献为 -1
如果出现 $a_{i-1}+b_{i-1}-c_{i-1} = 1$ 则当前位无论为什么都满足 $a+b>c$

Step 4

我们将 Step 2 和 Step 3 中的条件整合，我们发现一共有 $2^4 \times 3=48$ 种情况，考虑状压。设 $F_{i,j}$ 为第 i 为情况为 j 时的方案数。按照上述条件转移，不多赘述。

Step 5

答案为所有满足条件的状态 j

ans = \sum \left\{\begin{matrix} 2F_{n,j} \text{(a,b,c中有两个数相等)}\\ F_{n,j} \text{(a,b,c中任意两个数都不相等)} \end{matrix}\right.

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 200010, INF = 0x3f3f3f3f, mod = 998244353;

ll f[N][48];
// 状压
int idx(int a_b, int b_c, int c_s, int abc_l, int ab_c) {
	return a_b+b_c*2+c_s*4+abc_l*8+ab_c*16;
}

void solve() {
	string l, s; cin >> l >> s;
	int n = max(l.size(), s.size());
	string temp;
	for(int i=l.size();i<n;i++) temp += '0';
	for(int i=s.size();i<n;i++) temp += '0';
	if(l.size() < n) l = temp + l;
	if(s.size() < n) s = temp + s;
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<48;j++) f[i][j] = 0;
	f[0][idx(1,1,1,1,1)] = 1;
	for(int i=0;i<n;i++) {
		for(int st=0;st<48;st++) {
			int a_b = st%2;
			int b_c = st/2%2;
			int c_s = st/4%2;
			int abc_l = st/8%2;
			int ab_c = st/16%3;
			for(int j=0;j<8;j++) {
				int a = j%2, b = j/2%2, c = j/4%2;
				if(a_b && a>b) continue;
				if(b_c && b>c) continue;
				if(c_s && c>s[i]-'0') continue;
				if(abc_l && (a^b^c)>l[i]-'0') continue;
				if(ab_c == 2 && a+b <= c) continue;
				int ab = a_b && a==b;
				int bc = b_c && b==c;
				int cs = c_s && c==s[i]-'0';
				int abcl = abc_l && (a^b^c)==l[i]-'0';
				int abc;
				if(!ab_c) abc = 0;
				else if(ab_c==1 && a+b>c) abc = 0;
				else if(ab_c==1 && a+b==c) abc = 1;
				else if(ab_c==1) abc = 2;
				else if(ab_c==2 && a+b>c+1) abc = 1;
				else abc = 2;
				int nex = idx(ab,bc,cs,abcl,abc);
				f[i+1][nex] = (f[i+1][nex]+f[i][st])%mod;
			}
		}
	}
	int res = 0;
	for(int i=0;i<48;i++) {
		int ab_c = i/16%3;
		if(!ab_c) {
			int a_b = i%2;
			int b_c = i/2%2;
			if(a_b || b_c) res = (res+f[n][i])%mod;
			else res = res = (res+f[n][i]*2)%mod;
		}
	}
	cout << res << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

Round 3

A

题意

略

解

构造如下

\begin{pmatrix} 0 & 0 & 2 & 2 & 2 &\cdots\\ 0 & 0 & 0 & 3 & 3 &\\ 2 & 0 & 0 & 0 & 4 &\\ 2 & 3 & 0 & 0 & 0 &\\ 2 & 3 & 4 & 0 & 0 &\\ \vdots &&&&& \ddots \end{pmatrix}

B

题意

略

解

当 $c>a,b$ 先将 a，b 的最高位统一，设最高位在 t 处。接着将 a 左移使得 t 左边的每一位在 a 的最高位与 c 的最高位对住时它们一一对应相等。形如

\begin{matrix} & & & & & & & & t & & & \\ c: & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & \cdots\\ a: & & \gets & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & \cdots\\ b: & & & & & & & & \uparrow & 0 & 1 & \cdots\\ \end{matrix}

接着将 b 右移的同时跟新 a 与 c 右边部分的位。直到 a 与 c 完全相同，并且 b 等于 0 。此时再进行一次操作4就能使得 $a=b=c$ 。无解的情况只有当 $a=b=0$ 。

D

题意

给定01串 s 和 a，有如下两种操作

将连续的 a 个 1 变成 0
将连续的 a+1 个 0 变成 1

能否通过以上两种操作使得 s 全变成 1。

解

上面两个操作只要有一个能执行 1 次那么就能将 s 全变成 1。因为如果有长 a 的连续 1，那么可以将其都变成 0 后与右侧的 0 合并成长度为 a+1 的连续的 0 变成 1。循环往复，就能将所有 0 变成 1。

E

题意

给定长度为 n 的数组 a ，你可以选择两个数同时除以他们的公因数，或同时乘上任意一个数。问最后能否让数组的值全部相等。

解

考虑对每个数质因数分解。 $X = p_1^{b_1}\times p_2^{b_2}\times\cdots$ 对于每个质数 $p_i$ 我们都需要将其在每个数中次数 $b_i$ 相同。我们将这个质数在所有当前数中出现次数之和求得为 $sum_{p_i}$ ，因为每次操作是对两个数同时操作，我们发现我们改变不了 $sum_{p_i}$ 的奇偶性。但是对于 n 为奇数的情况我们可以钦定最终 $b_i$ 为奇数还是偶数，从而改变 $sum_{p_i}$ 的奇偶性使其与当前的奇偶性相同。综上

n 为奇数时一定可以相等
n 为偶数时
- $n=2$ 如果 $a_1=a_2$ 则可以，否则不行。
- $n>2$ 如果每个质数分解后的次数之和为奇数则不行，否则可以。

如果直接对数组 a 中的每一个数质因数分解，时间复杂度为 $N\sqrt N$ 不能通过。由于 $a_i$ 的范围并不大，考虑求出 $[1,10^{10}]$ 中所有数的质因数分解后的奇偶性情况即可。对于质数我们可以使用随机数。最后有

$\bigoplus_{i=1}^{i<=n}F(a_i)\left\{\begin{matrix} \ne 0\Rightarrow \text{NO} \\ = 0\Rightarrow \text{YES} \end{matrix}\right.$

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 1000010, INF = 0x3f3f3f3f, mod = 998244353;

mt19937_64 mt(time(0));

int a[N];
int primes[N], tt;
int isprime[N*5];
ull mp[N*5];

void init() {
	for(int i=2;i<N*5;i++) {
		if(!isprime[i]) primes[++tt] = i, mp[i] = mt();
		for(int j=1;primes[j]*i<N*5;j++) {
			if(!isprime[primes[j]*i]) isprime[primes[j]*i] = 1, mp[primes[j]*i] = mp[primes[j]] ^ mp[i];
			if(i%primes[j]==0) break;
		}
	}
}

void solve() {
	int n; cin >> n;
	int g = 0;
	for(int i=1;i<=n;i++) cin >> a[i], g = __gcd(g, a[i]);
	if(n&1) {
		cout << "YES\n";
		return ;
	}
	if(n==2) {
		if(a[1] == a[2]) cout << "YES\n";
		else cout << "NO\n";
		return ;
	}
	ull sum = 0;
	for(int i=1;i<=n;i++) sum ^= mp[a[i]];
	if(sum) cout << "NO\n";
	else cout << "YES\n";
}

signed main() {
	init();
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

H

题意

给定一棵树，和 n 个时间区间。每个时间区间不重合，并且每个时间区间内出现一个目标点。棋子从根出发，每 1 个时间单位朝目标点最短路径上前进 1 个节点。可以在任意时刻删除任意边。询问到达其中任意一个目标节点的最小时刻。

Step 1

棋子在任意时刻都不会往回跳，即往深度低的地方走，因为这样一定不优。

Step 2

对于每一个区间，我们都可以求出这个区间内能走到的最深节点的范围。因此对于一个区间 $[L,R]$ 我们可以先处理出在这个区间前棋子能走到的范围节点，然后沿着当前目标节点向上查询 $R-L+1$ 个节点看看是否已经到达。若已经到达那么棋子也能到达该节点，则第一次可到达的时间节点就为答案。否则我们可以更新出新的棋子可到达范围节点。

Step 3

直接向上一个一个查找时间复杂度为 $NM$ 显然不符合要求。我们可以通过树上倍增优化到 $N\log N$ 这是由于每个节点最多标记一次，均摊为N而非M。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 1000010, INF = 0x3f3f3f3f, mod = 998244353;

vector<int> h[N];
int d[N], fz[N][31], L, R, ans;
bool st[N];
struct node {
	int x, l, r;
} rg[N];

void dfs1(int u, int fa) {
	d[u] = d[fa] + 1;
	fz[u][0] = fa;
	for(int i=1;i<31;i++) {
		fz[u][i] = fz[fz[u][i-1]][i-1];
	}
	for(int v : h[u]) {
		dfs1(v, u);
	}
}

int dfs(int u) {
	int p, res = u;
	for(p=0;p<31 && !st[fz[u][p]];p++) ;
	p --;
	if(p>=0) res = dfs(fz[u][p]);
	return res;
}

void get(int &x, int dis) {
	for(int i=30;~i;i--) {
		if((dis>>i)&1) x = fz[x][i];
	}
}

void push(int x) {
	while(!st[x]) {
		st[x] = 1;
		x = fz[x][0];
	}
}

void go(int u) {
	int up = fz[dfs(u)][0];
	int l = d[u]-d[up], dis = R-L+1;
	if(l <= dis) {
		push(u);
		int w = L+l-1;
		ans = min(ans,w);
	} else {
		int p = u;
		get(p,l-dis);
		push(p);
	}
}

void solve() {
	int n, m; cin >> n >> m;
	for(int i=1;i<n;i++) {
		int u; cin >> u;
		h[u].push_back(i+1);
	}
	for(int i=1;i<=m;i++) {
		cin >> rg[i].x >> rg[i].l >> rg[i].r;
	}
	dfs1(1,0);
	st[1] = st[0] = 1, ans = INF;
	for(int i=1;i<=m;i++) {
		L = rg[i].l, R = rg[i].r;
		go(rg[i].x);
	}
	if(ans < INF) cout << ans << '\n';
	else cout << "-1\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_--) solve();
    return 0;
}

J

题意

略

解

考虑奇偶性。当 $x+y$ 为奇数时，我们发现游戏无法停止。因为停止的条件是有一个变成 0，这意味着只有当 $x=y$ 时游戏才有可能停止，此时 $x+y$ 为偶数。因此我们可以一边模拟一边判断什么时候两数和为奇数，否则就一定可以停止。并且我们发现操作等同于让较大数减去较小数，让较小数乘以2。只有开始有可能为两个奇数，后面都为偶数。因此我们可以一边判断一边除2，在两数之和为奇数的时候退出。并且回合数不会很多。

Round 4

B

题意

给定 $N\times M$ 的矩阵，已知起点为第一列，终点为最后一列，视野为 d。只能向上下或向右移动。判断从起点出发是否存在无法避免的死路。

解

先从左向右判断哪些点可以到达。在从右向左维护出每个点能走到的最大列。最后只需判断是否存在点能走到并且最大列和当前列的距离大于 d。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 200010, INF = 0x3f3f3f3f, mod = 998244353;

int a[N];

void solve() {
	int n, m, k; cin >> n >> m >> k;
	vector<vector<int>> mp(n+1,vector<int> (m+1)), r(n+1,vector<int> (m+1)), ok(n+1,vector<int> (m+1));
	for(int i=1;i<=n;i++) {
		string s; cin >> s;
		for(int j=1;j<=m;j++) mp[i][j] = s[j-1]-'0';
	}
	for(int i=1;i<=n;i++) r[i][m] = m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]) r[i][j] = j;
	for(int j=m-1;j;j--) {
		for(int i=1;i<=n;i++) if(!mp[i][j]) r[i][j] = r[i][j+1];
		for(int i=2;i<=n;i++) {
			if(!mp[i-1][j] && !mp[i][j]) r[i][j] = max(r[i-1][j],r[i][j]);
		}
		for(int i=n-1;i;i--) {
			if(!mp[i+1][j] && !mp[i][j]) r[i][j] = max(r[i+1][j],r[i][j]);
		}
	}
	
	for(int i=1;i<=n;i++) ok[i][1] = 1;
	for(int j=2;j<=m;j++) {
		for(int i=1;i<=n;i++) if(!mp[i][j]) ok[i][j] = ok[i][j-1];
		for(int i=2;i<=n;i++) {
			if(!mp[i-1][j] && !mp[i][j]) ok[i][j] = max(ok[i-1][j],ok[i][j]);
		}
		for(int i=n-1;i;i--) {
			if(!mp[i+1][j] && !mp[i][j]) ok[i][j] = max(ok[i+1][j],ok[i][j]);
		}
	}
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(ok[i][j] && r[i][j]!=m && r[i][j]-j >= k) {
				cout << "Yes\n";
				return ;
			}
		}
	}
	cout << "No\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--) solve();
    return 0;
}

F

题意

给定数组 a，和正整数 k。总价值为数组前 k 个数之和。可交换两个相邻的数，代价为 c。求总价值的最大值。

解

对于前 k 个数，如果移除一个数 $a_i$ 再移入 $a_j$ 增加的价值为 $a_j - a_i - (j-i)\times c$ 。我们可以分别求出移除 $a_i$ 的代价 $a_i+(k-i) \times c$ 和移入 $a_j$ 的收益 $a_j-(j-k)\times c$ 。分别放入小根堆和大根堆中每次交换堆顶元素。

G

题意

给定有效括号序列。序列中的每一个括号都有 $\frac{1}{2}$ 的概率消失。求能唯一还原括号序列的概率。

Step 1

将 "(" 视为 1 ，")" 视为 -1 。那么括号序列有效的条件变成任意位置的前缀和不为负。

Step 2

我们将消失的位置再唯一还原这一操作视为对于消失的位置可以任意交换，但都不能构成其他有效括号序列。如果一种括号消失的情况中存在交换两个括号使得能构成其他有效的括号序列，那么这种情况就不能唯一还原。

Step 3

我们可以在坐标系中画出前缀和值的变化情况。通过观察发现，交换 1 和 -1 的位置会使得中间值上下平移。如果 -1 在前，那么这段值会向上平移，显然一定可以构成一个符合条件的括号序列。如果 1 在前并且中间值有小于 2 的，才会出现不符合的情况。这正是我们想要的！

Step 4

处理出前缀和后，对于每一个为 “（” 的位置统计出右边最近的出现前缀和为 1 的位置。那么对于每一个从开始到最近的这个位置的 “）”都必须出现，对于从结尾到该位置的“）”都必须出现。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 1000010, INF = 0x3f3f3f3f, mod = 998244353;

ll qmi(ll a, ll b) {
	ll res = 1;
	a %= mod;
	while(b) {
		if(b&1) res = res*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return res;
}

int a[N], pre[N], r[N], cl[N];

void solve() {
	string s; cin >> s;
	int n = s.size();
	for(int i=1;i<=n;i++) {
		a[i] = s[i-1]=='(' ? 1 : -1;
		pre[i] = pre[i-1] + a[i];
		cl[i] = cl[i-1] + (s[i-1]=='(');
	}
	for(int i=n,j=n;i;i--) {
		if(pre[i] <= 1) j = i;
		r[i] = j;
	}
	ll i2 = qmi(2,mod-2);
	ll ans = qmi(i2,n/2)%mod;
	for(int i=1;i<=n;i++) {
		if(a[i] == 1) {
			int cr = -pre[r[i]]+cl[r[i]];
			ans = (ans+qmi(i2,cr)*qmi(i2,n/2-cl[i-1])%mod)%mod;
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_--) solve();
    return 0;
}

I

题意

将所有箱子在一定步数内推到目标点。

解

让每个连通块内的箱子找到最近的目标点，推过去就好了。如果过路径上有其他已经在目标点上的箱子，就将其移走，在将当前箱子推到该目标点上，让另一个箱子继续推到先前的目标点上即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 110, INF = 0x3f3f3f3f, mod = 998244353;

char g[N][N];
bool vis[N][N];
PII fa[N][N];
int fac[N][N];
int n, m, tt, tp;
vector<PII> path(200010);
vector<char> way(200010);

struct node{
	int x, y;
	char fac;
} ans[200010];

int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
char mov[] = {'U','D','L','R'}, remov[] = {'D','U','R','L'};

bool check(int x, int y) {
	if(g[x][y] == '#') return 1;
	queue<PII> que;
	que.push({x,y});
	vis[x][y] = 1;
	int tar = 0, box = 0;
	if(g[x][y] == '@') box ++;
	else if(g[x][y] == '*') tar++;
	while(que.size()) {
		auto t = que.front(); que.pop();
		for(int i=0;i<4;i++) {
			int tx = t.fir + dx[i], ty = t.sec + dy[i];
			if(vis[tx][ty] || tx<1 || tx >n || ty<1 || ty>m || g[tx][ty]=='#') continue;
			if(g[tx][ty] == '@') box ++;
			else if(g[tx][ty] == '*') tar++;
			que.push({tx,ty});
			vis[tx][ty] = 1;
		}
	}
	return tar == box;
}

void bfs(int x, int y) {
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j] = 0;
	queue<PII> que;
	que.push({x,y});
	vis[x][y] = 1;
	PII b, end = {x,y};
	while(que.size()) {
		auto t = que.front(); que.pop();
		if(g[t.fir][t.sec] == '@') { b = t; break;}
		for(int i=0;i<4;i++) {
			int tx = t.fir + dx[i], ty = t.sec + dy[i];
			if(vis[tx][ty] || tx<1 || tx >n || ty<1 || ty>m || g[tx][ty]=='#') continue;
			fa[tx][ty] = t;
			fac[tx][ty] = remov[i];
			vis[tx][ty] = 1;
			que.push({tx,ty});
		}
	}
	tp = 0;
	PII p = b;
	while(p!=end) {
		way[++tp] = fac[p.fir][p.sec];
		path[tp] = p;
		
		p = fa[p.fir][p.sec];
	}
	for(int i=1;i<=tp;i++) {
		if(i<=tp-1 && g[path[i+1].fir][path[i+1].sec] == '!') {
			int j = i+1, cnt = 0;
			while(j<=tp&&g[path[j].fir][path[j].sec] == '!') ans[++tt] = {path[j].fir,path[j].sec,way[j]}, j++, cnt ++;
			reverse(ans+tt-cnt+1,ans+tt+1);
			ans[++tt] = {path[i].fir,path[i].sec,way[i]};
			i = j-1;
		} else ans[++tt] = {path[i].fir,path[i].sec,way[i]};
	}
	g[end.fir][end.sec] = '!';
	g[b.fir][b.sec] = '.';
}

void solve() {
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		string s; cin >> s;
		for(int j=1;j<=m;j++) g[i][j] = s[j-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!vis[i][j] && !check(i,j)) {
				cout << "-1\n";
				return ;
			}
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(g[i][j] == '*') bfs(i,j);
		}
	}
	cout << tt << '\n';
	for(int i=1;i<=tt;i++) cout << ans[i].x << ' ' << ans[i].y << ' ' << ans[i].fac << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_--) solve();
    return 0;
}

L

题意

给定数组 a 和 x。每次操作将与 x 最接近的，大于 x 的 $a_i$ 减去 1，x 增加 1。问操作至少几次才能让 x 在 a 中排第 k。

Step 1

x 超过 $a_i$ 需要操作 $\lceil \frac{a_i+x}{2}\rceil$ 次。如果继续操作到 x 排第 k，则需要 $O_k = \frac{\cdots+\frac{a_{i+1}+\frac{a_i+x}{2}}{2}}{2}$ 我们发现当操作一定次数后 x 对操作次数的影响可以忽略不记。

Step 2

如果排名上升在 200 以内我们可以通过模拟，200 名以上的部分则可以通过预处理计算出。

Code

#include <bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;
typedef pair<int,int> PII;
const int N = 200010, INF = 0x3f3f3f3f, mod = 998244353;

ll a[N], pre[N];

int binary(int l, int r, int x) {
	while(l<=r) {
		int mid = (l+r) >> 1;
		if(a[mid] > x) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

void solve() {
	int n, q; cin >> n >> q;
	for(int i=1;i<=n;i++) cin >> a[i];
	sort(a+1,a+1+n,[](int a, int b) {return a>b;});
	ll t = 0, x = 0;
	for(int i=n;i;i--) {
		t += (a[i]+x+1)/2-x;
		x = (a[i]+x+1)/2;
		pre[i] = t;
	}
	while(q--) {
		int x, rk; cin >> x >> rk;
		int now = binary(1,n,x);
		ll ans = 0;
		for(int i=1;i<=200 && now > rk;i++) {
			ans += (a[now-1]+x+1)/2-x;
			x = (a[now-1]+x+1)/2;
			now --;
		}
		if(now > rk) ans += pre[rk]-pre[now];
		cout << ans << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_--) solve();
    return 0;
}

2025牛客暑期多校训练营

Round 1

E

题意

解

G

题意

解

I

题意

观察

解

Code

K

题意

解

L

题意

解

Code

Round 2

A

题意

解

Code

B

题意

解

D

题意

Step 1

Step 2

Step 3

解

Code

F

题意

解

G

题意

解

H

题意

Step 1

Step 2

Step 3

Code

I

题意

解

L

题意

解

M

题意

Step 1

Step 2

Step 3

Step 4

Step 5

Code

Round 3

A

题意

解

B

题意

解

D

题意

解

E

题意

解

Code

H

题意

Step 1

Step 2

Step 3