当前位置: 首页 > news >正文

Codeforces Global Round 23(A~C)

更好的阅读体验 \color{red}{更好的阅读体验} 更好的阅读体验


文章目录

    • A. Maxmina
    • B. Rebellion
    • C. Permutation Operations


A. Maxmina


Origional Link

题目大意

  • 给定长度为 n n n 只包含 0 , 1 0,1 0,1 的序列 a a a,和一个整数 k k k,保证 ( 2 ≤ k ≤ n ≤ 50 ) (2\le k\le n\le 50) (2kn50)
  • 不限次数进行如下操作:
  • 将连续且相邻的两个元素变为较小的一个。
  • 将连续的 k k k 个区间的元素变为区间内元素最大的哪一个。
  • 求给出的序列是否可以变为只包含 1 1 1 的序列。

思想

  • 签到题。
  • 保证 ( 2 ≤ k ≤ n ≤ 50 ) (2\le k\le n\le 50) (2kn50) 即保证了只要序列里含有 1 1 1,便可不断执行操作二,即只要存在 1 1 1 即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    int n, k; cin >> n >> k;

    bool flag = 0;

    for(int i = 0; i < n; i ++){
        int x; cin >> x;
        if(x == 1) flag = 1;
    }

    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

B. Rebellion


Origional Link

题目大意

  • 给定长度为 n n n 只包含 0 , 1 0,1 0,1 的序列 a a a
  • 不限次数进行如下操作:
  • 选择两个下标 1 ≤ i , j ≤ n , i ≠ j 1 \le i,j\le n,i\ne j 1i,jn,i=j
  • 使得 a j = a j + a i a_j = a_j + a_i aj=aj+ai
  • a i a_i ai a a a 中去除。
  • 若最终可以通过上述操作将 a a a 变为非严格单调递增的序列,则求出最小操作次数,否则输出 − 1 -1 1

思想

  • 思维题。
  • a a a 排序,与原位置不相同时只可能为原序列为 1 1 1 而排序后为 1 1 1 的情况。
  • 此时我们只需要执行操作一即可,等价于交换两数的值。
  • 由此我们可以利用双指针操作并记录次数,或者直接统计需要交换位置的数量除以 2 2 2 即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[N], b[N];

void solve(){

    int n; cin >> n;

    for(int i = 0; i < n; i ++){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    int cnt = 0;
    for(int i = 0; i < n; i ++){
        if(a[i] != b[i]) cnt ++;
    }
    cout << cnt / 2 << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

C. Permutation Operations


Origional Link

题目大意

  • 给定一个长度为 n n n 的排列序列 a a a
  • i i i 次操作中,你可以选择任意的 a a a 的非空后缀,使得所有的后缀元素加 i i i
  • 求如何操作,使得操作后的序列 a a a 不含逆序对。
  • 输出第 i i i 次操作的后缀的起始位置。
  • 逆序对:对于 i , j ( i > j ) i,j(i\gt j) i,j(i>j) 满足 a i < a j a_i \lt a_j ai<aj

思想

  • 思维题。
  • 记录每一对逆序对的差值,那么第 i i i 次操作需要补足该差值。
  • 由于对后缀的操作不会影响到前面,则我们不需要考虑操作的顺序,只需考虑差值何时补齐即可。
  • 显然,我们可以对所有的差值从小到大进行排序,第 i i i 次操作可以操作差值为 t , t < i t,t\lt i t,t<i 的位置后缀,若无法操作输出 1 1 1
  • 使用优先队列(小根堆)存储所有的差值,操作后出队,队列为空说明已经补齐了差值,此时仅需输出 1 1 1 即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[N];

void solve(){

    int n; cin >> n;
    
    for(int i = 1; i <= n; i ++) cin >> a[i];

    priority_queue<PII, vector<PII>, greater<PII>> b;

    for(int i = 2; i <= n; i ++){
        int t = a[i] - a[i - 1];
        if(t <= 0){
            b.push({-t + 1, i});
        }
    }

    if(b.empty()){
        for(int i = 1; i <= n; i ++) cout << 1 << ' ';
    }
    else{
        auto p = b.top();
        for(int i = 1 ; i <= n; i ++){
            if(i >= p.fi && !b.empty()){
                cout << p.se << ' ';
                b.pop(); p = b.top();
            }
            else cout << 1 << ' ';
        }
    }

    cout << endl;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

相关文章:

  • ARM64架构栈帧以及帧指针FP
  • 东莞交投集团供应链服务平台上线啦
  • 机器人机械手加装SycoTec 4060 ER-S电主轴高精密铣削加工
  • 2024最新Guitar Pro 8.1中文版永久许可证激活
  • 【机器学习】包裹式特征选择之序列后向选择法
  • 如何降低 BlueNRG-LPS 的开机峰值电流
  • Java Web(十一)--JSON Ajax
  • mac m3安装nvm安装说明;mac安装xbrew
  • 防御保护:VPN
  • 《TCP/IP详解 卷一》第6章 DHCP
  • Self-attention与Word2Vec
  • React最常用的几个hook
  • wy的leetcode刷题记录_Day15
  • GAMES104 雾系统、反走样与后处理
  • 成员方法传参机制
  • mac苹果通过pycharm进行ssh远程连接服务器(Ubuntu)
  • AJAX异步请求(Asynchronous Javascript And Xml)
  • Android12 A2DP连接[1]
  • JAVA SE_part.2
  • 5.HttpServletRequest类
  • 【SQL刷题】秋招刷爆SQL题之插入数据
  • 刷爆leetcode第九期 0020
  • Colmap安装与实践
  • 【苹果iMessage相册推信息推】 重要用于安装背面必要安装的watchman
  • 艾德克斯IT6512D可编程直流电源中文介绍
  • 使用机器学习做DGA域名识别
  • Day06-尚品汇-排序操作上
  • Linux进程替换(exec系列)
  • 史上最全软件测试工程师常见的面试题总结(百度、oppo、中软国际、华为)
  • 艾美捷抗人IL-2单抗MT8G10即用型解决方案
  • 头歌-信息安全技术-实训04 数据库SQL注入漏洞
  • C# 中的多线程