Codeforces Round #911 (Div. 2) A~E

A.Cover in Water(思维)

题意:

有一个 1 × n 1 \times n 1×n的水池,里面有些格子可以加水,有些格子是被堵上的,你可以进行以下两种操作:

  • 1.往一个空的格子里加水

  • 2.移除一个有水的格子中的水,并将这些水添加到另一个格子中

且如果两个有水的格子中间都是空格子,那么水将覆盖中间所有的空格子。

问最少进行多少次操作1,才能使所有空格子中均有水。

分析:

不难发现,只要出现一段长度大于2的连续空格子,那么就可以在这段格子两端各使用一次操作1,然后这段格子中间就全部被水覆盖了,且无论怎么使用操作2,由于两端均有水,取完之后格子也不会变空,可以无限取,即一定只需要两次操作1.

如果没有任意一段连续的空格子长度大于2,那么只能对每个格子使用一次操作1,才能使所有格子都包含水,此时的操作1使用次数就是空格子的个数。

代码:

#include <bits/stdc++.h>
using namespace std;


void solve() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            cnt++;
            if (cnt > 2) {
                cout << 2 << endl;
                return;
            }
        } else {
            ans += cnt;
            cnt = 0;
        }
    }
    ans += cnt;//不要忘了加上最后一段
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

B.Laura and Operations(思维)

题意:

给出 a a a 1 1 1 b b b 2 2 2 c c c 3 3 3,每次可以选择 1 ∼ 3 1 \sim 3 13中的两个不同数字,消除这两个数字,并产生一个新的数字,这个产生的数字与消除的两个数字均不同,问有没有方法可以使最后只剩下 1 , 2 , 3 1, 2, 3 1,2,3中的一种(能否剩下 1 , 2 , 3 1, 2, 3 1,2,3的可能性单独输出)

分析:

首先,如果想要剩下的全部都是 1 1 1,那么就需要先将 2 2 2 3 3 3的数量变为相同的,再通过一直消除 2 2 2 3 3 3使得只剩下 1 1 1

那么要怎么让 2 2 2 3 3 3数量相同呢?

可以先消除 1 1 1和出现较多的数,不难发现,如果此时没有 1 1 1,是无法完成消除操作的,此时无解。

而每次消除 1 1 1和出现较多的数字,每次进行消除,可以使较大出现次数和较小出现次数之间的差减少2(不用担心1是否不够用,通过消除 2 2 2 3 3 3可以再获得 1 1 1),那么如果这两个数的出现次数差为奇数,是无法将这两个数完全消除的,此时也是无解。

结论:只要另外两个数的差为偶数,且满足以下两个要求之一,就可以完成消除操作:

  1. 想要留下的数字出现次数不为0

  2. 需要消除的两个数字出现次数已经相同

代码:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if (abs(b - c) % 2 == 0 && (min(c, b) != 0 || a != 0)) {
        cout << 1;
    } else {
        cout << 0;
    }
    if (abs(a - c) % 2 == 0 && (min(a, c) != 0 || b != 0)) {
        cout << ' ' << 1;
    } else {
        cout << ' ' << 0;
    }
    if (abs(a - b) % 2 == 0 && (min(a, b) != 0 || c != 0)) {
        cout << ' ' << 1;
    } else {
        cout << ' ' << 0;
    }
    cout << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

C.Anji’s Binary Tree(树形DP)

题意:

有一棵二叉树,树上每个节点均写着"ULR"中的一个字符,这三个字符的含义如下:

  • 'U':当你走到这个节点,你需要向这个节点的父节点移动

  • 'L':当你走到这个节点,你需要向这个节点的左孩子移动

  • 'R':当你走到这个节点,你需要向这个节点的右孩子移动

问:你最少需要修改多少次节点上的字符,能使你从根节点出法到达叶节点。

分析:

  • 当前节点为'U':想要向叶节点移动,遇到'U'就需要修改,此时不需要考虑节点被修改成了什么。

  • 当前节点为'L':此时往左子树走不需修改次数,往右子树走需一次修改次数,记录两者中的较小值

  • 当前节点为'R':此时往右子树走不需修改次数,往左子树走需一次修改次数,记录两者中的较小值

从根节点开始搜索,到达叶节点返回,记录最小的修改次数即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

int n, L[300005], R[300005];
string s;

int dfs(int x) {
    if (x == 0) return INF;//走到空节点了,返回极大值
    if (L[x] == 0 && R[x] == 0) return 0;//走到叶节点,返回0
    if (s[x - 1] == 'U') {
        return min(dfs(L[x]), dfs(R[x])) + 1;
    } else if (s[x - 1] == 'L') {
        return min(dfs(L[x]), dfs(R[x]) + 1);
    } else {
        return min(dfs(L[x]) + 1, dfs(R[x]));
    }
}

void solve() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) cin >> L[i] >> R[i];
    cout << dfs(1) << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

D.Small GCD(容斥)

题意:

给出一个包含 n n n个元素的数组和一个函数 f ( a , b , c ) = g c d ( a , b ) f(a, b, c) = gcd(a, b) f(a,b,c)=gcd(a,b),其中 a < b < c a < b < c a<b<c

求: ∑ i = 1 n ∑ j = i + 1 n ∑ k = j + 1 n f ( a i , a j , a k ) \sum\limits_{i = 1}^{n}\sum\limits_{j = i + 1}^{n}\sum\limits_{k = j + 1}^{n}f(a_i, a_j, a_k) i=1nj=i+1nk=j+1nf(ai,aj,ak)

分析:

由于每轮取得三个数实际上只有两个较小数字会对答案产生影响,因此可以先对输入的元素进行排序。

然后使用两层for循环对 a i , a j a_i,a_j ai,aj进行枚举,此时的 g c d ( a i , a j ) gcd(a_i, a_j) gcd(ai,aj)的答案对于任意一个 k k k都是成立的,即 a i , a j a_i,a_j ai,aj对答案产生的贡献为 g c d ( a i , a j ) × ( n − j ) gcd(a_i, a_j) \times (n - j) gcd(ai,aj)×(nj)

但是,此时的时间复杂度为 O ( n 2 ) O(n^2) O(n2),是无法通过本题的,因此,需要对算法进行优化

优化

先考虑所有因数对答案的贡献,那么只需一层for循环,遍历到 a j a_j aj时,如果 a j a_j aj的因数 b b b在前面出现过,那么这个因数对答案的贡献就是在前面出现的次数(包含该因数的 a i a_i ai个数)乘上后面的数字个数,即: c n t [ b ] × ( n − i ) cnt[b] \times (n - i) cnt[b]×(ni)

而对于因数分解的时间复杂度是比较慢的,需要先对 1 0 5 10^5 105以内的数预处理所有因子。

求完所有因子产生的贡献后,需要考虑实际上求出的贡献计算了很多重复的情况,如因子为 2 2 2的贡献中包含了所有 2 2 2的倍数的贡献。需要将这些重复计算的贡献减去。

此时可以从后往前对因子进行遍历,每次先将所有由倍数产生的贡献减去,然后计算当前因子产生的贡献,即当前因子的出现次数乘上因子的值。

代码:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;

const int N = 1e5 + 5e2;

int n, a[N];
ll sum[N], cnt[N];

vector<int> fact[N];

void init() {
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
            fact[j].push_back(i);//预处理因子
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        int len = fact[a[i]].size();
        for (int j = 0; j < len; j++) {
            sum[fact[a[i]][j]] += cnt[fact[a[i]][j]] * (n - i);
            cnt[fact[a[i]][j]]++;
        }
    }
    ll ans = 0;
    for (int i = a[n]; i >= 1; i--) {
        for (int j = i + i; j < N; j += i) {
            sum[i] -= sum[j];
        }
        ans += sum[i] * i;
    }
    cout << ans << endl;
}

int main() {
    init();
    int Case;
    cin >> Case;
    while (Case--) {
    //初始化
        memset(sum, 0, sizeof (sum));
        memset(cnt, 0, sizeof (cnt));
        solve();
    }
    return 0;
}

E. Transitive Graph(图论)

题意:

给定一个有向图,点有点权,重复进行如下操作:如果存在边 a − > b a->b a>b b − > c b->c b>c但不存在 a − > c a->c a>c边 ,则添加边 a − > c a->c a>c。直到不存在这样的 ( a , b , c ) (a,b,c) (a,b,c)。做完操作后,询问点权之和最小且经过点数最多的简单路径的长度以及点权之和。

分析:

可以用强连通分离缩点,可以发现每个强连通分量在传递闭包中是一个完全图,因为我们需要的是最长路,所以只要走到这个强连通分量就必须走完分量中的所有点。
我们先用 t a r j a n tarjan tarjan进行缩点,原图中的简单路径就是缩点后的 D A G DAG DAG的路径,在 D A G DAG DAG上跑双关键字的 d p dp dp即可。

代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int ver[maxn], next1[maxn], head[maxn], dfn[maxn], low[maxn];
int stack1[maxn], vis[maxn], c[maxn];
vector<int> scc[maxn]; // 强连通分量
ll tot, top, num, cnt;
ll a[maxn];
vector<int> g[maxn];
ll sum[maxn];
ll dis[maxn];
struct node {
    int sum, num;
} aa[maxn];

void add(int x, int y) {
    ver[++tot] = y;
    next1[tot] = head[x];
    head[x] = tot;
}

int n, m;
ll dp[maxn];

void init() {
    num = 0;
    top = 0;
    for (int i = 0; i <= cnt; i++)
        scc[i].clear();
    cnt = tot = 0;
    for (int i = 1; i <= n; i++) {
        sum[i] = 0;
        dis[i] = 0;
        dp[i] = 0;
        head[i] = 0;
        g[i].clear();
        dfn[i] = low[i] = stack1[i] = vis[i] = c[i] = 0;
    }
}

void tarjan(int x) {
    num++;
    dfn[x] = low[x] = num;
    top++;
    stack1[top] = x;
    vis[x] = 1;
    for (int i = head[x]; i; i = next1[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (vis[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        int tmp;
        do {
            tmp = stack1[top--];
            vis[tmp] = 0;
            c[tmp] = cnt; // 每个点所属于的强连通分量编号
            scc[cnt].push_back(tmp);
            sum[cnt] += a[tmp];
        } while (x != tmp);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            add(x, y);
        }
        for (int i = 1; i <= n; i++) {
            if (!dfn[i])
                tarjan(i);
        }
        // cnt就是强连通块数量
        for (int x = 1; x <= n; ++x) {
            for (int i = head[x]; i; i = next1[i]) {
                int y = ver[i];
                if (c[x] != c[y]) {
                    g[c[x]].push_back(c[y]);
                }
            }
        }
        for (int i = 1; i <= cnt; i++) {
            aa[i].sum = sum[i];
            aa[i].num = scc[i].size();
        }
        for (int i = 1; i <= cnt; i++) {
            // 遍历出边

            if (g[i].empty()) {
                dis[i] = scc[i].size();
                dp[i] = sum[i];
            } else
                for (auto u: g[i]) {
                    if (dis[u] + scc[i].size() > dis[i]) {
                        dis[i] = dis[u] + scc[i].size();
                        dp[i] = dp[u] + sum[i];
                    } else if (dis[u] + scc[i].size() == dis[i]) {
                        dp[i] = min(dp[i], dp[u] + sum[i]);
                    }
                }
        }
        ll mlen = 0;
        for (int i = 1; i <= cnt; i++)
            mlen = max(mlen, dis[i]);
        ll ans = 1e18;
        for (int i = 1; i <= cnt; i++)
            if (dis[i] == mlen)
                ans = min(ans, dp[i]);
        cout << mlen << " " << ans << endl;
    }
    return 0;
}

学习交流

以下学习交流QQ群,群号: 546235402,大家可以加群一起交流做题思路,分享做题技巧,欢迎大家的加入。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/208252.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

论文阅读_AI生成检测_Ghostbuster

英文名称: Ghostbuster: Detecting Text Ghostwritten by Large Language Models 中文名称: 捉鬼人&#xff1a;检测大语言模型生成的文本 文章: http://arxiv.org/abs/2305.15047 代码: https://github.com/vivek3141/ghostbuster 作者: Vivek Verma&#xff0c;Eve Fleisig&a…

人工智能基础创新的第二增长曲线

编者按&#xff1a;2023年是微软亚洲研究院建院25周年。借此机会&#xff0c;我们特别策划了“智启未来”系列文章&#xff0c;邀请到微软亚洲研究院不同研究领域的领军人物&#xff0c;以署名文章的形式分享他们对人工智能、计算机及其交叉学科领域的观点洞察及前沿展望。希望…

docker-compose脚本编写及常用命令

安装 linux DOCKER_CONFIG/usr/local/lib/docker/cli-plugins sudo mkdir -p $DOCKER_CONFIG/cli-plugins sudo curl -SL https://521github.com/docker/compose/releases/download/v2.6.1/docker-compose-linux-x86_64 -o $DOCKER_CONFIG/cli-plugins/docker-compose sudo c…

VSCode下载安装教程+安装插件

一、vscode下载安装 1.打开 官网&#xff1a;https://code.visualstudio.com/Download 2.选择跟你电脑相对应的版本下载&#xff0c;我是win10&#xff0c;所以选择如下&#xff1a; 3.下载到你想要保存的目录下 4.下载完成后打开目录&#xff0c;双击安装包 5. 同意&#xff…

Linux 磁盘分区处理

最近实施过程中遇到客户提供给我们的服务器操作系统和Docke容器环境都已经安装完成&#xff0c;但磁盘的分区没有进行整理好。磁盘总共270G&#xff0c;系统安装分配了60G&#xff0c;剩余未创建分配需要处理。由于分区情况每家不一样&#xff0c;但大致流程都是相同的&#xf…

React项目使用NProgress作为加载进度条

React项目使用NProgress作为加载进度条 0、效果1、react安装依赖2、使用3.进度条颜色设置 文档参考&#xff1a;https://zhuanlan.zhihu.com/p/616245086?utm_id0 0、效果 如下&#xff0c;可全局在页面顶部有一条进度条 1、react安装依赖 yarn add nprogress通过以上安装…

uni-app+ts----微信小程序锚点定位 、自动吸顶、滚动自动选择对应的锚点(点击tab跳转对应的元素位置)

uni-app----微信小程序锚点定位 、自动吸顶、滚动自动选择对应的锚点&#xff08;点击tab跳转对应的元素位置&#xff09; html代码部分 重点是给元素加入【 :id“‘item’ item.id”】 <view class"radiusz bg-white pt-[30rpx] z-[999]"><u-tabs:list&q…

matlab 无迹卡尔曼滤波

1、内容简介 略 26-可以交流、咨询、答疑 2、内容说明 无迹卡尔曼滤波 无迹卡尔曼滤波 无迹卡尔曼滤波 3、仿真分析 %该文件用于编写无迹卡尔曼滤波算法及其测试 %注解&#xff1a;主要子程序包括&#xff1a;轨迹发生器、系统方程 % 测量方程、UKF滤波器 %----…

YOLOv8优化策略:SENetV2,squeeze和excitation全面升级,效果优于SENet | 2023年11月最新成果

🚀🚀🚀本文改进: SENetV2,squeeze和excitation全面升级,作为注意力机制引入到YOLOv8,放入不同网络位置实现涨点 🚀🚀🚀YOLOv8改进专栏:http://t.csdnimg.cn/hGhVK 学姐带你学习YOLOv8,从入门到创新,轻轻松松搞定科研; 1.SENetV2 论文:https://arxiv.org/…

2023开发者必备iOS开发工具

​ 工欲善其事&#xff0c;必先利其器。进行开发工作时&#xff0c;利用并熟练使用恰当的工具可以让工作效率得到大幅度提高。下边会介绍一些在进行iOS开发工作时常用的一些工具&#xff0c;本文并不对其进行展开&#xff0c;对使用方法及工作原理感兴趣的同学可以自行进行更深…

6.9 Windows驱动开发:内核枚举进线程ObCall回调

在笔者上一篇文章《内核枚举Registry注册表回调》中我们通过特征码定位实现了对注册表回调的枚举&#xff0c;本篇文章LyShark将教大家如何枚举系统中的ProcessObCall进程回调以及ThreadObCall线程回调&#xff0c;之所以放在一起来讲解是因为这两中回调在枚举是都需要使用通用…

理解位运算的规则

关卡名 理解位运算的规则 我会了✔️ 内容 1.理解位运算的基本规则 ✔️ 2.理解移位的原理以及与乘除的关系 ✔️ 3.掌握位运算的常用技巧 ✔️ 在学习位操作之前&#xff0c;我们先明确数据在计算机中怎么表示的。我们明确原码、反码和补码的概念和表示方法&#xff0c;之…

2023年营养保健品市场销售数据分析(京东数据运营-京东数据产品):10月销额同比增长67%

如今&#xff0c;随着健康经济、颜值经济的兴起&#xff0c;越来越多的年轻人加入养生大军&#xff0c;成为营养保健品市场上的一股新力量&#xff0c;带动市场扩容。在养生年轻化、人口老龄化等多重因素的驱动下&#xff0c;营养保健品市场增长强劲。 根据鲸参谋电商数据分析平…

RocketMQ(四):重复消费、消息重试、死信消息的解决方案

RocketMQ系列文章 RocketMQ(一)&#xff1a;基本概念和环境搭建 RocketMQ(二)&#xff1a;原生API快速入门 RocketMQ(三)&#xff1a;集成SpringBoot RocketMQ(四)&#xff1a;重复消费、消息重试、死信消息的解决方案 目录 一、重复消费1、消息重复的情况2、MySql唯一索引…

Hexo | 支持书写数学公式

为了能够让 Hexo 支持书写数学公式&#xff0c;遇到了好多个坑。虽然以下方法我亲测有效&#xff0c;但并不能保证每个人都能成功。最差的情况就是 hexo s 启动失败&#xff0c;不过还可以重新 hexo init 哈哈笑不出来。 提醒&#xff1a;本文主要针对 fluid 主题&#xff0c;…

视频合并方法:掌握视频批量嵌套合并技巧,成为剪辑高手

在视频剪辑的过程中&#xff0c;我们经常需要将多个视频片段合并在一起。传统的视频合并方法往往需要大量的时间和精力&#xff0c;通过掌握批量嵌套合并技巧&#xff0c;可以更高效地完成这项任务&#xff0c;成为剪辑高手。本文讲解一种简单易学的视频合并方法&#xff0c;轻…

【爬虫】Java 爬虫组件 Jsoup

【爬虫】Java 爬虫组件 Jsoup 写在前面实现思路和步骤步骤一&#xff1a;引入 Jsoup步骤二&#xff1a;获取页面组件内容步骤三&#xff1a;分析页面构成获取需要的组件 代码案例 写在前面 爬虫是通过编程的方式&#xff0c;从网站上获取数据的一种方式。很多语言都提供的有爬…

机器学习---EM算法

1. 极大似然估计与EM算法 极大似然估计是一种常用的参数估计方法&#xff0c;它是以观测值出现的概率最大作为准则。关于极 大似然估计&#xff0c;假设现在已经取到样本值了&#xff0c;这表明取到这一样本的概率L(θ) 比较 大。我们自然不会考虑那些不能使样本出现的θ作为…

高校智慧用电管理平台

高校智慧用电管理平台是一种基于物联网、云计算、大数据等技术的智能化用电管理系统&#xff0c;旨在实现高校用电的实时监测、智能控制、数据分析和管理决策。 具体来说&#xff0c;该平台通常包括以下功能和特点&#xff1a; 实时监测&#xff1a;通过安装传感器、智能终端等…