首页 > 其他分享 >Codeforces Round 923 (Div. 3)

Codeforces Round 923 (Div. 3)

时间：2024-02-22 17:44:07浏览次数：24  
标签：return int vi Codeforces const using Div 923 mod

A. Make it White

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y /= 2;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

void solve() {
    int n;
    string s;
    cin >> n >> s;
    int l = 0 , r = n - 1;
    while( l < n and s[l] == 'W') l ++;
    while( r >= 0 and s[r] == 'W' ) r --;
    cout << max( 0ll , r - l + 1  ) << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for( cin >> TC ; TC ; TC -- )
        solve();
    return 0;
}

B. Following the String

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y /= 2;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

void solve() {
    int n;
    cin >> n;
    vi cnt(26);
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        for (int j = 0; j < 26; j++) {
            if (cnt[j] != x) continue;
            cout << char(j + 'a');
            cnt[j]++;
            break;
        }
    }
    cout << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

C. Choose the Different Ones!

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y /= 2;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<bool> a(k), b(k), c(k);
    for (int i = 1, x; i <= n; i++) {
        cin >> x, x--;
        if (x < k) a[x] = 1, c[x] = 1;
    }
    for (int i = 1, x; i <= m; i++) {
        cin >> x, x--;
        if (x < k) b[x] = 1, c[x] = 1;
    }
    if (accumulate(a.begin(), a.end(), 0) < k / 2) {
        cout << "NO\n";
        return;
    }
    if (accumulate(b.begin(), b.end(), 0) < k / 2) {
        cout << "NO\n";
        return;
    }
    if (accumulate(c.begin(), c.end(), 0) < k) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

D. Find the Different Ones!

这题我用了区间最值查询来实现

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y /= 2;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}


int lgN;
vi lg2(2e5 + 1);


void solve() {
    int n;
    cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    auto exMax = [&a](int i, int j) {
        if (a[i] > a[j]) return i;
        else return j;
    };
    auto exMin = [&a](int i, int j) {
        if (a[i] < a[j]) return i;
        return j;
    };

    vector f(n + 1, vi(lgN + 1)), g(n + 1, vi(lgN + 1));
    for (int i = 1; i <= n; i++)
        f[i][0] = g[i][0] = i;
    for (int j = 1; j <= lgN; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = exMax(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
            g[i][j] = exMin(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
        }
    auto calcMax = [&exMax, &f](int l, int r) {
        int s = lg2[r - l + 1];
        return exMax(f[l][s], f[r - (1 << s) + 1][s]);
    };
    auto calcMin = [&exMin, &g](int l, int r) {
        int s = lg2[r - l + 1];
        return exMin(g[l][s], g[r - (1 << s) + 1][s]);
    };

    int q;
    cin >> q;
    for (int l, r, i, j; q; q--) {
        cin >> l >> r;
        i = calcMax(l, r), j = calcMin(l, r);
        if (a[i] == a[j]) i = j = -1;
        cout << i << " " << j << "\n";
    }
    cout << "\n";
    return;
}

void init() {
    lg2[0] = -1;
    for (int i = 1; i < lg2.size(); i++)
        lg2[i] = lg2[i / 2] + 1;
    lgN = lg2.back();
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

E. Klever Permutation

一个神秘的构造题，简单来说就是要求任意长度为k的子区间的和之差不超过1，这样的话实际上也就是要要求相邻区间的变化应该是加一或减一这样的，因此我们可以规定奇数位为加1，这样分别从两端开始填入就好

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y /= 2;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

void solve() {
    int n, k, m;
    cin >> n >> k;
    vi res(n + 1);
    int l = 1, r = n;
    for (int i = 1; i <= k; i++) {
        for (int j = i; j <= n; j += k) {
            if (i & 1)
                res[j] = l++;
            else
                res[j] = r--;
        }
    }
    for( int i = 1 ; i <= n ; i ++ )
        cout << res[i] << " ";
    cout << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

F. Feed Cats

首先我们定义\(f[i]\)表示只在区间\([1,i]\)中喂猫的最优解。那么答案就是\(f[n]\).

考虑转移，如果位置\(i\)不喂猫，则\(f[i]=f[i-1]\).如果当前位置喂猫，则需要求出来当前能喂的猫的数量\(k\)以及，当前所有能喂的猫的活动区间左端点的最小值\(l\),则\(f[i]=f[l-1]+k\).

显然求\(l,k\)是我们要解决的问题。

首先用\(a[l]\)记录所有活动范围左端点为\(l\)的猫的活动范围的右端点。然后用multiset<int> v维护当前点能喂养所有猫活动范围的左端点。则k=v.size() , l = *v.begin().这样的话，每次只要新到达一个点向v中插入a[i].size()个i，并且向now[a[i]]中插入i表示即可.然后当要离开当前点时，now[i]记录了哪些区间已经到达了有端点，在v中删掉即可。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = 1e9, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};


void solve() {
    int n, m;
    cin >> n >> m;
    vector<vi> a(n + 1), now(n + 1);
    multiset<int> v;
    vi f(n + 1);
    for (int l, r; m; m--)
        cin >> l >> r, a[l].push_back(r);
    for (int i = 1, x; i <= n; i++) {
        for (auto j: a[i])
            v.insert(i), now[j].push_back(i);
        if (v.empty()) x = 1;
        else x = *v.begin();

        f[i] = max(f[i - 1], f[x - 1] + (int) v.size());
        for (auto j: now[i]) v.erase(v.find(j));
    }
    cout << f.back() << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

当然我也看到了一些做法，通过预处理后缀最小值，加dp来计算\(l,k\)的方法.

G. Moving Platforms

本质还是求最短路

假设走到\(u\)最短用时\(d\)，需要等待\(x\)时刻才能使得\(l_u=l_v\)，则从\(u\)走到\(v\)所需要的时间就是\(x+1\)

要求\(x\)，等价于下式

\[l_u+d\times s_u + x\times s_u \equiv l_v+ d\times s_v + x\times s_v \pmod H\\ (s_u-s_v) \times x \equiv l_v-l_u + d\times(s_v-s_u)\pmod H \]

也就是解一元线性同余方程的最小正整数解，解出\(x\)后也就知道边权了

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = 1e9, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

int calc(int a, int b, int m) {
    int x, y, d, t;
    a = (a % m + m) % m, b = (b % m + m) % m;
    d = exgcd(a, m, x, y);
    if (b % d) return -1;
    x = x * b / d % (m / d);
    if (x < 0) x += m / d;
    return x;
}


void solve() {
    int n, m, H;
    cin >> n >> m >> H;
    vi l(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) cin >> l[i];
    for (int i = 1; i <= n; i++) cin >> s[i];

    vector<vi> e(n + 1);
    for (int u, v; m; m--) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vi dis(n + 1, -1);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.emplace(0, 1);
    while (not q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (dis[u] != -1) continue;
        dis[u] = d;
        for (int x; auto v: e[u]) {
            int B = ((l[v] + d % H * s[v]) % H - (l[u] + d % H * s[u]) % H + H) % H;
            int A = (s[u] - s[v] + H) % H;
            x = calc(A, B, H);
            if (x == -1) continue;
            q.emplace(d + x + 1, v);
        }
    }
    if (dis[n] == inf) cout << "-1\n";
    else cout << dis[n] << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

标签：return,int,vi,Codeforces,const,using,Div,923,mod
From： https://www.cnblogs.com/PHarr/p/18027848

相关文章

  • [ARC133B] Dividing Subsequence
    DividingSubsequence这道题与最长公共子序列类似，可以先去水一水那道题。题意本题就是让你从\(p\)里面选出一个子序列\(b_i\)和\(q\)里面选出一个子序列\(a_i\)，我们要使\(b_i\)是\(a_i\)的倍数。解法本题直接用动态规划，是\(O(n^2)\)做法，会超时，因此我们用树状数......
  • Codeforces Round 928 (Div. 4)
    CodeforcesRound928(Div.4)比赛链接A.VladandtheBestofFive思路就是统计字符A和字符B的个数，将个数多的那个输出出来Code#include<bits/stdc++.h>usingnamespacestd;#defineall(x)x.begin()+1,x.end()#defineintlonglongvoidsolve(){strings;......
  • The number of divisors(约数) about Humble Numbers
    Anumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers.Nowgivenahumblenumber,pleasewriteaprogramtocal......
  • Codeforces 1806E Tree Master
    考虑一个最基础的暴力，就是直接记忆化搜索暴力往上跳。但是能发现如果一层的节点数过多，状态数太多，就寄了。再考虑一个基础的暴力，就是直接跳。但是如果要跳的层数过多，就寄了。考虑结合一下，根号分治。对于一层内节点数\(\le\sqrt{n}\)的记录下每两个点间的答案。对于节点数......
  • Codeforces Round 928（Div. 4）
    Dashboard-CodeforcesRound928(Div.4)-Codeforces第一次参加CF，最后一道题连题都没读，下次不会就跳，菜是原罪A：找字符串中A,B数量，遍历一下最后比较即可B：判断是三角形还是正方形，题目表示除了正方形就是三角形，所以直接判断是不是正方形，用ans数组记录每一行1的个数，然后从大......
  • Codeforces Round 900 (Div. 3)
    题目A.只要k出现过就是YES#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,k;cin>>n>>k;map<int,int>mp;for(inti=0,x;i<n;i++){cin......
  • Codeforces Round 928 (Div. 4) (小白的复盘)
    A.VladandtheBestofFive思路:给你一个长度字符串只包含A和B输出最多的字符解法:按题意来Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){strings;cin>>s;intcnt=0;fo......
  • Codeforces Round 928 (Div. 4)（A、B、C、D、E、G）
    目录ABCDEGA统计A、B输出#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definelllonglong#definedbdouble#de......
  • Codeforces Round 928 (Div. 4)
    总结一下最近：感觉过于追求进度了，没有好好的把每题都吃透消化，然后有点依赖题解了，没有好好的思考...B.VladandShapesB题输入二维数组的时候不可以直接两个for循环然后cin，要读入char，再转为数字赋值给二维数组，因为他读入的时候不带有空格而int是要有空格的，这样子比如读000就把它......
  • Codeforces Round 924 (Div. 2)
    目录写在前面ABCDEF写在最后写在前面比赛地址：https://codeforces.com/contest/1928。终于把欠下的一堆题补上了呃呃天使骚骚共通线什么构式呃呃，一周目就想走老师线直通单身笑死我了。A签到。发现等分后重新拼接可以得到\(\frac{x}{2}\times2y\)与\(\frac{y}{2}\times2......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99