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

Codeforces Round 951 (Div. 2) C、D(构造、线段树)

1979C - Earning on Bets 

        

构造题:观察到k范围很小,首先考虑最终硬币总数可以是多少,我们可以先假设最终的硬币总数为所有k取值的最小公倍数,这样只需要满足每个结果添加1枚硬币即可赚到硬币。

        

// Problem: C. Earning on Bets
// Contest: Codeforces - Codeforces Round 951 (Div. 2)
// URL: https://codeforces.com/contest/1979/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve() 
{int n;cin >> n;LL ans = 1;for(int i = 2 ; i <= 20 ; i ++){ans = lcm(ans , i);}int tot = 0;for(int i = 0 ; i < n ; i ++){cin >> a[i];tot += ans / a[i];}int res = ans - tot;if(res < n){cout << -1 << endl;}else{for(int i = 0 ; i < n - 1; i ++){cout << ans / a[i] + 1 << " ";res--;}cout << ans / a[n - 1] + res << endl;}
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

1979D - Fixing a Binary String  

        题意:

翻译有误,请看英文题面

        思路:典型的一个区间合并求数量问题,我们可以直接构造两颗线段树解决。

// Problem: D. Fixing a Binary String
// Contest: Codeforces - Codeforces Round 951 (Div. 2)
// URL: https://codeforces.com/contest/1979/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = info[p] + v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F pred) {return findLast(1, 0, n, l, r, pred);}
};struct Info {int left0 = 0, left1 = 0;int right0 = 0, right1 = 0;int cnt = 0;int act = 0;
};Info operator + (Info a, Info b) {if(a.act == 0){return b;}if(b.act == 0){return a;}Info c;c.left0 = a.left0;c.left1 = a.left1;c.right0 = b.right0;c.right1 = b.right1;c.act = a.act + b.act;c.cnt = a.cnt + b.cnt;if(a.right0 > 0 && b.left0 > 0){int tmp = a.right0 + b.left0;if(tmp > m){c.cnt = -1;}if(tmp == m){c.cnt++;}if(a.right0 == a.act){c.left0 = a.act + b.left0;}if(b.left0 == b.act){c.right0 = a.right0 + b.act;}if(a.right0 != a.act && b.left0 != b.act && tmp != m){c.cnt = -1;}}else if(a.right1 > 0 && b.left1 > 0){int tmp = a.right1 + b.left1;if(tmp > m){c.cnt = -1;}if(tmp == m){c.cnt++;}if(a.right1 == a.act){c.left1 = a.act + b.left1;}if(b.left1 == b.act){c.right1 = b.act + a.right1; }if(a.right1 != a.act && b.left1 != b.act && tmp != m){c.cnt = -1;}}else if(a.right0 > 0 && b.left1 > 0){int tmp1 = a.right0;int tmp2 = b.left1;if(b.left1 == b.act){c.right1 = b.act;}else if(b.left1 != m){c.cnt = -1;}if(a.right0 == a.act){c.left0 = a.act;}else if(a.right0 != m){c.cnt = -1;}}else if(a.right1 > 0 && b.left0 > 0){int tmp1 = a.right1;int tmp2 = b.left0;if(b.left0 == b.act){c.right0 = b.act;}else if(b.left0 != m){c.cnt = -1;}if(a.right1 == a.act){c.left1 = a.act;}else if(a.right1 != m){c.cnt = -1;}	}return c;
}void solve() 
{cin >> n >> m;string s;cin >> s;vector<Info>v;for(int i = 0 ; i < n ; i ++){Info tmp;if(s[i] == '1'){tmp.cnt = 0;tmp.act = 1;tmp.left1 = 1;tmp.right1 = 1;tmp.left0 = 0;tmp.right0 = 0;if(m == 1){tmp.cnt = 1;}}else{tmp.cnt = 0;tmp.act = 1;tmp.left1 = 0;tmp.right1 = 0;tmp.left0 = 1;tmp.right0 = 1;	if(m == 1){tmp.cnt = 1;}		}v.pb(tmp);}vector<Info>vv;for(int i = n - 1 ; i >= 0 ; i --){Info tmp;if(s[i] == '1'){tmp.cnt = 0;tmp.act = 1;tmp.left1 = 1;tmp.right1 = 1;tmp.left0 = 0;tmp.right0 = 0;if(m == 1){tmp.cnt = 1;}				}else{tmp.cnt = 0;tmp.act = 1;tmp.left1 = 0;tmp.right1 = 0;tmp.left0 = 1;tmp.right0 = 1;	if(m == 1){tmp.cnt = 1;}				}vv.pb(tmp);		}SegmentTree	<Info> seg(v);SegmentTree<Info>seg2(vv);for(int i = 1 ; i <= n ; i ++){Info tmp1 = seg.rangeQuery(i , n);Info tmp2 = seg2.rangeQuery(n - i , n);Info tmp3 = tmp1 + tmp2;if(tmp3.cnt == n / m){cout << i << endl;return;}}cout << -1 << endl;
}            
int main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}

相关文章:

Codeforces Round 951 (Div. 2) C、D(构造、线段树)

1979C - Earning on Bets 构造题&#xff1a;观察到k范围很小&#xff0c;首先考虑最终硬币总数可以是多少&#xff0c;我们可以先假设最终的硬币总数为所有k取值的最小公倍数&#xff0c;这样只需要满足每个结果添加1枚硬币即可赚到硬币。 // Problem: C. Earning on Bets //…...

elmentUI el-table 总结行

背景 原因&#xff1a;表格展示的都是明细数据&#xff0c;需要对当前的明细数据的部分字段进行汇总难点&#xff1a;汇总的条件不一定&#xff0c;有时候客户查的是1天&#xff0c;有时候是10天 官方写法 只开启开关 开启汇总开关如果没有汇总方法&#xff0c; 会自动汇总所有…...

【大数据】计算引擎:Spark核心概念

目录 前言 1.什么是Spark 2.核心概念 2.1.Spark如何拉高计算性能 2.2.RDD 2.3.Stage 3.运行流程 前言 本文是作者大数据系列中的一文&#xff0c;专栏地址&#xff1a; https://blog.csdn.net/joker_zjn/category_12631789.html?spm1001.2014.3001.5482 该系列会成体…...

Python | C# | MATLAB 库卡机器人微分运动学 | 欧拉-拉格朗日动力学 | 混合动力控制

&#x1f3af;要点 &#x1f3af;正向运动学几何矩阵&#xff0c;Python虚拟机器人模拟动画二连杆平面机械臂 | &#x1f3af; 逆向运动学几何矩阵&#xff0c;Python虚拟机器人模拟动画三连杆平面机械臂 | &#x1f3af;微分运动学数学形态&#xff0c;Python模拟近似结果 | …...

Signac|成年小鼠大脑 单细胞ATAC分析(1)

引言 在本教程中&#xff0c;我们将探讨由10x Genomics公司提供的成年小鼠大脑细胞的单细胞ATAC-seq数据集。本教程中使用的所有相关文件均可在10x Genomics官方网站上获取。 本教程复现了之前在人类外周血单核细胞&#xff08;PBMC&#xff09;的Signac入门教程中执行的命令。…...

【POSIX】运行时so库动态加载

运行时可以自己自定义so库的动态加载框架&#xff0c;主动去加载某些库&#xff0c;并调用其中的某些方法 首先写一些方法&#xff0c;并生成so库 // hello.cpp#include <iostream>/*使用 nm 命令查看 so 库的内容 */// 1. 使用extern // dlsym(handle, "hello&qu…...

爱普生SG2520CAA汽车电子中控专用晶振

随着汽车电子技术的飞速发展&#xff0c;汽车中控系统变得越来越智能化和复杂化。为了确保这些系统的高性能和高可靠性&#xff0c;选择符合AEC-Q200标准的高品质晶振至关重要。爱普生SG2520CAA晶振凭借其优异的特性&#xff0c;成为汽车电子中控系统的理想选择。 爱普生晶振SG…...

Vue——监听器简单使用与注意事项

文章目录 前言编写简单demo注意事项 前言 监听器&#xff0c;在官网中称为侦听器&#xff0c;个人还是喜欢称之为监听器。官方文档如下&#xff1a; vue 官网 侦听器 编写简单demo 侦听器在项目中通常用于监听某个属性变量值的变化&#xff0c;并根据该变化做出一些处理操作。…...

OpenCV的“画笔”功能

类似于画图软件的自由笔刷功能&#xff0c;当按住鼠标左键&#xff0c;在屏幕上画出连续的线条。 定义函数&#xff1a; import cv2 import numpy as np# 初始化参数 drawing False # 鼠标左键按下时为True ix, iy -1, -1 # 鼠标初始位置# 鼠标回调函数 def mouse_paint(…...

uniapp封装picker选择器组件,支持关键字查询

CommonPicker.vue组件 路径在 components\CommonPicker.vue <template><view><uni-easyinput v-model"searchQuery" :placeholder"placeholder" /><picker :range"filteredOptions" :range-key"text" v-model&…...

智慧城市的规划与实施:科技引领城市运行效率新飞跃

随着信息技术的飞速发展&#xff0c;智慧城市的构想正逐步成为现实。作为地理信息与遥感领域的研究者&#xff0c;我深知在这一转型过程中&#xff0c;技术的创新与应用是提升城市运行效率的关键。本文旨在探讨如何利用地理信息系统&#xff08;GIS&#xff09;、遥感技术、大数…...

Linux——内存管理代码分析

虚空间管理 页框和页的关系 页框 将内存空间分为一个个大小相等的分区(比如:每个分区4KB),每个分区就是一个页框&#xff0c;也叫页帧&#xff0c;即物理页面&#xff0c;是linux划分内存空间的结果。 每个页框都有一个页框号&#xff0c;即内存块号、物理块号。 页 将用户…...

手机自动化测试:4.通过appium inspector 获取相关app的信息,以某团为例,点击,搜索,获取数据等。

0.使用inspector时&#xff0c;一定要把不相关的如weditor啥的退出去&#xff0c;否则&#xff0c;净是事。 1.从0开始的数据获取 第一个位置&#xff0c;有时0.0.0.0&#xff0c;不可以的话&#xff0c;你就用这个。 第二个位置&#xff0c;抄上。 直接点击第三个启动。不要…...

个人项目———密码锁的实现

布局组件 布局效果 组件绑定 密码锁的实现代码 using TMPro; using UnityEngine; using UnityEngine.UI;public class PasswordPanel : MonoBehaviour {// public Button button;// 所有按键的父物体public Transform buttonPanel;// 输入字符串的文本框public TMP_Text input…...

关于Input【type=number】可以输入e问题及解决方案

一、为什么 因为在数学里e 代表无理数&#xff0c;e是自然对数的底数&#xff0c;同时它又是一个无限不循环小数&#xff0c;所以我们在输入 e 时&#xff0c;输入框会默认 e 是数字&#xff0c;从而没有对它进行限制。 二、解决方案 小提示&#xff1a;vue下监听事件需要加n…...

zabbix“专家坐诊”第241期问答

问题一 Q&#xff1a;华为交换机的100GE 1/0/1口的光模块收光值监测不到&#xff0c;有没有人碰到过这个问题呢&#xff1f;其他的端口都能监测到收光值&#xff0c;但是100GE 1/0/1口监测不到收光值。底层能查到&#xff0c;zabbix 6.0监控不到&#xff0c;以下是端口的报错信…...

了解Kubernetes-RKE2的PKI以及证书存放位置

一、什么是PKI&#xff1f; 简称&#xff1a;证书基础设施。 可以方便理解为当你的集群有Server,Client架构&#xff0c;那么为了安全加密之间的通信&#xff0c;则需要使用证书进行交互&#xff0c;那么利用PKI架构可以安全加密组件之间的通信。 二、Kubernetes的PKI架构什…...

利用大语言模型进行事实匹配

论文地址:Automated Claim Matching with Large Language Models: Empowering Fact-Checkers in the Fight Against Misinformation | Companion Proceedings of the ACM on Web Conference 2024 WWW 2024 Automated Claim Matching with Large Language Models: Empowering F…...

【Stable Diffusion】(基础篇一)—— Stable Diffusion的安装

本系列笔记主要参考B站nenly同学的视频教程&#xff0c;传送门&#xff1a;B站第一套系统的AI绘画课&#xff01;零基础学会Stable Diffusion&#xff0c;这绝对是你看过的最容易上手的AI绘画教程 | SD WebUI 保姆级攻略_哔哩哔哩_bilibili **Stable Diffusion&#xff08;简称…...

维纳运动的概念

维纳运动&#xff08;Wiener Process&#xff09;&#xff0c;也称为标准布朗运动&#xff0c;是一种重要的随机过程&#xff0c;广泛应用于数学、物理学和金融学等领域。它是一个连续时间的随机过程&#xff0c;具有一些特殊的性质&#xff0c;使其成为描述随机动态系统的经典…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...