CF

题目链接 点击打开链接 题目解法 很不错的题 首先题目保证了一定有解，所以不用考虑奇怪的无解情况 从列中的数字种类入手 如果一列中有数字 \(c\) 恰好只有第 \(x\) 行存在，那么第 \(x\) 行一定在答案序列中 考虑选了第 \(x\) 行会牵连一些行不能选，那么把这些行去掉，继续跑上面的操 ......

题目链接：https://codeforces.com/contest/1910/problem/I 题意 有一个 \(n\) 个字符的字符串 \(S\)，你需要不断从中删除一个长度为 \(k\) 的子串，直到串的长度变为 \(n \mathbin{\rm mod} k\)，求能够产生的字典序最小的 ......

题意 给定 \(n\) 个递增数组。 \(k\) 次操作，每次你可以选择一个数组，使 \(ans\) 加上数组的第一个数，并删除。 问最大化的 \(ans\) 的值。 Sol 考虑当前选择的方案如何变得更优。 不难想到，如果当前有两个数组没有选满，则一定可以调整到其中一个变成空的方案，而使得答案不劣 ......

Optimizations From Chelsu 题意 给定 \(n\) 个结点的树，边有正整数边权 \(w_i\)。定义 \(len(u,v)\) 表示 \(u\) 到 \(v\) 的路径的边数，\(\gcd(u,v)\) 表示 \(u\) 到 \(v\) 的路径上所有边权的 \(\gcd\)， ......

题目链接：https://codeforces.com/contest/1916/problem/F 题意 已知点双连通的图 \(G = (V, E)\)。求一种划分方式 \(V = V_1 \cup V_2\)，使得 \(|V_1| = n_1\)，\(|V_2| = n_2\)，且 \(G\) ......

题目链接 点击打开链接 题目解法 很 \(nb\) 的字符串题 首先，\(x+y\) 是 \(s,t\) 的公共前缀，\(y+z\) 是 \(s,t\) 的后缀 所以如果 \(s,t\) 的最长公共后缀与 \(lcp\) 不交，那么无解，如果有解，则只留下 \(s,t\) 的最长公共后缀，因为前缀的 ......

好久没写题解了 思路 统计两个选手的分数，如果不是相同的就直接比大小，否则按字典序的大小，注意这里的字典序是两个选手的分数拼起来，比如样例 \(1\) 5 1 2 -3 -4 3 那么两个选手分别是 123 和 34。如果字典序相同，就看最后一个得分的选手是谁谁就赢。 代码 #include<ios ......

Problemset - Codeforces 考虑这些被释放的，值一定相同，并且等于区间gcd 于是用st表询问区间gcd，map套二分实现区间里某个数字出现次数 int n,a[100010]; int f[100010][20],lgn[100010]; map<int,vector<int> ......

ABC308 \(\operatorname{A}\sim \operatorname{F}.\) A 按题意模拟即可。 B 用 map 存一下即可。 C 考察 sort 的应用，但是胜率要开 long double 存。 D 因为 snuke 长度只有 \(5\)，所以可以记搜，设 \(f_{x, ......

鉴定为学 MO 学的。 MO 中著名的《数学奥林匹克小丛书高中卷》的第十五本曾经讲过，如果原方程较难解，可以考虑给左右两边同时对 \(M\) 取模，然后研究取模以后的问题，其中 \(M\) 为一个根据问题选取的适当的整数。 我们看见这个问题觉得很烦，因为大家都能发现这个条件给的相当于 \(d_i+d ......

这 3000？ 以下，\(\operatorname{op}(i)\) 代表对 \(i\) 进行一次操作。 我们考虑暴力。因为每一位都是分开处理的，我们考虑仅仅把一段区间的端点交换。即我们希望通过 \(\operatorname{solve(l, r)}\) 把 \(a_ia_j\) 交换而其他下标 ......

如果能想到这道题用随机化，想来这道题的解法就显然了。但是为什么这道题一定要随机呢？ 我们考虑一棵完美二叉树，编号随机。这棵树的熵毛估估一下应该是 \(O(\log^n n)\) 的，但是一次询问的话，考虑每次只能得到三个点的偏序关系为某几种情况的一种，这个熵是很小的，只有 \(O(\log n)\) ......

因为懒得用 bitset MLE 了。所以各位想 A 这题的别偷懒用布尔数组！ 本题解意在解释如何做类似的 dp 题，而不在于解释本道题做法的具体推导，只是给出一个思路。 我们观察发现，题目想让我们最小化一个最大值。我们并不能枚举每种方案去找最大值再取 \(\min\)，这样复杂度爆炸而且没有前途真 ......

不妨先考虑一个弱化版的问题，这个问题和原来的问题仅有一个区别：\(k\) 是给定整数。 称最后 \(n-k\) 个数是“特殊的”。那么我们可以注意到，每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列 \([7,5,8,1,4,2,6,3]\) 而且 \(k=2\)，那么极大段的下标应该 ......

题目链接 考虑拆贡献。 显然答案可以拆成对于所有 \(s_i\) 的每一个后缀的反串，作为前缀在所有串中的出现次数的加和。 这个东西字典树维护一下就行了。 不知道是谁考场上写哈希赛后被人对着模数卡掉了 点击查看代码 #include <bits/stdc++.h> #define FL(i, a, ......

Meaning 在二维平面内，有位置不同且不存在三点共线的 \(R\) 个红点和 \(B\) 个黑点，判断是否能用一些互不相交的线段连接每一个点，使得每条线段的两端都分别是黑点和白点。 Solution 当 \(R\ne{B}\) 时，显然无法实现红点与黑点的两两组合，故题干所述的情况一定不存在。 ......

第一章：我居然半小时内 AK 了一场 CF 比赛？？ 注意本篇文章纯属虚构，请勿对号入座 叮铃铃~一阵清脆的闹钟声响起，你揉着眼睛拍掉了放在床头响个不停的闹钟。你拿出手机，看了下时间，现在是2023年12月30号，22:20。作为一位优秀的 CPer，从这个时间点醒来是你常有的作息，你突然想起来今天 ......

对于这一类析合树问题有简单的线段树扫描线做法：考虑一个长为 \(len\) 的区间内一定有 \(len-1\) 个数值相邻的对，于是每次新加一个数 \(a_i\) 可以考虑相邻的两个数的出现位置 \(p\)，若 \(p\le i\) 就对 \([1,p]\) 区间加，表示左端点在 \([1,p]\) ......

题意 有 \(n\) 个人，\(m\) 对关系，要求每对关系中，有且仅有一个人给另外一个人送礼物，并且使送出礼物最多的人送的礼物尽可能少。并输出送礼物的方案。 Sol 二分答案，对于每个人向每个限制连 \(1\) 容量，每个限制向汇点连 \(1\) 容量。 Code array <pii, N> i ......

cf 918(D-G)div4 D.Unnatural Language Processing 算法分析:string模拟+贪心 贪心策略:把元音字母看作0,辅音字母作为1，因为是等价的,构造字符串，寻找a.find("101"),a.find("10");判断合理性,贪心选择101还是10,最后把 ......

思路 很不错的人类智慧题。 拿到以后，完全没有思路，看到数据范围，感觉是什么 \(n^2\log n\) 的逆天做法，但是又完全没思路，看后面的题感觉没希望，就在这道题死磕。 先打了个暴力程序，发现平方数太多，没什么规律，就拿了个 map 统计一下那些出现数字方案拥有的平方数比较多 程序如下： #i ......

思路 首先，我们可以考虑两个人会怎么操作，如果是选择了两个偶数和两个奇数，那么答案不会减小，如果选择了一个奇数一个偶数，那么答案会减小一。 所以想使答案大的人应该尽量选择前一种方案，想使答案小的人应该尽量选择后一种方案。 但这还不是最优的，想使答案大的人在可以选择两个奇数时，绝对不会选择两个偶数，因 ......

思路 看到题目要求求一个数 \(x\)，满足它的最大的两个因数分别是 \(a\) 和 \(b\)，并且规定一个数本身不是他的因数。 首先 \(x\) 需要是 \(a\) 和 \(b\) 的倍数，所以想到最小公倍数，如果不考虑最小公倍数等于 \(b\)，最小公倍数就一定是答案，因为最小公倍数是最小的满 ......

题意 给定一个序列，维护下列操作。 区间加 区间查询数中只包含 \(4, 7\) 数的个数。 所有数前后不超过 \(1e4\)。 Sol 块块版。 \(1e4\)，发现满足条件的数的个数只有 \(30\) 个。 对于每个块开一个桶，记录每种数有多少个。 查询时暴力枚举 \(30\) 个数，暴力判断即 ......

题意 给定一棵大小为 \(n\) 的树，有 \(k\) 个人，第 \(i\) 个人在节点 \(a_i\)。 从第 \(1\) 秒开始，依次操作第 \(1, 2, 3, \ldots, k, 1, 2, 3, \ldots, k, \ldots, k, \ldots\) 个人，把这个人移动到没有走过的 ......

CF1916B 分析 题目给出的是 \(x\) 的两个小于 \(x\) 的最大因子，首先考虑 \(a\) 不整除 \(b\) 的情况。既然 \(a\) 不整除 \(b\)，那么 \(a\times b\) 必定是 \(x\) 的倍数，但是此时 \(a,b\) 就不一定是最大的，所以需要除以一些东西， ......

题目传送门（CF） 题目传送门（luogu） 容易发现，选择两个偶数对于答案没有任何影响，因此先手必然会优先选择两个奇数合并在一起，而后手必然会优先选择一个奇数和一个偶数在一起，我们举个例子，有一个序列 \(\{1,1,1,1,1,1\}\)，先手先取编号为 \(1,2\) 的两个数，后手再取编号为 ......

Tree Queries Luogu CF1254D 题面翻译 给定一棵 \(N\) 个节点的树，有 \(Q\) 次操作。 \(1\ v\ d\) 给定一个点 \(v\) 和一个权值 \(d\)，等概率地选择一个点 \(r\)，对每一个点 \(u\)，若 \(v\) 在 \(u\) 到 \(r\) ......

Treeland and Viruses Luogu CF1320E 题面翻译 有一棵有 \(n\) 个节点的树，\(q\) 次询问（询问互相独立），每次给定 \(k_i\) 个颜色，每个颜色有一个起始点 \(v_j\) 和移动速度 \(s_j\)，每一个颜色在每一次操作中会使它周围没有被染色的连通 ......

CF1547E Air Conditioners 题目传送门 这道题我的思路严重劣于题解思路，所以请慎用 但是自认为我的贪心比dp好理解点 题意 有 \(q\) 组数据，每组第一排表示有 \(n\) 个方格和 \(k\) 个空调，第二排是每个空调的位置 \(a_i\) ,第三排是每个空调的温度 \( ......