Codeforces practice C++ 2024/9/11 - 2024/9/18

D. Mathematical Problem

Codeforces Round 954 (Div. 3)

原题链接：https://codeforces.com/contest/1986/problem/D

题目标签分类：brute force，dp，greedy，implementation，math，two pointers

题目难度：1400

题目大意：

给你一个长度为 n 的字符串，只由 0 到 9 这些字符组成，你需要往这个字符串中插入 n - 2 个 运算符，规定插入的运算符只有 * 和 + 两种。 

输入：

输出：

题目做法：

AC代码 ：

#include<bits/stdc++.h>
//#define int long long
//#define int __int128
#define loop(i, n) for(int i = 0; i < n; i++)
#define repeat(i, start, end, step) for(int i = start; i < end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using bigint = __int128;

const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;

int n, inips = 0, news[20];
string s, str[20];
int tonum(string t) {
    int res = 0;
    for(int i = 0; i < t.length(); i++) {
        res *= 10;
        res += t[i] - '0';
    }
    return res;
}
int construct(int x = -1, int y = -1) {
    inips = 0;
    for(int i = 0; i < n; i++) str[i] = s[i];
    for(int i = 0; i < n; i++) {
        if(i == x || i == y) {
            str[i + 1] = str[i] + s[i + 1];
            str[i] = "-";
        }
    }
    for(int i = 0; i < n; i++) if(str[i] != "-") news[inips++] = tonum(str[i]);
    int dp[20][2];
    dp[0][0] = dp[0][1] = news[0];
    for(int i = 1; i < inips; i++) {
        dp[i][0] = min(dp[i - 1][1] + news[i], dp[i - 1][0] + news[i]);
        dp[i][1] = min({dp[i][0], dp[i - 1][1] * news[i], dp[i - 1][0] * news[i]});
    }
    return dp[inips - 1][1];
}
void solve() {
    cin >> n >> s;
    int res = 1e9 + 10;
    if(n == 2) {
        cout << construct(0) << '\n';
        return ;
    }
    for(int i = 0; i < n - 1; i++) res = min(res, construct(i));
    cout << res << '\n';
}

signed main() {
    FastIO
    int TestCase = 1;
    cin >> TestCase;
    while(TestCase--) solve();
}

事后ps：Dp比较好像也很好写，就两种状态，预处理也不是很难。

D. Maximize the Root 

Educational Codeforces Round 168 (Rated for Div. 2)

原题链接：https://codeforces.com/problemset/problem/1997/D

题目标签分类：binary search，dfs and similar，dp，greedy，trees

题目难度：1500

题目大意：

​

给一颗树，规定编号为1的节点为根节点，每个节点上初始会有一个值，你每次可以进行操作，这个操作是选定一个非叶子节点的节点，给此节点上的值加一，此节点除了该节点外的子树种的节点上的值均减去1。规定每次操作后树上所有节点的值非负。

输入：

共 t 组输入数据。

每组数据有三行，第一行输入一个变量 n，代表这棵树有 n 个节点，第二行有 n 个变量 ai 分别代表初始的时候每个节点上的值，第三行有 n - 1 个变量代表树上每个节点的父节点，n - 1 是因为从下标从2开始，1号节点默认为根节点。

输出：

进行不限次数的合法调整过后根节点上的最大值。

题目做法：

如果根节点上的值确定了，那么这棵树的所有节点上的最小数值也就决定了。

因为结果显然是呈线性变化的，所以可以对答案进行二分，满足则往更大里搜索答案，反之往更小搜索，check 函数的写法应该是 dfs 一整颗树来检测当前二分的答案是否满足。dfs的时间复杂度是 n，二分的复杂度是 log\left ( n \right )，所以总复杂度是 O\left ( nlogn \right ) 。

AC代码 ：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using bigint = __int128;

const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;

int a[maxn] ,tval;
vector<int> tr[maxn];
bool check(int now, int val) {
    bool judge = 1;
    if(val < 0 || val >= 1e18 + 10) return 0;
    if(tr[now].size() == 0) return (max((ll)0, val - a[now]) <= 0);
    for(auto it:tr[now]) {
        judge &= check(it,val * (now != 1) + max((ll)0, val - a[now]));
    }
    return judge;
}

void solve() {
    int n, l = 0, r = 1e18 + 10, ans = 0 ,t;
    cin >> n;
    loop(i, n) cin >> a[i + 1], tr[i + 1].clear();
    rep(i, 2, n, 1) cin >> t, tr[t].pb(i);
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(1, mid)) {
            ans = max(ans, mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
}

signed main() {
    FastIO int TestCase = 1;
    cin >> TestCase;
    while(TestCase--) solve();
}

事后ps：分析整体情况后还是比较容易想到二分答案的，dfs的时候有细节需要注意可能会爆long long，我二分写得挺烂的，还是按板子来比较稳妥。

A. Distanced Coloring

​​​​​​EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

原题链接：https://codeforces.com/problemset/problem/2002/A

题目标签分类：constructive algorithms，implementation，math

题目难度：800

题目大意：

​

给出 n * m 的网格和一个 k ，满足如下条件的两个点为同一颜色，求填满网格的最小颜色数目。

条件：

题目做法：

在一行上最多就用k个颜色就能填满，如果k小于n的话，k大于n的话就用n个。在同一列上同理。这样最小，还是比较好像的，因为等于k的时候间距最小。

AC代码 ：

#include<bits/stdc++.h>
//#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using bigint = __int128;

const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    cout << min(n, k) * min(m, k) << '\n';
}

signed main() {
    FastIO int TestCase = 1;
    cin >> TestCase;
    while(TestCase--) solve();
}

B. Removals Game

​​​​​​EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

原题链接：https://codeforces.com/problemset/problem/2002/B

题目标签分类：constructive algorithms，games

题目难度：1000

题目大意：

Alice 和 Bob 一开始会分别拿到两个全排列数组，

输入：

输出：

题目做法：

AC代码 ：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using bigint = __int128;

const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    int a[n],b[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    bool is = 1, is2 = 1;
    rep(i, 0, n - 1, 1) is &= (a[i] == b[i]), is2 &= (a[n - 1 - i] == b[i]);
    if(is || is2) {
        cout << "Bob" << '\n';
        return ;
    }
    cout << "Alice" << '\n';
}

signed main() {
    FastIO int TestCase = 1;
    cin >> TestCase;
    while(TestCase--) solve();
}

事后ps：

A. Legs

Codeforces Round 962 (Div. 3)

原题链接：https://codeforces.com/contest/1996/problem/A

题目标签分类：binary search，math，ternary search

题目难度：800

题目大意：

输入：

输出：

题目做法：

AC代码 ：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

using namespace std;
using ll = long long;
using bigint = __int128;

const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    cout << n / 4 + (n % 4 != 0) << '\n';
}

signed main() {
    FastIO int TestCase = 1;
    cin >> TestCase;
    while(TestCase--) solve();
}

D. Paint the Tree

Codeforces Round 947 (Div. 1 + Div. 2)

原题链接：https://codeforces.com/problemset/problem/1975/D

题目标签分类：constructive algorithms，games

题目难度：1700

题目大意：

输入：

输出：

题目做法：

AC代码 ：

1

事后ps：

B. osu!mania

Codeforces Round 971 (Div. 4)

原题链接：https://codeforces.com/problemset/problem/2009/Bicon-default.png?t=O83Ahttps://codeforces.com/problemset/problem/2009/B

题目标签分类：constructive algorithms，games

题目难度：1700

题目大意：

输入：

输出：

题目做法：

AC代码 ：

1

事后ps：

E. Coloring Game

Pinely Round 4 (Div. 1 + Div. 2)icon-default.png?t=O83Ahttps://codeforces.com/contest/1991

原题链接：https://codeforces.com/problemset/problem/1991/Eicon-default.png?t=O83Ahttps://codeforces.com/problemset/problem/1991/E

题目标签分类：constructive algorithms，games

题目难度：1700

题目大意：

交互题，给一个 n 个节点，m 条边的无向图，每个节点可以被染成1，2，3，这三种颜色。最开始所有的点没有被染过色。

输入：

t 组测试数据，每组测试数据的第一行输入两个变量  n 和 m 分别代表 n 个顶点 m 条边。紧接着的m 每行两个变量 ui 和 vi 代表 ui 和 vi 间有一条边。

输出：

题目做法：

AC代码 ：

1

事后ps：

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

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

相关文章

svn回退到以前历史版本修改并上传

svn回退到以前历史版本修改并上传

svn回退到以前版本&#xff0c;并在以前版本上修改代码后&#xff0c;上传到svn库当中&#xff0c;如下步骤&#xff1a; 3、 以回退到版本号4为例&#xff1a;选中版本号4&#xff0c;右键->Revert to this version,在出现的对话框中 点击yes&#xff01; 4、 5、
阅读更多...
【C++ Primer Plus习题】16.8

【C++ Primer Plus习题】16.8

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream> #include <set> #includ…
阅读更多...
矩阵分析 学习笔记3 多项式矩阵 jordan标准型

矩阵分析 学习笔记3 多项式矩阵 jordan标准型

多项式矩阵 就是说这个矩阵里面的各个元素都是多项式&#xff0c;多项式的主角是类目大&#xff08;自变量&#xff09;。 多项式矩阵的秩 0多项式就是完全0的那种&#xff0c;就一个0&#xff0c;类目大都没有了。 多项式矩阵的秩和带一个类目大进去变成普通矩阵的秩不是一回…
阅读更多...
深度学习｜损失函数：网络参数优化基准

深度学习｜损失函数：网络参数优化基准

文章目录 引言均方误差计算示例矩阵形式代码实现 交叉熵误差计算示例代码实现 绝对误差计算示例代码实现 Hinge Loss计算示例代码实现 Kullback-Leibler Divergence计算示例代码实现 结语 引言 在上文「深度学习&#xff5c;模型训练&#xff1a;手写 SimpleNet」中&#xff0…
阅读更多...
十款主流的供应链管理系统盘点，优缺点一目了然！

十款主流的供应链管理系统盘点，优缺点一目了然！

本文将盘点十款供应链管理系统&#xff0c;为企业选型提供参考&#xff01; 想象一下&#xff0c;一家企业在生产和销售产品的过程中&#xff0c;原材料供应不及时、库存积压严重、物流配送混乱。这时&#xff0c;供应链管理系统就如同一位高效的指挥家&#xff0c;将各个环节紧…
阅读更多...
离散制造 vs 流程制造：锚定精准制造未来，从装配线到化学反应，实时数据集成在制造业案例中的多维应用

离散制造 vs 流程制造：锚定精准制造未来，从装配线到化学反应，实时数据集成在制造业案例中的多维应用

使用 TapData&#xff0c;化繁为简&#xff0c;摆脱手动搭建、维护数据管道的诸多烦扰&#xff0c;轻量替代 OGG, Kettle 等同步工具&#xff0c;以及基于 Kafka 的 ETL 解决方案&#xff0c;「CDC 流处理 数据集成」组合拳&#xff0c;加速仓内数据流转&#xff0c;帮助企业…
阅读更多...
Linux权限理解【Shell的理解】【linux权限的概念、管理、切换】【粘滞位理解】

Linux权限理解【Shell的理解】【linux权限的概念、管理、切换】【粘滞位理解】

目录 Linux权限理解1.Xshell命令以及运行原理2.linux权限的学习2.1linux权限的切换2.2linux权限的概念2.3linux权限管理2.3.1linux中文件访问者的分类2.3.2文件类型和访问权限(文件属性)2.3.2.1文件类型2.3.2.2文件权限拓展—文件的起始权限 2.3.3文件权限管理2.3.4文件权限的应…
阅读更多...
腾讯云Ubuntu系统安装宝塔，配置Java环境，运行spring boot项目

腾讯云Ubuntu系统安装宝塔，配置Java环境，运行spring boot项目

致谢 本次学习宝塔部署spring boot项目&#xff0c;参考如下资料 https://www.cnblogs.com/daen/p/15997872.html 系统安装宝塔 直接用的腾讯云云服务器面板上的登录&#xff0c;你可以换成 xshell 进入宝塔官网&#xff1a; https://www.bt.cn/new/download.html 我们采…
阅读更多...
跟《经济学人》学英文：2024年09月14日这期 Volunteering has big benefits for the elderly

跟《经济学人》学英文：2024年09月14日这期 Volunteering has big benefits for the elderly

Volunteering has big benefits for the elderly But those Britons who would most benefit are least likely to do it 原文&#xff1a; THE CROSSNESS Pumping Station is not what you’d expect of a sewage works. With its spiral staircases, colourful tiling and…
阅读更多...
Sapiens——人类视觉大模型的基础

Sapiens——人类视觉大模型的基础

引言 大规模预训练以及随后针对特定任务的语言建模微调取得了显著成功&#xff0c;已将这种方法确立为标准做法。同样&#xff0c; 计算机视觉方法正逐步采用大规模数据进行预训练。LAION5B、Instagram-3.5B、JFT-300M、LVD142M、Visual Genome 和 YFCC100M 等大型数据集的出现…
阅读更多...
计算机毕业设计 健身房管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 健身房管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
Linux--守护进程与会话

Linux--守护进程与会话

进程组 概念 进程组就是一个或多个进程的集合。 一个进程组可以包含多个进程。 下面我们通过一句简单的命令行来展示&#xff1a; 为什么会有进程组&#xff1f; 批量操作&#xff1a;进程组允许将多个进程组织在一起&#xff0c;形成一个逻辑上的整体。当需要对多个进程…
阅读更多...
Matlab如何配置小波工具（Wavelet Toolbox）

Matlab如何配置小波工具（Wavelet Toolbox）

1、发现问题 因为实验要使用小波工具函数&#xff0c;运行时报错如下&#xff1a; 查看对应文件夹发现没有小波工具&#xff08;也可在控制台输入ver&#xff09;&#xff0c;检查是否有该工具&#xff0c;输入后回车返回如下&#xff1a; 2、下载工具包 没有这个工具就要去下…
阅读更多...
【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例

【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例

【浅水模型MATLAB】尝试复刻SCI论文中的溃坝流算例 前言问题描述控制方程及数值方法浅水方程及其数值计算方法边界条件的实现 代码框架与关键代码模拟结果 更新于2024年9月17日 前言 这篇博客算是学习浅水方程&#xff0c;并利用MATLAB复刻Liang (2004)1中溃坝流算例的一个记录…
阅读更多...
Gitee丝滑版本：成功在新电脑添加新文件

Gitee丝滑版本：成功在新电脑添加新文件

git 关键步骤 1.首先在新电脑建一个文件夹&#xff0c;然后打开这个文件夹里面右键打开OPEN BASH GIT HERE。 2.然后输入git init&#xff0c;会在文件夹生成一个git.文件&#xff0c;接着把复制的get clone命令克隆过去就可以下载了&#xff0c;如果遇到403问题&#xff0c…
阅读更多...
循环神经网络RNN+长短期记忆网络LSTM 学习记录

循环神经网络RNN+长短期记忆网络LSTM 学习记录

循环神经网络&#xff08;RNN) RNN的的基础单元是一个循环单元&#xff0c;前部序列的信息经处理后&#xff0c;作为输入信息传递到后部序列 x为输入向量&#xff0c;y为输出向量&#xff0c;a为上一隐藏层的a与x通过激活函数得到的值&#xff0c;简言之&#xff0c;每一层神…
阅读更多...
从头开始学MyBatis—02基于xml和注解分别实现的增删改查

从头开始学MyBatis—02基于xml和注解分别实现的增删改查

首先介绍此次使用的数据库结构&#xff0c;然后引出注意事项。 通过基于xml和基于注解的方式分别实现了增删改查&#xff0c;还有获取参数值、返回值的不同类型对比&#xff0c;帮助大家一次性掌握两种代码编写能力。 目录 数据库 数据库表 实体类 对应的实体类如下&#x…
阅读更多...
Java项目: 基于SpringBoot+mybatis+maven洗衣店订单管理系统(含源码+数据库+开题报告+任务书+毕业论文)

Java项目: 基于SpringBoot+mybatis+maven洗衣店订单管理系统(含源码+数据库+开题报告+任务书+毕业论文)

一、项目简介 本项目是一套基于SpringBootmybatismaven洗衣店订单管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作…
阅读更多...
List＜Map＜String, Object＞＞汇总统计排序

List＜Map＜String, Object＞＞汇总统计排序

开发环境&#xff1a;jdk 1.8 需求一&#xff1a; 1、统计每个小时(升序)不同事件的产品产量 2、统计不同事件&#xff08;OK 、NG&#xff09;的总产量 public static void main(String[] args) {//数据源List<Map<String, Object>> list new ArrayList<Map…
阅读更多...
根据 IP 地址进行 VPN 分流（详细，亲测，通用）

根据 IP 地址进行 VPN 分流（详细，亲测，通用）

根据 IP 地址进行 VPN 分流&#xff08;详细&#xff0c;亲测&#xff0c;通用&#xff09; 背景 不在学校的时候需要使用实验室的服务器&#xff0c;但是实验室的服务器只能在校园网内访问&#xff0c;因此在校外就需要使用学校的 VPN&#xff0c;但是打开 VPN 以后会默认将…
阅读更多...
最新文章

Copyright @ 2022~2023