讨论详情 - FJNU

A. Love Median

考虑二分答案x，并设 $val[i] = (a[i] >= x ? 1 : -1)$ ，问题转化为询问连续子序列 $val[l...r] \geq 0$ 的数量是否过半，

再设前缀和 $sum[i]=val[1...i]$ ， $val[l...r] \geq 0$ 转化为 $sum[r] - sum[l-1] \geq 0$ ，树状数组维护即可，时间复杂度为 $O(nlog^2n)$

注意：有 $O(nlogn)$ 的做法

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100005;
const int MOD = 998244353;
const int D = 100000;

int n, c[MAXN << 1], val[MAXN], a[MAXN], b[MAXN], cnt = 0;
map<int, int> Map;

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

void Modify(int x, int k) {
	while(x <= 2 * D) c[x] += k, x += lowbit(x);
} 

int Query(int x) {
	int res = 0;
	while(x) res += c[x], x -= lowbit(x);
	return res;
}

bool Check(int x) {
	for(int i = 1; i <= n; i++) val[i] = (a[i] >= x ? 1 : -1);
	memset(c, 0, sizeof c);
	Modify(D, 1);
	int res = 0, sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += val[i];
		res += Query(sum + D);
		Modify(sum + D, 1);
	}
	/*
	cout << x << " : \n";
	for(int i = 1; i <= n; i++) cout << val[i] << " "; cout << "val\n";
	cout << res << " res\n";
	*/
	sum = n * (n + 1) / 2;
	return res >= sum - res;
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], Map[ a[i] ] = 1;
	for(auto i : Map) b[++cnt] = i.first;
	int l = 1, r = cnt;
	while(l < r) {
		int midpos = l + r + 1 >> 1, mid = b[midpos];
		if( Check(b[midpos]) ) l = midpos;
		else r = midpos - 1;
	}
	cout << b[l];
	return 0;
}

B. Subsequence

考虑固定中间的 $'I'$ （设其下标为 $i$ ），求左边 $'J'$ 和右边 $'K'$ 的数量，我们需要用数组 $pre[i]$ 记录 $[1...i]$ 中各个符号的数量，用数组 $suf[i]$ 记录 $[i...n]$ 中各个符号的数量。

对于求左边 $'J'$ ，我们通过分别计算原本串中的 $'J'$ 和 $'?'$ 解决问题。

对于 $'J'$ ，我们需要计算 $[1...i-1]$ 中有多少种方案得到 $'J'$ ；对于 $'?'$ ，我们将其替换为 $'J'$ ，计算还有多少种方案得到 $'J'$ ，

求 $'K'$ 时同理，具体式子看代码（时间复杂度为 $O(n)$ ）

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100005;
const int MOD = 998244353;

string S;
int n, suf[MAXN][6], pre[MAXN][6], pow3[MAXN];

int Hash(char ch) {
	if(ch == 'J') return 1;
	if(ch == 'I') return 2;
	if(ch == 'E') return 3;
	return 4;
}

int qpow(int a, int p) {
	int res = 1;
	while(p) {
		if(p & 1) res = res * a % MOD;
		a = a * a % MOD;
		p >>= 1;
	}
	return res;
}

int Calc1(int pos) {
	int cur = pre[pos][4];
	int res = pre[pos][1] * pow3[cur] % MOD;
	if(cur) res = (cur * pow3[cur - 1] % MOD + res) % MOD;
	return res;
}

int Calc2(int pos) {
	int cur = suf[pos][4];	
	int res = suf[pos][3] * pow3[cur] % MOD;
	if(cur) res = (cur * pow3[cur - 1] % MOD + res) % MOD;
	return res;
}

void Solve() {
	cin >> S; 
	n = S.length(); S = " " + S;
	pow3[0] = 1;
	for(int i = 1; i <= n; i++) pow3[i] = pow3[i - 1] * 3 % MOD;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 4; j++) pre[i][j] = pre[i - 1][j];
		pre[i][ Hash(S[i]) ]++;
	}
	for(int i = n; i >= 1; i--) {
		for(int j = 1; j <= 4; j++) suf[i][j] = suf[i + 1][j];
		suf[i][ Hash(S[i]) ]++;	
	}
	
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(S[i] == 'J' || S[i] == 'E') continue;
		//cout << Calc1(i - 1) << " " << Calc2(i + 1) << " calc\n";
		ans = (ans + Calc1(i - 1) * Calc2(i + 1) % MOD ) % MOD;
	}
	cout << ans;
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int TT = 1; //cin >> TT;
	while(TT--) Solve();
	return 0;
}

C. Protect the Second Best KK in the World

首先通过KMP求每个 $|p_i|$ 在 $|S|$ 中出现的位置，

设 $dp[i]$ 为 $S[1...i]$ 中满足条件的方案数，有$dp[i]=\sum_{S[j+1...i]==P_k, 1 \leq k \leq n} dp[j]$

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

const int MOD = 998244353;

int n, slen, tlen, tLen[100005], pmt[100005], dp[100005];
char S[100005], T[100005];
vector<int> vec[100005];

vector<int> KMP() {
	vector<int> vec;
	
	int p = 0;
	pmt[0] = pmt[1] = 0;
	for(int i = 2; i <= tlen; i++) {
		while(p && T[p + 1] != T[i]) p = pmt[p];
		if(T[p + 1] == T[i]) ++p;
		pmt[i] = p;
	}
	p = 0;
	for(int i = 1; i <= slen; i++) {
		while(p && T[p + 1] != S[i]) p = pmt[p];
		if(T[p + 1] == S[i]) p++;
		if(p == tlen) p = pmt[p], vec.push_back(i);
	}
	return vec;
}

signed main()
{
	cin >> n >> slen >> S + 1;
	for(int i = 1; i <= n; i++) {
		cin >> tlen >> T + 1;
		vec[i] = KMP();
		reverse(vec[i].begin(), vec[i].end());
		tLen[i] = tlen;
	}
	dp[0] = 1;
	for(int i = 1; i <= slen; i++) {
		for(int j = 1; j <= n; j++) {
			if(vec[j].empty()) continue;
			if(vec[j].back() == i) {
				dp[i] += dp[i - tLen[j]], dp[i] %= MOD;
				vec[j].pop_back();
			}
		}
	}
	cout << dp[slen];
	return 0;
}

D. Accumulation Degree

考虑计算每条边对答案的贡献，我们可以将边权从小到大排序，并用并查集维护，

每次计算一条边的时候，权值比其小(或相等)的边已经被添加进并查集，因此在边的两个端点集合中各选一点，利用乘法原理即可算出此边为最大边权的方案数，乘以边权即为答案的贡献。计算完后需要利用并查集维护端点集合，将两个集合合并。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

struct Node {
	int u, v, w;
}a[MAXN];
int n, f[MAXN], sze[MAXN], ans;

bool cmp(Node &a, Node &b) {
	return a.w < b.w;
}

int Find(int u) {
	return u == f[u] ? u : f[u] = Find(f[u]);
}

void Merge(int u, int v) {
	if(u > v) swap(u, v);
	f[v] = u;
	sze[u] += sze[v];
	sze[v] = 0;
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++) cin >> a[i].u >> a[i].v >> a[i].w;
	sort(a + 1, a + n, cmp);
	for(int i = 1; i <= n; i++) f[i] = i, sze[i] = 1;
	int ans = 0;
	for(int i = 1; i < n; i++) {
		int fu = Find(a[i].u), fv = Find(a[i].v);
		ans += a[i].w * sze[fu] * sze[fv];
		Merge(fu, fv);
	}
	cout << ans;
	return 0;
}

E. Cats or dogs?

对x坐标进行排序，并对y值求前后缀极值，

遍历坐标pos，二分距离dist，发现只有 $|x_i - x_{pos}| \geq dist$ 的坐标才有可能满足条件

因为排序后x坐标具有单调性，所以可以继续二分找到边界下标，并求出 $max(|y_i-y_{pos}|)$

复杂度 $O(nlog^2n)$

注意：有 $O(nlogn)$ 的做法

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100005;
const int MOD = 1e9 + 7;

int n, b[MAXN], premax[MAXN], sufmax[MAXN], premin[MAXN], sufmin[MAXN];
pair<int, int> a[MAXN];

bool Check(int x, int pos) {
	int l = upper_bound(b + 1, b + 1 + n, a[pos].first - x) - b - 1;
	int r = lower_bound(b + 1, b + 1 + n, a[pos].first + x) - b;
	//printf("%lld %lld : %lld %lld\n", pos, x, l, r);
	int maxx = 0;
	if(l) {
		maxx = max(maxx, abs(premax[l] - a[pos].second) );
		maxx = max(maxx, abs(premin[l] - a[pos].second) );
	}
	if(r <= n) {
		maxx = max(maxx, abs(sufmax[r] - a[pos].second) );
		maxx = max(maxx, abs(sufmin[r] - a[pos].second) );
	}
	return maxx >= x;
}

signed main()
{
	//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++) b[i] = a[i].first;
	premin[0] = sufmin[n + 1] = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++) {
		premax[i] = max(premax[i - 1], a[i].second);
		premin[i] = min(premin[i - 1], a[i].second);
	}
	for(int i = n; i >= 1; i--) {
		sufmax[i] = max(sufmax[i + 1], a[i].second);
		sufmin[i] = min(sufmin[i + 1], a[i].second);
	}
	int maxx = 0;
	for(int i = 1; i <= n; i++) {
		int l = 0, r = 1e9;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if( Check(mid, i) ) l = mid; 
			else r = mid - 1;
		}
		maxx = max(maxx, l);
	}
	cout << maxx;
	return 0;
}

F. Examination

一道很裸的背包，只需要分别枚举第 $i$ 类问题，做出 $j$ 题，当前得分为 $k$ ，即可得出式子

$$dp[i][k+j*s[i]+c[i]*(j==p[i])] = min(dp[i-1][k]+j) $$

由于 $dp[i]$ 只和 $dp[i-1]$ 有关，所以dp数组的第一维长度为2即可

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100 + 5;
const int MAXW = 2e4 + 5;

int n, d, p[MAXN], s[MAXN], c[MAXN], f[3][MAXW];

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> d;
	for(int i = 1; i <= n; i++) cin >> p[i] >> s[i] >> c[i];
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= p[i]; j++) {
			for(int k = 0; k <= d + 1e4; k++) {
				int cur = k + j * s[i];
				if(j == p[i]) cur += c[i];
				if(cur > d + 1e4) break;
				f[1][cur] = min(f[1][cur], f[0][k] + j);
			}
		}
		for(int k = 0; k <= d + 1e4; k++) f[0][k] = f[1][k];
	}
	int ans = 1e9;
	for(int k = d; k <= d + 1e4; k++) ans = min(ans, f[0][k]);
	cout << ans;
	
	return 0;
}

G. Burning

BFS+优先队列，其中优先队列是以温度为关键字的小根堆，按照题意BFS即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 505;
const int MOD = 1e9 + 7;

struct Node {
	int x, y, t;
	
	bool operator < (const Node &a) const {
		return t > a.t;
	}
};

priority_queue<Node> Q;
int n, m, a, b, c, d, G[MAXN][MAXN], vis[MAXN][MAXN];
int dx[5] = {0, 1, 0, -1}, dy[5] = {1, 0, -1, 0};

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> a >> b >> c >> d;
	memset(G, 0x3f, sizeof G);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) cin >> G[i][j];
	}
	Q.push( (Node){a, b, G[a][b]} );
	while(!Q.empty()) {
		Node cur = Q.top(); Q.pop();
		int x = cur.x, y = cur.y, t = cur.t;
		if(vis[x][y]) continue;
		if(x == c && y == d) {
			cout << t;
			break;
		}
		vis[x][y] = 1;
		for(int k = 0; k < 4; k++) {
			int cx = x + dx[k], cy = y + dy[k];
			Q.push( (Node){cx, cy, max(G[cx][cy], t)} );
		}
	}
	return 0;
}

H. Computational Geometry

求出各个点对之间的距离，并按边权排序，发现答案是最小生成树中的最大边，直接上Kruskal即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 505;
const int MAXM = 505 * 505;
const int MOD = 1e9 + 7;

struct Node {
	int u, v, w;
}e[MAXM];
int a[MAXN], b[MAXN], f[MAXN], n, m;

int dist(int u, int v) {
	int x = a[u] - a[v], y = b[u] - b[v];
	return ceil( sqrt(x * x + y * y) );
}

bool cmp(Node &a, Node &b) {
	return a.w < b.w;
}

int find(int u) {
	return u == f[u] ? u : f[u] = find(f[u]);
}

int Kruskal() {
	for(int i = 1; i <= n; i++) f[i] = i;
	sort(e + 1, e + 1 + m, cmp);
	int ans = 0;
	for(int i = 1; i <= m; i++) {
		int fu = find(e[i].u), fv = find(e[i].v);
		if(fu == fv) continue;
		if(fu > fv) swap(fu, fv);
		f[fv] = fu;
		ans = e[i].w;
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) e[++m] = (Node){i, j, dist(i, j)};
	}
	cout << ( (Kruskal() + 1) / 2 );
	return 0;
}

I. Friendship

将m个矛盾按照右端点排序后，遍历时贪心地选取最大右端点断链，若某次矛盾的左端点大于最大右端点，则代表矛盾在同一条链上，此时更新最大右端点并使答案+1

# include "algorithm"
# include "iostream"
# include "cstdio"

using namespace std;

const int maxm=1e5+10;

int N,M,Now_R;
int Ans;

struct node{
	int L;
	int R;
}Ask[maxm];

inline bool operator <(node x,node y){return x.R<y.R;}

int main(){
	register int i,j;
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++) scanf("%d%d",&Ask[i].L,&Ask[i].R);
	sort(Ask+1,Ask+1+M);
	for(i=1;i<=M;i++){
		if(Now_R>Ask[i].L) continue;
		Now_R=Ask[i].R;
		Ans++;
	}
	printf("%d",Ans);
	return 0;
}

J. Eating Snacks

首先考虑动态规划，设 $dp[i,k]$ 表示 $a[1...i]$ 中长度为 $k$ ，满足其他条件的子序列数量，有

$$k为奇数：dp[i,k] = \sum_{1\leq ja[j]} dp[j,k-1]\\ k为偶数：dp[i,k] = \sum_{1\leq j<i,a[i]<a[j]} dp[j,k-1]\\ $$

时间复杂度为 $O(n^2m)$ ，不能通过此题，我们需要在此基础上利用树状数组进行优化。

将a数组离散化后进行排序，按值从小到大（从大到小）遍历时求得 $[1,i-1]$ 中已经被放入树状数组的dp值，并将求得的dp值放入树状数组。时间复杂度为 $O(mnlogn)$

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

const int MAXN = 100000 + 5;
const int MOD = 1000000007;

int n, m, cnt = 0, val[3][MAXN], c[MAXN], b[MAXN];
pair<int, int> a[MAXN];
vector<int> vec[MAXN];

void Init() { // Discretization
	for(int i = 1; i <= cnt; i++) vec[i].clear();

	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i].first), a[i].second = i;

	cnt = 0;
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++) {
		if(a[i].first != a[i - 1].first) cnt++;
		b[i] = cnt;
		vec[cnt].push_back(a[i].second);
	}
	for(int i = 1; i <= n; i++) a[i].first = b[i];
	for(int i = 1; i <= n; i++) b[ a[i].second ] = a[i].first; 
}

int Query(int x) {
	int res = 0;
	while(x) res += c[x], res %= MOD, x -= (x & (-x));
	return res;
}

void Modify(int x, int k) {
	while(x <= n) c[x] += k, c[x] %= MOD, x += (x & (-x));
} 

int Solve() { // Use Binary Indexed Tree
	int ans = 0;
	for(int i = 1; i <= n; i++) val[0][i] = 1, val[1][i] = c[i] = 0;
	for(int t = 2; t <= m; t++) {
		if(t % 2 == 0) {
			for(int k = cnt; k >= 1; k--) {
				for(auto i : vec[k]) val[1][i] = Query(i - 1);
				for(auto i : vec[k]) Modify(i, val[0][i]);
			}	
		} else {
			for(int k = 1; k <= cnt; k++) {
				for(auto i : vec[k]) val[1][i] = Query(i - 1);
				for(auto i : vec[k]) Modify(i, val[0][i]);
			}
		}
		for(int i = 0; i <= n; i++) {
			val[0][i] = val[1][i];
			val[1][i] = c[i] = 0;
		}
		//for(int i = 1; i <= n; i++) cout << val[0][i] << " "; cout << "val\n";
	}
	for(int i = 1; i <= n; i++) ans += val[0][i], ans %= MOD;		
	return ans;	
}

signed main() 
{
	Init();
	printf("%lld\n", Solve() );
	return 0;
}

K. AvavaAva

首先考虑如何计算 $[1,i]$ 中“AvA”子序列的数量，

设 $S[l...r]$ 表示 $S$ 中从 $l$ 到 $r$ 这一段的子串， $dp[i,j]$ 表示 $S[1...i]$ 中有多少个子序列构成 $T[1...j]$

则有 $dp[i,j]=dp[i-1,j]+(S[i]==T[j])dp[i - 1][j - 1]$

我们需要计算 $T="AvA"$ 和 $T="vA"$ 时的dp数组，分别记为 $dp1, dp2$ , 还需计算 $[1...i]$ 中'A'和'v'的数量，设其分别为 $sum\_A[i],sum\_v[i]$

利用前缀和思想，我们发现 $[l,r]$ 中的"AvA"子序列数量可以由 $[1,r]$ 中的"AvA"子序列数量 $(dp1[r,3])$ 删减以下情况得出：

① $[1,l-1]$ 中存在"AvA"子序列 $(dp[l-1,3])$

② $[1,l-1]$ 中存在"A"子序列, $[l,r]$ 中存在"vA"子序列 $( \ Calc(l, r) * sum_A[l - 1] \ )$

③ $[1,l-1]$ 中存在"Av"子序列, $[l,r]$ 中存在"A"子序列$( \ dp1[l - 1][2] * (sum\_A[r] - sum\_A[l - 1]) \ )$

其中 $Calc(l,r)$ 的计算方法通过 $dp2[r,2]$ 删减以下情况得出：

① $[1,l-1]$ 中存在"vA"子序列 $(dp2[l-1,2])$

② $[1,l-1]$ 中存在"v"子序列, $[l,r]$ 中存在"A"子序列$( \ sum\_v[l - 1] * (sum\_A[r] - sum\_A[l - 1]) \ )$

时间复杂度为 $O(n+m)$ ，常数略大。

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

const int MAXN = 500000 + 5;
const int MOD = 1000000007;

int n, m, dp1[MAXN][5], dp2[MAXN][5], sum_A[MAXN], sum_v[MAXN];
string S;

void Init() {
	// Calculate AvA by dp
	dp1[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 4; j++) dp1[i][j] = dp1[i - 1][j];
		if(S[i] == 'A') {
			dp1[i][1] += dp1[i][0], dp1[i][1] %= MOD;
			dp1[i][3] += dp1[i][2], dp1[i][3] %= MOD;
		} else dp1[i][2] += dp1[i][1], dp1[i][2] %= MOD;
	}
	
	// Calculate vA by dp
	dp2[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) dp2[i][j] = dp2[i - 1][j];
		
		if(S[i] == 'v') dp2[i][1] += dp2[i][0], dp2[i][1] %= MOD;
		else dp2[i][2] += dp2[i][1], dp2[i][2] %= MOD;
	}
	
	// prefix sum
	for(int i = 1; i <= n; i++) {
		sum_A[i] = sum_A[i - 1], sum_v[i] = sum_v[i - 1];
		if(S[i] == 'A') sum_A[i]++;
		else sum_v[i]++;
	}
	
	/*
	for(int j = 1; j <= 3; j++) {
		for(int i = 1; i <= n; i++) cout << dp1[i][j] << " "; cout << "dp\n";
	}	
	for(int j = 1; j <= 2; j++) {
		for(int i = 1; i <= n; i++) cout << dp2[i][j] << " "; cout << "dp\n";
	}
	*/
}

int Calc11(int l, int r) {	// Calculate vA->[l,r]
	int cur = sum_v[l - 1] * (sum_A[r] - sum_A[l - 1]) % MOD;
	return (dp2[r][2] - dp2[l - 1][2] - cur + 2ll * MOD) % MOD;
}

int Calc1(int l, int r) {	// Calculate A->[1,l-1] and vA->[l,r]
	return Calc11(l, r) * sum_A[l - 1] % MOD;
}

int Calc2(int l, int r) {	// Calculate Av->[1,l-1] and A->[l,r]
	return dp1[l - 1][2] * (sum_A[r] - sum_A[l - 1]) % MOD;
}

signed main()
{
	scanf("%lld%lld", &n, &m); cin >> S;
	S = " " + S;
	Init();
	int ans = 0;
	for(int i = 1; i <= m; i++) {
		int l, r; scanf("%lld%lld", &l, &r); 
		ans = (dp1[r][3] - dp1[l - 1][3] - Calc1(l, r) - Calc2(l, r) + 3ll * MOD) % MOD;
		printf("%lld\n", ans);
	}
	return 0;
}

L. Cards

判断当前卡片是否与上一张卡片相同，若相同则需耗一张与这两个颜色不同的卡片，若不相同则不需要操作。按题意模拟即可

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000005;
const int MOD = 1e9 + 7;

int n, used = 0, a[MAXN], num[5];
string S;

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> num[0] >> num[1] >> S;
	for(int i = 0; i < n; i++) a[i + 1] = (S[i] == 'b');
	
	for(int i = 2; i <= n; i++) {
		if(a[i] == a[i - 1]) num[ a[i] ^ 1 ]--, used++;
	}
	
	if(num[0] >= 0 && num[1] >= 0) {
		cout << used + n;
	} else {
		cout << max(0ll, -num[0]) << " " << max(0ll, -num[1]);
	}
	return 0;
}

M. Prefix XORs

我们考虑前缀和操作, 该部分我们显然可以利用 $F^m(x)=(\sum_{i=0}^{n-1} x^i)^m$ 来表示 $m$ 次前缀和后每个数会被异或几次系数. 然后我们可以进行拆位我们记 $G_k(x)=\sum_{i=0}^{n-1}[A[i]\&2^k=2^k]x^i$ .

那么拆位后 $H(x)=F^m(x)\times G_k(x)$ 表示在 $2^k$ 位上对应位置会被异或上多少次 $1$ , 即若第 $i(1\leq i\leq n)$ 位 $H(x)$ 的系数为奇数, 则在第 $i$ 位上位权为 $2^k$ 二进制位上为 $1$ 否则为 $0$ .

用 $NTT$ 加上多项式快速幂即可, 时间复杂度 $O(n\log^2 n)$ .

注意不可以使用多项式 $EXP$ , 因为显然 $998244354$ 不是奇数但是在剩余系内会被认为同余 $1$ 即被认为是奇数.

#include <bits/stdc++.h> 
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define de(a) cerr << #a <<" = "<< a<<endl
#define dd(a) cerr<< #a <<" = "<<a<<" "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define rsz(a, x) (a.resize(x))
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;

const int LimBit=18, P=998244353;
const int M=1<<LimBit<<1;
inline int kpow(int a, int x, int p=P) { int ans=1; for(;x;x>>=1, a=(ll)a*a%P) if(x&1) ans=(ll)ans*a%P; return ans; }
inline int exgcd(int a, int b, int &x, int &y) {
	static int g;
	return b?(exgcd(b, a%b, y, x), y-=a/b*x, g):(x=1, y=0, g=a);
}
inline int inv(int a, int p=P) {
	static int x, y;
	return exgcd(a, p, x, y)==1?(x<0?x+p:x):-1;
}
namespace Poly {
	const int G=3;
	struct vir {
		int v;
		vir(int v_=0):v(v_>=P?v_-P:v_) {}
		inline vir operator + (const vir &x) const { return vir(v+x.v); }
		inline vir operator - (const vir &x) const { return vir(v+P-x.v); }
		inline vir operator * (const vir &x) const { return vir((ll)v*x.v%P); }
		
		inline vir operator - () const { return vir(P-v); }
		inline vir operator ! () const { return vir(inv(v)); }
		inline operator int() const { return v; }
	};
	struct poly : public vector<vir> {
		inline friend ostream& operator << (ostream& out, const poly &p) {
			if(!p.empty()) out<<(int)p[0];
			for(int i=1; i<sz(p); ++i) out<<" "<<(int)p[i];
			return out;
		}
	};
	
	int N, N_, Stk[M], curStk, rev[M];
	vir invN, Inv[M], w[2][M];
	inline void init() {
		N_=-1;
		curStk=0;
		Inv[1]=1;
		for(int i=2; i<M; ++i)
			Inv[i]=-vir(P/i)*Inv[P%i];
	}
	void work() {
		if(N_==N) return ;
		N_=N;
		int d=__builtin_ctz(N);
		vir x(kpow(G, (P-1)/N)), y=!x;
		w[0][0]=w[1][0]=1;
		for(int i=1; i<N; ++i) {
			rev[i]=(rev[i>>1]>>1)|((i&1)<<(d-1));
			w[0][i]=x*w[0][i-1], w[1][i]=y*w[1][i-1];
		}
		invN=!vir(N);
	}
	inline void FFT(vir a[M], int f) {
		static auto make = [=](vir w, vir &a, vir &b) { w=w*a; a=b-w; b=b+w; };
		for(int i=0; i<N; ++i) if(i<rev[i]) swap(a[i], a[rev[i]]);
		for(int i=1; i<N; i<<=1)
			for(int j=0, t=N/(i<<1); j<N; j+=i<<1)
				for(int k=0, l=0; k<i; k++, l+=t)
					make(w[f][l], a[j+k+i], a[j+k]);
		if(f) for(int i=0; i<N; ++i) a[i]=a[i]*invN;
	}
	
	vir p1[M], p0[M];
	inline void get_mul(poly &a, poly &b, int na, int nb) {
		for(N=1; N<na+nb-1; N<<=1);
		for(int i=0; i<na; ++i) p1[i]=(int)a[i]; for(int i=na; i<N; ++i) p1[i]=0;
		for(int i=0; i<nb; ++i) p0[i]=(int)b[i]; for(int i=nb; i<N; ++i) p0[i]=0;
		work(); FFT(p1, 0); FFT(p0, 0);
		for(int i=0; i<N; ++i) p1[i]=p1[i]*p0[i];
		FFT(p1, 1);
		rsz(a, na+nb-1); for(int i=0; i<sz(a); ++i) a[i]=p1[i];
	}
}
using Poly::poly;
using Poly::vir;

int n, m, a[M], b[M];
poly f, g;
inline void work() {
	rsz(f, n);
	rsz(g, n);
	cin>>a[0];
	g[0]=vir(1);
	for(int i=1; i<n; ++i) {
		cin>>a[i];
		g[i]=((i&(i+m-1))==i);
	}
	
	for(int k=0; k<30; ++k) {
		for(int i=0; i<n; ++i)
			f[i]=((a[i]>>k)&1);
		Poly::get_mul(f, g, n, n);
		rsz(f, n);
		for(int i=0, v; i<n; ++i) {
			v=(int)f[i];
			b[i]|=((v&1)<<k);
		}
	}
	
	for(int i=0; i<n; ++i)
		cout<<b[i]<<" \n"[i==n-1];
}
inline void init() {
	cin>>n>>m;
	Poly::init();
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	init();
	work();
	cout.flush();
	return 0;
}

目前还没有评论...

Solution

A. Love Median

B. Subsequence

C. Protect the Second Best KK in the World

D. Accumulation Degree

E. Cats or dogs?

F. Examination

G. Burning

H. Computational Geometry

I. Friendship

J. Eating Snacks

K. AvavaAva

L. Cards

M. Prefix XORs

0 条评论

状态

开发

支持

Solution

A. Love Median

B. Subsequence

C. Protect the Second Best KK in the World

D. Accumulation Degree

E. Cats or dogs?

F. Examination

G. Burning

H. Computational Geometry

I. Friendship

J. Eating Snacks

K. AvavaAva

L. Cards

M. Prefix XORs

0 条评论

状态

开发

支持

还没有账户？

登录