题解1525f cf

[XOR Counting](https://www.luogu.com.cn/problem/CF1815D) 由于 a 可以为非负整数并且不关心 a 的具体数值,所以 m 大了后填很多 0 即可。 分类讨论。 m=1 时直接输出 n 即可。 m>=3 时,注意到 xor 运算与加运算同奇偶,所以 ......

[原题](https://codeforces.com/contest/1823/problem/E) [翻译](https://www.luogu.com.cn/problem/CF1823E) 前置知识：[SG函数](https://zhuanlan.zhihu.com/p/562117547) ......

设 $check_i$ 为 $1\sim n$ 中满足题意的数的数量。 显然答案为 $check_j-check_{i-1}$。 注意到 $check$ 能直接暴力求出来。 那么就可以先把 $10^6$ 范围内的所有质数求出来，然后所有数跑一遍，每个数都去旋转得出所有数后判断是否均为质数，记录下来。 ......

[原题](https://codeforces.com/contest/1823/problem/D) [翻译](https://www.luogu.com.cn/problem/CF1823D) 首先我们发现$c_i \leq x_i$一定有解，否则一定无解 因为我们考虑如果以$s_i$结尾出现了 ......

- 给定 $n$，求： $$\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}$$ - 思路分析： 先化式子： $$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}&= \sum_{d= ......

## A 考虑在所有 $0$ 前添加正号，在 $1$ 前轮流添加正负号即可。 ## B 首先根据抽屉原理，我们可以取出最多的颜色，个数记为 $mx$，然后其余颜色可以填在 $mx$ 的两两中间，最少要有 $(mx-1)(k-1)$ 个空位。 但是只是必要的，而不是充分的。考虑有多个最大值的情况，发现 ......

任取一颗 $\text{DFS}$ 树。 如果最大深度 $\geq\frac{n}{k}$，则找到了一条路径。 对于剩下的情况，我们按环去处理。钦定一个合法环中的“代表点”为 $k$ 个环中只出现过一次的点。 考虑让叶子作为环的代表点。我们寻找到了一些性质：由于树高 $ 点击查看代码 ``` #in ......

## 思路 刚拿到题，想了一些方法但都被推翻了，在这里列举出来，并给出反例： - 每次减去最小的因数，反例：$1024$ 等形如 $a^k$ 的数，每次都会减去 $a$ 导致 $a$ 的出现次数超过 $2$ 次。 - 每次减去大于等于 $\sqrt x$ 的因子，$x$ 为目前的数，并特判指数的情况 ......

## 思路 第一时间想到的是暴力，因为同一行的互不影响，所以第一行的 $1$ 一定都需要操作，然后把后续的状态更新，再操作第二行的所有的 $1$，但是很可惜是 $O(n^4)$ 的复杂度，必然会 TLE。 所以思考其他的办法，考虑到可以统计有多少操作更改了这个位置的状态，所以可以使用一个类似前缀和的 ......

## 思路 首先，给定了一个序列的首项 $a_1$ 和末项 $a_n$ 以及项数 $n$，要求构造一个严格递增，且差严格递减的序列。 因为是构造题，所以可以随便造，考虑差严格递减，所以从后往前构造比较合理。 因为严格递增，所以差至少为 $1$，所以 $a_{n-1}$ 就构造成 $a_n-1$，$a ......

## 思路 刚看懂题意时感觉很难，但是观察样例后，大胆猜测，$k$ 为偶数时，直接排序；$k$ 为奇数时，分奇偶位排序。 快速了写了程序，一交果然 AC。 其实很简单，这里给出证明： 首先，操作 $1$ 保证了奇数位和偶数位上的字符可以任意变动顺序。 然后，操作 $2$ 当 $k$ 为偶数时，可以改 ......

[problem](https://www.luogu.com.cn/problem/P3888) & [blog](https://www.cnblogs.com/liangbowen/p/17664121.html)。 这怎么评到紫上去的啊？差不多就个上位绿吧 /qd。 首先出题人非常 low。 ......

#### **[原题传送门](https://atcoder.jp/contests/arc080/tasks/arc080_c)** 题意：给定一个 $n$ 的排列 $a$ 和一个初始为空的序列 $b$。你每次需要在 $a$ 中选择一对相邻的数，把它们从 $a$ 中拿出来，并按原先的相对顺序插到 ......

# [HAOI2012] 高速公路 题解 [题目链接](https://www.luogu.com.cn/problem/P2221) 题目要求我们求期望，先考虑一下求期望的公式。 根据期望的定义得：期望费用 $E_v = \dfrac{所有可能路线的总费用}{所有可能路线的数量}$. 其中，所有可 ......

# CF840E In a Trap ## 题意 有一颗以1为根的树，每个点上有一个点权ai，每次询问路径u到v上最大的 $ai \bigoplus dist(i,v) $，保证u为v的祖先 ## 题解 有意思的题，之前考过一道类似的，那题场切了，这题不会。 首先我们将值域折半，将 $dis$ 产生 ......

[problem](https://www.luogu.com.cn/problem/P2238) & [blog](https://www.cnblogs.com/liangbowen/p/17663441.html)。 kkk 的题解有一些地方是错的 /cf，所以写篇题解造福后人。 一眼 DP， ......

[原题](https://codeforces.com/contest/1817/problem/A) [翻译](https://www.luogu.com.cn/problem/CF1817A) 降智题 用一个前缀和数组$s_i$记录前缀中满足$a_{i-2} \geq a_{i-1} \geq ......

[原题](https://codeforces.com/contest/1826/problem/F) [翻译](https://www.luogu.com.cn/problem/CF1826F) 一道很~~难想~~巧妙的交互题 首先如果他给出点的顺序是有序的，那我们显然可以问一个与$x$轴平行的和 ......

考虑质因数分解，我们求区间的 $lcm$ 就是 $\prod a_i$ 除以一些东西。 不难发现如果算 $x^k \in lcm$ 那么我们只能算一次，那么我们直接把这个东西挂在前一个出现的位置即可。 使用主席树维护即可。这个题，很难。 ```cpp // LUOGU_RID: 123092767 ......

[原题](https://codeforces.com/contest/1826/problem/E) [翻译](https://www.luogu.com.cn/problem/CF1826E) ~~傻卵~~$bitset$题 高位偏序，直接套CDQ分治显然不可行 但是解决高维偏序还有一种常见的 ......

[原题](https://codeforces.com/contest/1826/problem/D) [翻译](https://www.luogu.com.cn/problem/CF1826D) 这题乍一看不太好做，当时还想了单调栈或改变枚举顺序之类的做法，但都不可做 但仔细一想，我们发现答案的$ ......

## 题目描述 Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call inte ......

## CF1586 f1 f2 Korney Korneevich and XOR 思维+dp ### [题目链接](https://codeforces.com/problemset/problem/1582/F2) ### 题意： 给出长度为n的数组a，对于数组的严格递增子序列，计其异或和为xo ......

# [BJWC2010] 严格次小生成树 ## 题目描述 小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： ......

```cpp #include using namespace std; typedef long long ll; ll n,a[5000+10],b[5000+10],abpre[5000+10],absuf[5000+10],ans; int main(){ cin >> n; for(ll ......

## CF1385 F. Removing Leaves 换根dp ### [题目链接](https://codeforces.com/problemset/problem/1385/F) ### 题意： 给你一棵树，有一种操作，选择k个叶子，若叶子节点的父亲相同，则可删去这k个节点，问你最多能操作 ......

# P5629 【AFOI-19】区间与除法 题解 由于题目中的运算是除法，所以对于一个数字 $x$，最多运算次数不会超过 $\lceil\log_{d}x\rceil$ 就会变成 $0$。 然后我们就可以在 $O(n\log C)$ 的时间复杂度内算出来每一个数字能被哪些原数消灭。 这样处理询问仍 ......

前言 最近学了一种新的数位dp的状态表示，打算应用到以前做过的数位dp的题目。如果我们对数$N$进行数位dp，以前的状态定义$f(i,j)$表示所有数位大小为$i$且最高位是数字$j$的数的个数，如果还有其他约束条件那么再补充相应的状态即可。而新的状态定义则是$f(i,1)$和$f(i,0)$，其中 ......

[CF231E Cactus](https://www.luogu.com.cn/problem/CF231E) 点仙人掌的性质：每个点最多只在一个环里。  对于 $u,v ......

[销售基因链](https://www.luogu.com.cn/problem/P9196) ### 题目大意 给定 $n$ 个字符串，长度总和为 $m$，进行 $q$ 次询问，每次询问给定两个字符串 $p,s$，问所有的字符串中以 $p$ 为前缀且以 $s$ 为后缀的有多少个。 ### 思路分析 ......