T1
This is a straightforward problem. Key reminder: read the problem carefully! Simpler problems are prone to errors.
T2
This is a straightforward problem. Greedy algorithms or dynamic programming can be used.
T3
Tip: When dealing with averages, subtract the average from all numbers and find subarrays with sum zero. Since the value range is small, enumerate possible averages. Handle negative values by using a bucket with an offset; avoid using memset to prevent TLE.
T4
With limited time, a crucial property was identified: numbers left of the minimum must form a non-increasing prefix, and those right must form a non-decreasing suffix. Enumerate positions for the minimum value to check validity. Core logic:
int minVal = *min_element(b, b + n);
vector<int> prefix(n, 1), suffix(n, 1);
for (int i = 0; i < n; ++i) {
if (b[i] == minVal) {
if (i > 0) prefix[i] = prefix[i-1] && (b[i] <= b[i-1]);
} else {
if (i > 0 && b[i] <= b[i-1]) prefix[i] = prefix[i-1];
}
}
for (int i = n-1; i >= 0; --i) {
if (b[i] == minVal) {
if (i < n-1) suffix[i] = suffix[i+1] && (b[i] <= b[i+1]);
} else {
if (i < n-1 && b[i] <= b[i+1]) suffix[i] = suffix[i+1];
}
}
for (int i = 0; i < n; ++i) {
if (b[i] == minVal && prefix[i] && suffix[i]) {
for (int j = 0; j < n; ++j) {
if (j != i && b[j] == minVal) cout << "INF ";
else cout << b[j] << " ";
}
cout << endl;
break;
}
}
T5
A construction problem. First, check if edge count constraints are met. If valid, add edges to satisfy constraints. Prioritize intra-component edges, then inter-component edges. If constraints cannot be met, output invalid.
National Day Joyful Contest Day 3
T1
Classic "General Crossing River" problem (geometric optimization).
T2
Simple binary search implementation.
T3
Meet-in-the-middle search with a trie tree. During building, maintain the maximum value in each subtree. When querying, traverse the trie by classifying bit differences. Core code:
void insert(int value, long long weight) {
int node = 0;
for (int bit = 30; bit >= 0; --bit) {
int curBit = (value >> bit) & 1;
if (!child[node][curBit]) child[node][curBit] = ++nodeCount;
maxVal[node][curBit] = max(maxVal[node][curBit], weight);
node = child[node][curBit];
}
}
long long query(int value) {
int node = 0;
long long result = LLONG_MIN;
for (int bit = 30; bit >= 0; --bit) {
int vBit = (value >> bit) & 1;
int mBit = (mask >> bit) & 1;
if (vBit) {
if (mBit) {
result = max(result, maxVal[node][1]);
if (!child[node][0]) return result;
node = child[node][0];
} else {
if (!child[node][1]) return result;
node = child[node][1];
}
} else {
if (mBit) {
result = max(result, maxVal[node][0]);
if (!child[node][1]) return result;
node = child[node][1];
} else {
if (!child[node][0]) return result;
node = child[node][0];
}
}
}
return result;
}
T4
Game theory problem. Use Grundy numbers or recursive analysis on a full binary tree. Each move changes all pieces simultaneously, so they stay on the same level. Recursively check states. Core code:
int solve(vector<int> positions, int player, int parity) {
int flag = parity;
for (int pos : positions) flag ^= color[pos];
vector<int> nextPos;
// Left move
for (int pos : positions) {
if (!children[pos].empty()) nextPos.push_back(children[pos][0]);
}
if (nextPos.empty()) {
if ((player && !flag) || (!player && flag)) return 1;
else return 0;
}
if (!solve(nextPos, player ^ 1, flag)) return 1;
// Right move
nextPos.clear();
for (int pos : positions) nextPos.push_back(children[pos][1]);
if (!solve(nextPos, player ^ 1, flag)) return 1;
// Both moves
nextPos.clear();
for (int pos : positions) {
nextPos.push_back(children[pos][0]);
nextPos.push_back(children[pos][1]);
}
if (!solve(nextPos, player ^ 1, flag)) return 1;
return 0;
}
T5
Each number has a cycle. High precision modulo is needed. Since modulus length up to 10^6, use digit-by-digit modulo (O(len)). For full points, exploit cycle length repetition and use bit packing (18 bits per long long). Core code:
for (int i = lenM; i >= 1; i -= 18) {
++blockCount;
for (int j = max(1, i - 17); j <= i; ++j) {
packedM[blockCount] = packedM[blockCount] * 10 + (s[j] - '0');
}
}
for (int i = 0; i < n; ++i) {
if (processed[i]) continue;
++cycleCount;
int x = a[i], time = 0;
do {
processed[x] = cycleCount;
cycles[cycleCount].push_back(x);
position[x] = time++;
x = a[x];
} while (x != a[i]);
}
for (int i = 0; i < cycleCount; ++i) {
long long mod = 0;
int size = cycles[i].size();
if (!visitedMod[size]) {
for (int j = blockCount; j >= 1; --j) {
mod = ((((mod % size) * (powBase % size)) % size) + packedM[j]) % size;
}
precomputedMod[size] = mod;
visitedMod[size] = true;
}
}
Multi-School Contest Day 1
T1
Invert the problem: treat unlimtied acceleration as +1 increments and unlimited deceleration as reverse steps.
T2
Maximum independent set on a tree. Use tree DP with memoization. Core code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 250000 + 10;
int n;
vector<pair<int, int>> edges;
vector<vector<int>> tree;
vector<array<int, 2>> dp;
vector<array<bool, 2>> feasible;
vector<array<bool, 2>> memo;
void dfs(int node, int parent) {
dp[node][1] = 1;
for (int child : tree[node]) {
if (child == parent) continue;
dfs(child, node);
dp[node][0] += max(dp[child][0], dp[child][1]);
dp[node][1] += dp[child][0];
}
}
void check(int node, int parent, int choice) {
if (memo[node][choice]) return;
memo[node][choice] = true;
feasible[node][choice] = true;
for (int child : tree[node]) {
if (child == parent) continue;
if (choice == 1) {
check(child, node, 0);
} else {
if (dp[child][0] == dp[child][1]) {
check(child, node, 1);
check(child, node, 0);
} else if (dp[child][0] > dp[child][1]) {
check(child, node, 0);
} else {
check(child, node, 1);
}
}
}
}
int main() {
cin >> n;
tree.resize(n + 1);
dp.assign(n + 1, {0, 0});
feasible.assign(n + 1, {false, false});
memo.assign(n + 1, {false, false});
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1, 0);
if (dp[1][0] == dp[1][1]) {
check(1, 0, 1);
check(1, 0, 0);
} else if (dp[1][0] > dp[1][1]) {
check(1, 0, 0);
} else {
check(1, 0, 1);
}
ll answer = 0;
int notTaken = 0;
for (int i = 1; i <= n; ++i) {
if (feasible[i][0]) {
answer += (n - 1);
++notTaken;
}
}
answer -= 1LL * notTaken * (notTaken - 1) / 2;
cout << answer << endl;
return 0;
}
T3
String modification with segment tree. For small queries, use brute force DP. For 5 characters, segment tree stores min costs for left/right endpoints. Full solution uses transformation to binary strings and offline processing. Core code:
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100000 + 10;
int n, m;
string s;
struct Query { int pos; char ch; int ans; };
vector<Query> queries;
struct Node {
int l, r;
int cost[2][2];
};
vector<Node> seg(4 * MAXN);
void update(int idx) {
for (int i = 0; i < 2; ++i)
for (int j = i; j < 2; ++j)
seg[idx].cost[i][j] = INF;
for (int i = 0; i < 2; ++i)
for (int j = i; j < 2; ++j)
for (int k = j; k < 2; ++k)
for (int l = k; l < 2; ++l)
seg[idx].cost[i][l] = min(seg[idx].cost[i][l],
seg[idx*2].cost[i][j] + seg[idx*2+1].cost[k][l]);
}
void build(int idx, int l, int r) {
seg[idx].l = l;
seg[idx].r = r;
if (l == r) {
for (int i = 0; i < 2; ++i)
for (int j = i; j < 2; ++j)
seg[idx].cost[i][j] = INF;
for (int i = 0; i < 2; ++i)
seg[idx].cost[i][i] = abs((s[l] - 'a') - i);
return;
}
int mid = (l + r) / 2;
build(idx*2, l, mid);
build(idx*2+1, mid+1, r);
update(idx);
}
void modify(int idx, int pos, int val) {
if (seg[idx].l == seg[idx].r) {
for (int i = 0; i < 2; ++i)
seg[idx].cost[i][i] = abs(val - i);
return;
}
int mid = (seg[idx].l + seg[idx].r) / 2;
if (pos <= mid) modify(idx*2, pos, val);
else modify(idx*2+1, pos, val);
update(idx);
}
int query(int idx) {
int res = INF;
for (int i = 0; i < 2; ++i)
for (int j = i; j < 2; ++j)
res = min(res, seg[idx].cost[i][j]);
return res;
}
int main() {
cin >> s;
n = s.size();
cin >> m;
queries.resize(m+1);
for (int i = 0; i < m; ++i) {
cin >> queries[i].pos >> queries[i].ch;
}
for (int i = 0; i <= m; ++i) queries[i].ans = 0;
for (int i = 0; i < 26; ++i) {
build(1, 0, n-1);
for (int j = 1; j <= n; ++j) {
int val = (s[j-1] - 'a' + 1 >= i) ? 1 : 0;
modify(1, j-1, val);
}
for (int j = 0; j <= m; ++j) {
if (j) {
int val = (queries[j].ch - 'a' + 1 >= i) ? 1 : 0;
modify(1, queries[j].pos-1, val);
}
queries[j].ans += query(1);
}
}
for (int i = 0; i <= m; ++i)
cout << queries[i].ans << endl;
return 0;
}
T4
Unresolved.
Multi-School Contest Day 2
T1
Binary search for answer. Simulate with priority queue: each group of cows is proecssed with available "avatars" (similar to workers). Core code:
bool check(long long x) {
priority_queue<pair<long long, long long>> pq;
pq.push({LLONG_MIN, x});
for (int i = 0; i < n; ++i) {
long long now = cows[i].first;
long long time = cows[i].second;
while (now > 0 && !pq.empty() && pq.top().first + A <= time) {
auto top = pq.top(); pq.pop();
if (top.second > now) {
pq.push({top.first, top.second - now});
pq.push({max(top.first + A + C, time - B + C), now});
now = 0;
} else {
now -= top.second;
pq.push({max(top.first + A + C, time - B + C), top.second});
}
}
if (now > 0) return false;
}
return true;
}
T2
Tree knapsack problem. For small n,m, use edge-based 0/1 knapsack. For full points, leverage random tree property: sum of subtree sizes is O(n log n), so few distinct sizes. Use binary optimizaton. Core code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100000 + 10;
int n, m;
vector<tuple<int,int,int>> edges;
vector<vector<pair<int,int>>> tree;
vector<array<ll, 5>> cnt;
vector<ll> dp;
ll totalValue = 0;
void dfs(int node, int parent, int edgeVal) {
int size = 1;
for (auto [child, val] : tree[node]) {
if (child == parent) continue;
dfs(child, node, val);
size += subtreeSize[child];
}
totalValue += (ll)edgeVal * size * (n - size);
if (parent != -1) {
cnt[size][edgeVal-1]++;
}
}
int main() {
cin >> n >> m;
tree.assign(n, {});
for (int i = 0; i < n-1; ++i) {
int x, y, z;
cin >> x >> y >> z;
edges.emplace_back(x, y, z);
tree[x].push_back({y, z});
tree[y].push_back({x, z});
}
cnt.assign(n+1, {});
dfs(0, -1, 0);
dp.assign(m+1, 0);
for (int size = 1; size <= n; ++size) {
for (int val = 1; val <= 5; ++val) {
if (cnt[size][val-1] == 0) continue;
int k = 1;
while (k <= cnt[size][val-1]) {
int weight = size * k;
ll value = (ll)val * size * (n - size) * k;
for (int i = m; i >= weight; --i) {
dp[i] = max(dp[i], dp[i-weight] + value);
}
cnt[size][val-1] -= k;
k *= 2;
}
if (cnt[size][val-1] > 0) {
int weight = size * cnt[size][val-1];
ll value = (ll)val * size * (n - size) * cnt[size][val-1];
for (int i = m; i >= weight; --i) {
dp[i] = max(dp[i], dp[i-weight] + value);
}
}
}
}
cout << totalValue - dp[m] << endl;
return 0;
}