题解860 div cf

显然这道题的解法与 \(8\) 强相关。从这一点下手，我们不难想到先对每一种奶牛做前缀和，这样我们可以做到 \(O(8)\) 查询每个区间是否可行，从而有了一个 \(O(4n^2)\) 的纯暴力做法。不知道多少 pts，反正不是正解。 下一步我们考虑优化。如果我们能快速地找到哪些区间是合法的，那么时 ......

远古模拟赛里的一道题，前来写篇题解记录一下。 我们考虑一个显然的转化。将每条边染色，那么原问题等价于求下面的染色的方案数： 对于每个点对 \(a,b\)，我们记 \(\operatorname{lca}(a,b)=c\) 有 \(a\sim c\) 上的所有边同色。 \(b\sim c\) 上的所有 ......

因为本题的代码难度远大于解法的思考，因此这里提供一种好写的写法。 做法不再赘述，就是转化为 \(depth\) 差以后上线段树分别维护两个信息以后求和。题解中大多数使用同一个线段树维护两个信息，可读性并不高，且比较难写。 事实上我们注意到两棵线段树仅有初始的信息不一样，剩下需要支持的操作完全一样，这 ......

省流：离线以后，每个字符做前缀和然后直接水过去 首先离线所有询问。对于每个英文字母，我们把查询这个字母的询问都一起处理。 对于每个字母 \(c\)，我们跑一遍前缀和，令 \(p_i\) 表示 \(\mathit{s}_{1,i}\) 中字符 \(c\) 出现的次数。接下来我们定义 \(\operat ......

前置知识：简要了解 CRT 和高斯消元 题意简述：给定一些系数，求 \(n\) 元线性同余方程组 \(A_i+\sum^{M}_{j=1}a_{i,j}x_j\equiv B_i(\mod 365)\) 的解。 注意到 \(365=5\times73\)，而且他们都是质数，这引导着我们思考先分别求出 ......

此题问 \(\operatorname{lcm}(a\sim b)\) 的后导 \(0\) 个数。 考虑 \(\operatorname{lcm}\) 相当于对唯一分解中的素数的指数取 \(\max\)，此题等价于： 定义 \(\operatorname{g}(x,y,z)\) 在 \([a,b]\ ......

题目链接 考虑拆贡献。 显然答案可以拆成对于所有 \(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，从这个时间点醒来是你常有的作息，你突然想起来今天 ......

P5765 [CQOI2005] 珠宝 题解 思路 好题，注意到有性质：颜色数最多为 \(\lfloor\log_2 n\rfloor + 1\)，有了这个性质之后直接树形 DP 糊上去就过了。 简要的证明： 考虑一个点，显然一种颜色即可。 对于一个颜色为 \(c\) 的点，其儿子至少有 \(c - ......

这套题感觉质量很高 A.Battle \[x \equiv r(\bmod P) \]\[P \mid x - r \]因此只有第一次操作是有效的 void solve() { int n, m, p; cin >> n >> m >> p; m -= m % p; if(!m) puts("Ali ......

对于这一类析合树问题有简单的线段树扫描线做法：考虑一个长为 \(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,最后把 ......

题目传送门 前置知识 二分答案 | 并查集 解法 对条件的合法性判断其他题解已经讲得很明白了，这里不再赘述。这里主要讲一下用并查集实现黑白染色问题。 以下内容称被覆盖为黑色，不被覆盖为白色。 本题因为是单向染色，即从白到黑，故可类似 luogu P1840 Color the Axis 和 D 的并 ......

思路 很不错的人类智慧题。 拿到以后，完全没有思路，看到数据范围，感觉是什么 \(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\) 的两个数，后手再取编号为 ......

title: Codeforces Round 918 (Div.4)刷题 type: "tags" Codeforces Round 918 (Div. 4) A.Odd One Out // Problem: A. Odd One Out // Contest: Codeforces - Cod ......

Question 杭州电子科技大学2023新生赛 G 逃离节奏面 题太长自己看吧 Solution 考虑到如果走了几步后走到了相同节奏面的相同点是没有意义的，所以直接 BFS ，对于走过的节奏面的哪个点不需要走就能刷出最短路了 实际上实现的时候细节很多，要注意一下 Code #include<bit ......

Question 杭州电子科技大学2023新生赛 E 树 给定一颗包含 \(n\) 个节点的带边权的树，定义 \(xordist(u,v)\) 为节点 \(u\) 到 \(v\) 的简单路径上所有边权值的异或和 有 \(q\) 次询问，每次给出 l r x 求 \(\sum_{i=l}^r xord ......

Dashboard - Codeforces Round 918 (Div. 4) - Codeforces from collections import * def solve(): a, b, c = list(map(int, input().split())) hs = defaultdi ......

省选题解第一发～ 【省选联考2020】树 我和这道题还挺有缘分的。 有一次看大佬的省选游记（不知道是哪一年），然后提到有一道是01trie整体加一，当时我就印象深刻，然后在 oiwiki 上看了一下，心想这整体加一也只能从低位到高位维护 01trie 啊，又不能查询最大值，有什么卵用（划掉）。 这是 ......

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\) ,第三排是每个空调的温度 \( ......