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

Codeforces Round 943 (Div. 3)

时间:2024-05-03 22:55:25浏览次数:21  
标签:ps int res 943 Codeforces pb 异或 ans Div

Codeforces Round 943 (Div. 3)

A. Maximize?

题意:给定x,求一个范围在[1, x)的数字y,内使得gcd(x, y) + y最大,输出任意的y

思路:数据范围很小,暴力枚举即可

void solve(){
    int x;
    cin >> x;
    int y = 1, ma = 0;
    for(int i = 1; i < x; i ++){
        int res = __gcd(i, x) * i;
        if(res > ma){
            ma = res;
            y = i;
        }
    }
    cout << y << '\n';
}

B. Prefiquence

题意:给定字符串s1, s2,求字符串s1是s2子序列一个最大前缀的长度

思路:两个指针即可,i 指针在s2, j 指针s1,当s2[i] == s1[j],j ++,最后答案就是 j

void solve(){
    int n, m;
    string s1, s2;
    cin >> n >> m >> s1 >> s2;
    int i = 0, j = 0;
    for(i = 0, j = 0; i < m && j < n; i ++){
        if(s1[j] == s2[i]) j ++;
    }
    cout << j << '\n';
}

C. Assembly via Remainders

题意:给定一个长度为n-1的数组a,构造一个长度为n的数组b,a[i] = b[i + 1] % b[i]

思路:求前缀和,然后把每个数加上一个极大值即可

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 2; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) a[i] += a[i - 1];
    for(int i = 1; i <= n; i ++){
        cout << a[i] + 1000000 << ' ';
    }
    cout << '\n';
}

D. Permutation Game

题意:给定两个数组a,p,刚开始两人分别位于pb,ps,没人一共可以进行k次操作,每次操作会发生两件事:

(1):获得a[pb]的分数

(2):从pb转移到p[pb](可以选择不转移)

(ps同理)

最后分数高的获胜,求最后获胜者或者平局

思路:赛时想太多了,其实很简单,枚举min(n, k)次转移,因为可以发现转移次序是一个环,求假设这次转移之后一直待在这个点直到最后获得的分数取max即可

void solve(){
    ll n, k, pb, ps;
    cin >> n >> k >> pb >> ps;
    vector<ll> p(n + 1), a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> p[i];
    for(int i = 1; i <= n; i ++) cin >> a[i];
    ll ans_pb = 0, ans_ps = 0;
    ll res_pb = 0, res_ps = 0;
    for(int i = 0; i < min(k, n); i ++){
        res_pb += a[pb];
        ans_pb = max(ans_pb, res_pb + (k - i - 1) * a[pb]);
        pb = p[pb];
        res_ps += a[ps];
        ans_ps = max(ans_ps, res_ps + (k - i - 1) * a[ps]);
        ps = p[ps];
    }
    if(ans_pb > ans_ps) cout << "Bodya\n";
    else if(ans_pb == ans_ps) cout << "Draw\n";
    else cout << "Sasha\n";
}

E. Cells Arrangement

题意:给定一个n*n的矩阵,在矩阵中放置n个点,求每个点到所有点的曼哈顿距离的总种类数最多的一种放置方式

思路:构造,观察发现,在(1,1)放一个,然后(2,1)下面放一个,如果有多的,右下角放一个, 剩下的放在(1,3)~(1,3 + n - 3)

void solve(){
    int n;
    cin >> n;
    cout << "1 1\n2 1\n";
    if(n > 2){
        cout << n << ' ' << n << '\n';
        for(int i = 3; i < n; i ++){
            cout << 1 << ' ' << i << '\n';
        }
    }
}

F. Equal XOR Segments

题意: 给定一个数组,一个数组为有趣的定义为:可以分为k>1个部分,每个部分连续异或后的结果相等,现在对这个数组查询q次子数组,判断子数组是否有趣

思路:可以确定,如果一个区间的异或和为0,那么肯定可以分为两个部分,如果不是0的话应该是分成三份,因为这三份异或之后还是这个区间的异或和,先处理出来前缀异或和,记录前缀异或和对应的每个点的下标,然后:

(1):找区间内左边的点PL,PL对 a[r] 的异或为PL的前缀异或和,因为pl~r的区间异或和为0

(2):找区间内右边的点PR,PR对 a[l - 1] 的异或为 a[l - 1] 的前缀异或和,与(1)同理

void solve(){
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    map<int, vector<int>> mp;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++){
        a[i] ^= a[i - 1];
        mp[a[i]].push_back(i);
    } 
    while(q --){
        int l, r;
        cin >> l >> r;
        ll p = a[r] ^ a[l - 1];
        if(p == 0){
            cout << "YES\n";
        }
        else{
            auto &v1 = mp[a[r]];
            auto pl = lower_bound(v1.begin(), v1.end(), l);
            if(pl == v1.end() || *pl >= r){
                cout << "NO\n";
                continue;
            }
            ll posl = *pl;
            auto &v2 = mp[a[l - 1]];
            auto pr = lower_bound(v2.begin(), v2.end(), posl + 1);
            if(pr != v2.end() && *pr < r){
                cout << "YES\n";
            }
            else cout << "NO\n";
        }
    }
}

G1. Division + LCP 

题意:定义 f(x) 为将字符串分割成 x 份的最大公共前缀,求 fl,fl+1,…,fr

思路:pending

标签:ps,int,res,943,Codeforces,pb,异或,ans,Div
From: https://www.cnblogs.com/RosmontisL/p/18171771

相关文章

  • Codeforces 1129E Legendary Tree
    考虑让选取的集合更加特殊,不妨就让\(S=\{x\}\)。那么这个时候能发现询问\((S=\{x\},T,v)\)得到的就是以\(x\)为根时\(v\)的子树内\(T\)中的点的数量。考虑定个根,不妨为\(1\),同时令\(S=\{1\}\)。那么询问\((\{1\},\{1,\cdotsn\}\backslash\{1,x\},x)......
  • G2. Division + LCP (hard version)
    G2.Division+LCP(hardversion)Thisisthehardversionoftheproblem.Inthisversion$l\ler$.Youaregivenastring$s$.Forafixed$k$,consideradivisionof$s$intoexactly$k$continuoussubstrings$w_1,\dots,w_k$.Let$f_k$bethemaximal......
  • Codeforces Round 943 (Div. 3)
    无伤但没速通,然后被hack两个题,直接从rk90掉到rk114514+了,我是真他妈的服了。特此纪念A暴力枚举秒了。B二分答案秒了C他妈脑子抽了,差一步完全整解。我们发现只要确定\(a_{\mathbf{1}}\)那么你直接不断加\(x_i\)就能求出\(a_i\),但是直接这么搞过不了样例,观察一下,然后直......
  • Codeforces 452F Permutation
    对于\(a,b,\frac{a+b}{2}\)肯定是需要固定下一些变量来考虑的。考虑固定下\(c=\frac{a+b}{2}\),考虑\(a,b\)。那么这样的\(a,b\)肯定满足\(a-c=b-c,a\not=b\),那么以\(c\)为中心,\(a,b\)就是对称的。用\(s_i=0,1\)来表示\(i\)是在\(c\)的......
  • CF-943(已更B-E)
    CF-943(已更B-E)D赛时没调出来(╬▔皿▔)╯,还有几分钟的时候反而把E过了,本来应该是上大分一场(⊙﹏⊙),等会会补G1这假期要刷题,还要补文化课……后面有空的话更一下之前打的线下赛的题解B双指针……voidsolve(){ intn,m;cin>>n>>m; stringa,b;cin>>a>>b; intnow=0......
  • Codeforces 1044F DFS
    考虑到存在方案使得以\(u\)为起点还能走出原树的条件。能发现是以\(u\)为根,在原树上新添加的边只会是返祖边而不会有横叉边。这是因为如果有横叉边就肯定会在遍历到一边的点后先通过这条边走到另一边的点,就算上了这条边就不是原树了。那么考虑\((x,y)\),合法的\(u\)需要......
  • Educational Codeforces Round 165 (Rated for Div. 2) C. Minimizing the Sum题解
    题意CodeforcesRound809(Div.2)D1.ChoppingCarrots(EasyVersion)给你两个整数\(n(1\len\le3e5),k(0\lek\le10)\),一个数组\(a(1\lea_i\le10^9)\)。你可以进行如下操作最多\(k\)次:选定一个数\(i(1\lei\len)\),让其变为相邻的数(变为\(a_{i-1},a_{i......
  • Codeforces Round 942 (Div. 2) (A - E)
    A.ContestProposal如果\(a_i>b_i\),则答案加一,令\(\foralli\in[i+1,n],\a_i\leftarrowa_{i-1}\)。submissionB.CoinGames题意:\(n\)枚硬币围成一圈,给出初始硬币状态,每取出一枚正面朝上的硬币并翻转相邻的两枚,没有正面则对方获胜,问先手胜负。令当前正面硬......
  • Codeforces Round 942 (Div. 2)
    CodeforcesRound942(Div.2)A.ContestProposal题意:有n个题目,每个题目的难度为a[i],要求每个题目的难度不大于对应的b[i],每次可以添加一个题目并且删去最难的题目,求最多能添加几个题目思路:暴力枚举即可,只要a[i]大于b[i],就把a[n]改为b[i],然后重新排序voidsolve(){int......
  • Codeforces Round 942 Div.2 题解
    蹭个热度,挽救一下cnblogs蒸蒸日上的阅读量。Q:你是手速狗吗?A:我觉得我是。2A因为选的\(w\)一定可以让它合法,一次操作可以看作\(a\)数组向右平移一位。枚举操作次数后暴力判断即可。#include<bits/stdc++.h>voidwork(){ intn; std::cin>>n; std::vector<......