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

cf 解题报告 01

E. Power of Points

Problem - 1857E - Codeforces

题意:

给你 n n n 个点,其整数坐标为 x 1 , … x n x_1,\dots x_n x1,xn,它们位于一条数线上。

对于某个整数 s s s,我们构建线段[ s , x 1 s,x_1 s,x1], [ s , x 2 s,x_2 s,x2], … \dots ,[ s , x n s,x_n s,xn]。注意,如果是KaTeX parse error: Expected 'EOF', got '&' at position 4: x_i&̲lt;s,那么线段看起来就像[ x i , s x_i,s xi,s]。线段[ a , b a, b a,b] 覆盖了所有的整数点 a , a + 1 , a + 2 , … , b a, a+1, a+2, \dots, b a,a+1,a+2,,b

我们把点 p p p 的幂定义为与坐标 p p p 的点相交的线段数,记为 f p f_p fp

你的任务是计算每个 s ∈ { x 1 , … , x n } s \in \{x_1,\dots,x_n\} s{x1,,xn} ∑ p = 1 1 0 9 f p \sum\limits_{p=1}^{10^9}f_p p=1109fp ,即从 1 1 1 1 0 9 10^9 109 所有整数点的 f p f_p fp 之和。

例如,如果初始坐标为 [ 1 , 2 , 5 , 7 , 1 ] [1,2,5,7,1] [1,2,5,7,1],我们选择 s = 5 s=5 s=5,那么线段将是 [ 1 , 5 ] [1,5] [1,5], [ 2 , 5 ] [2,5] [2,5], [ 5 , 5 ] [5,5] [5,5], [ 5 , 7 ] [5,7] [5,7], [ 1 , 5 ] [1,5] [1,5].这些点的幂将是 f 1 = 2 , f 2 = 3 , f 3 = 3 , f 4 = 3 , f 5 = 5 , f 6 = 1 , f 7 = 1 , f 8 = 0 , … , f 1 0 9 = 0 f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0 f1=2,f2=3,f3=3,f4=3,f5=5,f6=1,f7=1,f8=0,,f109=0.它们的和为 2 + 3 + 3 + 3 + 5 + 1 + 1 = 18 2+3+3+3+5+1+1=18 2+3+3+3+5+1+1=18

思路:说了这么多就是对每个xi求一个值,这个值得定义是:
∑ i n ( ∣ p − x i ∣ + 1 ) \sum_i^n( | p - x_i| + 1) in(pxi+1)
带绝对值不好计算。取绝对值之后就有两种。

  • p > xi

∑ i k ( p − x i + 1 ) = k ∗ p − ∑ i k ( x i ) − k \sum_i^k(p - x_i + 1) = k * p - \sum_i^k(x_i) - k ik(pxi+1)=kpik(xi)k

  • p < xi

∑ i k ( x i − p + 1 ) = ∑ i k ( x i ) − ( n − k + 1 ) ∗ p + n − k \sum_i^k(x_i - p + 1) = \sum_i^k(x_i) - (n - k + 1) * p + n - k ik(xip+1)=ik(xi)(nk+1)p+nk

对这两个式子进行观察,发现每次加一其实就是n,之后前面得p - xixi - p其实就是前后缀跟p操作一系列操作的结果。
∑ i n ( ∣ x k − x i ∣ + 1 ) = k ∗ x k − ∑ i k ( x i ) + ∑ k n ( x i ) − ( n − i + 1 ) ∗ x k + n \sum_i^n(|x_k - x_i| + 1) = k * x_k - \sum_i^k(x_i) + \sum_k^n(x_i) - (n - i + 1) * x_k + n in(xkxi+1)=kxkik(xi)+kn(xi)(ni+1)xk+n

进而转换为:排序后对第k个,k * xk - pre[k]suf[k] - (n - k + 1) * xkn的相加结果。

代码(记得LL):

void solve() {int n; cin>>n;vector<PII> a(n + 21);for(int i = 1; i <= n ;++i) {int t; cin>>t;a[i] = {t,i};}sort(a.begin() + 1, a.begin() + n + 1);vector<int> pre(n + 21), suf(n + 21);for(int i = 1; i <= n; ++i) {pre[i] = pre[i-1] + a[i].vf;}for(int i = n; i >= 1; --i) {suf[i] = suf[i+1] + a[i].vf;}vector<int> ans(n + 21);for(int i = 1; i <= n; ++i) {int x = a[i].vf;int pr = i * x - pre[i] + n;int sf = suf[i] - (n - i + 1) * x;ans[a[i].vs] = pr + sf;}for(int i = 1; i <= n; ++i) cout<<ans[i]<<" \n"[i == n];
}

C. Pull Your Luck

Problem - 1804C - Codeforces

题意:

image-20231002235053424

思路:当等于2n时:
f ( 2 n ) = 2 n ( 2 n + 1 ) 2 = n ( 2 n + 1 ) f(2n) = \frac{2n(2n + 1)}{2} = n(2n + 1) f(2n)=22n(2n+1)=n(2n+1)
此时,(x + f(2n)) %n == x进行循环,因此进行枚举即可。

_ = int(input())
for __ in range(_):n,x,p = list(map(int, input().split(" ")))ok = Falsefor i in range(1,min(2 * n, p) + 1):k = i * (i + 1) // 2if((k + x) % n == 0):ok = Truebreakprint("Yes" if ok else "No")

CF1804C Pull Your Luck - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

F. Range Update Point Query

Problem - 1791F - Codeforces

image-20231002235621960

解法一:线段树

区间修改用暴力,如果区间内都是小于10的表示这个区间不用再进行操作,可以知道这个每个位置的操作最多2、3次就不再进行操作。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;#define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
typedef pair<int,int> PII;const int INF = 0x3f3f3f3f;
const int N = 2e5 + 21;int calc(int x) {int tmp = 0; while(x) {tmp += x % 10; x /= 10; } return tmp;
}
int w[N],n,m; // 注意 w[N] 开LL ( https://www.luogu.com.cn/problem/P2357
struct SegTree {int l,r,val,tag;
}tr[N << 2];
// 左子树
inline int ls(int p) {return p<<1; }
// 右子树
inline int rs(int p) {return p<<1|1; }
// 向上更新
void pushup(int u) {tr[u].tag = tr[ls(u)].tag & tr[rs(u)].tag;
}// 建树
void build(int u, int l, int r) {if(l == r) {tr[u] = {l,r,w[l], w[l] < 10};}else {tr[u] = {l,r}; // 容易忘int mid = l + r >> 1;build(ls(u), l, mid), build(rs(u), mid + 1, r);pushup(u);}
}
// 修改
void modify(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r && tr[u].tag) {return ;}if(tr[u].l == tr[u].r) {tr[u].val = calc(tr[u].val);tr[u].tag = tr[u].val < 10;return ;}int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(ls(u), l, r);if(r > mid) modify(rs(u), l, r);pushup(u);
}
// 查询
LL query(int u, int l, int r) {if(tr[u].l >= l && tr[u].r <= r) return tr[u].val;int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) return query(ls(u), l,r);return query(rs(u), l, r);
}
void solve() {cin>>n>>m;for(int i = 1; i <= n; ++i) cin>>w[i];build(1, 1, n);while(m--) {int op,l,r; cin>>op;if(op == 1) {cin>>l>>r;modify(1,l,r);} else {cin>>l;cout<<query(1,l,l)<<endl;}}
}
int main()
{#ifdef Multiple_groups_of_examplesint T; cin>>T;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen("ANSWER.txt", "w",stdout);#endif
}

解法二

其实可能就是解法一的简化版。因为每个位置最多操作2次就不再进行操作了,只需要维护一个还需要进行操作的一个元素下标,每次区间操作对这个还要操作的元素下标进行查找,复杂度线段树差不多。

注意:对set用lower_bound函数时一定要用set自带的,s.lower_bound(l),而不是lower_bound(all(s), l),这题亲测会TLE3(

void solve() {int n,q; cin>>n>>q;vector<int> a(n + 1);set<int> s;for(int i = 1; i <= n; ++i) {cin>>a[i];if(a[i] >= 10) s.insert(i);}auto calc = [&](int x) -> int {int tmp = 0;while(x) {tmp += x % 10;x /= 10;}return tmp;};while(q--) {int op,l,r;cin>>op;if(op == 1) {cin>>l>>r;auto t = s.lower_bound(l);while(t != s.end() && *t <= r) {l = *t;a[l] = calc(a[l]);if(a[l] < 10) {s.erase(l);}t = s.lower_bound(l+1);}} else {cin>>l;cout<<a[l]<<endl;}}
}

相关文章:

cf 解题报告 01

E. Power of Points Problem - 1857E - Codeforces 题意&#xff1a; 给你 n n n 个点&#xff0c;其整数坐标为 x 1 , … x n x_1,\dots x_n x1​,…xn​&#xff0c;它们位于一条数线上。 对于某个整数 s s s&#xff0c;我们构建线段[ s , x 1 s,x_1 s,x1​], [ s , x…...

傅里叶系列 P1 的定价选项

如果您想了解更多信息&#xff0c;请查看第 2 部分和第 3 部分。 一、说明 这是第一篇文章&#xff0c;我将帮助您获得如何使用这个新的强大工具来解决金融中的半分析问题并取代您的蒙特卡洛方法的直觉。 我们都知道并喜欢蒙特卡洛数字积分方法&#xff0c;但是如果我告诉你你可…...

第二十届北京消防展即将开启,汉威科技即将精彩亮相

10月10日~13日&#xff0c;第二十届中国国际消防设备技术交流展览会&#xff0c;将在北京市顺义区中国国际展览中心新馆隆重举行。该展会由中国消防协会举办&#xff0c;是世界三大消防品牌展会之一&#xff0c;本届主题为“助力产业发展&#xff0c;服务消防救援”。届时将有4…...

mongodb、mysql、redis 区别

MongoDB、MySQL 和 Redis 是三种不同的数据库管理系统,它们在数据存储、访问模型和使用场景方面有一些显著的区别。 1. 数据存储模型: MongoDB:MongoDB 是一种文档数据库,它使用 BSON(Binary JSON)格式来存储数据。数据以文档的形式组织,每个文档可以有不同的字段,文档…...

【Flutter】Flutter Web 开发 如何从 URL 中获取参数值

【Flutter】Flutter Web 开发 如何从 URL 中获取参数值 文章目录 一、前言二、Flutter Web 中的 URL 处理三、如何从 URL 中获取参数四、实际业务中的用法五、完整示例六、总结 一、前言 大家好&#xff01;我是小雨青年&#xff0c;今天我想和大家分享一下在 Flutter Web 开发…...

【Java 进阶篇】JDBC Statement:执行 SQL 语句的重要接口

在Java应用程序中&#xff0c;与数据库进行交互是一项常见的任务。为了执行数据库操作&#xff0c;我们需要使用JDBC&#xff08;Java Database Connectivity&#xff09;来建立与数据库的连接并执行SQL语句。Statement接口是JDBC中的一个重要接口&#xff0c;它用于执行SQL语句…...

Python与数据分析--Pandas操作进阶

目录 1.文件读取方式 1.1.绝对路径读取文件 1.2.相对路径读取文件 2.列表数据操作 2.1.列索引指定 2.2.代码数据对齐 3.创建新CSV文件 4.缺失值处理 4.1.缺失值创建 4.2.缺失值检索 4.3.缺失值查询 4.3.1.isnull()函数判断 4.3.2.notnull()函数判断 4.3.3.any()函数…...

国庆小练习

一、二、三 一、 创建一个双向链表&#xff0c; 将26个英文字母通过头插的方式插入到链表中 通过尾删的方式将数据读取出来并删除。main.c #include <my_head.h> #include "dblink.h"int main(int argc, const char *argv[]) {dblink *h create_head();for…...

springboot单体项目如何拆分成微服务

要将一个Spring Boot单体项目拆分成微服务&#xff0c;可以按照以下步骤进行操作&#xff1a; 识别业务域&#xff1a;首先&#xff0c;需要对单体项目进行业务域的划分。将项目中的功能按照业务领域进行分类&#xff0c;每个业务领域可以成为一个独立的微服务。 定义服务接口…...

解决recovery页面反转的问题

1.前言 在android 10.0的系统rom定制化开发工作中&#xff0c;在系统中recoverv的页面也是相关重要的一部分&#xff0c;在系统recovery ta升级等功能&#xff0c;都是需要recoverv功能的&#xff0c;在某些产品定制化中 在recovery的时候&#xff0c;发现居然旋转了180度&…...

如何使用nuScenes数据集格式的单帧数据推理(以DETR3D为例)

【请尊重原创&#xff01;转载和引用文章内容务必注明出处&#xff01;未经许可上传到某文库或其他收费阅读/下载网站赚钱的必追究责任&#xff01;】 无论是mmdetection3D还是OpenPCDet都只有使用数据集(使用哪个数据集由配置文件里指定)训练和测试的代码&#xff0c;没有使用…...

大语言模型之十三 LLama2中文推理

在《大语言模型之十二 SentencePiece扩充LLama2中文词汇》一文中已经扩充好了中文词汇表&#xff0c;接下来就是使用整理的中文语料对模型进行预训练了。这里先跳过预训练环节。先试用已经训练好的模型&#xff0c;看看如何推理。 合并模型 这一步骤会合并LoRA权重&#xff0…...

iOS AVAudioSession 详解

iOS AVAudioSession 详解 - 简书 默认没有options&#xff0c;category 7种即可满足条件 - (BOOL)setCategory:(AVAudioSessionCategory)category error:(NSError **)outError API_AVAILABLE(ios(3.0), watchos(2.0), tvos(9.0)) API_UNAVAILABLE(macos); 有options&#xff…...

26-网络通信

网络通信 什么是网络编程&#xff1f; 可以让设备中的程序与网络上其他设备中的程序进行数据交互&#xff08;实现网络通信的&#xff09;。 java.net.包下提供了网络编程的解决方案&#xff01; 基本的通信架构有2种形式&#xff1a;CS架构&#xff08; Client客户端/Server服…...

嵌入式Linux应用开发-基础知识-第十九章驱动程序基石③

嵌入式Linux应用开发-基础知识-第十九章驱动程序基石③ 第十九章 驱动程序基石③19.5 定时器19.5.1 内核函数19.5.2 定时器时间单位19.5.3 使用定时器处理按键抖动19.5.4 现场编程、上机19.5.5 深入研究&#xff1a;定时器的内部机制19.5.6 深入研究&#xff1a;找到系统滴答 1…...

一文拿捏SpringMVC的调用流程

SpringMVC的调用流程 1.核心元素&#xff1a; DispatcherServlet(前端控制器)HandlerMapping(处理器映射器)HandlerAdapter(处理器适配器) ---> Handler(处理器)ViewResolver(视图解析器 )---> view(视图) 2.调用流程 用户发送请求到前端控制器前端控制器接收用户请求…...

一文详解 JDK1.8 的 Lambda、Stream、LocalDateTime

Lambda Lambda介绍 Lambda 表达式(lambda expression)是一个匿名函数&#xff0c;Lambda表达式基于数学中的λ演算得名&#xff0c;直接对应于其中的lambda抽象(lambda abstraction)&#xff0c;是一个匿名函数&#xff0c;即没有函数名的函数。 Lambda表达式的结构 一个 Lamb…...

WebSocket实战之二协议分析

一、前言 上一篇 WebSocket实战之一 讲了WebSocket一个极简例子和基础的API的介绍&#xff0c;这一篇来分析一下WebSocket的协议&#xff0c;学习网络协议最好的方式就是抓包分析一下什么就都明白了。 二、WebSocket协议 本想盗一张网络图&#xff0c;后来想想不太好&#x…...

LeetCode //C - 208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree) A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and s…...

【Python】time模块和datetime模块的部分函数说明

时间戳与日期 在说到这俩模块之前&#xff0c;首先先明确几个概念&#xff1a; 时间戳是个很单纯的东西&#xff0c;没有“时区”一说&#xff0c;因为时间戳本质上是经过的时间。日常生活中接触到的“日期”、“某点某时某分”准确的说是时间点&#xff0c;都是有时区概念的…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...