首页 > 其他分享 >Codeforces Round 884 (Div. 1 + Div. 2)

Codeforces Round 884 (Div. 1 + Div. 2)

时间:2023-07-13 11:55:51浏览次数:34  
标签:return 884 int res Codeforces fa solve -- Div

A. Subtraction Game

答案就是a+b此时后手必胜因为无论怎么操作后手都可保证自己取的时候一次全部取完

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int a , b;
    cin >> a >> b;
    cout << a + b << "\n";
    return ;
}

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

B. Permutations & Primes

赛时没有仔细想而是打了个表找规律,结果找到假规律了。

构造的方法是把2,3放在首尾,把 1 放在尽可能中间的地方,其他随意放即可。

这样包含 1 且不包含 2 或 3 的区间数量最多

#include <bits/stdc++.h>

using namespace std;

bool prime( int x ){
    if( x == 1 || x == 0 ) return false;
    for( int i = 2 ; i * i <= x ; i ++ )
        if( x % i == 0 ) return false;
    return true;
}

void solve(){
    int n;
    cin >> n;
    if( n == 1 )
        cout << "1\n";
    else if( n == 2 )
        cout << "1 2\n";
    else{
        cout << "2 ";
        int t = 4 , d = ( n - 3 ) / 2 ;
        for( ; d ; d -- ,t ++ )
            cout << t << " ";
        cout << "1 ";
        for( ; t <= n ; t ++ )
            cout << t << " ";
        cout <<"3\n";
    }

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

C. Particles

可以发现奇数位的只能和奇数位的合并,同理偶数位的也只能和偶数位的合并。所以分奇偶来看,先来考虑奇数位置上的a,b,c,d,e先删掉c得到a,b+d,e,再删b+d得到a+e所以显然我们可以选择奇数位上任意几个数字求和。所以答案就变成了奇数位上的正数之和。偶数位同理,二者取较大值即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n , res;
    cin >> n;
    vector<int> a(n);
    for( auto & i : a ) cin >> i;
    res = *max_element(a.begin(), a.end());
    if( res <= 0 ){
        cout << res << "\n";
        return ;
    }
    int cnt = 0;
    for( int i = 0; i < n ; i += 2 ){
        if( a[i] > 0 ) cnt += a[i];
    }
    res = max( res , cnt );

    cnt = 0;
    for( int i = 1; i < n ; i += 2 ){
        if( a[i] > 0 ) cnt += a[i];
    }
    res = max( res , cnt );

    cout << res << "\n";
    return;
}

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

D. Row Major

对于n我们求出所有的因子,然后计算因子的mex,间隔mex位的一定不会相邻,所以可以放相同的字母。

#include <bits/stdc++.h>

using namespace std;


void solve(){
    int n , t ;
    cin >> n;
    set<int> a;
    for( int i = 1 ; i*i <= n ; i ++ ){
        if( n % i ) continue;
        a.insert(i);
        if( i * i != n ) a.insert( n / i );
    }
    for( int i = 1 ; i ; i ++ )
        if( a.count(i) == 0 ){
            t = i;
            break;
        }
    vector<int> b(n+1);
    for( int i = 1 , p = 0 ; i <= t ; i ++ , p ++)
        for( int j = i ; j <= n ; j += t )
            b[j] = p;
    for( int i = 1 ; i <= n ; i ++ )
        cout << (char)(b[i] + 'a' );
    cout << "\n";

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

E. Great Grids

首先我们把\(A,B,C\)离散化为\(0,1,2\)

这样的话,我们可以推出对于任意的一个\(2\times 2\)的格子满足一下性质

\[a_{1,2} - a_{1,1} = a_{2,2} - a_{2,1}(\mod3)\\ a_{2,1}-a_{1,1} = a_{2,2}-a_{1,2}(\mod3) \]

根据这个性质,可以知道任意选择相邻两列作差相同,行有相同的结论。并且这个差值的取值只能为\(1,2\)

image-20230713102240485

以上图为例,\(a,b\)表示列变换量,\(x,y\)表示行变换量,则有

\[B = (A+a)\mod 3 ,E = (D+a)\mod 3 , H = (G+a)\mod 3\\ D = (A+x)\mod 3 , E = (B+x) \mod3,F=(C+x)\mod 3 \]

有因为行变换量和列变换量的取值只有两种,所以可以知道变换量之间的关系只有相等和不相等两种。

image-20230713102258484

再来看题目给出的额外限制,则可以推出

如果\(A=D\),则有\(a \ne x\)

如果\(B=C\),则有\(a=x\)

所以这题就是用扩展域并查集维护\(k\)个额外限制即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

map<int, int> cnt;

class dsu {
private:
    vector<int> fa;
public:
    dsu(int n = 1) {
        fa = vector<int>(n + 1, -1), fa[0] = 0;
    }

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
    }

    bool same(int x, int y) {
        x = getfa(x), y = getfa(y);
        return (x == y);
    }
};


void solve() {
    int n, m, k, p, f = 1;
    cin >> n >> m >> k, p = n + m;
    dsu d(p * 2);
    for (int xa, xb, ya, yb, x, y; k; k--) {
        cin >> xa >> ya >> xb >> yb;
        if (f == 0) continue;
        x = xb, y = max(ya, yb) + n;
        if (ya < yb) {
            if (d.same(x, y)) f = 0;
            else d.merge(x, y + p), d.merge(x + p, y);
        } else {
            if (d.same(x, y + p)) f = 0;
            else d.merge(x, y), d.merge(x + p, y + p);
        }
    }
    if( f ) cout << "YES\n";
    else cout << "NO\n";
    return;
}

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

标签:return,884,int,res,Codeforces,fa,solve,--,Div
From: https://www.cnblogs.com/PHarr/p/17550064.html

相关文章

  • codeforces-817 D. Imbalanced Array(单调栈)
    题意:求数组中每个连续子序列的的最大值-最小值之和。思路:题意可以理解为加上每一个序列的最大值,减去每一个序列的最小值。每个数都可以作为某一连续子序列的最大值和最小值,所以可以枚举每一个数作为最值的区间,暴力枚举时间复杂度过高,所以利用单调栈找出每个数左边或右边第一个比......
  • CF884G Tree Wights
    CF884GTreeWights给定一棵\(n\)个点的树,给定\(d_1,d_2,\cdots,d_{n-1}\),其中\(d_i\)表示\(i\)到\(i+1\)在树上简单路径的距离,问能否构造每条边的边权都是正整数,并构造一种解。\(2\len\le10^5\),\(1\led_i\le10^{12}\)。本题难点在于两次转化。首先,如果题目中......
  • Codeforces Round 871 (Div. 4) ABCDEF
    很久没写题目了,划点水题A.LoveStory#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLMAXN=1e18;constLLN=1e6,M=4002;constLLmod=1e9+7;intmain(){//cin.tie(0);cout.tie(0);ios......
  • 「解题报告」Codeforces Round #884 (Div. 1 + Div. 2) Editorial
    比赛地址:Dashboard-CodeforcesRound884(Div.1+Div.2)-Codeforces个人评价:这场是构造专场!A.SubtractionGameProblem-A-Codeforces有一堆石子(应该是石子),每次只能拿走\(a\)块或者\(b\)块,最先不能移动的人输,构造一个数\(n\),使得先手必输。两种构造方法:......
  • CodeForces Gym 102900B Mine Sweeper II
    CF传送门感觉像脑筋急转弯。考虑所有数字之和就是相邻的\((\text{雷},\text{空地})\)对数,因此翻转后这个对数不会改变。然后由于抽屉原理,\(b\toa\)和\(b\to\operatorname{inv}(a)\)中至少有一个操作次数\(\le\left\lfloor\frac{nm}{2}\right\rfloor\),然后就做完了......
  • UESTC 2023 Summer Training #02 Div.2
    Preface都给我丑完了这怎么办啊,被血虐了苦路西这场本来前面感觉都还可以,但是当中期看了眼C的题意后准备开C后就不对劲了起来最后1h扔掉一直T的C题去做H,结果因为被卡自然溢出的Hash一直挂到比赛结束,直接红温感觉这场策略问题挺大的,比如没有跟榜去写更加简单的E题(比赛的时候题......
  • Codeforces Round #771 (Div. 2) A-E
    A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intp[507];boolsolve(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>p[i];intpos1=0,pos2=0;for(inti=1;i<=n;i++){......
  • CodeForces 1525F Goblins And Gnomes
    洛谷传送门CF传送门套路地,将DAG的最小不交路径覆盖转化为点数减去拆点以后最大匹配。感性理解就是一开始每个点都是一条路径,一个匹配意味着两条路径结合了。由题意知,第\(i\)次进攻时最小不交路径覆盖必须\(>i\),也就是说,设最大匹配为\(k\),那么\(n-k>i\),即\(k\le......
  • E. Two Chess Pieces -- (codeforces) 树形DP
    原题链接:https://codeforces.com/contest/1774/problem/E题意:两颗棋子,给出两颗棋子必须要去的顶点,且给出两颗棋子的相隔距离不能大于d,算出两颗棋子完成目标后走的距离。最后两颗棋子都要回到顶点1上。思路:刚开始没想出来,顺着官方题解写的,大意就是我用数组s1和s2代表两颗棋子......
  • JQuery 控制 Div 显示和隐藏
    页面上有两个Div用JQuery控制Div显示和隐藏。实现Div间切换的需求<divclass="IndConKHuansoverH"id="divExtTelList">11111111111111111111<div><divclass="IndConBflex"id="divExtTelStatus">22222222222222......