题解1203 div cf
CF1886
A 给你一个正整数 \(n\),问是否存在 \(3\) 个正整数 \(a,b,c\) 满足 \(a+b+c=n\) 且 \(a,b,c\not\equiv 0 \pmod{3}\)。 分类讨论: 如果 \(n \not\equiv 0 \pmod{3}\) :若 \(n\le 5\) 则无解,否则可 ......
【题解】AtCoder-ARC167
AtCoder-ARC167A Toasts for Breakfast Party 一定不会有空盘,问题转化成 \(2m\) 个数,其中 \(2m-n\) 个是 \(0\),这样一定是最大值和最小值一起,次大值和次小值一起,以此类推。 提交记录:Submission - AtCoder AtCod ......
CF1119F Niyaz and Small Degrees 题解
原题 翻译 首先 \(O(n^2 \log n)\) 的 dp 是 simple 的,我们设 \(dp_{i,0/1}\) 表示以 \(i\) 为根, \(i\) 到 \(fa_i\) 这条边删/不删的最小权值和。转移是一个非常 trick 的问题,只需要假设所有都选 \(dp_{i,0}\) ,然 ......
CF27D Ring Road 2
好一眼的题,据说出题人给的做法不是2-SAT,因此才会有这样的数据范围,但这个模型yysy实在是太典了啊喂 不难发现每条边的取法就是两种,并且内部和外部的边之间绝对不会相交,因此考虑使用2-SAT模型 枚举两条边\(i,j\),如果\(i,j\)同时放在一边会产生冲突,就钦定两者的状态必须相异,然后 ......
CF553C Love Triangles
很有意思的一个题,想了一会才发现解题的关键 首先我们注意到对于某个大小\(\ge 3\)的连通块,其实连通块内的所有边的颜色都会被已知的边唯一确定 而不同的连通块间的连边方式有两种,因此设连通块个数为\(tot\),最后的答案就是\(2^{tot-1}\) 但还要考虑判掉不合法的情况,注意到不管是\ ......
CF1108F MST Unification
很丁真的一个题,权当复习下树上倍增的写法了 考虑先给图求出一个MST,那么很容易发现对于每条非树边\((u,v)\),它的权值必须严格大于MST上\(u,v\)之间所有边的权值,否则就可以用这条非树边来替换某一条树边 因此直接倍增维护树上两点间最大边权即可,复杂度\(O(n\log n)\) #in ......
Codeforces Round 896 (Div. 2) A. Make It Zero
给一个大小为 \(n\) 的数组 \(a\) \((n \geq 2)\) 。你希望进过一些操作使得 \(\forall i, a_i = 0\) 。 在一步操作中,可以选择 \(1 \leq l \leq r \leq n\) 并且执行: \(s = \bigoplus_{i = l}^{r} a ......
CF549B Looksery Party
这些题都是上周五写的了,周末两天因为比赛都没来得及写博客,只能到周一来补一补 这题做法很简单,考虑如果当前状态中\(\{a_i\}\)不含有\(0\)的话就已经得到一组合法解了 否则我们找到某个\(a_i=0\)的点,钦定让\(i\)这个人去派对即可,这样一定可以满足\(i\)这个人的条件,同时更新 ......
Educational Codeforces Round 153 (Rated for Div. 2) A. Not a Substring
给一个长度为 \(n\) 的括号字符串 \(a\) 。你需要构造一个长度为 \(2n\) 的合法括号字符串 \(b\) ,且满足 \(a\) 不是 \(b\) 的子串。或者回答不可能。 显然若 \(a = ()\) ,则一定不可能构造出 \(b\) ,否则可以。 观察到合法括号穿串中, \(()() ......
Codeforces Round 635 (Div. 2) B. Kana and Dragon Quest game
你需要击败一只巨龙,他有 \(h\) 点血量,你可以使用以下两种攻击方式: 黑洞:使巨龙的血量变为 \(\lfloor \frac{h}{2} \rfloor + 10\) 。可以使用 \(n\) 次。 雷击:使巨龙的血量变为 \(h - 10\) 。可以使用 \(m\) 次/ 当巨龙的血量 \(h ......
P9745 「KDOI-06-S」树上异或 题解
P9745 「KDOI-06-S」树上异或 题解 \(x_i = 0\) 这题一看就不是很可做,先考虑部分分。 对于一条链的情况,我们可以枚举上一个断边的位置,然后转移。 一看数据范围,估计和值域有关,所以考虑 \(x_i = 1\) 的部分分,如果全部点权都是 1,那么一种方案只有 0 和 1 两 ......
[ARC167D] Good Permutation 题解
题意 对于一个长度为 \(N\) 的排列 \(Q\),定义其为好的,当且仅当 对于任意整数 \(i \in \left[1, N\right]\),在进行若干次操作 \(i \leftarrow Q_i\) 后可以得到 \(i = 1\)。 给定一个排列 \(P\),定义一次操作为交换两个数。定义 ......
Codeforces Round 633 (Div. 2) A. Filling Diamonds
给定一个正整数 \(n\) ,询问有多少种方式填充满图中 \(4n - 2\) 的图。 你可以使用的菱形:竖着摆放和横着摆放都是一种方案。 显然选择某个位置竖着摆放,其他所有地方只能横着摆放,这样的位置有 \(n\) 个。 具体图形见:https://codeforces.com/problemse ......
Codeforces Round 637 (Div. 2) - Thanks, Ivan Belonogov! A. Nastya and Rice
纳斯塔亚掉了 \(n\) 个谷物,每个谷物的重量范围在 \([a - b, a + b]\) 。她猜测谷物的总重量范围在 \([c - d, c + d]\) 。询问她的猜测是否正确。 显然,若 \([n(a-b), n(a+b)]\) 和 \([c - d, c + d]\) 有交,则她的猜测正确 ......
Codeforces Round 641 (Div. 2) A. Orac and Factors
定义 \(f(x)\) 为 \(x\) 的 \(> 1\) 的最小因子。 给一个正整数 \(n\ (n \geq 2)\) 。对它执行 \(k\) 次操作:每次让 \(n = n + f(n)\) 。询问 \(k\) 次操作后 \(n\) 的值。 在唯一分解定理下观察 \(n\) :偶数的最小非 \ ......
Codeforces Round 636 (Div. 3) A. Candies
\(vv\) 有 \(n\) 个糖果,\(vv\) 记得这些糖果是按如下方式购买的: 第 \(i\) 天买了 \(2^{i - 1}x\) 个,总共买了 \(k\) 天,\(k > 1\) 。 但是 \(vv\) 忘了 \(x\) 是多少,询问任意一个满足条件的 \(x\) 。保证给出的 \(n\) ......
UVA12046 题解
前言: 有些虚高,建议降蓝。感觉比 CF55D 要简单。 题目大意: 定义一个数为好数,满足以下要求: 每个数位都能整除原数。 每个数位都小于等于 \(6\)。 求长度为 \(n\) 的好数有多少个。 思路: 首先,\(0\) 整除任何数都没有意义,可以不枚举。其次,要满足条件二,所以每个数位可以只 ......
UVA1366 Martian Mining 题解
这个题可以用动态规划解决。 令\(sbe_{i,j}\) 为第 \(j\) 列 \(1\) 至 \(i\) 个格子 \(BE\) 矿总和,令\(snw_{i,j}\) 为第 \(i\) 行 \(1\) 至 \(j\) 个格子 \(NEW\) 矿总和。 \(dp_{i,j,0}\) 表示为以第(\(i ......
CF1873E Building an Aquarium 题解
这题看到第一眼就是二分。 单调性 二分最关键的东西是单调性在哪。单调性是如果高度越高,需要的水就越多,高度越矮,要用的水越少。 不难得出代码: check 函数: int check(int mid){ int sum=0; for(int i=1;i<=n;i++){ sum+=max(0ll,m ......
P8854 [POI2002] 超级马 题解
这题其实就是搜索,不知道怎么评绿的。 题意 有一个大小无限的棋盘,有一只马,给定 \(n\) 种跳法,判断马是否能跳到棋盘所有点。 题解 搜索马是否可以跳到他上下左右的四个点,因为只要能跳到这四个点,就可以以这四个点为基础跳到其他所有的点。 这里有一些细节需要处理: 因为每次操作能是横纵坐标加减 1 ......
CF1870E Another MEX Problem 题解
原题 翻译 首先 \(O(n^3)\) 的 dp 是 simple 的。设 \(dp_{i,j}\) 表示前 \(i\) 个划分后异或和为 \(j\) 是否可行。因为转移不具有连续性,故bitset无法优化(其实 \(O(\frac{n^3}{\omega})\) 也跑不过去) 官方做法: 定义对于 ......
CF863C 1-2-3
わたしが命を賭けるから あげるから
あなたは時間をくれたのでしょう?
あらゆる望みの総てを叶えたら ああ果たせたら
あなたに会いたい
星に願いをかけて ......
题解 AcWing 1272. 与众不同
题目描述 定义完美序列:若一个序列内没有重复的数,称这个数列为完美数列。 每次给定一个区间 \([l,r]\),求这个区间内最长的完美序列长度。 具体思路 设 \(len_i\) 表示从 \(i\) 出发往右的最长完美序列长度。 我们定义一个指针 \(st\),表示当前枚举的区间左端点,同时定义多一 ......
Educational Codeforces Round 87 (Rated for Div. 2) A. Alarm Clock
你总共需要睡满 \(a\) 分钟,第一个闹钟将会在第 \(b\) 分钟的时候响起。如果你醒来的时候睡眠不足,你会将脑子往后调 \(c\) 分钟,然后你需要 \(d\) 分钟的时间进入睡眠。假设第 \(0\) 分钟时你刚进入睡眠状态。 询问你最快能的起床时间,或者说明这是不可能的。 若 \(a \le ......
Educational Codeforces Round 90 (Rated for Div. 2) B. 01 Game
\(Alice\) 和 \(Bob\) 在玩一个 \(01\) 游戏,一开始有一个 \(01\) 串 \(s\) 。\(A\) 先开始,两人轮流操作。在每一步操作中,玩家可以选择 \(s\) 中两个相邻的不同数并且将他们删除。最后不能删数的玩家将失败。询问 \(Alice\) 是否可以获得胜利。 首 ......
[CF1137C] Museums Tour 题解
[CF1137C] Museums Tour 题解 首先看到 \(d\le 50\),考虑拆点。 把一个点拆成 \(d\) 个点,分别代表到这个点的时候是周几。 然后对于一条有向边,每一天向出边的下一天连边。 这样观察发现,如果两个点在同一个强连通分量内,那么它们可以无限转圈,也就是说,只要到达了一 ......
Codeforces Round 653 (Div. 3) B. Multiply by 2, divide by 6
给一个正整数 \(n\) ,每一步可以让 \(n\) 除以 \(6\) 或者让 \(n\) 乘以 \(2\) 。询问进过多少次操作可以使得 \(n\) 变为 \(1\) 。或者回答不可能。 在唯一分解定理下观察 \(n\) 。 如果 \(n\) 除以 \(6\) ,则 \(2^{\alpha_1}3 ......
ARC167D Good Permutation 题解
题意 给定一个长度为 \(N\) 的排列 \((P_1,P_2,\cdots,P_N)\)。称一个排列 \(P\) 为“好排列”当且仅当对于所有 \(1\leq x\leq N\),都能通过不停地使 \(x\leftarrow P_x\) 将 \(x\) 变成 \(1\)。 通过最小次数操作将 \( ......
Educational Codeforces Round 91 (Rated for Div. 2) A. Three Indices
给一个 \(n\) 个整数的排列 \(p_1, p_2, \cdots, p_n\) ,需要找到三个数 \(i, j, k\) 满足: \(1 \leq i < j < k \leq n\) \(p_i < p_j\) , \(p_j < p_k\) 否则回答不可能。 \(key\) :若存在上述 ......