tripartite complete 1228d cf

## 思路 对于每次操作，会把序列分成两个部分，两部分之间不会排序。 考虑仅每次排一个数字，理由如下： 假设已经排好了 $1,2,3\cdots i-1$ 的顺序，对于数字 $i$，如果 $i+1$ 在该数字的前面，那么 $k$ 应选择为 $i+1$，这样才能排好 $i$ 和 $i+1$。如果选择的 ......

## 思路 乍一看，感觉无从下手，于是就先列举了几个例子： ``` 02 10 21 02 013 201 320 132 013 12345 01234 50123 45012 34501 23450 12345 ``` 容易发现周期是 $n+1$，下面解释理由： 首先因为数量 $n$，且两两各不 ......

## 思路 首先考虑保证每行的黑白数量一样，横着的一定是贡献一黑一白，所以只用考虑竖着的，同理竖着的任何方案也不会影响横着的要求。 因为两个同行的竖着的颜色可以互换，所以在满足条件的情况下，谁黑谁白无所谓。 考虑从上往下满足，因为 ```D``` 的格子已经在上一行中确定了，所以可以在上一行时就先把 ......

题意：给定一个物品序列。每个物品有 $m$ 种属性和一个收益（第 $i$ 个物品的第 $j$ 种属性为 $r_{j,i}$）。你需要从原序列中取出几个物品（可以乱序取），并给这些取出的物品安排顺序，使得新的物品序列满足：对于任意 $i,j[i 点击查看代码 ``` #include #define ......

**题目大意：** 数组$a$长度为$n$，数组$b$长度为$m$，构造数组$c$满足$c[i]=a[i]\&b[j]$,求数组$c$按位或的和的最小值。 *** 设题目的答案为$ans$。 由于数组$a$和$b$的元素值小于$2^{9}$，所以数组$c$元素和$ans$在二进制表示下最多为$9$位 ......

## A.Morning Sandwich ### 题目描述： 吃货小 C 喜欢三明治，他有三种材料：面包、芝士、火腿。正确的三明治组合应为一层面包和一层芝士或火腿之一轮流放置，以面包为结尾，例如面包-芝士-面包-火腿-面包就是合法的三明治。 给定每次做三明治的材料：$ b $ 面包，$ c $ 芝 ......

一、题目描述： 给你一个长度为 $n$ 模板串 $S$ 以及 $m$ 个匹配串 $T$。 $q$ 次询问，给定 $l,r,L,R$，询问 $S_l\sim S_r$ 在 $T_L\sim T_R$ 中出现次数最多的字符串编号以及最多的出现次数。 注意，若有多个出现次数最多的字符串，取编号最小的那一个 ......

**题目大意：** 给出$n(1\le n\le2\times 10^{5})$个三元组$(t,a,b)(0\le a,b\le 1)$，选出其中任意个，使得被选中的元素$a$、$b$的总和均为$k$，求$t$总和的最小值 *** 因为被选中的元素$a$、$b$的总和均为$k$，所以被选中的三元组中 ......

# 打cf的时候用unordered_map防止被hack可以重新自定义哈希函数 ## 第一种 ``` struct custom_hash { static uint64_t splitmix64(uint64_t x) { x ^= x > 7; x ^= x > 30)) * 0xbf5847 ......

# CF1864C Divisor Chain 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1864C) [Codeforce](https://codeforces.com/problemset/problem/1864/C) ## De ......

## 题意 给定一个整数 $x$，定义一个操作： > 选择一个 $x$ 的因数 $d$，把 $x$ 修改为 $x-d$。 限制相同的 $d$ 值不能选择超过 $2$ 次，需要在最多 $1000$ 次操作内把 $x$ 操作至 $1$，求操作序列。 （$1 \le x \le 10^9$）。 ## 题解 ......

# CF1864B Swap and Reverse 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/CF1864B) [Codeforces](https://codeforces.com/problemset/problem/1864/B) # ......

## 题意 给定一个长度为 $n$ 的字符串 $s$ 和一个正整数 $k$，每次可以进行如下两种操作当中的一种（字符串下标从 $1$ 开始标号）： - 选择 $i \in \left[1, n - 2\right]$ 并交换 $s_i$ 和 $s_{i + 2}$； - 选择 $i \in \lef ......

> 给定一棵树与两个序列 $a\set{n}$ 与 $b\set{n}$，定义 $R\left(u\right)$ 为节点 $u$ 的祖先集合，节点 $u$ 的权值定义如下： > > $$\left| \sum_{i \in R\left(u\right)} a_i \right| \times \ ......

赛场上思路出来了但是代码没调出来。 首先考虑右端点，很明显，要让操作后的序列字典序尽量地大，那么就要使操作后的序列第一个数尽量地大，考虑 $n$ 或 $n-1$，如果 $n$ 在原序列的第一个位置，那么此时无论怎么调整都无法使得它在新序列的第一个位置，此时就要考虑让 $n-1$ 在新序列的第一个位置 ......

首先把式子拆一下，可以知道 $x-i \ge |y-j|$ 等价于 $x-y \ge i-j$ 和 $x+y \ge i+j$，注意到每次操作 $(i,j)$，影响到的点 $(x,y)$ 均要满足 $x>i$，那么我们每次就必须要按照从上往下的顺序进行，否则上面的点无法影响到，即从第一行开始操作。 ......

注意到交换操作，无法改变下标的奇偶性，因此只能通过考虑翻转操作改变。注意到如果 $i$ 是奇数，那么要令 $i+k-1$ 为偶数的话 $k$ 必须为偶数，若 $i$ 是偶数，要令 $i+k-1$ 是奇数的话，$k$ 也应为偶数，而 $k$ 为奇数的情况翻转了也无法改变奇偶性。 因此通过 $k$ 的奇 ......

先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 $k$，那么最后就要减去 $d \times k$。 得出这个性质之后开个小根堆反悔贪心即可，首先 $a_i0$ 的，如果还没到 $m$ 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最 ......

首先考虑无解的情况，很明显 $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$ 为偶数时，可以改 ......

# 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 ......