信息学奥赛-提高级 题库
生产线测试
题目背景
工厂打算通过客户反馈来间接测试生产线,从而找到存在缺陷的生产线。工厂有n条生产线(编号0~n-1),已知其中恰有一条生产线存在缺陷。每一轮测试为,从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品,客户将要求退货(结果记为1),否则正常收货(记为0)。受售后压力限制,在所有发货批次中,最多只能有k次退货(即结果为1的次数≤k)。工厂的目标是,设计最少的间接测试轮数w(发货总批次),保证根据客户收货或退货的反馈结果,唯一确定存在缺陷的生产线。
以下程序实现了工厂的目标,包含两部分:
i) 确定w的最小值,并设计最优测试方案;
ii) 根据测试结果推断存在缺陷的生产线。
该程序确定w最小值的方法为:由于不同的生产线故障时,测试应当返回不同的结果,因此w轮测试的可能结果数不应少于生产线数量。
`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
试补全程序。
假期计划(holiday)



#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int cp = 998244353;
inline int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1ll * a * a % cp) {
if (b & 1) {
ret = 1ll * ret * a % cp;
}
}
return ret;
}
inline int inv(int x) {
return ksm(x, cp - 2);
}
inline int rev(int p, int q) {
return 1LL * p * inv(q) % cp;
}
const int N = 2505;
int n, m, K, pos[N][3], f[N][N];
ull a[N], ans;
vector<int> G[N];
queue<int> Q;
void bfs(int S) {
f[S][S] = 1;
Q.push(S);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (auto v : G[x]) {
if (f[S][v] < 0) {
f[S][v] = f[S][x] + 1;
Q.push(v);
}
}
}
}
void check(int A, int B, int C, int D) {
if (!A || !B || !C || !D) return;
if (A == B || A == C || A == D || B == C || B == D || C == D) return;
if (f[1][A] > K || f[A][B] > K || f[B][C] > K || f[C][D] > K || f[D][1] > K) return;
ans = max(ans, a[A] + a[B] + a[C] + a[D]);
}
signed main() {
memset(f, -1, sizeof(f));
n = read(), m = read(), K = read() + 2;
for (int i = 2; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1, x, y; i <= m; ++i) {
x = read(), y = read();
G[x].push_back(y);
G[y].push_back(x);
}
bfs(1);
for (int i = 2; i <= n; ++i) {
bfs(i);
for (int j = 2; j <= n; ++j) {
if (f[i][j] != -1 && f[1][j] != -1 && f[i][j] <= K && f[1][j] <= K && i != j) {
int x = j;
if (a[x] > a[pos[i][0]]) swap(x, pos[i][0]);
if (a[x] > a[pos[i][1]]) swap(x, pos[i][1]);
if (a[x] > a[pos[i][2]]) swap(x, pos[i][2]);
}
}
}
for (int B = 2; B <= n; ++B) {
for (int C = 2; C <= n; ++C) {
if (B != C && f[B][C] <= K && f[B][C] != -1) {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
check(pos[B][i], B, C, pos[C][j]);
}
}
}
}
}
cout << ans;
return 0;
}策略游戏(game )



#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define int long long
int n, m, q, l_1, r_1, l_2, r_2;
int ans, ans1, ans2, ans3, ans4, ans5, ans6;
struct Block {
#define MAXM 331 // 块的个数
int n, len, tot;
int a[MAXN], bl[MAXN];
int L[MAXM], R[MAXM]; // 每个块的左端点和右端点
int maxn[MAXM], minn[MAXM]; // 每个块的最大值和最小值
Block(int x) { // 构造函数
n = x;
}
void init() { // 初始化
len = sqrt(n); // 块长
tot = (n - 1) / len + 1; // 块的数量
R[0] = 0;
for (int i(1); i <= tot; ++i) { // 求 L,R
L[i] = R[i - 1] + 1;
R[i] = i * len;
}
R[tot] = n; // 注意最后一个块的右端点
for (int i(1); i <= tot; ++i) {
maxn[i] = LLONG_MIN;
minn[i] = LLONG_MAX;
for (int j(L[i]); j <= R[i]; ++j) {
bl[j] = i; // j 在第 i 个块
maxn[i] = max(maxn[i], a[j]);
minn[i] = min(minn[i], a[j]);
}
}
}
int gmin(int l, int r) {
int p(bl[l]), q(bl[r]), res(LLONG_MAX);
if (p == q) { // 当 l,r 处于同一个块时,暴力枚举
for (int i(l); i <= r; ++i) {
res = min(res, a[i]);
}
return res;
}
for (int i(l); i <= R[p]; ++i) {
res = min(res, a[i]); // 枚举第一个块
}
for (int i(p + 1); i < q; ++i) {
res = min(res, minn[i]); // 枚举中间的块
}
for (int i(L[q]); i <= r; ++i) {
res = min(res, a[i]); // 枚举最后一个块
}
return res;
}
int gmax(int l, int r) { // 同gmin,求最大值
int p(bl[l]), q(bl[r]), res(LLONG_MIN);
if (p == q) {
for (int i(l); i <= r; ++i) {
res = max(res, a[i]);
}
return res;
}
for (int i(l); i <= R[p]; ++i) {
res = max(res, a[i]);
}
for (int i(p + 1); i < q; ++i) {
res = max(res, maxn[i]);
}
for (int i(L[q]); i <= r; ++i) {
res = max(res, a[i]);
}
return res;
}
};
int f(int x) { // 模拟 B 的决策
if (x >= 0) {
return ans6;
}
return ans5;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q;
Block a(n), b(m), a2(n), a3(n); // a2 为负数处理、a3 为非负数处理
for (int i(1); i <= n; ++i) {
cin >> a.a[i];
a2.a[i] = a3.a[i] = a.a[i];
if (a.a[i] < 0) {
a3.a[i] = LLONG_MAX; // 非负数集合中排除负数
} else {
a2.a[i] = LLONG_MIN; // 负数集合中排除非负数
}
}
for (int i(1); i <= m; ++i) {
cin >> b.a[i];
}
a.init(); // 初始化块结构(不能在构造函数中初始化)
b.init();
a2.init();
a3.init();
while (q--) {
cin >> l_1 >> r_1 >> l_2 >> r_2;
// 获取区间最值
ans1 = a.gmax(l_1, r_1);
ans2 = a.gmin(l_1, r_1);
ans3 = a2.gmax(l_1, r_1);
ans4 = a3.gmin(l_1, r_1);
ans5 = b.gmax(l_2, r_2);
ans6 = b.gmin(l_2, r_2);
// 计算可能的最大值
ans = max(ans1 * f(ans1), ans2 * f(ans2)); // A取最大值和最小值的情况
if (ans3 != LLONG_MIN) {
ans = max(ans, ans3 * f(ans3)); // A取负数最大值
}
if (ans4 != LLONG_MAX) {
ans = max(ans, ans4 * f(ans4)); // A取非负数最小值
}
cout << ans << '\n';
}
return 0;
}星战(galaxy)




#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, q, a[N];
long long to[N], sum[N], tot, ans;
int main() {
mt19937 rnd(time(0));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
ans += (a[i] = rnd());
}
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
to[v] += a[u];
sum[v] = to[v];
tot += a[u];
}
scanf("%d", &q);
for (int i = 1, t, u, v; i <= q; ++i) {
scanf("%d%d", &t, &u);
if (t == 1) {
scanf("%d", &v);
to[v] -= a[u];
tot -= a[u];
}
if (t == 2) {
tot -= to[u];
to[u] = 0;
}
if (t == 3) {
scanf("%d", &v);
to[v] += a[u];
tot += a[u];
}
if (t == 4) {
tot += sum[u] - to[u];
to[u] = sum[u];
}
puts(tot == ans ? "YES" : "NO");
}
return 0;
}数据传输(transmit)



#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 200500, B = 20, K = 3;
ll n, q, T;
ll v[N], mn[N];
vector<ll> e[N];
ll f[B][N], dep[N];
ll dis[B][N][K][K];
void gi(ll &x, ll y) {
x = min(x, y);
}
void dfs(ll k, ll fa) {
dep[k] = dep[fa] + 1;
f[0][k] = fa;
for (ll i = 1; i < B; i++) {
f[i][k] = f[i - 1][f[i - 1][k]];
}
auto D = dis[0][k];
if (T == 1) {
D[0][0] = v[fa];
}
if (T == 2) {
D[0][0] = D[1][0] = v[fa];
D[0][1] = 0;
}
if (T == 3) {
D[0][0] = D[1][0] = D[2][0] = v[fa];
D[0][1] = D[1][2] = 0;
D[2][2] = mn[k];
}
for (ll i = 1; i < B; i++) {
for (ll x = 0; x < 3; x++) {
for (ll y = 0; y < 3; y++) {
for (ll z = 0; z < 3; z++) {
gi(dis[i][k][x][z], dis[i - 1][k][x][y] + dis[i - 1][f[i - 1][k]][y][z]);
}
}
}
}
for (auto to : e[k]) {
if (to != fa) {
dfs(to, k);
}
}
}
ll lca(ll x, ll y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (ll i = B - 1; i >= 0; i--) {
if (dep[f[i][x]] >= dep[y]) {
x = f[i][x];
}
}
if (x == y) {
return x;
}
for (ll i = B - 1; i >= 0; i--) {
if (f[i][x] != f[i][y]) {
x = f[i][x];
y = f[i][y];
}
}
return f[0][x];
}
vector<ll> calc(ll k, ll l) {
vector<ll> res(3, v[k]);
for (ll i = B - 1; i >= 0; i--) {
if (dep[f[i][k]] < dep[l]) {
continue;
}
vector<ll> nw = res;
fill(res.begin(), res.end(), 1e18);
for (ll x = 0; x < 3; x++) {
for (ll y = 0; y < 3; y++) {
gi(res[y], nw[x] + dis[i][k][x][y]);
}
}
k = f[i][k];
}
return res;
}
ll calcdis(ll x, ll y) {
ll l = lca(x, y);
auto F = calc(x, l), G = calc(y, l);
ll res = 1e18;
gi(res, F[0] + G[0] - v[l]);
for (ll i = 0; i < T; i++) {
for (ll j = 0; j < T; j++) {
gi(res, F[i] + G[j] + (mn[l] * (i + j > T)));
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> q >> T;
for (ll i = 1; i <= n; i++) {
cin >> v[i];
mn[i] = v[i];
}
for (ll i = 1; i < n; i++) {
ll x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
mn[x] = min(mn[x], v[y]);
mn[y] = min(mn[y], v[x]);
}
memset(dis, 1, sizeof(dis));
dfs(1, 0);
while (q--) {
ll s, t;
cin >> s >> t;
cout << calcdis(s, t) << '\n';
}
return 0;
}day1-1 格雷码


#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
unsigned long long k;
cin >> n >> k;
unsigned long long gray = k ^ (k >> 1);
string result(n, '0'); // 初始化为n个'0'的字符串
for (int i = 0; i < n; ++i) {
// 检查第(n-1 - i)位是否为1,若为1则将对应位置设为'1'
if (gray & (1ULL << (n - 1 - i))) {
result[i] = '1';
}
}
cout << result << endl;
return 0;
}方法思路
1、格雷码性质:第 k 个格雷码的二进制值可以通过 k ^ (k >> 1) 计算得到,其中^表示异或运算,>>表示右移运算。
2、转换为二进制字符串:将计算得到的格雷码值转换为 n 位的二进制字符串,不足 n 位时在前面补零。
代码解释
1、输入处理:读取输入的 n(格雷码的位数)和 k(编号)。
2、计算格雷码值:利用性质 gray = k ^ (k >> 1) 计算第 k 个格雷码的数值。
3、生成二进制字符串:初始化一个长度为 n 的字符串,所有字符初始为 '0'。通过位运算逐位检查格雷码值的每一位,若某一位为 1,则将字符串对应位置的字符设为 '1'。
4、输出结果:输出生成的 n 位二进制字符串。
这种方法的时间复杂度为 O (n),空间复杂度为 O (n),能够高效处理 n 最大为 64 的情况。
day1-2 括号树



#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n;
string brackets;
vector<vector<int>> children;
long long ans = 0;
void dfs(int u, vector<int>& stack, vector<int>& dp, long long& cnt) {
char c = brackets[u - 1];
int prev_stack_size = stack.size();
int prev_dp_size = dp.size();
long long prev_cnt = cnt;
int prev_left = -1; // 记录弹出的左括号位置,用于回溯
if (c == '(') {
stack.push_back(u);
dp.push_back(0);
} else {
if (!stack.empty()) {
prev_left = stack.back();
stack.pop_back();
int current_dp = (prev_left > 1 ? dp[prev_left - 2] : 0) + 1;
dp.push_back(current_dp);
cnt += current_dp;
} else {
dp.push_back(0);
}
}
ans ^= (long long)u * cnt;
for (int v : children[u]) {
dfs(v, stack, dp, cnt);
}
// 回溯操作,恢复进入当前节点前的状态
dp.pop_back();
if (c == '(') {
stack.pop_back();
} else {
if (prev_left != -1) {
stack.push_back(prev_left);
}
}
cnt = prev_cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> brackets;
children.resize(n + 1); // 节点编号从1到n
for (int i = 2; i <= n; ++i) {
int f;
cin >> f;
children[f].push_back(i);
}
vector<int> stack;
vector<int> dp;
long long cnt = 0;
dfs(1, stack, dp, cnt);
cout << ans << endl;
return 0;
}方法思路
1、合法括号子串判断:使用栈来匹配括号,维护一个动态规划数组dp,其中dp[i]表示以第i个字符结尾的合法括号子串数量。
2、树的遍历:通过 DFS 遍历树的每个节点,处理每个节点的括号时,维护栈和dp数组,并在回溯时恢复状态,以避免重复计算。
3、状态回溯:进入子节点前记录当前栈、dp数组和合法子串总数的状态,处理完子节点后恢复这些状态,确保每个节点的处理独立。
代码解释
1、输入处理:读取节点数n、括号字符串和父节点信息,构建子节点列表。
2、DFS 遍历:从根节点(节点 1)开始遍历,处理每个节点的括号:
3、左括号:压入栈,dp数组添加 0(以左括号结尾无合法子串)。
4、右括号:若栈非空,弹出栈顶左括号,计算以当前右括号结尾的合法子串数,更新dp和合法子串总数cnt。
5、状态回溯:处理完子节点后,恢复栈、dp数组和cnt到进入当前节点前的状态,确保后续节点处理正确。
6、异或和计算:每个节点处理时,计算i * k_i并累加到异或和ans中。
这种方法确保了每个节点的处理时间为 O (1)(均摊),整体时间复杂度为 O (n),空间复杂度为 O (n),适用于大规模数据。
day1-3 传统型



#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 2010;
vector<int> adj[MAXN];
int pos[MAXN]; // 数字i的初始节点
int ans[MAXN]; // 数字i的最终节点
int parent[MAXN]; // BFS中记录父节点
// 查找从u到v的路径(节点序列,不包含u,包含v)
vector<int> findPath(int u, int v, int n) {
fill(parent, parent + n + 1, -1);
queue<int> q;
q.push(u);
parent[u] = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == v) break;
for (int neighbor : adj[cur]) {
if (parent[neighbor] == -1) {
parent[neighbor] = cur;
q.push(neighbor);
}
}
}
vector<int> path;
int cur = v;
while (parent[cur] != 0) {
path.push_back(cur);
cur = parent[cur];
}
reverse(path.begin(), path.end());
return path;
}
// 查找u所在连通块中的最小节点
int findMinNode(int u, int n) {
vector<bool> visited(n + 1, false);
queue<int> q;
q.push(u);
visited[u] = true;
int minNode = u;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur < minNode) minNode = cur;
for (int neighbor : adj[cur]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
return minNode;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> pos[i];
ans[i] = pos[i];
adj[i].clear();
}
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
int u = ans[i];
int minNode = findMinNode(u, n);
if (u == minNode) continue;
vector<int> path = findPath(u, minNode, n);
ans[i] = minNode;
// 移除路径上的边(简化处理,实际需更精确标记)
int prev = u;
for (int v : path) {
auto& vec = adj[prev];
vec.erase(find(vec.begin(), vec.end(), v));
auto& vec2 = adj[v];
vec2.erase(find(vec2.begin(), vec2.end(), prev));
prev = v;
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << (i == n ? "\n" : " ");
}
}
return 0;
}方法思路
1、树的表示:使用邻接表表示树的结构。
2、贪心策略:对于每个数字从 1 到 n,找到其当前所在节点所在连通块中编号最小的节点,然后通过路径查找将该数字移动到该最小节点。
3、路径查找:使用广度优先搜索(BFS)查找当前节点到最小节点的路径,并标记路径上的边为已处理,确保后续处理不重复使用这些边。
代码解释
1、输入处理:读取多组测试数据,构建树的邻接表,并记录每个数字的初始节点。
2、查找最小节点:对于每个数字,使用 BFS 查找其所在连通块中编号最小的节点。
3、路径查找:使用 BFS 查找当前节点到最小节点的路径。
4、更新节点与边:将数字移动到最小节点,并移除路径上的边,确保后续处理不重复使用这些边。
5、输出结果:输出每个数字最终所在的节点编号,形成字典序最小的排列。
该方法通过贪心策略和 BFS 路径查找,确保每次将数字移动到最小可能的节点,从而得到字典序最小的结果。
day2-1 Emiya家今天的饭



#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
// 计算总方案数:所有选至少一道且烹饪方法不同的方案数
long long total = 1;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = 0; j < m; ++j) {
sum = (sum + a[i][j]) % MOD;
}
total = total * (sum + 1) % MOD; // 每道可选择任意食材或不选
}
total = (total - 1 + MOD) % MOD; // 减去都不选的情况
long long invalid = 0;
// 对每种食材j,计算非法方案数(该食材使用次数超过一半)
for (int j = 0; j < m; ++j) {
// dp[i][d + n]表示前i道烹饪方法,j的数量比其他食材多d的方案数
vector<vector<int>> dp(n + 1, vector<int>(2 * n + 2, 0));
dp[0][n] = 1; // 初始状态:0道,差值为0
for (int i = 1; i <= n; ++i) {
int sum_a = 0;
for (int k = 0; k < m; ++k) {
sum_a = (sum_a + a[i - 1][k]) % MOD;
}
int aj = a[i - 1][j];
int others = (sum_a - aj + MOD) % MOD;
// 遍历前i-1道的所有可能差值
for (int d = -(i - 1); d <= i - 1; ++d) {
int pos = d + n;
if (dp[i - 1][pos] == 0) continue;
// 不选当前烹饪方法
dp[i][pos] = (dp[i][pos] + dp[i - 1][pos]) % MOD;
// 选当前烹饪方法的j食材
dp[i][pos + 1] = (dp[i][pos + 1] + (long long)dp[i - 1][pos] * aj) % MOD;
// 选当前烹饪方法的非j食材
dp[i][pos - 1] = (dp[i][pos - 1] + (long long)dp[i - 1][pos] * others) % MOD;
}
}
// 统计差值大于0的情况(j的数量超过一半)
for (int pos = n + 1; pos <= 2 * n; ++pos) {
invalid = (invalid + dp[n][pos]) % MOD;
}
}
long long ans = (total - invalid + MOD) % MOD;
cout << ans << endl;
return 0;
}方法思路
1、总方案数计算:首先计算所有满足 “烹饪方法互不相同” 的方案数(至少选一道菜)。对于每道烹饪方法,可以选择其中一种食材或不选,因此总方案数为所有烹饪方法可选情况的乘积减 1(减去都不选的情况)。
2、非法方案数计算:对于每种食材,计算存在该食材使用次数超过一半的非法方案数。使用动态规划来跟踪每道烹饪方法选择后,该食材数量与其他食材数量的差值,从而判断是否超过一半。
3、结果计算:总合法方案数等于总方案数减去所有非法方案数的和,结果对 998244353 取模。
代码解释
1、输入处理:读取烹饪方法数n和食材数m,以及每道烹饪方法使用各食材的菜数。
2、总方案数计算:通过遍历每道烹饪方法,计算其可选情况的乘积,再减 1 得到至少选一道的总方案数。
3、非法方案数计算:对每种食材,使用动态规划跟踪其数量与其他食材数量的差值,统计差值大于 0 的情况(即该食材使用次数超过一半)。
4、结果计算:总合法方案数为总方案数减去所有非法方案数的和,确保结果为非负数后输出。
该方法通过动态规划高效处理了每种食材的非法情况,确保了时间复杂度和空间复杂度在合理范围内。
day2-2 划分



#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10; // 调整为更常见的测试规模,可根据需要扩大
const ll INF = LLONG_MAX / 2;
ll a[MAXN];
ll sum[MAXN];
ll dp[MAXN]; // dp[i]表示前i个元素的最小平方和
ll last[MAXN]; // last[i]表示前i个元素最后一段的和
int main() {
int n, type;
scanf("%d%d", &n, &type);
// 读取或生成数组a
if (type == 0) {
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
}
} else {
ll x, y, z, b1, b2;
int m;
scanf("%lld%lld%lld%lld%lld%d", &x, &y, &z, &b1, &b2, &m);
vector<ll> b(n + 2); // 1-based索引
b[1] = b1;
if (n >= 2) b[2] = b2;
for (int i = 3; i <= n; ++i) {
b[i] = (x * b[i - 1] + y * b[i - 2] + z) % (1LL << 30);
}
int prev_p = 0;
for (int j = 0; j < m; ++j) {
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
ll len = r - l + 1;
for (int i = prev_p + 1; i <= p && i <= n; ++i) {
a[i - 1] = (b[i] % len) + l;
}
prev_p = p;
}
}
// 计算前缀和
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i - 1];
}
// 初始化DP
dp[0] = 0;
last[0] = 0; // 前0个元素没有段,用0作为初始值
for (int i = 1; i <= n; ++i) {
dp[i] = INF;
// 寻找最佳的j,j < i
for (int j = 0; j < i; ++j) {
ll current_sum = sum[i] - sum[j];
// 关键条件:当前段的和 >= 前一段的和
if (current_sum >= last[j]) {
ll candidate = dp[j] + current_sum * current_sum;
if (candidate < dp[i]) {
dp[i] = candidate;
last[i] = current_sum;
}
}
}
}
printf("%lld\n", dp[n]);
return 0;
}方法思路
1、动态规划状态定义:dp[i] 表示前 i 个元素的最小平方和,last[i] 表示前 i 个元素划分的最后一段的和。
2、状态转移:对于每个 i,寻找所有 j < i 使得 sum[i] - sum[j] >= last[j](保证当前段和 >= 前一段和),则 dp[i] = min(dp[j] + (sum[i]-sum[j])²),同时更新 last[i] = sum[i]-sum[j]。
3、优化策略:利用前缀和的单调性,维护有效候选 j 的集合,避免不必要的计算。
代码解释
1、明确判断条件 current_sum >= last[j],确保当前段的和大于等于前一段的和,严格满足非递减要求。
2、动态规划初始化:dp[0] = 0 表示空序列的平方和为 0,last[0] = 0 作为初始参考值。
3、状态转移:对每个位置 i,遍历所有可能的前一段结束位置 j,计算当前段和并检查非递减条件,更新最小平方和及最后一段的和。
day2-3 树的重心



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
vector<int> adj[MAXN];
// 计算以u为根,排除exclude节点的子树大小
int compute_size(int u, int parent, int exclude) {
int s = 1;
for (int v : adj[u]) {
if (v != parent && v != exclude) {
s += compute_size(v, u, exclude);
}
}
return s;
}
// 查找以root为根,排除exclude节点的子树的所有重心
vector<int> find_centroids(int root, int exclude, int total_size) {
vector<int> centroids;
function<void(int, int, int&)> dfs = [&](int u, int p, int& current_size) {
current_size = 1;
int max_sub = 0;
for (int v : adj[u]) {
if (v != p && v != exclude) {
int child_size = 0;
dfs(v, u, child_size);
current_size += child_size;
max_sub = max(max_sub, child_size);
}
}
max_sub = max(max_sub, total_size-current_size);
if (max_sub <= total_size / 2) {
centroids.push_back(u);
}
};
int dummy = 0;
dfs(root, exclude, dummy);
return centroids;
}
ll solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) adj[i].clear();
vector<pair<int, int>> edges;
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
edges.emplace_back(u, v);
}
ll ans = 0;
for (auto& e : edges) {
int u = e.first, v = e.second;
// 计算分割后两个子树的大小
int s = compute_size(u, -1, v);
int t = n-s;
// 查找两个子树的重心
vector<int> c1 = find_centroids(u, v, s);
vector<int> c2 = find_centroids(v, u, t);
// 累加重心编号
for (int x : c1) ans += x;
for (int x : c2) ans += x;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--) {
cout << solve() << '\n';
}
return 0;
}方法思路
1、子树大小计算:对于每条边,删除后会得到两个子树,需要分别计算这两个子树的大小。
2、重心查找:对于每个子树,遍历其所有节点,判断每个节点是否为该子树的重心。判断条件是:删除该节点后,其所有子树的大小(包括父方向的子树)均不超过子树总大小的一半。
3、遍历所有边:对每条边,分别处理分割后的两个子树,找到各自的重心并求和,最终累加所有边的结果。
代码解释
1、compute_size函数:计算以u为根,排除exclude节点的子树大小。通过递归遍历子树,累加所有子节点的大小(排除父节点和exclude节点)。
2、find_centroids函数:查找以root为根,排除exclude节点的子树的所有重心。使用深度优先搜索(DFS)遍历子树,计算每个节点的最大子树大小(包括父方向的子树大小),判断是否为重心。
3、solve函数:处理每组测试用例,读取树的结构,遍历每条边,计算分割后两个子树的大小,查找各自的重心并累加结果。
该方法通过递归和深度优先搜索高效处理每个子树的重心查找,确保了时间复杂度在合理范围内,能够处理题目给定的数据规模。
1、廊桥分配



//参考代码1
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e5 + 5;
struct e {
int st, ed;
} a[Maxn];
bool cmp(e x, e y) {
return x.st < y.st;
}
priority_queue<int> hp_id;
priority_queue<pair<int, int>> hp_ed;
int n, m1, m2, ca[Maxn], cb[Maxn];
int main() {
scanf("%d%d%d", &n, &m1, &m2);
for (int i = 1; i <= m1; ++i) {
scanf("%d%d", &a[i].st, &a[i].ed);
}
sort(a + 1, a + m1 + 1, cmp);
for (int i = 1; i <= n; ++i) {
hp_id.push(-i);
}
for (int i = 1; i <= m1; ++i) {
if (!hp_ed.empty()) {
while (-hp_ed.top().first < a[i].st) {
hp_id.push(-hp_ed.top().second);
hp_ed.pop();
if (hp_ed.empty()) {
break;
}
}
}
if (!hp_id.empty()) {
int x = -hp_id.top();
hp_id.pop();
ca[x]++;
hp_ed.push(make_pair(-a[i].ed, x));
}
}
for (int i = 1; i <= n; ++i) {
ca[i] += ca[i - 1];
}
while (!hp_ed.empty()) {
hp_ed.pop();
}
while (!hp_id.empty()) {
hp_id.pop();
}
for (int i = 1; i <= m2; ++i) {
scanf("%d%d", &a[i].st, &a[i].ed);
}
sort(a + 1, a + m2 + 1, cmp);
for (int i = 1; i <= n; ++i) {
hp_id.push(-i);
}
for (int i = 1; i <= m2; ++i) {
if (!hp_ed.empty()) {
while (-hp_ed.top().first < a[i].st) {
hp_id.push(-hp_ed.top().second);
hp_ed.pop();
if (hp_ed.empty()) {
break;
}
}
}
if (!hp_id.empty()) {
int x = -hp_id.top();
hp_id.pop();
cb[x]++;
hp_ed.push(make_pair(-a[i].ed, x));
}
}
for (int i = 1; i <= n; ++i) {
cb[i] += cb[i - 1];
}
int mx_ans = 0;
for (int i = 0; i <= n; ++i) {
mx_ans = max(mx_ans, ca[i] + cb[n - i]);
}
printf("%d", mx_ans);
return 0;
}//参考代码2
#include <bits/stdc++.h>
using namespace std;
// 计算某类航班(国内或国际)分配bridgeNum个廊桥时,能停靠的最大飞机数
int countPlanes(vector<pair<int, int>>& flights, int bridgeNum) {
if (bridgeNum == 0) return 0;
sort(flights.begin(), flights.end()); // 按到达时间升序排序
// used: 存储(离开时间, 廊桥编号),小根堆(按离开时间排序,便于释放过期廊桥)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> used;
// idle: 存储空闲廊桥编号,小根堆(便于分配最小编号的空闲廊桥)
priority_queue<int, vector<int>, greater<>> idle;
for (int i = 1; i <= bridgeNum; ++i) {
idle.push(i);
}
int res = 0;
for (auto& flight : flights) {
int arrTime = flight.first, depTime = flight.second;
// 释放所有离开时间 <= 当前航班到达时间的廊桥(将这些廊桥加入空闲队列)
while (!used.empty() && used.top().first <= arrTime) {
idle.push(used.top().second);
used.pop();
}
// 若有空闲廊桥,分配给当前航班
if (!idle.empty()) {
int bridgeId = idle.top();
idle.pop();
used.push({depTime, bridgeId});
res++;
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m1, m2;
cin >> n >> m1 >> m2;
vector<pair<int, int>> domestic, international;
// 读取国内航班信息
for (int i = 0; i < m1; ++i) {
int a, b;
cin >> a >> b;
domestic.emplace_back(a, b);
}
// 读取国际航班信息
for (int i = 0; i < m2; ++i) {
int a, b;
cin >> a >> b;
international.emplace_back(a, b);
}
// 计算国内分配0~n个廊桥时的最大停靠数
vector<int> ca(n + 1);
for (int i = 0; i <= n; ++i) {
ca[i] = countPlanes(domestic, i);
}
// 计算国际分配0~n个廊桥时的最大停靠数
vector<int> cb(n + 1);
for (int i = 0; i <= n; ++i) {
cb[i] = countPlanes(international, i);
}
// 枚举所有分配方案,找到最大值
int maxAns = 0;
for (int i = 0; i <= n; ++i) {
maxAns = max(maxAns, ca[i] + cb[n - i]);
}
cout << maxAns << endl;
return 0;
}2、括号序列



//参考代码1
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 550, mo = 1e9 + 7;
LL dp[N][N][5];
int n, k;
char S[N];
signed main() {
scanf("%d%d", &n, &k);
scanf("%s", S + 1);
// 初始化边界
for (int i = 1; i <= n; ++i) {
dp[i][i - 1][0] = 1;
}
// 枚举区间长度
for (int len = 1; len <= n; ++len) {
// 枚举左右端点
for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
// 处理长度不超过k的*或?序列
if (len <= k && dp[i][j - 1][0] && (S[j] == '*' || S[j] == '?')) {
dp[i][j][0] = 1;
}
// 用子区间转移(长度至少为2才有意义)
if (len >= 2) {
// 判断左右端点是否为匹配的括号
if ((S[i] == '(' || S[i] == '?') && (S[j] == ')' || S[j] == '?')) {
dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +
dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % mo;
}
// 枚举子区间的断点
for (int t = i; t <= j - 1; ++t) {
dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % mo;
dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % mo;
dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % mo;
}
}
// 合并状态
dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % mo;
}
}
printf("%lld", dp[1][n][3]);
return 0;
}//参考代码2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 550;
const int MOD = 1e9 + 7;
int n, k;
char s[N];
LL dp[N][N][5]; // dp[i][j][0~4] 分别对应不同状态
int main() {
scanf("%d%d", &n, &k);
scanf("%s", s + 1); // 字符串从下标1开始存储
// 初始化:空区间是合法的*串(用于后续转移)
for (int i = 1; i <= n; ++i) {
dp[i][i - 1][0] = 1;
}
// 枚举区间长度
for (int len = 1; len <= n; ++len) {
// 枚举左端点i,右端点j = i + len - 1
for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
// 状态0:*串,长度<=k,且j位置可填*或?,且[i,j-1]是*串
if (len <= k && dp[i][j - 1][0] && (s[j] == '*' || s[j] == '?')) {
dp[i][j][0] = 1;
}
// 长度至少为2时,处理其他状态
if (len >= 2) {
// 状态1:(A)形式,判断i和j是否可作为括号
if ((s[i] == '(' || s[i] == '?') && (s[j] == ')' || s[j] == '?')) {
dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +
dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % MOD;
}
// 枚举断点t,拆分区间为[i,t]和[t+1,j]
for (int t = i; t < j; ++t) {
// 状态2:A*B,A是状态3,B是状态0
dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % MOD;
// 状态3:A*B,A是状态2或3,B是状态1;或直接由状态1转移(后续会加)
dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % MOD;
// 状态4:A*B,A是状态0,B是状态3
dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % MOD;
}
// 状态3还可由自身的状态1转移而来(总合法状态包含(A)形式)
dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % MOD;
}
}
}
// 最终答案:整个区间[1,n]的合法超级括号序列数量(状态3)
printf("%lld\n", dp[1][n][3]);
return 0;
}3、回文


#include <bits/stdc++.h>
using namespace std;
int t, n, l, r, l1, r1;
int a[1000010], ton1[1000010], ton[1000010], vis[1000010];
stack<int> q;
vector<int> q1;
int read() {
int asd = 0, qwe = 1;
char zxc;
while (!isdigit(zxc = getchar())) {
if (zxc == '-') {
qwe = -1;
}
}
while (isdigit(zxc)) {
asd = asd * 10 + zxc - '0';
zxc = getchar();
}
return asd * qwe;
}
int dfs(int k) {
// cout << k << " " << l1 << " " << r1 << " " << l << " " << r << " " << q.size() << endl;
if (k == n / 2) {
for (int i = 0; i <= n / 2 - 1; i++) {
if (q1[i] == 1) {
cout << "L";
} else {
cout << "R";
}
}
while (!q.empty()) {
int x = q.top();
q.pop();
if (a[l] == x) {
cout << "L";
l++;
} else {
cout << "R";
r--;
}
}
cout << endl;
return 1;
} else {
// cout << ton[l1 + 1] << l - 1 << ton[l1 + 1] << r + 1 << endl;
if (vis[a[l1 + 1]] == 0 && (ton[l1 + 1] == l - 1 || ton[l1 + 1] == r + 1)) {
l1++;
if (ton[l1] == l - 1) {
l--;
} else {
r++;
}
q1.push_back(1);
q.push(a[l1]);
vis[a[l1]] = 1;
return dfs(k + 1);
} else if (vis[a[r1 - 1]] == 0 && (ton[r1 - 1] == l - 1 || ton[r1 - 1] == r + 1)) {
r1--;
if (a[ton[r1]] == a[l - 1]) {
l--;
} else {
r++;
}
q1.push_back(2);
q.push(a[r1]);
vis[a[r1]] = 1;
return dfs(k + 1);
} else {
return 0;
}
}
}
int main() {
// freopen("palin.in" , "r" , stdin);
// freopen("palin.out" , "w" , stdout);
t = read();
while (t--) {
n = read() * 2;
l1 = 0;
r1 = n + 1;
while (!q.empty()) {
q.pop();
}
q1.clear();
for (int i = 1; i <= n; i++) {
vis[i] = ton1[i] = ton[i] = 0;
}
for (int i = 1; i <= n; i++) {
a[i] = read();
if (ton1[a[i]]) {
ton[i] = ton1[a[i]];
ton[ton1[a[i]]] = i;
} else {
ton1[a[i]] = i;
}
}
// 第一种尝试:从左侧开始
vis[a[++l1]] = 1;
l = r = ton[l1];
q1.push_back(1);
q.push(a[l1]);
if (dfs(1) == 0) {
// 重置状态,尝试从右侧开始
for (int i = 1; i <= n; i++) {
vis[i] = 0;
}
q1.clear();
l1 = 0;
r1 = n + 1;
while (!q.empty()) {
q.pop();
}
vis[a[--r1]] = 1;
l = r = ton[r1];
q1.push_back(2);
q.push(a[r1]);
if (dfs(1) == 0) {
cout << -1 << endl;
}
}
}
return 0;
}4、交通规划



#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 360005; // 增大数组容量适配题目规模
const ll INF = 1e18;
struct Edge {
int to, rev;
ll cap;
Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {}
};
vector<Edge> g[MAXN];
int level[MAXN], iter[MAXN];
int n, m, T;
// 添加双向边
void add_edge(int from, int to, ll cap) {
g[from].emplace_back(to, (int)g[to].size(), cap);
g[to].emplace_back(from, (int)g[from].size() - 1, 0); // 反向边初始容量为0
}
// BFS构建层次图
void bfs(int s) {
memset(level, -1, sizeof(level));
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (const Edge& e : g[u]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
}
// DFS寻找增广路
ll dfs(int u, int t, ll f) {
if (u == t) return f;
for (int& i = iter[u]; i < g[u].size(); ++i) {
Edge& e = g[u][i];
if (e.cap > 0 && level[u] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
// 计算最大流(最小割)
ll max_flow(int s, int t) {
ll flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
memset(iter, 0, sizeof(iter));
ll f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
}
// 射线编号转网格坐标(修正版)
pair<int, int> get_coord(int p) {
p--; // 转为0基索引
if (p < m) { // 上边界:(1, p+1)
return {0, p};
}
p -= m;
if (p < n-1) { // 右边界:(p+2, m)
return {p+1, m-1};
}
p -= n-1;
if (p < m) { // 下边界:(n, m-p)
return {n-1, m-1 - p};
}
p -= m; // 左边界:(n-p, 1)
return {n-1 - p, 0};
}
int main() {
// 移除文件操作,适配标准输入输出
scanf("%d%d%d", &n, &m, &T);
// 存储水平和垂直边的权重
vector<vector<ll>> horizontal(n-1, vector<ll>(m));
vector<vector<ll>> vertical(n, vector<ll>(m-1));
// 读取水平边(上下相邻格子)
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%lld", &horizontal[i][j]);
}
}
// 读取垂直边(左右相邻格子)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m-1; ++j) {
scanf("%lld", &vertical[i][j]);
}
}
while (T--) {
int k;
scanf("%d", &k);
// 清空图结构
for (int i = 0; i < MAXN; ++i) {
g[i].clear();
}
int S = 0; // 源点(黑色)
int T_node = n * m + 1; // 汇点(白色)
int node_cnt = n * m; // 网格节点总数
// 连接水平相邻格子(i,j)和(i+1,j)
for (int i = 0; i < n-1; ++i) {
for (int j = 0; j < m; ++j) {
int u = i * m + j + 1; // 网格节点编号从1开始
int v = (i+1) * m + j + 1;
ll cap = horizontal[i][j];
add_edge(u, v, cap);
add_edge(v, u, cap); // 双向边
}
}
// 连接垂直相邻格子(i,j)和(i,j+1)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m-1; ++j) {
int u = i * m + j + 1;
int v = i * m + (j+1) + 1;
ll cap = vertical[i][j];
add_edge(u, v, cap);
add_edge(v, u, cap); // 双向边
}
}
// 处理附加点约束
for (int i = 0; i < k; ++i) {
ll x3;
int p, t;
scanf("%lld%d%d", &x3, &p, &t);
// 获取射线对应的网格坐标
auto [r, c] = get_coord(p);
if (r < 0 || r >= n || c < 0 || c >= m) {
// 无效坐标处理
continue;
}
int node = r * m + c + 1; // 转换为节点编号
if (t == 1) { // 必须染黑色(连接到源点)
add_edge(S, node, INF); // 保证不会被割开
add_edge(node, S, x3); // 附加权重
} else { // 必须染白色(连接到汇点)
add_edge(node, T_node, INF); // 保证不会被割开
add_edge(T_node, node, x3); // 附加权重
}
}
// 计算并输出最小割(最大流)
printf("%lld\n", max_flow(S, T_node));
}
return 0;
}T1、决斗(duel)


#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, x;
struct bj {
int num;
bool flag, gjf;
};
vector<bj> v;
int bs(int k) {
int r = n - 1, l = 0, res = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (v[mid].num > k && v[mid].flag == true && v[mid].gjf == true) {
res = mid;
r = mid - 1;
} else l = mid + 1;
}
return res;
}
bool cmp(bj a, bj b) {
return a.num < b.num;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
v.push_back({x, true, true});
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n - 1; i++) {
int re = bs(v[i].num);
if (re == -1) continue;
else {
v[i].flag = false;
v[re].gjf = false;
}
}
int ans = 0;
for (int i = 0; i < n; i++)
if (v[i].flag == true) ans++;
cout << ans;
return 0;
}T2、超速检测(detect)




#include<bits/stdc++.h>
using namespace std;
bool Mbegin;
void File_Work(){
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
}
const int N=1e5+8;
int n,m,L,V,p[N],d[N],v[N],a[N];
struct Interval{
int l,r;
void init(){
l=r=0;
}
friend bool operator <(Interval a,Interval b){
if(a.r!=b.r)
return a.r<b.r;
return a.l<b.l;
}
}itv[N];
bool check(int pos,int i){
int x=p[pos]-d[i];
int v2=v[i]*v[i]+2*a[i]*x;
if(V*V<v2)
return 1;
return 0;
}
void MAIN(){
for(int i=1;i<=n;i++)
p[i]=0,itv[i].init();
cin>>n>>m>>L>>V;
for(int i=1;i<=n;i++)
cin>>d[i]>>v[i]>>a[i];
for(int i=1;i<=m;i++)
cin>>p[i];
sort(p+1,p+m+1);
int ans1=0;
for(int i=1;i<=n;i++){
if(p[m]<d[i])
continue;
int pos=lower_bound(p+1,p+m+1,d[i])-p;
if(a[i]==0&&v[i]>V)
itv[++ans1]={pos,m};
else if(a[i]<0){
int x=p[pos]-d[i];
int v2=v[i]*v[i]+2*a[i]*x;
if(V*V<v2){
int l=pos,r=m,res=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid,i)==1){
res=mid;
l=mid+1;
}
else
r=mid-1;
}
itv[++ans1]={pos,res};
}
}
else if(a[i]>0){
int x=p[m]-d[i];
int v2=v[i]*v[i]+2*a[i]*x;
if(V*V<v2){
int l=pos,r=m,res=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid,i)==1){
res=mid;
r=mid-1;
}
else
l=mid+1;
}
itv[++ans1]={res,m};
}
}
}
cout<<ans1<<' ';
sort(itv+1,itv+ans1+1);
int ans2=0,cur;
for(int i=1;i<=ans1;i++){
if(itv[i].l<=cur&&cur<=itv[i].r)
continue;
ans2++;
cur=itv[i].r;
}
cout<<m-ans2<<'\n';
}
bool Mend;
int main(){
// File_Work();
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cerr<<fixed<<setprecision(3)<<(&Mbegin-&Mend)/1048576.0<<" MB\n\n\n";
int testid=0,testnum=1;
// cin>>testid;
cin>>testnum;
while(testnum--)
MAIN();
cerr<<"\n\n\n"<<fixed<<setprecision(0)<<1e3*clock()/CLOCKS_PER_SEC<<" ms";
return 0;
}T3、染色(color)



//参考代码1
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll t,anstmp;
ll dp[2000005][2];
ll lst[2000005];
struct num{
ll n,last;
}a[2000005];
int main(){
ll t;
scanf("%lld",&t);
while (t--){
ll n;
scanf("%lld",&n);
memset(dp,0,sizeof(dp));
memset(lst,0,sizeof(lst));
anstmp=0;
for (ll i=1;i<=n;i++){
scanf("%lld",&a[i].n);
if (lst[a[i].n]) a[i].last=lst[a[i].n];
else a[i].last=0;
lst[a[i].n]=i;
if (a[i-1].n==a[i].n) anstmp=anstmp+a[i].n;
}
for (ll i=1;i<=n;i++){
if (a[i].n==a[i-1].n){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-1][1];
continue;
}
else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
if (a[i].last) dp[i][1]=max(max(dp[a[i].last][0],dp[a[i].last][1]),max(dp[a[i].last+1][0],dp[a[i].last+1][1]))+a[i].n;
}
printf("%lld\n",max(dp[n][0],dp[n][1])+anstmp);
}
return 0;
}//参考代码2
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
namespace work{
const int N = 2e5+5,M = 1e6 + 5;
int n,a[M],s[M],f[M],t[M];
void solve() {
memset(s,0,sizeof(s));
memset(t,0,sizeof(t));
memset(f,0,sizeof(f));
n = rd();
for(int i = 1;i<=n;i++) a[i] = rd();
for(int i = 2;i<=n;i++) s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
for(int i = 1;i<=n;i++) {
f[i] = f[i - 1];
if(t[a[i]]) f[i] = max(f[i],f[t[a[i]] + 1] + a[i] + s[i] - s[t[a[i]] + 1]);
t[a[i]] = i;
}
wt(f[n]);putchar('\n');
}
}
signed main() {
int T = rd();
while(T--) work::solve();
return 0;
}T4、擂台游戏(arena)




//参考代码1
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
template<class T>void rd(T &x) {
static char ch(0);
for(x=0,ch=getc(); !isdigit(ch); ch=getc());
for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
}
template<class T>void wr(T x,const char End='\n') {
static int top(0);
static int st[50];
do st[++top]=x%10,x/=10;
while(x);
while(top)putc(st[top]^'0'),--top;
putc(End);
}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
if(L>R)return;
if(!h) {
int x(u-(1<<k)+1);
if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
return;
}
dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
rd(n),rd(m);
while((1<<k)<n)++k;
FOR(i,1,n)rd(a_[i]);
FOR(i,1,m)rd(c[i]);
DOR(i,k-1,0) {
scanf("%s",s);
DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
}
rd(Q);
while(Q--) {
static int X[4];
rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
FOR(i,1,n)a[i]=a_[i]^X[i&3];
dfs0(1,k),RCL(sum+1,0,ll,n);
FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
FOR(i,1,n)sum[i]+=sum[i-1];
ll ans(0);
FOR(i,1,m)ans^=i*sum[c[i]];
wr(ans);
}
return 0;
}//参考代码2
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
template<class T>void rd(T &x) {
static char ch(0);
for(x=0,ch=getc(); !isdigit(ch); ch=getc());
for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
}
template<class T>void wr(T x,const char End='\n') {
static int top(0);
static int st[50];
do st[++top]=x%10,x/=10;
while(x);
while(top)putc(st[top]^'0'),--top;
putc(End);
}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
if(L>R)return;
if(!h) {
int x(u-(1<<k)+1);
if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
return;
}
dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
rd(n),rd(m);
while((1<<k)<n)++k;
FOR(i,1,n)rd(a_[i]);
FOR(i,1,m)rd(c[i]);
DOR(i,k-1,0) {
scanf("%s",s);
DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
}
rd(Q);
while(Q--) {
static int X[4];
rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
FOR(i,1,n)a[i]=a_[i]^X[i&3];
dfs0(1,k),RCL(sum+1,0,ll,n);
FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
FOR(i,1,n)sum[i]+=sum[i-1];
ll ans(0);
FOR(i,1,m)ans^=i*sum[c[i]];
wr(ans);
}
return 0;
}//参考代码3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define ll long long
using namespace std;
const int N = (1 << 17) + 5;
int mx[20][N << 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1;
bool vis[N];
ll ans[N], sum;
struct node {
ll sum;
int x;
bool tp, d;
} t[N << 2];
inline void build(int x, int l, int r) {
if (l == r) {
t[x].x = l;
return ;
}
int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
build(lson);
build(rson);
int win = a[t[x << 1 | d].x] >= k;
t[x].x = t[x << 1 | (d ^ !win)].x;
if (!d && win)t[x].tp = 1, ok[r]++, ok[mid]--;
else t[x].tp = 0;
}
inline void build2(int x, int l, int r, int *mx) {
t[x].sum = (l + r) * (r - l + 1ll) / 2;
if (l == r)return ;
int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
if (~mx[x])mx[ls] = mx[rs] = mx[x];
else mx[x << 1 | d] = k;
build2(lson, mx);
build2(rson, mx);
}
inline void up(int x) {
sum += !vis[x] * x;
vis[x] = 1;
}
inline int rd() {
char c;
int f = 1;
while (!isdigit(c = getchar()))if (c == '-')f = -1;
int x = c - '0';
while (isdigit(c = getchar()))x = x * 10 + (c ^ 48);
return x * f;
}
inline char gc() {
char c;
while ((c = getchar()) <= ' ');
return c;
}
int main() {
// freopen("arena.in","r",stdin);
// freopen("arena.out","w",stdout);
n = rd();
m = rd();
for (int i = 1; i <= n; i++)aa[i] = rd();
for (int i = 1; i <= m; i++)c[i] = rd();
while (nn < n)nn <<= 1;
for (int i = 2; i <= nn; i++)lg[i] = lg[i >> 1] + 1;
for (int i = nn / 2; i; i >>= 1)
for (int j = i; j < i * 2; j++)
t[j].d = gc() - '0';
memset(mx, -1, sizeof mx);
for (int s = 0; (1 << s) <= nn; s++)
build2(1 << s, 1, nn>>s, mx[s]);
for (int T = rd(); T--;) {
int yh[4] = {rd(), rd(), rd(), rd()};
for (int i = 1; i <= n; i++)a[i] = aa[i] ^ yh[i & 3];
memset(ok, 0, sizeof ok);
build(1, 1, nn);
for (int i = nn, rt = 1, s = 0; i; i--) {
if ((1 << lg[i]) == i) {
if (i != nn)rt <<= 1, s++;
for (int j = 1; j <= i; j++)vis[j] = 0;
sum = 0;
up(t[rt].x);
}
ans[i] = sum;
if (ok[i] += ok[i + 1])continue;
up(i);
int x = i + nn - 1;
while (x != rt) {
int d = x & 1;
x >>= 1;
if (!d)
if (t[x].tp)sum += t[rs].sum;
else break;
else if (a[t[ls].x] >= mx[s][ls])up(t[ls].x);
}
}
ll num = 0;
for (int i = 1; i <= m; i++)num ^= i * ans[c[i]];
printf("%lld\n", num);
}
return 0;
}密码锁(lock)
【题目描述】
小Y有一把五个拨圈的密码锁。如图所示,每个拨圈上是从0到9的数字。每个拨圈都是从0到9的循环,即9拨动一个位置后可以变成0或8,

图1:密码锁
因为校园里比较安全,小Y采用的锁车方式是:从正确密码开始,随机转动密码锁仅一次;每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。当小Y选择同时转动两个相邻拨圈时,两个拨圈转动的幅度相同,即小Y可以将密码锁从00115转成11115,但不会转成12115。
时间久了,小Y也担心这么锁车的安全性,所以小Y记下了自己锁车后密码锁的n个状态,注意这n个状态都不是正确密码。
为了检验这么锁车的安全性,小Y有多少种可能的正确密码,使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部n个状态。
【输入格式】
从文件lock.in中读入数据。
输入的第一行包含一个正整数n,表示锁车后密码锁的状态数。
接下来n行每行包含五个整数,表示一个密码锁的状态。
【输出格式】
输出到文件lock.out中。
输出一行包含一个整数,表示密码锁的这n个状态按照给定的锁车方式能对应多少种正确密码。
【样例1输入】
【样例1输出】
【样例1解释】
一共有81种可能的方案。
其中转动一个拨圈的方案有45种,转动两个拨圈的方案有36种。
【样例2】
见选手目录下的lock/lock2.in与lock/lock2.ans。

