favorite 1523f game cf

首先考虑无解的情况，很明显 $a_n$ 必须为 $0$，否则没有解，因为如果最后一位为 $1$ 那么必须有 $n$ 这个数存在于 $b$ 序列中，而这种情况时不符合题意的。 然后考虑如何求解，先考虑一种比较特殊的情况，就是若干个 $1$ 后面接着一个 $0$，这里假设 $1$ 的数量有 $k$ 个， ......

[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) ......

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

## 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$ 为偶数时，可以改 ......

[洛谷传送门](https://www.luogu.com.cn/problem/CF1864E "洛谷传送门") [CF 传送门](https://codeforces.com/problemset/problem/1864/E "CF 传送门") 感觉是很费脑子的题，可能是因为我没有脑子。 因为 ......

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

[原题](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 ......

```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个节点，问你最多能操作 ......

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

我 是 傻 逼。 先不管那个限制。如果有一个序列 $a$，怎么求答案？ 假设我们一个一个减，那么答案就是序列长度；但是，我们不一定会一个一个减：如果有 $x 点击查看代码 ```cpp #include #define int long long using namespace std; const ......

​ 洛谷P5937 [CEOI1999]Parity Game ​ 本来是想练习一下离散化的，结果看到这道又有并查集又有离散化的题，于是就逝了逝，在阅读题解后， 发现自己对并查集和离散化认识有点问题，于是写下这篇笔记总结一下。 看到这种给出几个条件判断矛盾的题，便想到了两种常见思路，一种是拓扑排序， ......

# Shadow Mapping (Games202) ## 2-Pass Algorithm ### Pass 1. Render from Light Pass1需要知道光线能照射到的点，也就是从光源所在的视角去渲染模型，有哪些是能被渲染出，哪些会被遮挡住而不被渲染。 ![16928508543 ......

[CF1830D](https://www.luogu.com.cn/problem/CF1830D) 贪心地想,黑白交替染色,这样每条大于1的路径的值都为2。但有些情况不优,树的形态是两棵子树中间由一条边相连,这样的最优方案是这条边上两点染1,其余点染0。 并且我们发现只用把每个同色连通块的贡献算 ......

[题目链接](https://www.luogu.com.cn/problem/P9580) 挺好的博弈论题，这是一个跟官方题解不太一样的做法。 遇到这种组合游戏可以先考虑逆推胜负，把握一下规律，我们先从一个区间的胜负判断开始入手。 考察区间中最后一个数字的从属关系，如果它属于弈，因为 $a_i>0 ......

[CF1763F Edge Queries](https://www.luogu.com.cn/problem/CF1763F) 圆方树板子题，~~这题真的有3000吗~~。 首先想到的是缩边双，但是以下情况边双不好处理： ![image.png](https://s2.loli.net/2023/ ......

记录一道昨天卡住的题[问题链接](https://codeforces.com/contest/1864/problem/C) 给你一个整数$n$，你可以进行最多$1000$次操作，使得$n$减去它的一个因数，要求每种减数至多出现两次 我们考虑先把$n$进行质因数分解，得到质因数序列$P$ $\{ ......

## 思路 首先特判特殊情况，若 $p_i$ 本身不可被 $q_i$ 整除，那么 $x_i$ 就直接取 $p_i$ 最大。 否则的话，$p_i=q_i\times k$。所以 $q$ 的质因数，$p$ 都有，并且数量一定大于等于 $q$ 的这个质因数的数量。 那么如果 $x_i$ 的某个质因数个数小 ......