CF

理解很困难，但是代码真的很简单。祝贺我过了我做的第一个有关置换的题目。 problem ~~已经不是能简化的东西了~~ 一位科学家正在研究一个自我生长的长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$。 排列每天都会变化，每一天，元素 $x$ 都会变成 $a_x$，即 $a_x$ 会 ......

给你一个长度为n的数列a和整数c 你需要把它任意分段 每一段假设长度为k，就去掉前[ k/c] ( 向下取整)小的数 最小化剩下的数的和 #include<iostream> #include<algorithm> #include<cstring> #include<queue> #define ......

简要题意 给出一个三个正整数 $n,m,k$ 和一个长度为 $n$ 的序列 $a$。 有 $m$ 个询问，每个询问给出一个区间 $[l,r]$。求这个区间内有多少个子区间异或和等于 $k$。 允许离线。$1 \leq n,m \leq 10^5,0 \leq a_i,k \leq 10^6$。时间限 ......

题目链接：https://codeforces.com/problemset/problem/1295/E 题目大意： 将排列 $p_1, p_2, \ldots, p_n$ 先分成 $p_1, \ldots, p_k$ 与 $p_{k+1}, \ldots, p_n$ 两个集合。 然后可以将元素从 ......

CF1366E Chiori and Doll Picking 位运算和 __builtin 函数记得开 long long！！！！！ 这题很厉害。 记 $p(x) = \operatorname{popcount}(x)$，$\operatorname{span}(B)$ 表示 $B$ 张成的线性 ......

problem 一个长为 $n$ 的序列，每一个数是 $[0,k)$ 的整数。说一个数列幸运，当且尽当 $\exists i$ 使得 $a_i\equiv(\sum_j a_j)-a_i\pmod k$，求方案数，$n\leq 10^{18},k\leq 2000$。 引理：若钦定数列的和为 $s$ ......

题目分析： 感觉这个题目难度适中，而且换根 $dp$ 的过程相当好写并且很 educational，所以就当作换根 $dp$ 的典例，来讲讲换根 $dp$ 到底是个啥吧。 换根 $dp$ 其实就是用来解决：树上询问以每个点为根的相关信息，以指定某个点为根的时候信息很好求解，在换根的时候只会影响极少点 ......

题目分析： 因为要对每个点都进行求解，所以可以考虑换根 $dp$。 也就是我们先想想若给定根，怎么求解，我们发现点 $u$ 若可以走到某一个黑色点，当且仅当它的某一个儿子可以走到这个黑色点且它可以走到它的儿子，而他能走到它的某一个儿子节点并经过儿子节点继续走，当且仅当它这个儿子的子树内有大于等于 $ ......

首先，我们考虑枚举所有的 $a_i$ 的和 $sum$。如果 $y$ 可以满足条件，那么 $y\equiv sum-y(\bmod k)$，也就是 $2y\equiv sum(\bmod k)$ 然后考虑有多少种可能的答案。我们发现，当 $k$ 是奇数的时候，$y$ 有唯一解。当 $k$ 是偶数的时 ......

~~都要考省选了大脑还在这里下线~~ 场上看到这道题很快推出了 $k$ 为奇数的搞法，发现可以直接做到 $O(k\log n)$，一阵狂喜然后肝起了 E3，结果 E1 都没过。 事实上这道题可以直接做到 $O(\log n)$，不过需要细致的观察自己场上推的式子。 题意： 对长度为 $n$，值域为 ......

我忘记了今天有阳间 CF，所以就开打的很晚，所以只是说一下做法，代码实现....还是算了吧。 但是我也看了，我的思路其他的人都有写，所以这个做法正确性没问题。 A.Lucky Numbers 题目分析： 加不超过 $100$ 次，一定会有 $0,9$ 同时出现的情况，所以直接暴力做没问题。 C.Un ......

一、题目描述： 给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 的子树中到 u 距离为 x 的节点数。对于每个点，求一个最小的 k，使得 d(u,k) 最大。 二、做题思路： 很明显是一个线段树合并的题，但是线段树里面放什么呢？设当前节点为 u，如果放的是距 u 距离为 x 的点的数 ......

摘要:为了制备低膨胀、高强、轻质复合材料,采用模压法制备了ZrW2 O8-Cf/E51复合材料,并研究了超声时间对其微观组织、热膨胀行为和极限抗拉强度的影响。结果表明 : 在制备过程中颗粒团聚后容易受到纤维单丝阻挡并在纤维束表面聚集。在 20 min之内,延长超声时间会减少ZrW2 O8颗粒团聚。随 ......

CF1770F Koxia and Sequence 题目链接。 $\text{difficulty}={\color{red}6},1$。 $\text{tags}=组合数学,子集反演,容斥原理,二进制$。 神仙题。 首先进行观察。由于计算式与每个数在那个位置无关，所以每个位置都是相同的。 可以将 ......

题目链接：https://codeforces.com/contest/1809/problem/G 题解： 一道很强的 dp 首先翻译条件：predictable 是什么意思？发现就是对每一个下标，前缀 max 和下一个位置至少差一个 $k+1$ 看到 $n \leq 10^6$，可以猜测最后应该 ......

1 /* 2 _ooOoo_ 3 o8888888o 4 88" . "88 5 (| -_- |) 6 O\ = /O 7 ____/` '\____ 8 .' \\| |// `. 9 / \\||| : |||// \ 10 / _||||| -:- |||||- \ 11 | | \\\ - ......

思路: 关键是操作2的性质: 随机找->找一个路径最长的点 操作1,阻止建边顾名思义, 发现和最短路很想, 从n到每一个点的权值嘛 改变权值更新方式, 边的权值为: val[i]+前面那个点是第几大的, (这里每一个出度的点都要算) ->满足题目要求 然后 这个第几大,利用出度来优化, 更新一个后就 ......

思路: 关键性质是赋值是由跟到某个点,然后权值是不减序列 从叶子节点进行回推, 由于是不减序列,而且为了然后父亲节点能够白嫖,于是让儿子节点的权值尽量大就行了, 然后就看父亲点能不能白嫖, 不能操作就+1. ......

题目链接：http://codeforces.com/problemset/problem/429/D 题目大意： 给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。 用 $s$ 表示 $a$ 的前缀和数组，即 $s_i = \sum\limits_{j = 1}^i ......

来翻译一下 cf 评论区一老哥的证明。 首先问题可以转化为选出 $k$ 个长为 $l$ 的区间使得覆盖的 $1$ 个数最多。 不妨设 $kl\le n$，设选 $k$ 个区间最多能覆盖 $f_k$ 个 $1$，显然存在一种最优方案使得区间两两不交。 下面证明 $f_{k+1}\ge \frac{f_ ......

给出x和y，求一个长度为y的序列，其乘积为x，允许有负数，求这种序列的个数， x分解质因数，考虑每个 p^e, 把e分为y 份( 可以为0），个数为 C( e+y-1,e) 这题需要乘法逆元 来进行乘法 #include <iostream> #include <cstring> #include ......

给你对于任意一个 ai,bj 的大小关系的判断，让你构造 a,b 序列满足条件。无解输出No 拓扑排序+并查集 #include <iostream> #include <cstring> #include <queue> using namespace std ; const int N=4000 ......

A - Showstopper #include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while (t--) { int n,a[110],b[110]; scanf("%d",&n); f ......

题目链接：http://codeforces.com/problemset/problem/768/B 解题思路： 分治。 本题和 的解题思路相似。 tips：如果如果 $n$ 对应的区间完全被 $[l, r]$ 覆盖了，则区间 $[l, r]$ 范围内的所有数字和为 $n$。 示例程序： #inc ......

题目链接：http://codeforces.com/problemset/problem/743/B 题目大意： 对于一个 n-序列，如果 n==0 ，那么它是一个空的序列（也就是说空序列中没有元素）。 然后会进行 i 次操作，每次操作，会在原序列末尾添加一次原序列，并且在两个原序列之间插入一个值 ......

给一些单词，它们可能是同义或者反义，给出一些关系定义，从前面的定义开始建立关系，如果有的关系定义和之前的冲突输出NO,否则输出YES。 然后查询q次单词x和单词y的关系。 扩展域并查集 1~n 存朋友，n+1~2n 存敌人 #include <iostream> #include <map> usi ......

题面传送门 还是见识太少了。 直接算颜色个数不好算，因为是和式，所以考虑计算某个颜色的贡献。 对于某个时刻，有一些位置是当前时刻，那么设所有没有这些位置的联通块平方和为 $S$ ，则贡献为 $n^2-S$。 因为总共有效的修改只有 $O(m)$ 个，因此我们需要支持：改变一个点的状态，查询为 $1$ ......

需要构造一个符合如下条件的字符串： 长度为 n，并且只包含字符 1∼m (n≤1e15,m≤52) 满足 K 个要求，第 i 个要求为 xi 后面不能是 yi 现在问你，有多少种字符串符合条件。 F[ i ][ j] += F[i -1] [lk ]* a[k][j] 用矩阵快速幂优化 即 F[1] ......

脑筋急转弯 https://leetcode.cn/problems/minimum-impossible-or/ https://leetcode.cn/problems/minimum-score-by-changing-two-elements/ 1200 找规律？ https://codef ......

CF1806F GCD Master Div. 2 的 2900，还是非常有难度的，看了题解才有思路。 这题是一个结论题，我们一步步来观察。不难发现每次操作相当于合并两个已经操作的集合，那么最终的问题就是把序列划分成了 $(n-k)$ 个集合。 结论一：考察最小值所在的集合 $S_0$，假设从小到大 ......