题解1203 div cf
P9755 [CSP-S 2023] 种树 题解
Description 你是一个森林养护员,有一天,你接到了一个任务:在一片森林内的地块上种树,并养护至树木长到指定的高度。 森林的地图有 \(n\) 片地块,其中 \(1\) 号地块连接森林的入口。共有 \(n-1\) 条道路连接这些地块,使得每片地块都能通过道路互相到达。最开始,每片地块上都没有 ......
[题解]P9752 [CSP-S 2023] 密码锁
这次 CCF 的行为过于迷惑了。 思路 首先发现只会有 \(10^5\) 种密码,考虑枚举它们,然后去 check。 假设当前密码是:\(p_1,p_2,p_3,p_4,p_5\)。如果它能从对于所有 \(1 \sim n\) 种错误的密码按照题目所述的操作得到,那么此密码就是合法的。 假设我们现在 ......
洛谷-P9779 题解
正文 对于每个选择题,都有两种状态,因此总状态数为 \(2^n\)。 请注意初始所有选择题都不选也是一个状态,不计入贡献,因此答案为 \(2^n-1\)。 代码: #include<iostream> using namespace std; int main(){ long long n; cin ......
CSP-S 2023 题解
CSP-S 2023 题解 密码锁 发现总状态数只有 \(10^5\) 个,枚举 \(O(n)\) 暴力判断即可,复杂度 \(O(10^5 n)\)。 或者每一个状态只对应了 \(81\) 个状态,枚出来,取交集即可,复杂度 \(O(81 n)\)。 消消乐 好的,来一波抽象做法 QwQ 我看到这道 ......
洛谷题解 | AT_abc321_c Primes on Interval
目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数,其含义就是除了数字一和本身之外不能被其 ......
[ABC231E] Minimal payments 题解
题目传送门 一道贪心题。 感觉很裸啊,模拟赛时随便乱写了个暴力递归就能过。每次找最接近钱数 \(x\) 的面额 \(num\),如果比钱数少那么答案为剩下 \(x \bmod num\) 钱数的答案加上 \(x \div num\)。否则答案则为剩下 \(num-x\) 钱数的答案加上 \(1\)。 ......
[ABC234E] Arithmetic Number 题解
题目传送门 一道枚举题。 暴力枚举数字位数、首位、等差数列的公差即可。注意公差的枚举范围,并且需要看看末尾合不合法。顺便提一下,我是用字符串存储枚举的数字的,所以写了一个 check 函数代替大于号。 Code #include <bits/stdc++.h> using namespace std ......
[ABC118D] Match Matching 题解
题目传送门 一道 dp 题。 在 dp 之前,我们需要明确以下几个东西: 状态的表示,状态转移方程,边界条件跟答案的表示。 状态的表示 \(dp_i\) 表示恰好用完 \(i\) 根火柴能拼出来的最大数字。 状态转移方程 \[dp_i = \max\{j \times 10^{len(dp_{i-w ......
ABC323D题解
ABC323D Merge Slimes 题目简述 小 A 有 \(N\) 种橡皮泥。对于第 \(i\) 种橡皮泥,它的大小为 \(S_i\) 且一共有 \(C_i\) 个。 小 A 可以合成两个大小相同的橡皮泥,若这两个橡皮泥大小为 \(X\),则新和成的橡皮泥大小为 \(2X\)。 小 A 想知 ......
P9754 [CSP-S 2023] 结构体 题解
前言 在考场上调了 2h+ 还没调出来,并且 T4 也没来得及做。希望看到这段文字的你能避免这样的悲剧。 正文 题目要求动态创建类型,于是我用结构体代表一个 struct(禁止套娃),要新建就 new 出来一个。(最后也没 delete) struct Obj{ typnam tnam; ll le ......
CSP-S 2023 题解
expect: \(100+100+65+25=290\) 真实: \(100+85+0+15=205\) , rk62 感觉自己考的好烂好烂好烂 T4 这么简单竟然想不出来,感觉如果自己不被 T4 吓到,全做出来其实有望 365+ ? 今年 CSP-S 怎么这么简单吓得我不敢做了 T1 暴力 T2 ......
CSP-S2023 题解
更好的阅读体验 CSP-S2023 游记 密码锁(lock) \(10^5\) 枚举所有可能答案,然后判断。 代码 #include <bits/stdc++.h> int n; int a[13][7], b[7]; bool check(int i) { int cnt = 0; for(int ......
Codeforces Round 887 (Div. 2)
Codeforces Round 887 (Div. 2) A. Desorting 解题思路: 每次操作能使相邻数之差减\(2\),设最小相邻数之差为\(mind\),答案为\(ans = (mind + 1) / 2\)。 代码: #include <bits/stdc++.h> using n ......
P9752 [CSP-S 2023] 密码锁 题解
分析 最水 S 组 T1。 每次可以转动一个拨圈,或者转动相邻的两个拨圈,且幅度相同。那么就有一个简单粗暴的思路,枚举修改的方案,用 vector 来储存修改后的方案,存到 map 当中,当然也可以转换为数字存进去。 切记要用两个 map 来储存,一个存方案,下文称为 \(mp\),一个存这个方案在 ......
Codeforces Round 855 (Div. 3) C. Powering the Hero
有 \(n\) 张卡的卡堆,你可以自顶向下抽卡。装备卡显示数值为 \(a_i(a_i>0)\) ,英雄卡显示数值为 \(a_i = 0\) 。 如果是装备卡,你可以将卡抽出放在装备堆。如果是英雄卡,你可以将装备堆顶端的一张数值为 \(x\) 的装备卡装备给英雄,英雄数值 \(+ x\) 。无论是否装 ......
Codeforces Round 857 (Div. 2) B. Settlement of Guinea Pigs
你非常喜欢豚鼠。每个笼子可以住两只豚鼠,且你不想把每个笼子放入不同性别的豚鼠。豚鼠只有两种性别。假设你买到豚鼠时并不知道性别,只有医生能够分辨。 接下来的 \(n\) 天方案中,若第 \(i\) 天为 \(1\) ,你买入一只豚鼠;若为 \(2\) ,你请医生分辨你的豚鼠性别。 给出方案,你最少需要 ......
Nebius Welcome Round (Div. 1 + Div. 2) B. Vaccination
你管理一个疫苗接种站,将会有 \(n\) 个人前来接种疫苗。第 \(i\) 个到来的人时间为 \(t_i\) ,已知每个人的等待时间不会超过 \(w\) 分钟。 疫苗存放在特质冰箱中,一袋疫苗有 \(k\) 支,当一袋疫苗在 \(x\) 时刻打开时,它的有效时间为 \(d\) 。 现在询问最少需要打 ......
Educational Codeforces Round 145 (Rated for Div. 2) B. Points on Plane
给一个二维平面,你需要在上面放 \(n\) 个芯片。将一个芯片放在 \((x, y)\) 的代价为 \(|x| + |y|\) 。放 \(n\) 个代价的代价为,所有芯片中耗费的最大代价。并且你需要保证任意两个芯片之间的距离严格 \(> 1\) 。 现在给出 \(n\) 给芯片,询问放 \(n\) ......
CSP-J2023 题解
T1 code #include <bits/stdc++.h> using namespace std; int n,ans; signed main() { ios::sync_with_stdio(0);cin.tie(0); cin>>n; for(int i = n; i; i -= (i ......
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees( DFS )
Codeforces Round 875 (Div. 2) C. Copil Copac Draws Trees 思路: 在输入树的边的同时记录他们的输入顺序 从 1 开始跑 DFS ,遇到未连上的边时 , 有两种情况(用 q 表示当前点的顺序序号) 1.边的顺序在这个点连上之前,那么 DFS 的 ......
Educational Codeforces Round 149 (Rated for Div. 2)
这场D被切穿了。 A题 答案为 x 或者 x-1 1 B题 答案就是最长的连续一段的长度+1 证明的话大概可以将它看成是几段连续上升和下降的段,然后在峰谷、峰顶分别填上最小、最大,剩下的就依次递增或递减就行。 C题 将一段连续的0/1视作一个块,那么我们最小化这个块的数量就行。 D题如果猜到如果有解 ......
KDOI-06-S 模拟题解
目录P9744 「KDOI-06-S」消除序列P9745 「KDOI-06-S」树上异或 P9744 「KDOI-06-S」消除序列 发现这是一道贪心题,第一种操作只会使用一次,也就是在最开始的时候进行清零操作,从而使得整个前缀都变成0。考虑两种情况,一种是前缀全部为1,另一种为0,分别考虑转移即可 ......
[CF444E] DZY Loves Planting
DZY Loves Planting 逆天题。 想到二分,判断用网络流,但是好像 n 有点大。 我们想尽量让每个点的 g 能大于下界,所以我们尽量往大的边走,其实就是尽量不走小的边。 所以考虑将边从小到大排序,每次合并两端的连通块,如果剩下点的 x 总和小于总点数就只能内部消化。 又因为这已经是最劣 ......
【0xGame 2023】题解week1
前段时间在忙各种事情,这两天有学弟学妹要入re,想带着他们打个新生赛,我就打算把这个比赛week1的题先出一遍,后面的之后再说。 这次0xGame的re题目名称都很有意思,开始做吧。 数字筑基 解法 直接搜索字符串 代码金丹 解法 就比第一题多个判断过程,不过flag仍然明文 网络元婴 解法 进去后 ......
Codeforces Round 863 (Div. 3) B. Conveyor Belts
给一个 \(n \times n\) 的矩阵, \(n\) 是偶数。将矩阵按圈分割,同一圈的位置可以不消耗代价移动,可以消耗一个代价移动到相邻圈。 给出 \(n, x_1, y_1, x_2, y_2\) ,询问 \((x_1, y_1)\) 移动到 \((x_2, y_2)\) 的代价最小是多少。 ......
Codeforces Round 865 (Div. 2) B. Grid Reconstruction
给一个 \(2 \times n\) 的网格,且 \(n\) 是偶数。你需要将 \(1 \sim 2 \times n\) 填入这个网格。 一条路径是从 \((1, 1)\) 开始,每次只能向右或向下,到 \((2, n)\) 结束时,所经过的位置。按经过点的顺序标号,一两条路径的代价是 \(cos ......
Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
\(D. Effects of Anti Pimples\) 对每个数字能到达的所有位置先预处理最大值,那么就代表选择这个数字之后真实的贡献,那么对这样的预处理值,最小值显然只有一种做法,为 \(2^0\) ,第二小的值应该可以与最小值一起选择,所以答案为 \(2^1\) ,以此类推之后,每个值乘上 ......
CF1634F
知识点:差分 Link:https://codeforces.com/contest/1634/problem/F 差分的本质是递推。 简述 给定两长度为 \(n\) 的数列 \(a, b\),模数 \(p\),要求进行 \(q\) 次操作,每次操作为 c l r 的形式,表示将数列 \(c\) 的 ......
CF1100E Andrew and Taxi
套路题又来咯,最大值最小先直接上个二分答案\(lim\) 对于图中的边,若它的权值\(>lim\)的话这条边的方向就确定了,那么直接把这些边连出来跑个拓扑排序看看有没有环即可 如果有环则当前答案一定不合法,否则我们总存在如下的构造方法: 先把权值\(>lim\)的边得到的图的拓扑序搞出来,对于所有权 ......
CF1003E Tree Constructing
很trivial的构造题 首先上来判掉一些显然无解的情况,然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来 考虑在链上接一些点使得直径不会变长,对于链上的某个点,它最多能接上的链的长度就是它到两个端点距离的最小值 不妨设计递归函数求解,设solve(x,dis,lim)表示在 ......