hsl-beat的blog

前言以及UPD 前言 线段树是一种非常美的数据结构，她不仅可以拿来维护数组里的信息并支持快速查询以及修改，还能广泛的应用在其他算法的优化中。这篇文章记录着我对线段树的全部理解。 UPD 2.6 文章创建，写了最最基础的线段树。 3.3 增加了懒标记这个东西 但只是举了区间加这个例子。 8.6 阅读了这篇博客，重写了整篇文章并发布在了洛谷专栏 线段树是什么 线段树是我们经常会使用的一种可以在O(log n)\text{O(log n)}O(log n)的时间内实现区间修改和区间查询的数据结构，并且也可以拿来辅助别的算法或者数据结构的优化。反正她非常好用就是了！ 线段树初步 ...

Atcoder ABC416游记（A~E) 这把手速场吧 那我纯吃亏了 一个多小时才过了E 但是F题又没写完 赛后30min过 呜呜 A.Vacation Validation 题目描述 给你一个长度为 NNN 的字符串 SSS ，它由 o 和 x 以及整数 LLL 和 RRR 组成。 请判断从 SSS 的 LLL -th到 RRR -th的所有字符是否都是o。 思路 水 代码 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int main(){ int n, l, r; cin >> n >> l >> r; string s; cin >> s; for (int i = l; i <= r; i++) { if (s[i - 1] == 'x') { cout << "No"; return 0; ...

Atcoder ABC415游记（A~E） A.Unsupported Type 题目描述 给你一个长度为 NNN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N)A=(A1​,A2​,…,AN​) 和一个整数 XXX 。 请判断 XXX 是否包含在 AAA 中。 思路 水 代码 1234567891011121314151617#include<bits/stdc++.h>using namespace std;int main(){ int n; cin >> n; set<int> s; while (n--) { int x; cin >> x; s.insert(x); } int x; cin >> x; cout << (s.count(x) ? "Yes" : "No"); return 0;} B.Pick Two ...

atcoder尼干嘛哈哈哎呦 Atcoder ABC414游记(A~E) A.Streamer Takahashi 题目描述 流媒体播放器 Takahashi 决定从 LLL 点钟到 RRR 点钟（使用 242424 小时钟）进行流媒体播放。 他有 NNN 个听众，其中 iii 个听众可以收听 XiX_iXi​ 点到 YiY_iYi​ 点的流媒体节目。 有多少听众可以从头到尾收听高桥的节目？ 思路 高桥就是个流媒体播放器（（（怒怒怒 没错这个题面翻译来自deepl不代表本博客立场 水 代码 123456789101112131415#include<bits/stdc++.h>using namespace std;int main(){ int n, l, r; cin >> n >> l >> r; int ans = 0; while (n--) { int x, y; cin >> x >> y; ans += (x...

无关紧要的彩蛋在后面，去看看今天的日期吧 没怎么写的原因一个是因为有事 一个是浏览量感人 Atcoder ABC411游记（A~G） A.Required Length 题目描述 给你一个字符串PPP，判断这个字符串的长度是否大于等于LLL 思路 唐 代码 12345678910#include<bits/stdc++.h>using namespace std;int main(){ string s; int a; cin >> s >> a; cout << (s.length() >= a ? "Yes" : "No"); return 0;} B.Distance Table 题目描述 在一条直线上有NNN个烟花，对于(1≤i<n)(1 \leq i < n)(1≤i<n)，第iii个烟花与第i+1i+1i+1个烟花之间的距离为did_idi​。 对于满足1≤i<j≤n1 \leq i < j \leq...

405~407有事情没打所以没写文章 Atcoder ABC408游记（A~E） A.Timeout 题目描述 beat会立即睡着。具体地说，如果从上次拍打beat的肩膀到现在已过去 S+0.5S+0.5S+0.5 秒或更长时间，beat就会睡着。 目前，beat是醒着的，一个人刚刚拍了拍beat的肩膀。 从现在开始，这个人会准确地拍打beat的肩膀 NNN 次。 iii 次拍肩将在 TiT_iTi​ 秒后进行。 判断beat从现在开始到 TNT_NTN​ 秒后是否一直保持清醒。 思路 阅读理解题，水 代码 12345678910111213141516171819#include<bits/stdc++.h>using namespace std;int main(){ int n, s; cin >> n >> s; vector<int> a(n + 1); a[0] = 0; for (int i = 1; i <= n; i++) { cin >>...

啊哈 来写一个状压dp八 状态压缩 状态压缩DP，简称状压DP。 那状态压缩是什么捏？比如我们有一个vis数组，这个数组的第iii个元素代表这个元素选或不选。 那比如编号1,4,51,4,51,4,5的元素选了，0,2,30,2,30,2,3没有选的vis数组就可以这样表示： 123456vis------------------------------|key | 0 | 1 | 2 | 3 | 4 | 5 ||----|---|---|---|---|---|---||val | 0 | 1 | 0 | 0 | 1 | 1 | ------------------------------ 这里vis数组的一系列权值都是0和1。只有0和1有没有让你想起什么？没错，2进制啊！！！ 那如果想用一个二进制数表示这个vis数组，就可以这样： 12( 1 1 0 0 1 0)vis[5] vis[4] vis[3] vis[2] vis[1]...

Atcoder ABC404游记（A~D） 用G逼迫自己学会了差分约束。。。赛时过的人还是L4的是什么情况 但是代码写下来感觉G比E爽，其实习惯了，atc民间风俗好吧 喜欢调换顺序 A. Not Found 题目描述 给你一个长度在 111 和 252525 之间的字符串 SSS ，它由小写英文字母组成。 请输出一个没有出现在 SSS 中的小写英文字母。 如果有多个这样的字母，可以输出其中任意一个。 思路 水 代码 123456789101112131415161718#include<bits/stdc++.h>using namespace std;bool vis[26];int main(){ string s; cin >> s; for (int i = 0; i < s.length(); i++) { vis[s[i] - 'a'] = 1; } for (int i = 0; i < 26; i++) { if (!vis[i]) { ...

标题长，别怪我 没啥好说的，因为只有板子，直接上板子题 （小黄油美式害得我根本睡不着，浅浅写一下，哪里有问题欢迎喷我，脑子可能今晚有点不好使） P5960 【模板】差分约束 题目描述 给出一组包含 mmm 个不等式，有 nnn 个未知数的形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​xc1​​−xc1′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​ 的不等式组，求任意一组满足这个不等式组的解。 对于 100%100\%100% 的数据，1≤n,m≤5×1031\leq n,m \leq 5\times 10^31≤n,m≤5×103，−104≤y≤104-10^4\leq y\leq 10^4−104≤y≤104，1≤c,c′≤n1\leq...

Atcoder ABC403游记（A~D） 66 这回D和上回不同，不是余数性质了 A. Odd Position Sum 题目描述 给你一个整数序列，对于所有iii满足1≤2∗i+1≤N1 \leq 2*i+1 \leq N1≤2∗i+1≤N，计算AiA_iAi​的和。 思路 水 代码 12345678910111213141516171819#include<bits/stdc++.h>using namespace std;int main(){ int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 0; for (int i = 0; i < n; i++) { if (i % 2 == 0) { ans += a[i]; } } cout <<...