首页 > 其他分享 >Codeforces Round #842 (Div. 2)

Codeforces Round #842 (Div. 2)

时间:2023-01-06 23:34:35浏览次数:65  
标签:cnt 842 val int s1 Codeforces pos solve Div

Codeforces Round #842 (Div. 2)

https://codeforces.com/contest/1768
好困,放完代码就跑路。

A. Greatest Convex

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n;
    cin >> n;
    cout << n - 1 << endl;
}

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

B. Quick Sort

#include <bits/stdc++.h>

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

void solve () {
    int ans = 0, pos = 0, len = 1;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1)     pos = i;
    }
    for (int i = pos + 1, k = 2; i <= n; i++) {
        if (a[i] == k)  len ++, k++;
    }
    //cout << cnt << ' ';
    cout << (n - len + k - 1) / k << endl;
}

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

//最长有序序列

C. Elemental Decompress

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int cnt[N], p[N], q[N], n;
pii a[N];

void solve () {
    cin >> n;
    set<int> s1, s2;
    for (int i = 1; i <= n; i++)    cnt[i] = 0, s1.insert (i), s2.insert (i);
    for (int i = 1; i <= n; i++) {
        int x;  cin >> x;
        a[i] = {x, i};
        cnt[x] ++;
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] > 2) {
            puts ("NO");
            return ;
        }
    }

    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        int val = a[i].first, pos = a[i].second;
        if (cnt[val] != 2) {
            p[pos] = q[pos] = val;
            s1.erase (val), s2.erase (val);
        }
        else {
            if (s1.count (val)) {
                if (*s2.begin () > val) {
                    puts ("NO");
                    return ;
                }
                p[pos] = val, q[pos] = *s2.begin ();
                s1.erase (val), s2.erase (s2.begin ());
            }
            else {
                if (*s1.begin () > val) {
                    puts ("NO");
                    return ;
                }
                q[pos] = val, p[pos] = *s1.begin ();
                s2.erase (val), s1.erase (s1.begin ());
            }
        }
    }
    puts ("YES");
    for (int i = 1; i <= n; i++)    cout << p[i] << ' ';  cout << endl;
    for (int i = 1; i <= n; i++)    cout << q[i] << ' ';  cout << endl;
}

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

//从小往大放

D. Lucky Permutation

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N], n, cnt;
bool vis[N], exist;
set<int> s;

void dfs (int x) {
    if (vis[x])     return ;
    vis[x] = true;
    s.insert (x);
    if (s.count (x - 1) || s.count (x + 1))     exist = true;
    dfs (a[x]);
}

void solve () {
    cin >> n;
    cnt = 0, exist = false;
    for (int i = 1; i <= n; i++)    cin >> a[i], vis[i] = false;
    for (int i = 1; i <= n; i++) {
        if (vis[i])     continue;
        cnt ++, s.clear ();
        dfs (i);
    }
    int ans = n - cnt + 1;
    if (exist)  ans -= 2;
    cout << ans << endl;
}

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

//置换环结论: cnt个环,变成排列所需次数为n-cnt
//有序排列->一个逆序对: 交换任意邻项(本来是n-cnt+1,如果环中存在邻项的话就可以节省两次)

标签:cnt,842,val,int,s1,Codeforces,pos,solve,Div
From: https://www.cnblogs.com/CTing/p/17031909.html

相关文章

  • Codeforces Round #842 (Div. 2)
    Preface唉现在这是是做稍微难点的SB题(指Div2正常场的CD难度)总是要犯病因此Rating上不去不说,比赛的时候连EF题面都没机会看一眼这场先是C交上去忘记本机调试的时候把数组......
  • Codeforces Round 842
    目录写在前面ABCDE写在最后写在前面仁王真好玩大太刀真好玩下辈子我还要玩大太刀[](https://pic.imgdb.cn/item/63b7fdb4be43e0d30ec2dccd.jpg)顺带吐槽一下,这什么排......
  • 《Quantifying the effects of environment and population diversity in multi-agent
    量化多智能体强化学习中环境和种群多样性的影响总结:在多种实验环境下评估多智能体强化学习受到环境多样性以及智能体多样性的影响,主要是泛化能力实验过程主要是通过改......
  • Codeforces Round #842 (Div. 2)
    题目链接A核心思路:样例模拟出答案。#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<bits/std......
  • Codeforces Round #842 (Div. 2) A-D
    比赛链接A题意给一个数\(k\)找到最大的\(x\),满足\(1\leqx<k\)且\(x!+(x-1)!\)是\(k\)的倍数。题解知识点:数学。猜测\(x=k-1\),证明\((k-1)!+(k-......
  • 1.6 vp Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
    A-AddPlusMinusSign题意:给出01字符串,可以在每两个字符中间任意添加‘+’,‘-’。最后要使表达式的绝对值最小思路:设表达式的值为\(cnt\),若当前\(cnt\)大于\(0\),不管......
  • Codeforces Round #842 (Div. 2) A-C, 补D
    A.GreatestConvex题意:给定一个k,求一个小于k的数x,使得x!+(x-1)!是k的倍数分析:题目已经给出提示:y!=y⋅(y−1)!,输出n-1cout<<n-1<<endl......
  • Codeforces Round #842 (Div. 2) A-D题解
    比赛链接A、GreatestConvex非常的简单。根据样例直接猜是输出\(n-1\).上一个\(Python\)代码。T=int(input())whileT>0:T-=1n=int(input())......
  • B. Quick Sort【Codeforces Round #842 (Div. 2)】
    B.QuickSortYouaregivenapermutation【排列】†\(p\)oflength\(n\)andapositiveinteger\(k≤n\).Inoneoperation,you:Choose\(k\)distinctelement......
  • Codeforces Contest 1616
    A.IntegerDiversity直接用个map贪心,如果有相同的就反向即可。B.MirrorintheString这道题洛谷的翻译锅了,所以建议去看原题。考虑这样一个字符串baacc,那么答案显......