首页 > 其他分享 >Codeforces Round 934 (Div. 2)

Codeforces Round 934 (Div. 2)

时间：2024-03-17 14:12:47浏览次数：24  
标签：int ll Codeforces len vector long using Div 934

Codeforces Round 934 (Div. 2)

A - Destroying Bridges

解题思路:

完全图每个点的连边数为\(n - 1\)。

  • \(k < n - 1\)：都可到达。
  • \(k \geq n - 1\)：将点\(1\)的边删完，只能呆在点\(1\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    if (k >= n - 1)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << n << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B - Equal XOR

解题思路:

对于每个数字只有三种情况：

  • 只出现在\((1, n)\)
  • 只出现在\((n + 1, 2 n)\)
  • 一个出现在\((1, n)\)，另一个出现在\(n + 1, 2n\)

前两种情况数目肯定是相同的。

我们先用前两种成对分别填入\(l,r\)中，不够的再用第三种补，整个过程都是同步的。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(2 * n + 2);
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
    }
    vector<int> l, r;
    vector<int> vis(2 * n + 10);
    // 2, 3, 4
    for (int i = 1; i <= n; i++)
    {
        vis[a[i]] += 1;
    }
    for (int i = n + 1; i <= 2 * n; i++)
    {
        vis[a[i]] += 2;
    }
    vector<int> ls, rs, t;
    for (int i = 1; i <= n; i++)
    {
        if (vis[a[i]] == 3)
        {
            t.push_back(a[i]);
        }
        else if (vis[a[i]] == 2)
        {
            ls.push_back(a[i]);
        }
    }
    for (int i = n + 1; i <= 2 * n; i++)
    {
        if (vis[a[i]] == 4)
        {
            rs.push_back(a[i]);
        }
    }
    sort(ls.begin(), ls.end());
    ls.erase(unique(ls.begin(), ls.end()), ls.end());
    sort(rs.begin(), rs.end());
    rs.erase(unique(rs.begin(), rs.end()), rs.end());
    for (int i = 0; i < min(ls.size(), rs.size()) && l.size() < 2 * k; i++)
    {
        l.push_back(ls[i]);
        l.push_back(ls[i]);
        r.push_back(rs[i]);
        r.push_back(rs[i]);
    }
    for (int i = 0; i < t.size() && l.size() < 2 * k; i++)
    {
        l.push_back(t[i]);
        r.push_back(t[i]);
    }
    // int t1 = 0;
    // int t2 = 0;
    for (auto x : l)
    {
        cout << x << ' ';
        // t1 ^= x;
    }
    cout << "\n";
    for (auto x : r)
    {
        cout << x << ' ';
        // t2 ^= x;
    }
    cout << "\n";
    // if (t1 == t2)
    // {
    //     puts("YES");
    // }
    // // for (int i = 1; i <= n; i++)
    // // {
    // //     t1 ^= a[i];
    // // }
    // for (int i = n + 1; i <= 2 * n; i++)
    // {
    //     t2 ^= a[i];
    // }
    // cout << t1 << ' ' << t2 << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - MEX Game 1

解题思路:

出现次数大于\(1\)次的，无论先后手肯定都能抢到。

所以我们按照\(mex\)，从小到大优先拿出现次数为\(1\)的。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> cnt;
    vector<bool> vis(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (auto t : cnt)
    {
        if (t.se >= 2)
        {
            vis[t.fi] = true;
        }
    }
    int cur = 0;
    while (vis[cur])
    {
        cur++;
    }
    for (int i = 1; i <= n; i++)
    {
        while (vis[cur])
        {
            cur++;
        }
        if (cnt[cur] == 1)
        {
            cnt[cur]--;
            vis[cur] = true;
        }
        else
        {
            break;
        }
        while (vis[cur])
        {
            cur++;
        }
        if (cnt[cur] == 1)
        {
            cnt[cur]--;
        }
    }
    int ans = 0;
    while (vis[ans])
    {
        ans++;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D - Non-Palindromic Substring

解题思路:

\(len = r - l + 1\)：

  • \(k = 1\)：肯定回文。
  • \(k = len\)：单独判断
  • \(2 \leq k \leq len - 1\)：
    • \(k\)为奇数：只要整个区间不是\(aba...aba\)这种交叉形式，奇数子串一定都存在。如果\(k = 3\)不存在，意味着整个区间都是\(aba...aba\)这种交叉形式。
    • \(k\)为偶数：只要整个区间字符不是都一样，偶数子串一定都存在。如果\(k = 2\)不存在，意味着整个区间都是一样的。

注意：本题疑似卡了单哈希，如果要用哈希判断整体是否回文，建议使用双哈希映射。

判断整体回文：\(manacher\)；双哈希

判断奇数是否存在：

  • 思路一：\(f[i]:记录右侧奇偶性相同的下标中，第一个不同的字符的位置\)，\((f[l] \leq r || f[l + 1]\leq r)\)。
  • 思路二：哈希判断\((l, r - 2)和(l + 2, r)\)是否完全相同。

判断偶数是否存在：

  • 思路一：\(f[i]:记录右侧第一个不同的字符的位置\)，\((f[l] \leq r)\)。
  • 思路二：区间最大最小值相同。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int P = 13331;
std::vector<int> manacher(std::string s)
{
    std::string t = "#";
    for (auto c : s)
    {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++)
    {
        if (2 * j - i >= 0 && j + r[j] > i)
        {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]])
        {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j])
        {
            j = i;
        }
    }
    return r;
}

void solve()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    auto rad = manacher(s);
    string str = s;
    s = ' ' + s;
    vector<ull> h(n + 1), p(n + 1), h1(n + 10);
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i];
    }
    reverse(str.begin(), str.end());
    str = ' ' + str;
    for (int i = 1; i <= n; i++)
    {
        h1[i] = h1[i - 1] * P + str[i];
    }
    auto get1 = [&](int l, int r) -> ull
    {
        return h[r] - h[l - 1] * p[r - l + 1];
    };
    auto get2 = [&](int l, int r) -> ull
    {
        return h1[r] - h1[l - 1] * p[r - l + 1];
    };
    vector<vector<int>> f(n + 1, vector<int>(22)), g(n + 1, vector<int>(22, 1e9));
    for (int j = 0; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if (j == 0)
            {
                f[i][j] = s[i];
            }
            else
            {
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    auto q1 = [&](int l, int r)
    {
        int len = (r - l + 1);
        int k = log(len) / log(2);
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    };
    for (int j = 0; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if (j == 0)
            {
                g[i][j] = s[i];
            }
            else
            {
                g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    auto q2 = [&](int l, int r)
    {
        int len = (r - l + 1);
        int k = log(len) / log(2);
        return min(g[l][k], g[r - (1 << k) + 1][k]);
    };

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        ll len = r - l + 1;
        ll ans = 0;
        // if (len & 1)
        // {
        //     ll t = len / 2;
        //     if (get1(l, l + t - 1) != get2(n - r + 1, n - (l + t + 1) + 1))
        //     {
        //         ans += len;
        //     }
        // }
        // else
        // {
        //     ll t = len / 2;
        //     if (get1(l, l + t - 1) != get2(n - r + 1, n - (l + t) + 1))
        //     {
        //         ans += len;
        //     }
        // }
        // cout << ans << endl;
        if (rad[l + r - 1] <= len)
        {
            ans += len;
        }
        if (q1(l, r) != q2(l, r))
        {
            ll up = len;
            if (len & 1)
            {
                up--;
            }
            else
            {
                up -= 2;
            }
            ll k = up / 2;
            ans += (2 + up) * k / 2;
        }
        if (len > 3 && get1(l, r - 2) != get1(l + 2, r))
        {
            ll up = len;
            if (len & 1)
            {
                up -= 2;
            }
            else
            {
                up--;
            }
            ll k = up / 2;
            ans += (3 + up) * k / 2;
        }
        cout << ans << "\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签：int,ll,Codeforces,len,vector,long,using,Div,934
From： https://www.cnblogs.com/value0/p/18078508

相关文章

  • codeforce Round 934 div2 个人题解（A~C）
    A.DestroyingBridges时间限制:1秒内存限制:256兆输入:标准输入输出:标准输出有$n$个岛屿，编号为$1,2,…,n$。最初，每对岛屿都由一座桥连接。因此，一共有$\frac{n(n-1)}{2}$座桥。Everule住在岛屿$1$上，喜欢利用桥梁访问其他岛屿。Dominater有能力摧毁最多$k$座......
  • 5 分钟小工具：使用 dive 分析 docker 镜像
    需求拿到一个镜像之后，我想知道：分层查看镜像里都有哪些文件各层使用了什么命令构建的这个镜像镜像里比较大的文件有哪些（可能需要优化）dive工具介绍dive工具可以做这些分析。dive的github地址是 wagoodman/dive，小巧玲珑，MIT开源协议，42.9k的star。它的介绍是这么一......
  • Codeforces Round 908 (Div. 2)
    CodeforcesRound908(Div.2)A-SecretSport解题思路:有一说一，没看很懂，感觉最后赢的就是赢了。。。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingpiii=pair<ll,pa......
  • Codeforces 1948G MST with Matching
    因为贡献是两个之和，考虑固定下一个，求解另一个的最优。\(\text{MST}\)似乎找不到什么好的办法固定，便考虑固定下最大匹配。对于树的最大匹配，考虑到因为树也是二分图，所以树的最大匹配\(=\)最小点覆盖。考虑如果知道了最小点覆盖内的点，那就说明如果一条边两个端点都不在点集中，是......
  • Educational Codeforces Round 163 A-E
    A.SpecialCharacters构造。形如\(A\)和\(B\)这类单个字符构成的字符串对答案的贡献为\(0\)，而\(AA\)和\(AAAA\)这类多个相同字符构成的字符串对答案的贡献固定为\(2\)​，则无法构造出奇数值，由第二类字符串拼接即可构造出偶数值。时间复杂度：\(O(n)\)。#include<bit......
  • Codeforces 1948E Clique Partition
    考虑到有\(|i-j|\)，所以肯定是让相邻的一部分在一个团里。考虑构造出一个最长长度的，后面类似复制几遍即可。考虑到\(|k-1|=k-1\)，且因为\(a_i\)为一个排列，差的绝对值至少为\(1\)，所以只考虑两端最长长度也只可能为\(k\)。不妨先假设最长长度为\(k\)来构造。那么......
  • Codeforces-1005C
    https://codeforces.com/problemset/problem/1005/C一、代码目录#include<bits/stdc++.h>usingnamespacestd;voidsolve(){inta[122222],n,ans=0;map<int,int>m;scanf("%d",&n);for(inti=0;i<n;i++){......
  • Educational Codeforces Round 163 (Rated for Div. 2)
    EducationalCodeforcesRound163(RatedforDiv.2)A-SpecialCharacters解题思路:一个相同的连续段会贡献两个特殊字符，所以答案一定是偶数，找个不同的数分隔开即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll......
  • 3.14 CF Round 933 (Div. 3)
    (1)CF1941BRudolfand121给定一个长度为\(n\)的序列\(a\)。求最少进行多少次操作后所有\(a_i=0\)：选择一个\(2\lei<n\)，并让\(a_i\getsa_i-2,a_{i-1}\getsa_{i-1}-1,a_{i+1}\getsa_{i+1}-1\)。我们记选择\(i=x\)时的操作为\(\opera......
  • Codeforces Round 933 (Div. 3)赛后总结
    CodeforcesRound933(Div.3)B从边缘开始计算，因为边缘肯定只能一个一个减，就可以遍历得到答案.代码C只要对mapie特判，然后判断map和pie的个数就是答案了。D(记忆化搜索)可以通过二维数组来标记搜索状态，将已经出现过的状态直接返回，极大减少时间。#include<bits/stdc++.h>......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99