博客广场/ 陈俊霖

比赛总结

8月Day7

A.Move Brackets 核心思路将一个括号序列调整为合法括号序列，最少操作次数等于前缀和达到的最小负值的绝对值。因为每次操作可将任意一个括号移到开头或结尾，而移动右括号到开头（或左括号到结尾）能消除前缀中的负平衡。所需移动的括号数即为最深的不平衡程度。具体步骤初始化平衡值 bal = 0，最小前缀和 mn = 0。遍历字符串 s 的每个字符：

陈俊霖发布于 2026-8-9 17:35:34

综合/比赛总结综合/题解动态规划/状态压缩DP

A.Move Brackets

核心思路

将一个括号序列调整为合法括号序列，最少操作次数等于前缀和达到的最小负值的绝对值。因为每次操作可将任意一个括号移到开头或结尾，而移动右括号到开头（或左括号到结尾）能消除前缀中的负平衡。所需移动的括号数即为最深的不平衡程度。

具体步骤

初始化平衡值 bal = 0，最小前缀和 mn = 0。
遍历字符串 s 的每个字符：
- 若为 '('，则 bal++；
- 若为 ')'，则 bal--；
- 更新 mn = min(mn, bal)。
遍历结束后，输出 -mn。

题解

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

int main() 
{
	int t;
	cin >> t;
	while (t--) 
	{
		int n;
		string s;
		cin >> n >> s;
		int b = 0, mn = 0;
		for (char c : s) 
		{
			if (c == '(') b++;
			else b--;
			mn = min(mn, b);
		}
		cout << -mn << endl;
	}
	return 0;
}

B.And It's Non-Zero

核心思路

要使剩余元素的按位与结果不为 0，只需保证所有剩余元素在同一个二进制位上均为 1。因此最优策略是选择一个二进制位，保留区间内该位为 1 的所有数字，删除其余数字。最少删除数 = 区间长度 - 该位为 1 的数字个数的最大值。

具体步骤

对每个测试用例，读取区间 [l, r]，总元素数 total = r - l + 1。
初始化 maxKeep = 0。
枚举二进制位 k（0 到 18，因为 r ≤ 2×10^5 < 2^19）：
- 计算区间 [l, r] 内第 k 位为 1 的数字个数 cnt。
- 更新 maxKeep = max(maxKeep, cnt)。
答案 = total - maxKeep，输出。

位计数函数

countOnes(n, k) 返回 [0, n] 中第 k 位为 1 的整数个数：

周期 p = 2^(k+1)，半周期 h = 2^k。
完整周期贡献 (n / p) * h，剩余部分贡献 max(0, n % p - h + 1)。

题解

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

long long countOnes(long long n, int k) 
{
	if (n < 0) return 0;
	long long p = 1LL << (k + 1);
	long long h = 1LL << k;
	long long rem = n % p;
	long long res = n / p * h;
	if (rem >= h) res += rem - h + 1;
	return res;
}

int main() 
{
	int t;
	cin >> t;
	while (t--)
	{
		long long l, r;
		cin >> l >> r;
		
		long long total = r - l + 1;
		long long maxKeep = 0;
		
		for (int k = 0; k <= 18; k ++)
		{
			long long cnt = countOnes(r, k) - countOnes(l - 1, k);
			maxKeep = max(maxKeep, cnt);
		}
		
		cout << total - maxKeep << '\n';
	}
	return 0;
}

C.Iva & Pav

核心思路

由于按位与运算具有单调性：区间越长，按位与的结果只会变小或不变。因此对于固定的左端点 l，满足 f(l, r) >= k 的所有 r 构成一个连续前缀区间。可以用ST 表预处理任意区间的按位与，然后对每个询问进行二分查找最大的右端点。

具体步骤

预处理对数表
计算 lg[len] 表示 len 的二进制最高位（用于 ST 表查询）。
构建 ST 表
- st[0][i] = a[i]（0-indexed）。
- 对于 len = 1..⌊log2(n)⌋，令 st[len][i] = st[len-1][i] & st[len-1][i + 2^(len-1)]。
- 这样 st[len][i] 表示从 i 开始长度为 2^len 的区间按位与结果。
区间查询函数
- 对于区间 [l, r]，取长度 len = r-l+1，k = lg[len]，返回 st[k][l] & st[k][r - 2^k + 1]。
处理每个询问
- 读取 l（转为0-indexed）和 k。
- 若 a[l] < k，则任何区间与值都小于 k，直接输出 -1。
- 否则在 [l, n-1] 内二分查找最大的 r，使得 query(l, r) >= k。
  - 由于单调性，若中点满足，则向右搜索；否则向左搜索。
- 输出 r+1（1-indexed）。
输出结果
每个询问输出答案，用空格分隔，每组测试用例后换行。

题解

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

const int N = 2e5 + 5;
const int LOG = 20; 

int st[LOG][N];
int lg[N];

int query(int l, int r) {
	int len = r - l + 1;
	int k = lg[len];
	return st[k][l] & st[k][r - (1 << k) + 1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	lg[1] = 0;
	for (int i = 2; i < N; i++) 
	{
		lg[i] = lg[i / 2] + 1;
	}
	int t;
	cin >> t;
	while (t --) 
	{
		int n;
		cin >> n;
		for (int i = 0; i < n; i ++) 
		{
			cin >> st[0][i];
		}
		
		for (int len = 1; (1 << len) <= n; len ++) 
		{
			for (int start = 0; start + (1 << len) - 1 < n; start ++) 
			{
				st[len][start] = st[len - 1][start] & st[len - 1][start + (1 << (len - 1))];
			}
		}
		int q;
		cin >> q;
		while (q --)
		{
			int l, k;
			cin >> l >> k;
			l--;
			if (st[0][l] < k) 
			{
				cout << -1 << ' ';
				continue;
			}
			
			int low = l, high = n - 1, ans = l;
			while (low <= high) 
			{
				int mid = (low + high) / 2;
				if (query(l, mid) >= k) 
				{
					ans = mid;
					low = mid + 1;
				} 
				else high = mid - 1;
			}
			
			cout << ans + 1 << ' ';
		}
		cout << '\n';
	}
	return 0;
}

D.Number of Ways

核心思路

利用前缀和快速判断分割点位置。首先整个数组总和必须能被 3 整除，否则无解。设目标值为 target = sum / 3。枚举第二个分割点 j（即第二段右端点），同时统计其左侧有多少个位置可以作为第一个分割点 i-1（即前缀和等于 target）。当 pre[j] == 2*target 时，当前第二段右端点合法，累加已统计的第一分割点数量。

具体步骤

读入 n 和数组 a。
计算前缀和 pre，pre[i] 表示前 i 个元素之和（i 从 1 到 n）。
若 n < 3 或 sum % 3 != 0，直接输出 0。
令 target = sum / 3，初始化 cnt = 0（可作为第一分割点的前缀和等于 target 的位置数），ans = 0。
枚举 q 从 2 到 n-1（q 表示第二个分割点的右端点）：
- 若 pre[q-1] == target，则位置 q-1 可作为第一分割点，cnt++。
- 若 pre[q] == 2*target，则当前第二分割点有效，ans += cnt。
输出 ans。

题解

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<long long> a(n);
	long long sum = 0;
	vector<long long> pre(n + 1, 0);
	for (int i = 0; i < n; i ++) 
	{
		cin >> a[i];
		sum += a[i];
		pre[i + 1] = pre[i] + a[i];
	}
	
	if (n < 3) {
		cout << 0;
		return 0;
	}
	
	if (sum % 3 != 0) 
	{
		cout << 0;
		return 0;
	}
	
	long long target = sum / 3;
	long long cnt = 0, ans = 0;
	
	for (int q = 2; q <= n - 1; q ++) 
	{
		if (pre[q - 1] == target) 
		{
			cnt ++;
		}
		if (pre[q] == 2 * target) 
		{
			ans += cnt;
		}
	}	
	cout << ans;
	return 0;
}

E.Xor-Subsequence (easy version)

核心思路

采用分块动态规划，将原数组分成大小为 256 的块，在每一块内独立求解最长美丽子序列，最后取各块最大值作为答案。其核心假设是：最优子序列不会跨越块边界，因此可以在每个块内进行二次 DP，将总体复杂度降低到 O(256·n)。

具体步骤

分块
遍历所有起始下标 start，每次取长度不超过 256 的块 [start, end)（end = min(n, start+256)）。
块内 DP
令块内元素数量为 sz = end - start，用数组 dp 表示以块内第 idx 个元素结尾的最长美丽子序列长度，初始均为 1。
枚举块内所有下标对 (jdx, idx)（jdx < idx），对应的原下标分别为 j = start + jdx，i = start + idx。
若满足条件 (a[j] ^ i) < (a[i] ^ j)，则可以从 j 转移到 i，更新 dp[idx] = max(dp[idx], dp[jdx] + 1)。
记录块内最大值
在块内 DP 过程中维护最大值 best，并用 ans 记录所有块的最大值。
输出答案
每组测试用例输出 ans。

题解

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

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) 
	{
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i ++) cin >> a[i];
		
		int ans = 0;
		
		for (int start = 0; start < n; start += 256) 
		{
			int end = min(n, start + 256);
			int sz = end - start;
			vector<int> dp(sz, 1);
			int best = 1;
			
			for (int idx = 0; idx < sz; idx ++) 
			{
				int i = start + idx;
				for (int jdx = 0; jdx < idx; jdx ++) 
				{
					int j = start + jdx;
					if ((a[j] ^ i) < (a[i] ^ j)) 
					{
						dp[idx] = max(dp[idx], dp[jdx] + 1);
					}
				}
				best = max(best, dp[idx]);
			}
			ans = max(ans, best);
		}
		
		cout << ans << '\n';
	}
	return 0;
}

F.Shuffling Songs

核心思路

将每首歌曲看作图的一个顶点。若两首歌曲的流派相同或作者相同，则在它们之间连一条边。题目要求选出尽量多的歌曲，使得它们可以排列成一个序列，并且序列中任意相邻两首歌曲之间都有边（即原图的一条路径）。因此问题等价于在图中寻找最长简单路径（不要求覆盖所有顶点），最少删除数等于总顶点数减去最长路径的顶点数。

由于 n≤16，可用状态压缩动态规划枚举所有子集和路径末端顶点，求出所有可行的路径中顶点数的最大值。

具体步骤

建图
对于所有 i≠j，若 gi=gj 或 wi=wj，则标记 adj[i][j] = true，表示两首歌可以相邻。
动态规划初始化
用 dp[mask][last] 表示已选歌曲集合为 mask，且路径最后一个顶点为 last 时，是否存在这样的路径。
初始状态：对每个顶点 i，dp[1<<i][i] = true。
状态转移
枚举当前状态 (mask, last)，若该状态可达，则尝试向路径末尾添加一个尚未选过的顶点 nxt（mask 中不包含该位）。
若 adj[last][nxt] 为真，则新状态 dp[mask | (1<<nxt)][nxt] 可达。
求解最大保留数
遍历所有 dp[mask][last] 为真的状态，计算 popcount(mask) 的最大值，记为 maxKeep。
输出答案
最少删除数 = n−maxKeep。

题解

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

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) 
	{
		int n;
		cin >> n;
		vector<string> g(n), w(n);
		for (int i = 0; i < n; i ++) 
		{
			cin >> g[i] >> w[i];
		}
		vector<vector<bool>> adj(n, vector<bool>(n, false));
		for (int i = 0; i < n; i ++) 
		{
			for (int j = 0; j < n; j ++) 
			{
				if (i != j && (g[i] == g[j] || w[i] == w[j])) 
				{
					adj[i][j] = true;
				}
			}
		}
		
		int totalMask = 1 << n;
		vector<vector<bool>> dp(totalMask, vector<bool>(n, false));
		
		for (int i = 0; i < n; i ++) 
		{
			dp[1 << i][i] = true;
		}
		
		for (int mask = 0; mask < totalMask; mask ++) 
		{
			for (int last = 0; last < n; last ++) 
			{
				if (!dp[mask][last]) continue;
				for (int nxt = 0; nxt < n; nxt ++) 
				{
					if (mask & (1 << nxt)) continue;
					if (adj[last][nxt]) 
					{
						dp[mask | (1 << nxt)][nxt] = true;
					}
				}
			}
		}
		
		int maxKeep = 0;
		for (int mask = 0; mask < totalMask; mask ++) 
		{
			for (int last = 0; last < n; last ++) 
			{
				if (dp[mask][last]) 
				{
					maxKeep = max(maxKeep, __builtin_popcount(mask));
				}
			}
		}
		
		cout << n - maxKeep << '\n';
	}
	
	return 0;
}

G.旅行商问题

核心思路

用状压动态规划求解 TSP。

状态：dp[mask][i] 表示已经访问过的城市集合为 mask，且当前位于城市 i 时的最小总费用。
转移：从当前城市 i 前往尚未访问的城市 j，更新 dp[mask | (1<<j)][j] = min(..., dp[mask][i] + cost[i][j])。
答案：枚举最后停留的城市 i，加上返回起点 0 的费用，取最小值。

具体步骤

读入城市数 n 和费用矩阵 cost[n][n]。
初始化 dp 为无穷大，dp[1<<0][0] = 0（起点为城市 0）。
枚举所有状态 mask（0 到 (1<<n)-1），再枚举当前城市 i（需在 mask 中）。
若 dp[mask][i] 有效，则枚举所有未访问城市 j，进行转移。
遍历完整状态后，计算 ans = min(dp[(1<<n)-1][i] + cost[i][0])。
输出 ans。

题解

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

const long long INF = 4e18;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<vector<long long>> cost(n, vector<long long>(n));
	for (int i = 0; i < n; i ++) 
	{
		for (int j = 0; j < n; j ++) 
		{
			cin >> cost[i][j];
		}
	}
	
	vector<vector<long long>> dp(1 << n, vector<long long>(n, INF));
	dp[1 << 0][0] = 0;
	
	for (int mask = 0; mask < (1 << n); mask ++) 
	{
		for (int i = 0; i < n; i ++) 
		{
			if (dp[mask][i] == INF) continue;
			if (!(mask & (1 << i))) continue;
			
			for (int j = 0; j < n; j ++) 
			{
				if (mask & (1 << j)) continue;
				int nmask = mask | (1 << j);
				dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + cost[i][j]);
			}
		}
	}
	
	long long ans = INF;
	for (int i = 0; i < n; i ++) 
	{
		ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
	}
	
	cout << ans << '\n';
	return 0;
}

A.Move Brackets

核心思路

具体步骤

题解

B.And It's Non-Zero

核心思路

具体步骤

位计数函数

题解

C.Iva & Pav

核心思路

具体步骤

题解

D.Number of Ways

核心思路

具体步骤

题解

E.Xor-Subsequence (easy version)

核心思路

具体步骤

题解

F.Shuffling Songs

核心思路

具体步骤

题解

G.旅行商问题

核心思路

具体步骤

题解

评论

还没有账户？

登录