首页 > 其他分享 >Codeforces Round 868 Div 2

Codeforces Round 868 Div 2

时间：2023-04-29 13:44:18浏览次数：56  
标签：868 int Codeforces cin ans Div du sg dp

A. A-characteristic (CF 1823 A)

题目大意

要求构造一个仅包含\(1\)和 \(-1\)的长度为 \(n\)的数组 \(a\)，使得存在 \(k\)个下标对 \((i, j), i < j\)满足 \(a_i \times a_j = 1\)。

解题思路

当有\(x\)个 \(1\)， \(y\)个 \(-1\)时，其满足条件的下标对数量为 \(\frac{x (x - 1)}{2} + \frac{y (y - 1)}{2}\)。

由于\(n\)只有 \(100\)，直接枚举 \(x\)即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        int one = 0;
        for(; one <= n; ++ one){
            int neg = n - one;
            if (neg * (neg - 1) + one * (one - 1) == 2 * k)
                break;
        }
        if (one > n)
            cout << "No" << '\n';
        else{
            cout << "Yes" << '\n';
            for(int i = 0; i < one; ++ i)
                cout << 1 << ' ';
            for(int i = 0; i < n - one; ++ i)
                cout << -1 << ' ';
            cout << '\n';
        }
    }

    return 0;
}

B. Sort with Step (CF 1823 B)

题目大意

给定一个排序，问能否仅通过交换相隔\(k\)的俩元素，使得有序。不能的话问能否事先通过一次任意交换操作后，再通过之前的操作交换得到有序。

解题思路

考虑每个元素的原始位置和最后所在的位置，它们对\(k\)的取模应该相同。否则就不能有序。

而如果恰好有两个元素其对\(k\)的取模不同，且交换之后是相同的，则可以。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for(auto &i : a){
            cin >> i;
            i --;
        }
        bool ok1 = true;
        map<pair<int, int>, int> cnt;
        for(int i = 0; i < n; ++ i){
            if (i % k != a[i] % k){
                ok1 = false;
                cnt[{min(i % k, a[i] % k), max(i % k, a[i] % k)}] ++;
            }
        }
        if (ok1)
            cout << 0 << '\n';
        else if (cnt.size() == 1 && cnt.begin()->second == 2)
            cout << 1 << '\n';
        else 
            cout << -1 << '\n';
    }

    return 0;
}

C. Strongly Composite (CF 1823 C)

题目大意

给定一个数组\(a\)，构造数组 \(b\)，要求最大化数组的元素数量，使得俩数组的所有元素的乘积相同，且数组 \(b\)的每个数都是强合数。

强合数的定义为，合数因子数量\(\geq\)质数因子数量。

解题思路

乘积相同，相当于将数组\(a\)里的质数重新组合；数量最大，相当于尽可能少用质数来组成一个新的数。

可以发现，两个相同的质数组成一个强合数，或者三个不同的质数可以组成一个强合数。

由此我们统计数组 \(a\)中的每个质数的数量，同个质数俩俩组合，不同质数三三组合，就能最大化答案了。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        map<int, int> cnt;
        auto fac = [&](int a){
            for(int i = 2; i * i <= a; ++ i){
                while (a % i == 0){
                    cnt[i] ++;
                    a /= i;
                }
            }
            if (a != 1)
                cnt[a] ++;
        };
        for(int i = 0; i < n; ++ i){
            int a;
            cin >> a;
            fac(a);
        }
        LL ans = 0;
        int left = 0;
        for(auto &[_, value] : cnt){
            ans += value / 2;
            left += (value & 1);
        }
        ans += left / 3;
        cout << ans << '\n';

    }

    return 0;
}

D. Unique Palindromes (CF 1823 D)

题目大意

要求构造一个仅包含小些字母的字符串\(s\)，长度为\(n\)，且满足 \(k\)个限制。

每个限制表述为\((x_i, c_i)\)， 字符串\(s\)的长度为 \(x_i\)的前缀满足有 \(c_i\)个本质不同的回文串）

解题思路

通过打表发现本质不同的回文串数量不会超过字符串长度。

注意到\(k\)最大只有 \(20\)，这启示我们每个限制可以用一个字符去满足。

思考朴素的构造方法，对于一个长度为 \(n\)的字符串，我们可以 \(aaaaaaaabcabcabc\)这样去构造，一开始连续的 \(a\)的数量就能控制这个字符串的本质不同的回文串的数量。这样的构造方法满足其数量在 \([3, n]\)之内，这刚好符合题意里 \(c_i \geq 3\)的限制。

因此我们可以先根据第一个限制构造出如上的字符串，对于之后的限制进行增量构造，增加的回文数量用 \(dddd\)， \(eeeee\)这样构造，剩下的长度用 \(abc\)这样不会增加回文串数量的形式去填充。

注意用于填充的字符串，在每次填充时应该继续前面的，而不是从头（从\(abc\) ）开始（如代码的fill_cur），不然可能会新增回文串。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<int> x(k), c(k);
        for(auto &i : x)
            cin >> i;
        for(auto &i : c)
            cin >> i;
        string ans;
        int fill_cur = 0;
        auto fill = [&](int x){
            while(x--){
                ans.push_back('a' + fill_cur);
                fill_cur = (fill_cur + 1) % 3;
            }
        };
        auto ok = [&](){
            int cur = 0;
            for(int i = 0; i < k; ++ i){
                int dis = x[i] - c[i];
                if (dis < 0)
                    return false;
                if (cur > dis)
                    return false;
                cur = dis;
            }

            ans += string(c[0] - 3, 'a');
            fill(x[0] - ans.size());
            for(int i = 1; i < k; ++ i){
                ans += string(c[i] - c[i - 1], 'c' + i);
                fill(x[i] - ans.size());
            }
            return true;
        };
        if (ok()){
            cout << "YES" << '\n';
            cout << ans << '\n';
        }else {
            cout << "NO" << '\n';
        }
    }

    return 0;
}

E. Removing Graph (CF 1823 E)

题目大意

两人博弈。

给定\(n\)个环，每个人可以从\([l, r]\) 中选一个数\(x\)，然后选择由\(x\) 个点组成的连通子图，将点及其边去掉。不能操作者输。

在绝顶聪明的情况下，问先后手谁必赢。

解题思路

每个环都是一个独立局面，因此我们求出每个环的\(sg\)值，异或起来，非零就先手赢，否则后手赢。

对于一个环来说，取了一次之后就变成一条链了。因此一个环的 \(sg\)值就是所有可能的链的长度对应的\(sg\)值的 \(mex\)。

对于一个链来说，取了一次之后就变成两条链，这两条链分别都是一个独立局面，因此一个链的 \(sg\)值，就是一些操作值的 \(mex\)， 而操作值就是取了之后（有取的长度和取的位置两个因素）的两个链的\(sg\)值的异或。

abc287g和abc297g就是要求一个链的\(sg\)值。

注意到题目保证了 \(l \neq r\)，对于一条链来说，如果它能取（即长度 \(\geq l\)），则必定能分成两条长度一样的链，之后先手就模仿后手的操作，就能必赢了。

也就是说，对于一个环来说，如果其长度\(len \geq l + r\)，那么先手取了一次后，变成的链因为后手必定可以再取（\(len - r \geq l\) )，所以对于后手来说必定是个必胜态，所以这样的环对于先手来说必定是个必败态，其 \(sg\)值为 \(0\)。

而长度小于 \(l\)，不能取，那肯定是必败态，其 \(sg\)值为 \(0\)。

考虑环长度 在 \([l, l+r)\)之间的\(sg\)值，其对应的链长度有 \(len - l, len - l - 1, len - l - 2, ..., len - r\)。其\(sg\)值就是这些可能的链长度的 \(sg\)值取 \(mex\)。

考虑链长度，小于 \(l\)，是必败态，其 \(sg\)值为 \(0\)。 而\(sg(l) = sg(l + 1) = sg(l + 2) ... = sg(l + l - 1) = 1\)，

\(sg(2l) = mex(sg(l), sg(l - 1), sg(l - 2), ..., sg(1), sg(0)) = mex(1, 0, 0, 0, ..., 0) = 2 = sg(2l + 1) = sg(2l + 2)\)

\(sg(3l) = mex(sg(2l), sg(2l - 1), ..., sg(l), sg(l - 1), ..., sg(0)) = mex(2, 1, ..., 1, 0, ..., 0) = 3 = sg(3l + 1) = sg(3l + 2)\)

上述的\(mex\)里的每一项都是取最边边的结果（即取了之后还有一个链），至于有两条链的结果，是长度更小的两个链的\(sg\)的异或值，其不会超过上面的最大值。

由此（或打表）可以发现长度为\(sg(len) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)

进而环的 \(sg_c(len) = mex(sg(len - l), sg(len - l - 1), ..., sg(len - r)) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)

环的\(sg\)值求出来了，异或一下就知道谁赢了。

至于环大小，用并查集或\(BFS\)一下就知道了。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

class dsu {
    public:
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        sz.resize(n);
        iota(p.begin(), p.end(), 0);
        fill(sz.begin(), sz.end(), 1);
    }

    inline int get(int x) {
        return (x == p[x] ? x : (p[x] = get(p[x])));
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            p[x] = y;
            sz[y] += sz[x];
            return true;
        }
        return false;
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, l, r;
    cin >> n >> l >> r;
    dsu d(n);
    for(int i = 0; i < n; ++ i){
        int u, v;
        cin >> u >> v;
        -- u;
        -- v;
        d.unite(u, v);
    }
    int ans = 0;
    for(int i = 0; i < n; ++ i){
        if (d.get(i) == i){
            if (d.sz[i] >= l && d.sz[i] < l + r)
                ans ^= d.sz[i] / l;
        }
    }
    if (ans)
        cout << "Alice" << '\n';
    else 
        cout << "Bob" << '\n';

    

    return 0;
}

F. Random Walk (CF 1823 F)

题目大意

树上随机游走，从点\(s\)到点 \(t\)，问每个点访问次数的期望值。

解题思路

每次的期望题感觉都比较神仙。

注意到这是棵树，点\(s\)到点\(t\)的路径是唯一的，设路径为\(s, u_0, u_1, ..., u_k, t\)。

一开始设状态\(dp[s][v][t]\)表示从 \(s\)点到 \(t\)点，期望访问到 \(v\)号点的次数，然后枚举到相邻点的状态，即\(dp[s][v][t] = \sum_{(s, u) \in E}dp[u][v][t]\)，但感觉怎么都算不出来。

然后想着从点 \(s\)出发，它可以往很多个相邻点走，只有一个点\(u_0\)是更接近点 \(t\)的， 且最终到点\(t\)时立刻停下来，这意味着点\(t\)之后的点的访问次数的期望值一定是 \(0\)。

考虑到一旦走到点\(u_0\)时，发现问题貌似变成了一个子问题了，可以认为是从点\(u_0\)出发，到点 \(t\)的情况。换句话说，我们可以将 点\(s\)到点 \(t\)的步骤分成若干步，分别是点 \(s\)到点 \(u_0\)，点 \(u_0\)到点 \(u_1\)... 点\(u_t\)到点 \(t\)，由于期望的线性可加性，每个点的期望访问次数，可以由这些的每个步骤的影响依次累计。

设 \(dp[s][w]\)表示从 \(s\) 点往更接近点\(t\)的方向走（即走到 \(u_0\)点），对 \(w\)点的期望访问次数。

设点 \(s\)的度数为 \(du_s\)，其余字母定义看图，根据期望定义，可以得到：

tree

\[dp[s][w] = \frac{1}{du_s} \times 0 + \frac{1}{du_s} (dp[x][w] + dp[s][w]) + \frac{du_s - 2}{du_s}(dp[y][w] + dp[s][w]) \]

这里有三个部分：

  • 有\(\frac{1}{du_s}\)的概率选择走到 \(u_0\)，然后就停下来了，此时对 \(v\)的访问贡献是\(0\)。
  • 有\(\frac{1}{du_s}\)的概率往 \(w\)所在的子树走（即点 \(x\)），此时对\(w\)的访问贡献是由\(x \to s\)和\(s \to u_0\)组成，即 \(dp[x][w] + dp[s][w]\)。
  • 有\(\frac{du_s - 2}{du_s}\)的概率往其他子树走（即点 \(y\)表示的其他所有点），此时对\(w\)的访问贡献是由\(y \to s\)和\(s \to u_0\)组成，即 \(dp[y][w] + dp[s][w]\)。但由于从点\(y\)到点\(w\)必须经过点 \(s\)，而一旦到点 \(s\)就会停下来（ \(dp[y][w]\)即表示从点 \(y\)到更接近 点\(t\)的方向走（即往点 \(s\)），对点 \(w\)的访问贡献），因此 \(dp[y][w] = 0\)。

这样上述式子移一下项，就得到

\[dp[s][w] = dp[x][w] \]

即点\(s\)往点 \(u_0\)走时的对点\(w\)访问次数的贡献是等价于点 \(x\)往点 \(s\)走时，对点 \(w\)的贡献。由此就可以得到

\[dp[s][w] = dp[x][w] = dp[x_1][w] = ... = dp[x_k][w] = dp[w][w] \]

剩下的就是求 \(dp[w][w]\)。根据期望定义，可以得到

\[dp[s][s] = \frac{1}{du_s} \times 1 + \frac{du_s - 1}{du_s}(dp[o][s] + dp[s][s]) \]

这里有两部分：

  • 有\(\frac{1}{du_s}\)的概率选择走到 \(u_0\)，此时就停下来了，因此对\(s\)的访问贡献是\(1\)（一开始在\(s\)时的贡献）。
  • 有\(\frac{du_s - 1}{du_s}\)的概率选择走到除点\(u_0\)之外的其他点(设点\(o\)，即 \(x\)或 \(y\))，因此对\(s\)的访问贡献是\(o \to s\)和 \(s \to s\)，即\(dp[o][s] + dp[s][s]\)，而因为点\(o\)到点 \(s\)就会停下来（点 \(s\)是更接近点 \(t\)的点），因此 \(dp[o][s] = 1\)（一开始在\(s\)时的贡献包含在 \(dp[s][s]\)里）。

这样上述式子移一下项，就得到

\[dp[s][s] = du_s \]

综合上述的两个式子\(dp[s][w] = dp[w][w] = du_w\)，可以得出，每当进行一次 \(s \to u_0, u_0 \to u_1,\cdots, u_k \to t\) 时，其他点\(w\)的期望访问次数都会增加 \(du_w\)，其中点\(w\)是点 \(s\)除了 \(u_0\)方向的其他方向的点（见上图的虚线包括起来，就是对应颜色的箭头的影响）。

也就是说一个点\(a\)的期望访问次数就是\(du_a \times cnt_a\)，其中 \(cnt_a\)等于该点与路径\(s \to t\)的交点（以上图为例，就为 \(u_{k-1}\)）到 \(t\)的点数（见上图的点\(a\)）。

剩下的就是如何求 \(cnt_w\)，我们可以以点 \(s\)为根，然后我们从点 \(t\)开始，一路沿着 父亲节点上去，就回到点\(s\)，其中每往父亲跳一次时， \(cnt_w\)就会加一，比如从\(t \to u_k\)时， \(cnt = 0 + 1 = 1\)，此时再遍历一下除了\(t\)和 \(u_{k - 1}\)方向的所有点 \(w\)，它们的答案就是 \(du_w \times cnt\) 。

最终的时间复杂度是\(O(n)\)。

虽然答案不会超过\(n^2\)，但记得对\(998244353\)取模。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mod = 998244353;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, s, t;
    cin >> n >> s >> t;
    -- s, -- t;
    vector<vector<int>> edge(n);
    vector<int> du(n);
    for(int i = 1; i < n; ++ i){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        edge[u].push_back(v);
        edge[v].push_back(u);
        ++ du[u];
        ++ du[v];
    }
    vector<int> fa(n);
    function<void(int, int)> dfs = [&](int u, int f){
        fa[u] = f;
        for(auto &v : edge[u]){
            if (v == f)
                continue;
            dfs(v, u);
        }
    };
    dfs(s, s);
    vector<int> ans(n);
    int cnt = 1;
    ans[t] = 1;
    function<void(int, int, int)> dfs2 = [&](int u, int f, int cnt){
        ans[u] = 1ll * du[u] * cnt % mod;
        for(auto &v : edge[u]){
            if (v == f)
                continue;
            dfs2(v, u, cnt);
        }
    };
    do{
        int cur = fa[t];
        ans[cur] = 1ll * cnt * du[cur] % mod;
        for(auto &u : edge[cur]){
            if (u != fa[cur] && u != t)
                dfs2(u, cur, cnt);
        }
        t = cur;
        ++ cnt;
    }while(s != t);
    for(auto &i : ans)
        cout << i << ' ';
    cout << '\n';

    return 0;
}

标签：868,int,Codeforces,cin,ans,Div,du,sg,dp
From： https://www.cnblogs.com/Lanly/p/17363927.html

相关文章

  • Codeforces Round 868 (Div. 2)
    Preface恭迎废物hl666终于回到了他忠诚的蓝名之位本来这场25min切完前三题而且没挂的时候感觉状态不错的，然后D被自己的一个假做法坑了1h最后ztc想出了大概的构造方法后已经来不及写了，一些细节没考虑好直接爆炸本来当时就有弃D开E的想法的，但可以E的题意在公告出来之前就已经读......
  • ie6 ie 8 ff 总在页脚右下角的绝对定位top div
    top.jsfunctionsetH(){varmain_div_w=1010;vardiv_w=$e('top_t').offsetWidth;vardiv_h=$e('top_t').offsetHeight;//下面二行必须定义docw3c标准varwin_w=document.documentElement.clientWidth;varwi......
  • Codeforces Round 868 (Div. 2) A-E题解
    比赛地址这把真不在状态，麻了，看来还得再练A.A-characteristic题意：给出n和k，要求构造只含1和-1数组a，存在k对(i,j)（i≠j），有a[i]*a[j]=1Solution令构造的数组有x个1和y个-1，那么其对于答案的贡献有\[x*(x-1)/2+y*(y-1)/2\]又因为有x+y=n，所以可以转化成关于x的一元二次方程化简后......
  • cf-div.2-868-D
    题目链接：https://codeforces.com/contest/1823/problem/D比赛的时候关键性质已经想到，但没想到怎么正确构造。性质：每次新加一个字母，回文子串的数量最多增加1(因为题目需要不相同的回文子串)。证明：可以用反证法，易证。构造方法：由于k的值很小(只有20)，所以对于不再增加(回文子串)的......
  • Codeforces Round 867 (Div. 3)(A~D)
    目录A.TubeTubeFeed题意思路代码B.KarinaandArray题意思路代码C.BunLover题意思路代码D.Super-Permutation题意思路代码A.TubeTubeFeed题意给定时间\(t\),每个视频有一个价值\(b_i\)，观看一个视频需要\(a_i\)秒，跳过一个视频需要花费\(1s\),求能观看完的价值最大......
  • Codeforces Round 867 (Div. 3)
    CodeforcesRound867(Div.3)A-TubeTubeFeed#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedefpair<string,int>PSI;constintN=50+5,INF=0x3f3f3f3f,Mod=1e6;constdoubleeps=1e-6;typedeflonglongll;......
  • js javascript 鼠标触碰select下拉列表渐变出div层,鼠标离开渐变缩回
    <!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metahttp-equiv="Content-......
  • Codeforces Round 866 (Div. 1) C. The Fox and the Complete Tree Traversal （构造）
    传送门题目大意：  给定一个有n个点的树，我们可以任意选择一个点作为起点，这个点可以跳到跟自己距离为1或者距离为2的点，已经到达的点不能再到达（最终必须回到起点），询问是否存在一种方案可以从一个点出发经过所有的点最终再回到这个点来。  输入一个整数n。紧接着输入n-1条边。大......
  • Codeforces Round 847 (Div. 3) G.Tokens on Graph （构造）
    传送门题目大意  给定一个无向图，我们定义图中有四种点，一种是黑色的点表示终点，并且黑色的点始终是1号点，一种是红色的点，一种是灰色的点，最后一种就是没有颜色的点。  游戏规则：我们必须移动任意一个灰色的点到相邻的点上，如果灰色的点移动到了红色的点上，那么我们可以移动其他灰......
  • 前端隐藏和显示div的方式js和beetle：
    方式一：设置元素style对象中的display属性1、vart=document.getElementById('demo');//选取id为test的div元素2、t.style.display='none';//隐藏选择的元素3、t.style.display='block';//以块级样式显示方式二：设置元素style对象中的visibility属性1、vart=documen......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99