题解codeforces round div3
ABC328F 题解
blog。提供一个普通并查集 + 启发式合并做法。 考虑直接维护 \(X_i\)。对于 \(X_u-X_v=w\),分四种情况。 \(X_u,X_v\) 都没被维护过。直接钦定 \(X_u\gets w,X_v\gets0\),以后再改。 \(X_u\) 没被维护过,\(X_v\) 被维护过。显然 ......
[题解] CF407E k-d-sequence
k-d-sequence 给你一个长为 \(n\) 的序列,求最长的子区间使得它加入至多 \(k\) 个数后,重排后是公差为 \(d\) 的等差数列。 \(n, k \le 2 \times 10^5\),\(0 \le d \le 10^9\)。 公差是 \(d\) 的等差数列模 \(p\) 的值 ......
ABC328G 题解
blog。剩下几分钟的时候胡出来了,但是时间不够,痛失 AK /dk。 \(N\le22\),显然状压 DP。\(dp_s\) 表示确定 \(s\) 集合的元素所需的代价(这些元素都放在最前面)。 确定了 \(s\) 后,发现会有 \(\operatorname{popcount}(s)\) 个元素 ......
[题解] CF505E Mr. Kitayuta vs. Bamboos
Mr. Kitayuta vs. Bamboos 给定 \(n\) 个数 \(h_{1 \dots n}\)。 你需要进行 \(m\) 轮操作,每轮操作为 \(k\) 次修改,每次修改可以选择一个数 \(h_i\) 修改为 \(\max(h_i - p, 0)\)。 每轮操作后每个 \(h_i\) ......
ABC328题解(C-G)
A/B 较为简单,略去。 C 预处理一下,然后前缀和就好了。 时间复杂度 \(O(n)\)。 D 用链表来记录字符串。 注意到每次能够消去意味着链表上连续三个节点拼起来是 ABC,然后从左到右一个个算就行了。 匹配到的话把三个节点一起删掉。 时间复杂度 \(O(n)\)。 E 注意到 \(N\le ......
【题解 P8763】[蓝桥杯 2021 国 ABC] 异或变换
同楼上dalao做法: #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #inclu ......
2022新生赛 玩石头 题解
这题乍一看是个背包,但是它对背包物品的重量进行了限制,而且我们没有手段得知当前物品是否大于前面所有物品。研究发现,纪念品最大价值不会超过4000.因此我们可以用类似于01背包的做法,以纪念品价值作为重量,纪念品重量作为价值来dp.打表可以发现,在给定数据的范围下,石头塔最多为三十层,则时髦值之和最大 ......
P9836 种树 题解
蒟蒻在考场上花了 2h45min AC 本题 通过高度求宽度 定义一棵树的宽度为它高度的正因数个数 我们可以预处理 \(10^4\) 之内素数。 for(ll i=2; i<=10000; i++) { if(ok[i]==0) { ok[i]=i; pr[++nP]=i; } for(ll j=1 ......
[题解] CF1327F AND Segments
AND Segments 有 \(m\) 个限制 \((l, r, x)\)。 要计算满足以下条件的长度为 \(n\) 的序列 \(a\) 的数量: \(\forall i \in [1, n], 0 \le a_i < 2^k\)。 \(\forall i \in [1, m], a_{l_i} ......
AT_agc057_e 题解
AT_agc057_e [0] 约定 \(r_i = \sum\limits_{j = 1}^{m}[A_{i,j}\le k]\) \(r^{'}_i = \sum\limits_{j = 1}^{m}[B_{i,j}\le k]\) \(c_j = \sum\limits_{i = 1}^{n} ......
[题解] AT_dp_w Intervals
Intervals 有 \(m\) 条形如 \((l, r, a)\) 的限制,表示如果 \(s_{[l, r]}\) 中有 1 就会有 \(a\) 的价值。 你要求长度为 \(n\) 的 01 串的价值的最大值。 \(n, m \le 2 \times 10^5\)。 将每个限制挂到右端点上,在右 ......
Codeforces Round 908 (Div. 2) A-D
Secret Sport 观察到数据不大,直接摁住x和y枚举即可,方案合法当且仅当刚好打若干局,且赢最后一局的人是赢家 #include<bits/stdc++.h> using namespace std; void solve(){ int n; cin>>n; string s;cin>>s; ......
Codeforces Round 887 (Div. 2)
https://codeforces.com/contest/1853 C题感觉很不好写的样子,首先通过打表发现最后答案每次都是+n,那么我们考虑前i个,假如当前的ans+i仍然小于a[i+1],则没有影响,我们依然可以直接往后跳,否则,我们越过了a[i+1],那么我们应当加上i+1,注意,这有可能 ......
洛谷 P9680 string[_view] 题解
洛谷 P9680 string[_view] 题解 link Sol 模拟题。 我们先定义一个结构体,来存储定义的字符串的名字,内容和长度。每一次输入分两个字符串,一个是类型,一个是名字和赋值内容。当遇到 string 时,如果是用字面量赋值,那么就计算引号里字符串的长度 \(l\)。然后把答案加上 ......
[POI2011] SMI-Garbage 题解
题目链接 显然,对于初始颜色与目标颜色不同的边,我们需要走过奇数次;对于初始颜色与目标颜色相同的边,我们需要走过偶数次。 对于只有偶数边的情况,这种情况下不走就行;对于只有奇数边;可以理解为每条边只能经过一次,就是欧拉路径问题,并且考虑这题的特殊性质,如果一个图是由若干个简单环构成的连通图,那么显然 ......
CF1485F Copy or Prefix Sum 题解
思路 考虑 \(a_i\) 要么是 \(b_i\) 要么是 \(b_i - s\)。 考虑 \(s\) 代表着什么。 它是 \(a\) 的前缀和。 那么必然是往前一段 \(b\) 的和。 因为每个 \(b\) 代表着要么是这一位的 \(a\) 或者前面所有的 \(a\)。 考虑设 \(f_i\) 为 ......
Codeforces vp 寄
难度标记: \(\verb!A!\) :傻逼题。 \(\verb!B!\) :看完题解后马上就会了。 \(\verb!C!\) :看完题解后还需要想一会,甚至仍然不会。 + 和 - 表示在同档题中的难度。 Codeforces Round 694 (Div. 1) 最终 \(\rm performa ......
CSP-S2019 江西 题解
为什么有 \(5\) 道题? [CSP-S2019 江西] 和积和 简单化一下式子: \[(n + 1) \times \sum A_i \times B_i - (\sum A_i) \times (\sum B_i) \]其中 \(A, B\) 都是前缀和。 [CSP-S2019 江西] 网格图 ......
CF1485E Move and Swap 题解
不要什么脑子的带 \(log\) 做法。 思路 考虑 \(dp_{i,j}\) 表示红点到 \(i\),蓝点到 \(j\) 的最大权值。 那么有: \[dp_{i,j}=\max(dp_{fa_i,pre},dp_{fa_j,pre})+|a_i-a_j| \]其中 \(pre\) 是任意一个上一层 ......
Codeforces Round 907 (Div. 2) ABCF
Codeforces Round 907 (Div. 2)ABCF A. Sorting with Twos 题意:给你一个数组\(a_1,a_2,...,a_n\),你可以进行以下操作: 选择一个非负整数\(m\),并且\(2^m\le n\) 把\(1\le i \le 2^m\)的元素\(a_ ......
CSP-2019-S 题解
做了这套题,如果是让现在的我当时去考的话应该一共可以有 450 分,格雷码,括号树,树的重心都可以做,树上的数可以有 10 分,Emiya 至少可以有 76 分, 划分也可以有 64 分。看 OIerDB 上可以有 166 名的好成绩。 我的代码合集:洛谷 / 云剪贴板 [CSP-S2019] 格雷 ......
Codeforces Round 903 (Div. 3) ABCDE
Codeforces Round 903 (Div. 3)ABCDE A. Don't Try to Count 题意:复制\(s\)串若干遍,是否能在\(s\)串中找到\(t\)串。 思路:直接暴力,注意不要超限,会MLE // AC one more times // nndbk #includ ......
CF1428F Fruit Sequences 题解
使用了一种和大多数题解不同的做法。 虽然是带 \(log\) 的。 思路 首先考虑如何求一个固定左端点的答案。 我们发现,每个答案会随着右端点的递增单调不降。 而每个答案在增加时会形成若干个区间。 例如: 11101010111111 我们答案增加的区间即为: 11100000000111 可以发现 ......
CSP-S R2 T4 种树题解
\(First\) -大意: 给定一颗以 \(1\) 为根有 \(n\) 个节点的树,可以在每个节点上种一颗高度为 \(0\) 的树,每天可以选择一个未种树且与某个已种树的节点通过一条边连接的节点种树,每个节点 \(i\) 的树种下后第 \(x\) 天( \(x\) 从整个任务的第一天开始计算)会成 ......
luogu P1608 路径统计题解
update 2022.2.17 图炸了 update 2022.8.20 修改了一些错误 step 0 一些建议 做此题前建议先去做 P1144 最短路计数 并且建议使用 Dijkstra 算法去写,原因在 这个帖子 和 这个帖子 也感谢这位大佬的付出。 不然我就要拿SPFA写了。 step 1 ......
排队-题解
排队-题解 《排队》是一道很优美的贪心题(我不知道它的来源,估计其难度提高+/省选),曾被出在了计算概论B的考试中。本文的受众主要是学习计算概论的同学以及老师,不假定读者有信息竞赛(OI)经验。 题目描述 有 N 名同学从左到右排成一排,第 i 名同学的身高为 hi。现在张老师想改变排队的顺序,他能 ......
Codeforces Round 908 (Div. 2)
比赛链接 A. Secret Sport 题解 O(1 * T) 对于一场比赛,结束前谁最后赢就是谁赢 #include <bits/stdc++.h> using namespace std; string s; void solve() { int n; cin >> n >> s; cout ......
Educational Codeforces Round 157 D
tilian 不太会这种题 发现找到一个数就能确定整个序列 然后转而发现 前缀异或和 b1 ^ b2 = a1 b1 ^ b3 = a2 ... 我们发现要是n为偶数时能直接求出b1从而确定整个序列 而为奇数时我们无法确定b1 我们思考拆位之后 如果b1该位为0 算出真实的异或后的0 1 个数 b1 ......
CodeForces 852C Property
洛谷传送门 CF 传送门 NOIP 模拟赛 T1,小清新几何题。 要让选出的点组成的多边形面积最大,就要让正多边形的面积减去选出的点组成的多边形面积最小。而这个面积差可以表示成 \(2n\) 个三角形的面积,即 \(\sum\limits_{i = 0}^{2n - 1} S_{\triangle ......