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

Codeforces Round #828 (Div. 3)

时间:2022-10-17 21:55:22浏览次数:68  
标签:int Codeforces long cin ++ solve 828 ans Div

Codeforces Round #828 (Div. 3)

https://codeforces.com/contest/1744
罚时爆炸的a~e1

A. Number Replacement

数字一样的对应字母一定要一样

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 55;

void solve () {
    int n;
    cin >> n;
    vector <int> v[N];
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[x].push_back (i);
    }
    
    string s;
    cin >> s;
    for (int i = 1; i <= 50; i++) {
        if (v[i].empty ())  continue;
        for (int j = 1; j < v[i].size (); j++) {
            if (s[v[i][j]] != s[v[i][j-1]]) {
                puts ("NO");
                return ;
            }
        }
    }
    puts ("YES");
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

B. Even-Odd Increments

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int a[N];

void solve () {
    int n, q, ans = 0, odd = 0, even = 0;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i], ans += a[i];
        if (a[i] & 1)   odd ++;
        else    even ++;
    }
    
    while (q --) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            //偶+x
            if (x & 1) {
                //偶 + 奇数 = 奇
                ans += even * x;
                //全变奇
                odd = n, even = 0;
            }
            else {
                //偶 + 偶 = 偶
                ans += even * x;
            }
        }
        else {
            if (x & 1) {
                //奇 + 奇 = 偶
                ans += odd * x;
                //全变偶
                even = n, odd = 0;
            }
            else {
                // 奇 + 偶 = 奇
                ans += odd * x;
            }
        }
        cout << ans << endl;
    }
}

signed main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

C. Traffic Light

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N];

void solve () {
    int n;
    char c;
    string s;
    cin >> n >> c >> s;
    if (c == 'g') {
        cout << "0\n";
        return ;
    }
    set <int> ss;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'g')    ss.insert (i);
    }

    //s += s;
    int ans = 0, tt = *ss.begin ();
    for (int i = 0; i < n; i++) {
        if (s[i] == c) {
            auto it = ss.upper_bound (i);
            if (it == ss.end ())    ans = max (ans, n - i + tt);
            else    ans = max (ans, *it - i);
        }
    }
    cout << ans << "\n";
}

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

D. Divisibility by 2^n

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 5;
//int a[N];

void solve () {
    int n, cnt = 0; //2的个数, 额外的
    cin >> n;
    vector <int> v;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (x % 2 == 0)  x /= 2, cnt ++;
        int dx = 0, j = i;
        while (j % 2 == 0)  j /= 2, dx ++;
        if (dx) v.push_back (dx);
    }
    if (cnt >= n) {
        cout << "0\n";
        return ;
    }
    int res = n - cnt;
    //cout << "res=" << res << endl;
    sort (v.begin (), v.end (), greater <int> ());
    // vector <int> sum (v.size ());
    // sum[0] = v[0];
    // for (int i = 1; i < v.size (); i++) sum[i] = sum[i-1] + v[i];
    //for (auto i : v)    cout << i << ' ';   cout << endl;
    //auto t = lower_bound (sum.begin (), sum.end (), res);

    int pos = 0, ans = 0;
    while (res > 0 && pos < v.size ()) {
        res -= v[pos ++];
        ans ++;
    }

    if (res > 0)    cout << "-1\n";
    else    cout << ans << "\n";
}

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

//看缺几个2,补就完了

E1. Divisible Numbers (easy version)

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve () {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int m = a * b;
    if (c - a <= b - d) {
        for (int i = a + 1; i <= c; i++) {
            int ans = m / __gcd (m, i);
            //cout << "ans=" << ans << endl;
            if (ans > d)    continue;
            int base = ans;
            for (int j = 1; ans <= d; j++) {
                ans = base * j;
                //cout << "ans=" << ans << endl;
                if (ans > b)    break;
            }
            if (ans <= d) {
                cout << i << ' ' << ans << "\n";
                return ;
            }
        }
        cout << "-1 -1\n";
    }
    else {
        for (int i = b + 1; i <= d; i++) {
            int ans = m / __gcd (m, i);
            //cout << "ans=" << ans << endl;
            if (ans > c)    continue;
            int base = ans;
            for (int j = 1; ans <= c; j++) {
                ans = base * j;
                //cout << "ans=" << ans << endl;
                if (ans > a)    break;
            }
            if (ans <= c) {
                cout << ans << ' ' << i << "\n";
                return ;
            }
        }
        cout << "-1 -1\n";
    }
}

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

//交叉构造

E2. Divisible Numbers (hard version)

#include <bits/stdc++.h>
#define int long long

using namespace std;

void get_div (int x, vector <int> &v) {
    for (int i = 2; i * i <= x; i++) {
        while (x % i == 0) {
            v.push_back (i);
            x /= i;
        }
    }
    if (x > 1)  v.push_back (x);
}

void solve () {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int m = a * b;
    
    vector <int> v;
    get_div (a, v), get_div (b, v);
    map <int, bool> dp; //储存c范围内的素因子组合
    dp[1] = true;

    for (auto i : v) { //枚举a*b的所有因子
        auto tmp = dp;
        for (auto j : dp) {
            if (i * j.first <= c)   tmp[i * j.first] = true;
        }
        dp = tmp;
    }

    //for (auto i : dp)   cout << i.first << ' ';cout << endl;

    for (auto i : dp) {
        int x = i.first;
        int y = m / x;
        x = x * (c / x), y = y * (d / y); //限定范围下的上界
        if (x > a && y > b) {
            if (x <= c && y <= d && (x * y) % (a * b) == 0) {
                cout << x << ' ' << y << "\n";
                return ;
            }
        }
    }

    cout << "-1 -1\n";
}

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

//质因数分解

F. MEX vs MED

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N], pos[N], n;

void solve () {
    cin >> n;
    for (int i = 0; i <= n; i++)    pos[i] = 0;
    for (int i = 1; i <= n; i++)    cin >> a[i], pos[a[i]] = i;
    long long ans = 0;
    int l = pos[0], r = pos[0];
    for (int i = 1; i <= n; i++) {
        if (l <= pos[i] && pos[i] <= r)     continue; //不满足mex
        int len = r - l + 1;
        if (len <= 2 * i) { //满足med
            if (r < pos[i]) { //i在右
                for (int j = r; j < pos[i]; j++) {
                    int dx = max (1, j - 2 * i + 1);
                    ans += max (0, l - dx + 1);
                }
            }
            else {
                for (int j = pos[i] + 1; j <= l; j++) {
                    int dx = min (n, 2 * i + j - 1);
                    ans += max (0, dx - r + 1);
                }
            }
        }
        l = min (l, pos[i]), r = max (r, pos[i]);
    }
    cout << ans << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

标签:int,Codeforces,long,cin,++,solve,828,ans,Div
From: https://www.cnblogs.com/CTing/p/16800842.html

相关文章

  • Codeforces Round #827 (Div. 4) 复盘+题解
    原比赛链接复盘:ABC签到,手速太慢了。D捣鼓了好久才想起来从更小的值域出发去做。E简单二分答案。然后就timeout了。D题搞错方向浪费太久时间了。F思维题,拐两个弯再$r......
  • Codeforces Round #729 (Div. 2) C
    C.StrangeFunction考虑反想我们将x确定看看有多少个i对于f[i]=x我们显然i%lcm(1,2,3,...x-1)!=0这里就可以通过容斥直接求解i%lcm(1,2,3,...x-1)是含有1,2,3,...x-1......
  • Dive into deep learning
    前言虽然pytorch等框架已经有现成的函数不用我们再重复造轮子,但是自己实现对于我们“炼丹”有很大的好处,基于此我想把我学习过程中遇到的一些函数,给写下来,方便自己理解。......
  • Educational Codeforces Round 112 D
    D.SayNotoPalindromes很牛逼我们手动模拟一下可以知道只有3个字母不构成回文串只有可能是这样的abcabc....acbacb.......6种情况所以直接暴力预处理即可#inclu......
  • Codeforces Global Round 16 D
    D2.SeatingArrangements(hardversion)题意我们要先按照a来排序然后再来安排d的位置最开始都能想到的一点就是我们可以每一组内按照逆序排序我们就可以让组内是0贡......
  • jquery鼠标移入移出事件显示div
    <liclass="active"><divclass="PartR"></div></li><scripttype="text/javascript">$(function(){//显示隐藏varcolor......
  • MaHengbo-2022-MultiObjectiveDiverseHumanPredictionWithKnewledgeDistillation
    Multi-ObjectiveDiverseHumanMotionPredictionWithKnowledgeDistillation#paper1.paper-info1.1MetadataAuthor::[[HengboMa]],[[JiachenLi]],[[Ramti......
  • Codeforces Round #781 (Div. 2) - D. GCD Guess
    GCD+位运算[Problem-1665D-Codeforces](https://codeforces.com/problemset/problem/1627/D)题意交互题,有一个未知数\(x\;(1<=x<=10^9)\),最多有30次询问,每次......
  • Codeforces Round #742 (Div. 2) C
    C.CarryingConundrum这样子进位显然奇偶就独立了我们分别对于奇偶计算方案数然后乘法法则即可比如我们现在奇数位num1偶数位num2我们的方案就是num1+1偶数位就是n......
  • Codeforces Round #628 (Div. 2)——D(二进制,构造,思维)
    https://codeforces.com/problemset/problem/1325/D题目大意给你\(u,v\)两个数,叫你构造出最短的数组,满足所有的异或等于\(u\),所有的和等于\(v\)思路首先我们可以......