LinhoNotes

外观

Codeforces Round 991 赛后复盘 ​

第一次 “准” AK 祭

E. Three Strings ​

游记 & 思路 ​

当时一眼的动态规划，因为给的数据范围太刚好了，很容易想到可以按照 a 和 b 的字符使用情况来划分子问题，由于已经用掉的部分和已经被匹配的部分不能回滚，显然地满足无后效性。

当时只顾着写动态规划了，忘记了答案要求的是最小的不匹配数，我输出最大的匹配数，还调了几分钟，蠢死我得了。

AC 代码 ​

c++
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        string a, b, c;
        cin >> a >> b >> c;
        vector<vector<ll>> dp(a.size() + 1, vector<ll>(b.size() + 1, 0));
        for (ll i = 0; i <= a.size(); i++) {
            for (ll j = 0; j <= b.size(); j++) {
                if (j)
                    dp[i][j] = dp[i][j - 1] + (c[i + j - 1] == b[j - 1]);
                if (i)
                    dp[i][j] =
                        max(dp[i][j],
                            dp[i - 1][j] + (c[i + j - 1] == a[i - 1]));
                //				cout<<dp[i][j]<<' ';
            }
            //			cout<<endl;
        }

        //		OOO
        cout << c.size() - dp[a.size()][b.size()] << endl;
    }

    cout.flush();

    return 0;
}

F. Maximum modulo equality ​

游记 & 思路 ​

区间查询 + 数论类最值问题，很容易会想到求取区间 GCD。

那能想到求取区间 GCD，再结合题目所给的 Mod m 意义下相等的条件，就能得出题目要我们维护的性质：差分数组的区间 GCD

正确性显然。

就这样？就这样。

AC 代码 ​

c++
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        ll n, q;
        cin >> n >> q;
        vector<ll> v(n + 1), diff(n + 1);
        vector<vector<ll>> Gcd(n + 1, vector<ll>(22));
        for (ll i = 1; i <= n; i++)
            cin >> v[i];
        for (ll i = 1; i < n; i++)
            Gcd[i][0] = diff[i] = max(v[i + 1] - v[i], v[i] - v[i + 1]);
        for (ll i = 1; i <= 20; i++)
            for (ll j = 1; j < n; j++)
                if (j + (1 << (i - 1)) < n)
                    Gcd[j][i] = __gcd(Gcd[j][i - 1],
                                      Gcd[j + (1 << (i - 1))][i - 1]);
                else
                    Gcd[j][i] = Gcd[j][i - 1];
        ll l, r;
        //		OOO
        for (ll i = 1; i <= q; i++) {
            cin >> l >> r;
            if (l == r) {
                cout << 0 << ' ';
                continue;
            }
            r -= 1;
            ll lg = (l == r) ? 0 : __lg(r - l);
            cout << __gcd(Gcd[l][lg], Gcd[r - (1 << lg) + 1][lg]) << ' ';
        }
        cout << endl;
    }

    cout.flush();

    return 0;
}

G. Tree Destruction ​

游记 & 思路 ​

傻逼东西，DFS 都能写锅，差十分钟没能赛时 AK，急疯了

一道很简单的树上 DP，我们很容易可以分析得知：

  • 对于一个端点，分出的连通组件数就是他的儿子数 + 1（根节点没有父节点所以不加）
  • 而对于一条路径（或一个单断点），他在两端拓展路径得到的连通组件数就是当前连通组件数 - 1 再加上新加入的断点的贡献
  • 根据上一条，即有以纳入最优解的部分不影响后续拓展优化，即无后效性和子问题最优结构
  • 又有对于任意的简单路径均可以由两个端点向其 LCA 合并得到，所以用 DFS 的方式向上回溯求解是可行的

至于 DP 式子，我们只要考虑当前节点不向下延伸（单断点），向下延伸一条边（他是根，并且还可以向上拓展），和向下延伸两条边（他是根，并且不能用于向上拓展）这三种情况，具体转化见代码

AC 代码 ​

c++
ll tt, tot, n;

struct Node {
    ll fir, key, son, kkk;
    bool vis;
    Node() {
        fir = 0;
        key = 0; // 可延伸的最值
        son = 0;
        vis = 0;
        kkk = 0; // 不可延伸的最值
    }
};
struct Edge {
    ll u, v, next;
    Edge() {
        u = v = 0;
        next = 0;
    }
};

Node node[200010];
Edge edge[400010];

void add_edge(ll u, ll v) {
    edge[++tot].u = u;
    edge[tot].v = v;
    edge[tot].next = node[u].fir;
    node[u].fir = tot;
}

void init() {
    tot = 0;
    for (ll i = 1; i <= n; i++)
        node[i] = Node{};
    for (ll i = 1; i <= 2 * n; i++)
        edge[i] = Edge{};
}

void DFS(ll x) {
    Node &cur = node[x];
    cur.vis = 1;

    for (Edge e = edge[cur.fir]; e.u; e = edge[e.next]) {
        if (node[e.v].vis)
            continue;
        cur.son++;
        DFS(e.v);
    }
}

void solve(ll x) {
    Node &cur = node[x];
    cur.vis = 1;
    cur.key = cur.son;
    vector<ll> tmp;
    for (Edge e = edge[node[x].fir]; e.u; e = edge[e.next]) {
        if (node[e.v].vis)
            continue;
        solve(e.v);
        tmp.emplace_back(node[e.v].key);
        cur.key = max(cur.key, node[e.v].key + cur.son - 1);
    }

    sort(tmp.begin(), tmp.end(), greater<ll>());

    if (tmp.size() >= 2)
        cur.kkk = cur.son - (x == 1 ? 2 : 1) + tmp[0] + tmp[1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        cin >> n;
        init();
        ll u, v;
        for (ll i = 1; i < n; i++) {
            cin >> u >> v;
            add_edge(u, v);
            add_edge(v, u);
        }
        DFS(1);
        //		for(ll i=1;i<=n;i++) cout<<node[i].son<<' ';

        for (ll i = 1; i <= n; i++)
            node[i].vis = 0;
        solve(1);
        ll ans = 0;
        //		cout<<"!!!SON";
        //		for(ll i=1;i<=n;i++) cout<<node[i].key<<' ';
        //		cout<<endl;

        for (ll i = 1; i <= n; i++) {
            ans = max(ans, node[i].key + (i == 1 ? 0 : 1));
            ans = max(ans, node[i].kkk);
        }
        //		OOO
        cout << ans << endl;
    }

    cout.flush();

    return 0;
}