3月1日-3月9日¶

以后只会记录每周的情况了，或者一段时间的。

因为很难保证每天能固定做多少个特定难度的题目，可能会有各种各样的事情，或者有比赛之类的。而且就是也正好可以记录一下这周都打了哪些比赛之类的。

以后新VP或者补最近比赛的题，就会放在比赛的界面或XCPC。然后日常找的写的题可能会放这。

3月3日¶

CF2065G *1700¶

就上个星期才做过一道用了质数筛和筛最小质因子的题目，于是就想了下这题的性质很快就能对。

虽然也是WA了一次，看了数据才知道哪有问题。应该先排序的。可以少考虑很多。

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

constexpr int N = 2e5;
bitset<N + 1> is;
std::vector<int> primes;
// 记一下最小质因子
vector<int> minp(N + 1);

void solve()
{
    int n;
    cin >> n;
    long long ans = 0;
    int sum = 0;
    vector<int> cnt(n + 1);
    // auto sqrtI = [&](int x) {
    //     int y = (int)sqrt(x);
    //     return y * y == x ? y : 0;
    // };
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    for (int i = 1; i <= n; i++) {
        int x = a[i - 1];
        // cin >> x;
        cnt[x]++;
        if (!is[x]) {
            // 如果是一个质数，那么只能和其他的质数，除了它本身
            sum++;
            ans += sum - cnt[x];
            // 还得看一下 x*x
            if (1LL * x * x <= n)
                ans += cnt[x * x];
        } else {
            // 否则判一下最小质因子
            if (!is[x / minp[x]]) {
                // cerr << x << " " << minp[x] << '\n';
                // 如果只有两个质因子 那么答案加上这两个的数量
                // 当然它自己和自己也是可以的
                ans += cnt[minp[x]] + cnt[x];
                if (1LL * minp[x] * minp[x] != x)
                    ans += cnt[x / minp[x]];
            }
            // 2 3 ,6 ,2 7
        }
    }
    cout << ans << '\n';
}
/*
6
5 4 6 6 2 3
这为什么会是8呢？
5 2,5 3,2 3,2 4
6 2,6 3. 偶没有判 质数可能和倍数
*/
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 2; i <= N; i++) {
        if (!is[i]) {
            minp[i] = i;
            primes.push_back(i);
            // cerr << i << '\n';
            if (1LL * i * i > N)
                continue;
            for (int j = i * i; j <= N; j += i) {
                is[j] = true, minp[j] = i;
            }
        }
    }
    // cout << primes.size() << '\n';
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

CF2065F *1700¶

这个更是简单了。满足答案的情况实际上只需要判断长度为2和3的路径是否满足。就很简单了。但是DFS是不是可能会超时来着。

只要连边的时候就处理就行了。好吧DFS好像也行。

看了下，其实也可以输入时先判下长度为2的，然后找的时候只需要遍历每个点连的点，看这一次标记是否有重复的。也很好。差不多，或者每次开个set。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    string s(n, '0');
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<set<int>> g(n + 1);
    // vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        if (a[u] == a[v]) {
            s[a[u] - 1] = '1';
        }
        if (g[u].contains(a[v])) {
            s[a[v] - 1] = '1';
        } else
            g[u].insert(a[v]);
        if (g[v].contains(a[u])) {
            s[a[u] - 1] = '1';
        } else
            g[v].insert(a[u]);
        // g[u].insert(a[v]), g[v].insert(a[u]);
    }
    // auto dfs = [&](auto&& self, int u, int pre, int val, int cnt, int len) -> void {
    //     if ((s[val - 1] == '1') || (pre && cnt > 0)) {
    //         // cerr << pre << " " << u << " " << val << '\n';
    //         s[val - 1] = '1';
    //         return;
    //     }
    //     if (len == 3)
    //         return;
    //     for (auto v : adj[u]) {
    //         if (v == pre)
    //             continue;
    //         if (a[v] == val)
    //             self(self, v, u, val, cnt + 1, len + 1);
    //         else
    //             self(self, v, u, val, cnt - 1, len + 1);
    //     }
    // };
    // for (int i = 1; i <= n; i++) {
    //     dfs(dfs, i, 0, a[i], 1, 0);
    // }
    cout << s << '\n';
}

set::count 和 contains 效率差别不是很大，都是 \(\log n\) ，但是 multiset::count 的复杂度时 n 。

CF2065E *1600¶

有点简单的构造。

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    auto work = [](int n, int m, int k) -> string {
        // 让n 大于 m
        // 直接放k个0，
        // 然后如果n-k>m 那么不行

        // 好像也行
        // 不对，应该不行吧，每个都需要一个1来阻挡。

        // 还有其他方式吗？
        string s(k, '0');
        if (k > n || n - k > m) {
            return {};
        }
        n -= k;
        for (int i = k; n && m; i += 2) {
            s += "10";
            n--, m--;
        }
        // m剩下的肯定小于k
        s = string(m, '1') + s;
        return s;
    };
    string ans = (n > m ? work(n, m, k) : work(m, n, k));
    if (n < m) {
        for (int i = 0; i < ans.size(); i++) {
            if (ans[i] == '0')
                ans[i] = '1';
            else
                ans[i] = '0';
        }
    }
    if (ans.empty())
        cout << "-1\n";
    else
        cout << ans << '\n';
}

3月5日¶

CF2006B *1800¶

统计当前的已知边的权值之和 sum ，若是一条路径不是所有的边都已经确定，那么它的权值可以加上 w-sum 。而其实每条边都一定会被经过两次。

这个确实是一个很巧妙的结论了。我们只需要看有多少条路径上的边已经被全部赋值了。

void solve()
{
    int n;
    long long w;
    cin >> n >> w;
    vector<vector<int>> adj(n + 1, vector<int>());
    vector<vector<int>> f(n + 1, vector<int>());
    vector<int> p(n + 1), cnt(n + 1);
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        adj[p[i]].push_back(i);
    }
    auto dfs = [&](auto&& self, int u) -> int {
        int mx = u;
        // cerr<<u<<'\n';
        for (auto v : adj[u]) {
            cnt[mx]++;
            f[v].push_back(mx);
            mx = max(mx, self(self, v));
            cnt[mx]++;
            f[v].push_back(mx);
        }
        return mx;
    };
    dfs(dfs, 1);
    // for(int i=1;i<=n;i++)
    //     cerr<<cnt[i]<<" \n"[i==n];
    // return ;
    long long ans = 0, sum = 0;
    int tot = n;
    for (int z = 1; z < n; z++) {
        int x;
        long long y;
        cin >> x >> y;
        for (auto v : f[x]) {
            cnt[v]--;
            if (!cnt[v]) {
                --tot;
            }
        }
        w -= y;
        ans += 2 * y;
        cout << ans + 1LL * tot * w << ' ';
    }
    cout << '\n';
}

说实话，可能还是有些地方不太理解的。

CF1990D *1800¶

说实话，这个纯水题了。很显然如果当前这一行的1的个数是大于2的话，那咱们肯定得消除一行吧。如果是两个2且连着，那我们肯定不会介意去使用 1 操作。

那么我们从上往下遍历，我们第一次使用1操作会是在什么地方呢？肯定是在第一列的位置，那么此时如果下一行的数量是小于等于2，咱们无需进行操作了，如果是在34之间，我们肯定还可以进行一次1操作，且显然肯定是只能在第3列使用。

就记一下上一行的使用情况就好了，而且只会在第一列和第三列使用。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> lst(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!a[i])
            continue;
        if (lst[i - 1] == 1) {
            if (a[i] <= 2)
                continue;
            if (a[i] > 4) {
                ans++;
                continue;
            }
            lst[i] = 3, ans++;
        } else if (lst[i - 1] == 3) {
            if (a[i] > 4) {
                ans++;
                continue;
            }
            ans++;
            lst[i] = 1;
            continue;
        } else {
            if (a[i] <= 2) {
                lst[i] = 1;
                ans++;
            } else
                ans++;
        }
    }
    cout << ans << '\n';
}

CF1987D *1800¶

我们先对A进行去重，记一下每个数字出现的次数。

这时候我们令 \(n\) 为数组的长度。

我们需要从 \(n\) 个数字里选出 \(k\) 个数字进行删除，且希望删除的数字最多。

我们删除的第一个数字的数量一定要小于它前面的不同元素的数量，即满足能在Alice到这里之前删除完这个数字。后面的同理。

可以用 dp 来实现。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> A(1), c(1);
    sort(a.begin() + 1, a.end());
    for (int i = 1, cnt = 0; i <= n; i++) {
        cnt++;
        if ((i == n) || (a[i + 1] != a[i])) {
            A.push_back(a[i]);
            c.push_back(cnt);
            cnt = 0;
        }
    }
    n = A.size() - 1;
    // vector<vector<int>> dp(n + 1, vector<int>(n + 1, 6666));
    vector<int> dp(n + 1, 6666);
    dp[0] = 0;
    cerr << n << '\n';
    for (int i = 1; i <= n; i++) {
        vector ndp = dp;
        for (int j = 1; j <= i; j++) {
            // if (dp[j - 1] == 6666)
            //     break;
            if (dp[j - 1] + c[i] <= i - j)
                ndp[j] = min(dp[j - 1] + c[i], dp[j]);
        }
        dp = ndp;
    }
    for (int i = n; i >= 0; i--) {
        if (dp[i] != 6666) {
            cout << n - i << '\n';
            return;
        }
    }
}

\(dp_{i,j}\) 表示从前 \(i\) 个数字里选出 \(j\) 个进行删除花费的最小回合数。

details¶

3月1日¶

CF2071C
24四川省赛BFG
ABC394ABCD

补了昨晚没写出来的 CF2071C 。

中午VP了2024年四川省赛，大概110名铜，54银，我们80。

只能说算正常吧，得多补题啊，能自己写出来的，大概率帮助不大，只有觉得坐牢的题目才会有些价值。。。

这场 B， F ， G ，补题都可以看下。

晚上打了 ABC394 ，只写了4题，E题没写出来，没多少时间了，D题写得太慢了，E一开始又想错了。

应该是dijkstra板子题。

3月2日¶

3月3日¶

CF2065G
CF2065F
CF2065E

3月5日¶

CF2006B
CF1990D
CF1987D

3月7日¶

唉唉，昨天又是没咋写题，今天再好好写下，今天杭电春季联赛第一场。