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

Codeforces Round 923 (Div. 3)

时间：2024-02-18 23:11:52浏览次数：24  
标签：return int vi Codeforces ans 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;
}

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

相关文章

  • Codeforces 1661F Teleporters
    先考虑贪心，令\(f(x,k)\)为满足\(\sum\limits_{i=1}^ks_i=x,s_i\in\mathbb{N}_+\)的\(s\)的\(\sum\limits_{i=1}^ks_i^2\)的最小值。也就是题目中在两个固定的点中放\(k-1\)个点这两个点中的最小贡献。平均分肯定是最优的，可以通过\(x\bmodk\)的值\(O(......
  • CF926 Div.2
    C.SashaandtheCasino赌场规则：如果下注\(y(y>0)\)元，如果赢了则除了\(y\)元外，额外获得\(y\times(k-1)\)元，否则则输掉\(y\)元；并且你不能连续输超过\(x\)次最初，你有\(a\)枚硬币，询问是否能够赢取任意数量的硬币题解：思维考虑这样一种策略：假设前面一直输，保......
  • SMU Winter 2024 div2 ptlks的周报Week 3（2.12-2.18）
    这周主要加强了对知识点的掌握。P10161[DTCPC2024]小方的疑惑10从题目可以得知a个连续括号贡献为a(a+1)/2，代价为2a。要求总贡献恰为k，且代价不高于n。一开始我想到了模拟，先取一个贡献低于k最大的a，剩下的再直接在外面套括号，结果wa。又想到可以分出多个a来组成k，就用递归，每次......
  • Codeforces Round 903 (Div. 3)
    题目链接A.按题意模拟字符串find函数if(x.find(s)==string::npos)//没找到#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn,m;cin>>n>>m;stringx,s;cin>>x&g......
  • CF1929 Codeforces Round 926 (Div. 2)
    C.SashaandtheCasino当\(k<x\)时,显然我们只需要每次下注一个硬币就好了.当\(k>x\)时.考虑先一个一个的下硬币,那么为了保证不亏本,最多输\(k-2\)局,然后在第\(k-1\)局赢,这样才能盈利\(1\)个硬币.那么在第\(k\)局之后呢?此时我们最少也需要下注两个硬币,这......
  • 【赛后反思】【LGR-175 Div.4】 洛谷入门赛#20 赛后反思
    洛谷入门赛#20赛后反思今日推歌：《水与水之歌feat.绮萱》きくお呆在这里直到精神恍惚为止让我们一起快乐地玩耍我们术术人有自己的《让我们荡起双桨》（大雾Before先看结果（是同步赛的成绩，因为前一天晚上我在死磕dfs）：省流：暴力-纯度75%STL-纯度25%展开目录目录洛谷入......
  • Codeforces Round 922 (Div. 2)
    A.BrickWall因为水平砖块的长度至少为\(2\)，所以一行中水平砖块最多放\(\lfloor\frac{m}{2}\rfloor\)块，因此答案不超过\(n\cdot\lfloor\frac{m}{2}\rfloor\)。如果\(m\)是奇数，用长度为\(\lfloor\frac{m}{2}\rfloor\)的水平砖块平铺过去，最后一块长度为\(3\)，这样......
  • Codeforces 解题报告（202402）
    CodeforcesRound926D-SashaandaWalkintheCitydp，主要难点在于设状态。发现子树内一旦存在一个点，到当前子树的根节点路径上有两个危险点，那么除了那条链所属的子树，其他的点就都不能选了。所以把这个性质放进状态，设\(f_{u,0/1}\)表示以\(u\)为根的子树内，是否存在一......
  • Codeforces(1500板刷)
    目录写在前面1.A.DidWeGetEverythingCovered?(构造、思维)题目链接题意题解代码总结2F.Greetings（离散化+树状数组）题目链接题意题解代码总结写在前面开始板刷1500了，主要是最近卡1300-1400上不去，发现cf很多思维题要不是想不到，要不就是签的慢，被读题卡了心态就巨难受，一下就......
  • Codeforces Round 926 (Div. 2) 总结
    A题意：给出一个数组，让你重新排序，\(\sum_{i=1}^{n-1}a_i-a_{i+1}\)最大。做法：显然从小到大排序即可，答案就是最大值减去最小值。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e6+5,MOD=998244353;signedmain(){ios::sync_with_s......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99