程序员经验分享-hwhale

Codeforces Round #677 (Div. 3) 题解

2023-05-16

Codeforces Round #677 (Div. 3) 题解

A. Boring Apartments

题目

在这里插入图片描述

题解

简单签到题，直接数，小于这个数的 + 10 +10 +10。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 2e5 + 10;
int a[maxn];
void solve(){
    ll ans = 0;
    int n; cin >> n;

    int cnt = 0, x = n, c10 = 1;
    while(x){
        x /= 10;
        cnt++;
        c10 *= 10;
    }
    c10 /= 10;
    int t = n / c10;
    // cout << c10 << " " << cnt << " " << t << endl;
    ans += (t - 1) * 10;
    cout << ans + (1 + cnt) * cnt / 2 << endl;
}
int main(){
    IOS; int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

B. Yet Another Bookshelf(思维)

题目

在这里插入图片描述

题意

让书架上所有的书 ( a [ i ] = 1 ) (a[i] = 1) (a[i]=1) 相邻。每次可以将相邻的一段 1 1 1(可以是 1 1 1个)向左移或者右移。

题解

开始模拟了一遍，但没过，太菜了。

思路：统计每个 1 1 1与其最近 1 1 1之间有多少个 0 0 0。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 100 + 10;
int a[maxn], b[maxn];
void solve1(){
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> num;
    for (int i = 0; i < n; i++){
        if(a[i] == 0) num.push_back(0); 
        if(a[i] == 1) {if(i == 0 || a[i-1] == 0) num.push_back(1); }
        // cout << i << " " << a[i] << " " << num.size() << endl;
    }
    // for (auto x : num) cout << x << " "; cout << endl;

    n = num.size();
    int cnt = 0, ans = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) cnt += (num[i] & 1);
    
    if(cnt == 1){
        cout << 0 << endl;  return;
    }

    for (int l = 0; l + cnt - 1 < n; l++){
        int r = l + cnt - 1;
        int res = 0;

        vector<int> c0, c1;
        for (int i = 0; i < n; i++){
            if(i >= l && i <= r) {if(num[i] == 0) c0.push_back(i);}
            else {
                if(num[i] == 1) c1.push_back(i);
            }
        }
        for (int i = 0; i < c1.size(); i++){
            res += abs(c1[i] - c0[i]);
        }
        // cout << l << " " << r << " " << res << endl;
        ans = min(ans, res);
    }

    cout << ans << endl;
}

void solve(){
    int n; cin >> n;
    vector<int> num;
    for (int i = 0; i < n; i++){ 
        cin >> a[i]; 
        if(a[i]) num.push_back(i);
    }

    cout << num.back() - num[0] - 1 - num.size() + 2 << endl;
}
int main(){
    IOS; int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

C. Dominant Piranha（思维）

题目

在这里插入图片描述

题意

水族馆里的食人鱼每次可以吃掉比它小的相邻的食人鱼。求最后的那一个食人鱼最开始的位置。

题解

找最大值。(比B简单？)

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 3e5 + 10;
int a[maxn];
void solve(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<pi> num;
    for (int i = 1; i <= n; i++){
        if(i > 1 && a[i] > a[i-1]) num.push_back({a[i], i});
        if(i < n && a[i] > a[i+1]) num.push_back({a[i], i});
    }

    int pos = -1;
    for (auto p : num){
        if(pos == -1) pos = p.second;
        else if(a[pos] < p.first) pos = p.second;
    }
    cout << (pos == -1 ? -1 : pos) << endl;
}
int main(){
    IOS; int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

D. Districts Connection(简单构造)

题目

在这里插入图片描述

题意

要在 n n n个点建建立 n − 1 n-1 n−1 条边，使 n n n个点联通（直接或者间接）。但是相同的帮派间不可以建边，构造出一个可行的方案。

题解

  • 当只有 1 1 1个帮派的时候，连接 n n n个顶点是不可能的。

  • 我们可以选一个帮派，记为 g a n g 1 gang1 gang1，将其中一个点和其他的每一个点连接。这样保证这个点与不是帮派 g a n g 1 gang1 gang1的所有的点联通。 再将帮派 g a n g 1 gang1 gang1的其他点与不在帮派 g a n g 1 gang1 gang1的任一点连接，这样构造保证所有的点互相联通。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 5e3 + 10;
int a[maxn];
void solve(){
    int n; cin >> n;
    unordered_map<int, vector<int>> p;
    for (int i = 0; i < n; i++){ 
        cin >> a[i];
        p[a[i]].push_back(i + 1);
    }

    if((int)p[a[0]].size() == n){
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    int pos = a[0];
    for(auto x : p){
        if(x.first == pos) continue;
        for(auto c : x.second) cout << 1 << " " << c << endl;
    }
    for(auto x : p){
        if(x.first != a[0]){
            pos = x.first;
            break;
        }
    }

    vector<int> t = p[a[0]];
    int q = p[pos][0];
    // cout << "at: " << pos << " " << t.size() << " " << q << endl;
    for (int i = 1; i < (int)t.size(); i++){
        cout << q << " " << t[i] << endl;
    }
}
int main(){
    IOS; int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

E. Two Round Dances

题目

在这里插入图片描述

题解

( 在oeis网上输入 12164510040883200 12164510040883200 12164510040883200 就明白了。)

圆排列。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 3e5 + 10;
int a[maxn], dp[maxn];
void solve(){
    int n; cin >> n;
    if(n <= 4){
        cout << (n == 2 ? 1 : 3) << endl;
        return;
    }
    n /= 2; n-=1;
    ll ans = 1;
    for (int i = 1; i <= 2 * n + 1; i++) if(i != n + 1) ans *= i;

    cout << ans << endl;
}
int main(){
    IOS; int t = 1;
    while(t--){
        solve();
    }
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Codeforces

Round

677

div

Codeforces Round #677 (Div. 3) 题解 的相关文章

随机推荐

  • 【SLAM 十四讲】---第七讲、视觉里程计

    第七讲 视觉里程计

  • Vscode配置git

    1 Git介绍和安装 Git是什么 Git是目前世界上最先进的分布式版本控制系统 xff08 没有之一 xff09 简单来说 它是控制项目版本的一个工具 我们可以利用Git进行多人协作和代码备份等工作 下载git xff08 64bit w

  • Xshell连接虚拟机Ubantu失败解决办法（主机和虚拟机能够互ping的前提）

    主机和虚拟机互ping 在主机命令行里输入ipconfig指令 xff0c 查询主机ip地址 xff0c 在虚拟机Ubantu终端里输入ping 主机ip地址 xff0c ping通后 xff0c 按ctrl 43 c停止 在虚拟机Uban

  • windows 11系统安装

    安装前注意事项 1 准备8G或8G以上U盘 xff08 32G以内 xff09 2 安装系统前备份好个人需要数据 xff08 制作U盘会格式化U盘 xff0c U盘内的重要文件也要事先备份好 xff09 3 预装office的务必记住自己激

  • docker 权限问题 Got permission denied while trying to connect to the Docker daemon socket at

    一 前言 docker安装完成 xff0c 一般用户没有权限启动docker服务 xff0c 只能通过sudo来通过root用户权限来启动docker xff0c 此时对于一般用户而言 xff0c 需要执行docker ps或者docker

  • Neo4j（七）——创建新数据库（如何在Neo4j中创建新数据库）

    方法一 xff1a 找到neo4j安装目录 xff0c 编辑conf文件夹中的neo4j conf 找到dbms active database 61 xff0c 将下图中的graph db用其他名称替换 xff0c 并解除注释 xff08

  • python VScode使用gitlab简单使用流程

    一 下载安装软件 1 安装好vscode xff0c 如未安装 xff0c 下载并且安装 https code visualstudio com Download 2 安装git windows客户端 https git scm com d

  • keil5工程函数无法跳转到函数定义解决方法

    问题描述 在使用keil查看工程代码时 xff0c 进行函数的跳转 xff0c 跳转不成功并提示以下错误 这是因为在编译工程的时候少勾选了一个选项 xff0c 按下以下方式勾选上然后重新Rebuild一下工程就好了

  • Codeforces D. Prefix-Suffix Palindrome

    Codeforces D Prefix Suffix Palindrome 题解 xff1a 和D1相同 xff0c 区别是找中间的回文串要压缩时间 xff0c 用到了马拉车算法 xff08 算法介绍在下面 xff1a span class

  • codeforces 1326 E.Bombs

    codeforces 1326 E Bombs 题意 xff1a 给定 1 n 1 n 1 n 的排列p q xff0c 将

  • Educational Codeforces Round 84 题解

    Educational Codeforces Round 84 题解 A Sum of Odd Integers 题意 xff1a n n n 是否能表示为 k k k 个不同的正奇

  • codeforces 1332 E - Height All the Same(组合数学、奇偶性)

    codeforces 1332 E Height All the Same 组合数学 奇偶性 题意 xff1a 现在有一个 n m n m n m 的方格 xff0c 第 i

  • codeforces 1330 C.D.题解

    codeforces 1330 C D 题解 Dreamoon Likes Coloring 题意 xff1a 给 n lt 61 100000 n lt 61 100000 n lt 61

  • LeetCode数独问题中Bitset的巧妙用处

    LeetCode数独问题中Bitset的巧妙用处 36 有效的数独 判断一个 9x9 的数独是否有效 只需要根据以下规则 xff0c 验证已经填入的数字是否有效即可 数字 1 9 在每一行只能出现一次 数字 1 9 在每一列只能出现一次 数

  • Morris 遍历

    Morris 遍历 中序遍历 前言 我们在中序遍历的时候 一定先遍历左子树 然后遍历当前节点 最后遍历右子树 在常规方法中 我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点 但这需要我们付出额外的空间代价 我们需要用一种巧妙地方法

  • 第九届蓝桥杯c/c++A组省赛题解

    分数 题目 1 1 43 1 2 43 1 4 43 1 8 43 1 16 43 每项是前一项的一半 xff0c 如果一共有20项 求这个和是多少 xff0c 结果用分数表示出来 类似 xff1a 3 2 当然 xff0c 这只是加了前2

  • Ltp介绍及实践（20200925）

    Ltp中源代码和模型包括 xff1a 中文分词 词性标注 未登录词识别 依存句法 语义角色标注几个模块 目录 1 标注集合 分词标注集 词性标注集 命名实体识别标注集 依存句法关系 语义角色类型 2 快速使用 载入模型 分句 用户自定义词典

  • 第十一届蓝桥杯省赛C/C++B组题解

    试题 A 跑步训练 本题总分 xff1a 5 分 题目 问题描述 小明要做一个跑步训练 初始时 xff0c 小明充满体力 xff0c 体力值计为 10000 如果小明跑步 xff0c 每分钟损耗 600 的体力 如果小明休息 xff0c 每

  • codeforces Round680 C. Division 题解

    codeforces Round680 C Division 题解 题目 Oleg s favorite subjects are History and Math and his favorite branch of mathematic

  • Codeforces Round #677 (Div. 3) 题解

    Codeforces Round 677 Div 3 题解 A Boring Apartments 题目 题解 简单签到题 xff0c 直接数 xff0c 小于这个数的 43 10 43 10 43 1 0 代码 span class to

热门标签