ABC369

A

signed main() {
    IOS;
    int a, b;
    cin >> a >> b;
    if (a == b) {
        cout << 1 << endl;
    } else {
        if((a + b) % 2) {
            cout << 2 << endl;
        } else {
            cout << 3 << endl;
        }
    }
    return 0;
}

B

signed main() {
    IOS;
    int q;
    cin >> q;
    int L = -1, R = -1;
    ll ans = 0;
    while (q--) {
        int x;
        char s;
        cin >> x >> s;
        if (s == 'R') {
            if (R == -1) {
                R = x;
            } else {
                ans += abs(x - R);
                R = x;
            }
        }
        else {
            if (L == -1) {
                L = x;
            } else {
                ans += abs(x - L);
                L = x;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

C

signed main() {
    IOS;
    int n;
    cin >> n;
    int m = 0;
    int L = 0, R = 0;
    int ans = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        L = i;
        if (L == R) {
            if (L == n - 1) {
                ans += 1;
                break;
            } else {
                m = a[R + 1] - a[L];
            }
        }
        while (R < n - 1 && a[R + 1] - a[R] == m) {
            R++;
        }
        //cout << L << ' ' << R << endl;
        ans += (R - L + 1);
    }
    cout << ans << endl;
    return 0;
}

D

#define MAX 200005
int dp[MAX][2];
signed main() {
    IOS;
    int n;
    cin >> n;
    dp[0][1] = -1e15;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + 2 * x);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + x);
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

E

用到了全排列和状态压缩来枚举所有可能，数据范围直接多源最短路就行

#define MAX 405
int f[MAX][MAX];
int n, m;
int E[200005][2];
vector<PII> G[MAX];
int W[200005];
signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++)
        f[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        E[i][0] = a, E[i][1] = b, W[i] = c;
        f[a][b] = f[b][a] = min(f[a][b], c);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    int q;
    cin >> q;
    while (q--) {
        int len;
        cin >> len;
        vector<int> b(len + 1);
        ll more = 0;
        for (int i = 1; i <= len; i++)
            cin >> b[i], more += W[b[i]];
        ll res = 1e18;
        do
        {
            for (int i = 0; i < 1 << len; i++)
            {
                ll cost = 0;
                cost += f[1][E[b[1]][i & 1]] + f[E[b[len]][((i >> (len - 1)) & 1) ^ 1]][n];
                for (int j = 1; j < len; j++)
                    cost += f[E[b[j]][((i >> j - 1) & 1) ^ 1]][E[b[j + 1]][(i >> j) & 1]];
                res = min(res, cost);
            }
        } while (next_permutation(b.begin() + 1, b.end()));
        cout << res + more << '\n';
    }
    return 0;
}

F

二分优化最长上升子序列，然后找点

#define MAX 200005
PII coin[MAX];
int h, w, n;
signed main()
{
    IOS;
    cin >> h >> w >> n;
    for(int i = 0; i < n; i++) {
        cin >> coin[i].first >> coin[i].second;
    }
    sort(coin, coin + n);
    vector<int> f(n, 1e9), id(n, -1), pre(n, -1);
    for (int i = 0; i < n; i++) {
        int x = coin[i].second;
        int it = upper_bound(f.begin(), f.end(), x) - f.begin();
        f[it] = x;
        id[it] = i;
        pre[i] = it ? id[it - 1] : -1;
    }
    int m = n - 1;
    while(id[m] == -1) {
        m--;
    }
    int now = id[m];
    vector<PII> path(1, {h, w});
    while (now != -1) {
        path.push_back(coin[now]);
        now = pre[now];
    }
    path.push_back({1, 1});
    reverse(path.begin(), path.end());
    string s;
    for (int i = 1; i < path.size(); i++)
    {
        int d = path[i].first - path[i - 1].first;
        int r = path[i].second - path[i - 1].second;
        while (d--)
            s.push_back('D');
        while (r--)
            s.push_back('R');
    }
    cout << m + 1 << endl;
    cout << s << endl;
    return 0;
}

G

长链刨分板子题

using namespace std;
#define MAX 200005
int n, d[MAX], fa[MAX], son[MAX];
vector<PII> G[MAX];
void dfs(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].first, w = G[u][i].second;
        if (v != fa[u]) {
            fa[v] = u;
            dfs(v);
            if (d[u] < d[v] + w) {
                d[u] = d[v] + w;
                son[u] = v;
            }
        }
    }
}
vector<int> ans;
int top[MAX];
void dfs2(int u, int t) {
    top[u] = t;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].first, w = G[u][i].second;
        if (v != fa[u]) {
            if (v == son[u]) {
                dfs2(v, t);
            } else {
                dfs2(v, v);
            }
        }
    }
    if (top[u] == 0) {
        top[u] = u;
    }
}
void dfs3(int u) {
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i].first, w = G[u][i].second;
        if (v != fa[u])
        {
            if(v == top[v]) {
                ans.push_back(d[v] + w);
            }
            dfs3(v);
        }
    }
}
signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dfs(1);
    dfs2(1, 1);
    dfs3(1);
    ans.push_back(d[1]);
    while (ans.size() < n - 1)
        ans.push_back(0);
    sort(ans.begin(), ans.end(), greater<int>());
    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        res += ans[i] * 2;
        cout << res << '\n';
    }
    return 0;
}

ending……………………………………….