由于今晚有其他安排，未能参加比赛，赛后补题。

A 购买钢笔

根据题目要求进行模拟即可，共有三种颜色对应的情况：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int priceRed, priceBlue, priceGreen;
    cin >> priceRed >> priceBlue >> priceGreen;
    string selectedColor;
    cin >> selectedColor;
    
    if (selectedColor == "Red") {
        cout << min(priceBlue, priceGreen) << '\n';
    } else if (selectedColor == "Blue") {
        cout << min(priceRed, priceGreen) << '\n';
    } else {
        cout << min(priceRed, priceBlue) << '\n';
    }
    return 0;
}

B 直角三角形

给定三个平面坐标点，计算两两之间的欧氏距离平方，然后利用勾股定理判断是否构成直角三角形。直角三角形的充要条件是：某两条边的平方和等于第三条边的平方。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    
    // 计算各边长的平方
    long long distAB = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
    long long distBC = (x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2);
    long long distCA = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1);
    
    if (distAB + distBC == distCA || 
        distAB + distCA == distBC || 
        distBC + distCA == distAB) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

C 和为零

首先考虑极端情况：若将所有区间都取最小值，总和仍大于0，则必然无解（因为无法取到更小的负数）。同理，若将所有区间都取最大值，总和仍小于0，也无解。

对于其他情况，我们一定可以调整部分数的取值来达到和为0。这是因为当我们从全取最小值出发，如果总和小于0，可以通过将某些正数增大（或负数向0方向调整）来逐步逼近0。由于全取最大值时总和大于0，因此在调整过程中必然能恰好达到0。

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

struct Interval {
    int left, right;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<Interval> seg(n + 1);
    vector<int> result(n + 1);
    long long minSum = 0, maxSum = 0;
    
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        seg[i] = {l, r};
        minSum += l;
        maxSum += r;
        result[i] = l;
    }
    
    // 检查无解情况
    if (minSum > 0 || maxSum < 0) {
        cout << "No\n";
        return 0;
    }
    
    cout << "Yes\n";
    
    // 调整数值使其和为0
    for (int i = 1; i <= n; i++) {
        int l = seg[i].left, r = seg[i].right;
        if (minSum < 0 && r - l > 0) {
            int adjust = min(abs(minSum), r - l);
            result[i] += adjust;
            minSum += adjust;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        cout << result[i] << ' ';
    }
    return 0;
}

D 最短路径 3

典型的带节点权重的最短路径问题。每个节点除了边权外，还有点权。路径的总代价为：边权之和加上途径所有节点的点权。使用Dijkstra算法即可解决。

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

struct Edge {
    int to;
    int weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int nodeCount, edgeCount;
    cin >> nodeCount >> edgeCount;
    
    vector<int> nodeValue(nodeCount + 1);
    vector<vector<Edge>> graph(nodeCount + 1);
    
    for (int i = 1; i <= nodeCount; i++) {
        cin >> nodeValue[i];
    }
    
    for (int i = 0; i < edgeCount; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    
    // Dijkstra算法
    const long long INF = 1e18;
    vector<long long> dist(nodeCount + 1, INF);
    vector<char> visited(nodeCount + 1, false);
    
    using State = pair<long long, int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    
    dist[1] = nodeValue[1];
    pq.push({nodeValue[1], 1});
    
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (const auto& edge : graph[u]) {
            int v = edge.to;
            long long w = edge.weight;
            long long newDist = currentDist + w + nodeValue[v];
            
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }
    
    for (int i = 2; i <= nodeCount; i++) {
        cout << dist[i] << " ";
    }
    return 0;
}

E 等差子序列计数

解法一：三元组扩展

定义状态dp[i][j][k]表示以a[i]和a[j]作为等差数列的前两项、长度为k的方案数。当三个数满足等差性质时（a[i] - a[l] = a[j] - a[i]，其中l < i < j），可以进行状态转移：

dp[i][j][k] += dp[l][i][k-1]

为什么只需要判断三个数即可？因为若三个数构成等差，则它们蕴含的公差是确定的，较短的等差子序列必然包含在这三个数形成的等差中。

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

const int MAXN = 100;
const int MOD = 998244353;
int dp[MAXN + 1][MAXN + 1][MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dp[i][j][2] = 1;
            
            for (int len = 3; len <= n; len++) {
                for (int l = 1; l < i; l++) {
                    if (a[i] - a[l] == a[j] - a[i]) {
                        dp[i][j][len] = (dp[i][j][len] + dp[l][i][len - 1]) % MOD;
                    }
                }
            }
        }
    }
    
    for (int len = 1; len <= n; len++) {
        long long answer = 0;
        if (len == 1) {
            cout << n << ' ';
            continue;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                answer = (answer + dp[i][j][len]) % MOD;
            }
        }
        cout << answer << ' ';
    }
    return 0;
}

解法二：公差为状态

定义状态dp[len][end][d]表示以位置end结尾、公差为d、长度为len的等差子序列个数。使用哈希表存储不同公差对应的方案数。

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

const int MAXN = 105;
const int MOD = 998244353;
map<int, int> dp[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        dp[1][i][0] = 1;
        
        for (int j = 1; j < i; j++) {
            int diff = a[i] - a[j];
            dp[2][i][diff]++;
        }
        
        for (int len = 3; len <= n; len++) {
            for (int j = 1; j < i; j++) {
                int diff = a[i] - a[j];
                dp[len][i][diff] = (dp[len][i][diff] + dp[len - 1][j][diff]) % MOD;
            }
        }
    }
    
    for (int len = 1; len <= n; len++) {
        long long answer = 0;
        for (int i = 1; i <= n; i++) {
            for (auto& kv : dp[len][i]) {
                answer = (answer + kv.second) % MOD;
            }
        }
        cout << answer << ' ';
    }
    return 0;
}

F 树的完美匹配

考虑每条边对答案的贡献：删除某条边后，树被分成两个连通块，设其中一个块的节点数为v，则另一个块节点数为n-v。若选中的两个点分别位于两个连通块内，则它们之间的最短路径必然经过这条边，该边的贡献为min(v, n-v)。

要使总贡献最大，应选择使得两边节点数较为均衡的边，即树的重心（每个子树大小不超过n/2的节点）。当总结点数为偶数时，重心需要特殊处理。

具体实现：首先找到树的重心，然后按照DFS顺序将节点排列，依次配对i和i+n/2位置的节点。

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

const int MAXN = 1000005;

int n, root;
int subtreeSize[MAXN], maxSubtree[MAXN];
vector<int> tree[MAXN];

void findCentroid(int u, int parent) {
    subtreeSize[u] = 1;
    maxSubtree[u] = 0;
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        findCentroid(v, u);
        subtreeSize[u] += subtreeSize[v];
        maxSubtree[u] = max(maxSubtree[u], subtreeSize[v]);
    }
    maxSubtree[u] = max(maxSubtree[u], n - subtreeSize[u]);
    
    if (maxSubtree[u] < maxSubtree[root]) {
        root = u;
    }
}

void collectNodes(int u, int parent, vector<int>& nodes) {
    if (u != root) nodes.push_back(u);
    for (int v : tree[u]) {
        if (v == parent) continue;
        collectNodes(v, u, nodes);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    root = 1;
    maxSubtree[0] = INT_MAX;
    findCentroid(1, 0);
    
    vector<int> nodes;
    nodes.push_back(0);
    
    if (n % 2 == 0) {
        nodes.push_back(root);
    }
    
    collectNodes(root, 0, nodes);
    
    for (int i = 1; i <= n / 2; i++) {
        cout << nodes[i] << ' ' << nodes[i + n / 2] << '\n';
    }
    return 0;
}

G 子串查询

本题为AC自动机模板题，考察字符串模式匹配的基本应用。