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;}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言结构体指针学习

结构体变量存放内存中&#xff0c;也有起始地址&#xff0c;定义一个变量来存放这个地址&#xff0c;那这个变量就是结构体指针&#xff1b; typedef struct mydata{int a1;int a2;int a3; }mydata;void CJgtzzView::OnDraw(CDC* pDC) {CJgtzzDoc* pDoc GetDocument();ASSERT…

npm ,yarn 更换使用国内镜像源,淘宝源

背景 文章首发地址 在平时开发当中&#xff0c;我们经常会使用 Npm&#xff0c;yarn 来构建 web 项目。但是npm默认的源的服务器是在国外的&#xff0c;如果没有梯子的话。下载速度会特别慢。那有没有方法解决呢&#xff1f; 其实是有的&#xff0c;设置国内镜像即可&#x…

基于web的医院预约挂号系统/医院管理系统

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&a…

如何解决版本不兼容Jar包冲突问题

如何解决版本不兼容Jar包冲突问题 引言 “老婆”和“妈妈”同时掉进水里&#xff0c;先救谁&#xff1f; 常言道&#xff1a;编码五分钟&#xff0c;解冲突两小时。作为Java开发来说&#xff0c;第一眼见到ClassNotFoundException、 NoSuchMethodException这些异常来说&…

八大排序(三)堆排序,计数排序,归并排序

一、堆排序 什么是堆排序&#xff1a;堆排序&#xff08;Heap Sort&#xff09;就是对直接选择排序的一种改进。此话怎讲呢&#xff1f;直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的&#xff0c;但是在选出最大或者最小的数后&#xff0c;并没有对原来的序列…

k8s--storageClass自动创建PV

文章目录 一、storageClass自动创建PV1.1 安装NFS1.2 创建nfs storageClass1.3 测试自动创建pv 一、storageClass自动创建PV 这里使用NFS实现 1.1 安装NFS 安装nfs-server&#xff1a; sh nfs_install.sh /mnt/data03 10.60.41.0/24nfs_install.sh #!/bin/bash### How to i…

springboot 简单配置mongodb多数据源

准备工作&#xff1a; 本地mongodb一个创建两个数据库 student 和 student-two 所需jar包&#xff1a; # springboot基于的版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId>&l…

SSM - Springboot - MyBatis-Plus 全栈体系(十六)

第三章 MyBatis 三、MyBatis 多表映射 2. 对一映射 2.1 需求说明 根据 ID 查询订单&#xff0c;以及订单关联的用户的信息&#xff01; 2.2 OrderMapper 接口 public interface OrderMapper {Order selectOrderWithCustomer(Integer orderId); }2.3 OrderMapper.xml 配置…

一文拿捏基于redis的分布式锁、lua、分布式性能提升

1.分布式锁 jdk的锁&#xff1a; 1、显示锁&#xff1a;Lock 2、隐式锁&#xff1a;synchronized 使用jdk锁保证线程的安全性要求&#xff1a;要求多个线程必须运行在同一个jvm中 但现在的系统基本都是分布式部署的&#xff0c;一个应用会被部署到多台服务器上&#xff0c;s…

【系统架构】软件架构的演化和维护

导读&#xff1a;本文整理关于软件架构的演化和维护知识体系。完整和扎实的系统架构知识体系是作为架构设计的理论支撑&#xff0c;基于大量项目实践经验基础上&#xff0c;不断加深理论体系的理解&#xff0c;从而能够创造新解决系统相关问题。 目录 1、软件架构演化和定义 …

关掉在vscode使用copilot时的提示音

1. 按照图示的操作File --> Preferences --> Settings 2. 搜索框输入关键字Sound&#xff0c;因为是要关掉声音&#xff0c;所以找有关声音的设置 3. 找到如下图所示的选项 Audio Cues:Line Has Inline Suggetion,将其设置为Off 这样&#xff0c;就可以关掉suggest code时…

Python无废话-基础知识字典Dictionary详讲

“字典Dictionary” 是一种无序、可变且可嵌套的数据类型&#xff0c;用于存储键值对。字典使用花括号{}来定义&#xff0c;并用逗号分隔键值对。本文对字典常使用方法&#xff0c;创建字典、添加字典、删除字典、如何获取字典做了知识归纳。 字典有以下几个特征&#xff1a; …

傅里叶系列 P1 的定价选项

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

VS code本地安装PlantUML

VS code本地安装PlantUML 需要条件vs code安装插件使用常见错误 需要条件 在VS Code上安装PlantUML扩展之前&#xff0c;请确保您具有以下先决条件: : Java与GraphViz(点击可直接跳转下载界面); 安装省略 vs code安装插件 vs code安装以下两个插件&#xff08;PlantUML,Grap…

nodejs+vue流浪猫狗救助领养elementui

第三章 系统分析 10 3.1需求分析 10 3.2可行性分析 10 3.2.1技术可行性&#xff1a;技术背景 10 3.2.2经济可行性 11 3.2.3操作可行性&#xff1a; 11 3.3性能分析 11 3.4系统操作流程 12 3.4.1管理员登录流程 12 3.4.2信息添加流程 12 3.4.3信息删除流程 13 第四章 系统设计与…

火热报名中 | 2天峰会、20+热门议题,AutoESG 2023数智低碳---中国汽车碳管理创新峰会亮点抢先看!

在碳中和的背景下&#xff0c;减碳之风吹遍全球&#xff0c;而汽车行业则由于产业链长、辐射面广、碳排放总量增长快、单车碳强度高的特点&#xff0c;成为各国碳排放管理的监管重点&#xff0c;聚焦汽车业的碳博弈也逐步升级。 2020年&#xff0c;国务院办公厅印发的《新能源…

Multiple CORS header ‘Access-Control-Allow-Origin‘ not allowed

今天在修改天天生鲜超市项目的时候&#xff0c;因为使用了前后端分离模式&#xff0c;前端通过网关统一转发请求到后端服务&#xff0c;但是第一次使用就遇到了问题&#xff0c;比如跨域问题&#xff1a; 但是&#xff0c;其实网关里是有配置跨域的&#xff0c;只是忘了把前端项…

下载盗版网站视频并将.ts视频文件合并

. 1.分析视频请求123 2.数据获取和拼接 1.分析视频请求 1 通过抓包观察我们发现视频是由.ts文件拼接成的每一个.ts文件代表一小段2 通过观察0.ts和1.ts的url我们发现他们只有最后一段不同我们网上找到url获取的包3 我们发现index.m3u8中储存着所有的.ts文件名在拼接上前面固定…

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

嵌入式Linux应用开发-基础知识-第十九章驱动程序基石④ 第十九章 驱动程序基石④19.7 工作队列19.7.1 内核函数19.7.1.1 定义 work19.7.1.2 使用 work&#xff1a;schedule_work19.7.1.3 其他函数 19.7.2 编程、上机19.7.3 内部机制19.7.3.1 Linux 2.x的工作队列创建过程19.7.3…

Monkey测试

一&#xff1a;测试环境搭建 1&#xff1a;下载android-sdk_r24.4.1-windows 2&#xff1a;下载Java 3&#xff1a;配置环境变量&#xff1a;关于怎么配置环境变量&#xff08;百度一下&#xff1a;monkey环境搭建&#xff0c;&#xff09; 二&#xff1a;monkey测试&#xff1…
推荐文章