| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 0 | 0 | 0 |
| C | 2 | 1 | 0 |
| E | 2 | 0 | 1 |
| F | 0 | 1 | 2 |
| G | 2 | 0 | 2 |
| I | 2 | 1 | 0 |
| J | 2 | 1 | 1 |
给定一个长度为 $n$ 的 $01$ 串 $S$，对每个 $i=1\sim n$，询问下述流程的结果：
首先不难发现对于固定 $i$，由于每次操作至少取出长度为 $i$ 的前缀，所以上述操作最多执行 $O\left(\frac ni\right)$ 次，所以总操作次数 $O(n\log n)$。
所以如果能 $O(1)$ 找到每次操作满足条件的前缀，即可 $O(n\log n)$ 解决此题。
首先考虑如何找到至少有 $i$ 个 $0$ 或者 $i$ 个 $1$ 的最短前缀，可以提前记录第 $k$ 个 $0$ 和 $1$ 的位置，分被为 $p(0,k)$ 和 $p(1,k)$。
于是可以 $O(1)$ 跳转。接下来在这个位置的基础上寻找满足 $0$ 的个数和 $1$ 的个数的差值不小于 $2$ 的位置。
如果当前位置已经满足条件，则已经找到前缀。否则假如当前位置的得分差为 $1$，则在移动一位，使得分差为 $0$ 或 $2$。如果是 $2$ 则也已经找到前缀。
接下来只需要考虑得分差为 $0$ 的情况，提前维护 $\text{next}$ 数组表示从得分相同到比赛结束的位置。
不难发现有 $\text{next}(i)=(s[i]==s[i+1])?(i+1):\text{next}(i+2)$，提前预处理后也可以 $O(1)$ 跳转。
给定一棵以 $1$ 为根的点权树，记第 $i$ 个点的原始点权为 $a_i$。每条边有一种操作符，可能为 $\text{OR},\text{AND},\text{XOR}$。
设路径 $u\to v$ 上的点权和操作符依次为 $p_1,e_1,p_2\cdots e_{k-1},p_k$，则路径的权重 $w(u,v)=p_1 e_1(p_2 e_2(\cdots (p_{k-2}e_{k-2}(p_{k-1}e_{k-1}p_k))\cdots))$。
定义 $\text{Tree}(u)$ 表示 $u$ 的子树，不包括 $u$ 本身。接下来若干询问，每次给定 $d,u$，将每个点的点权变为 $a_i+d\times i$，求
$$ \text{OR}_{v\in Tree(u)}w(u,v),\text{AND}_{v\in Tree(u)}w(u,v),\text{XOR}_{v\in Tree(u)}w(u,v) $$
注意，每组询问对点权的修改独立，即一个询问对点权的修改不影响另一个询问。同时有 $0\le d\le 100$。
发现 $d$ 很小，直接枚举 $d$，暴力树形 $\text{dp}$ 即可。设 $\text{dp}(u,0/1/2)$ 表示 $u$ 求 $\text{OR},\text{AND},\text{XOR}$ 情况下的答案，大力分类讨论即可。
注意权值直接运算时每个位是独立的，所以在讨论时可以只考虑权值是 $0/1$ 的情况，然后枚举 $u$ 是 $0,1$ 考虑一下即可。
例如，考虑边是 $\text{XOR}$ 的情况，计算下式
$$ (a_u\oplus v_1)|(a_u\oplus v_2)|\cdots (a_u\oplus v_k) $$
首先假设 $a_u=0$，得到 $(a_u\oplus v_1)|(a_u\oplus v_2)|\cdots |(a_u\oplus v_k)=v_1|v_2|\cdots |v_k=\text{dp}(v,0)$。
假设 $a_u=1$，得到 $(a_u\oplus v_1)|(a_u\oplus v_2)|\cdots |(a_u\oplus v_k)=(\sim v_1)|(\sim v_2)|\cdots |(\sim v_k)=\sim (v_1\And v_2\And \cdots \And v_k)=\sim \text{dp}(v,1)$。
于是有 $\text{dp}(u,0)|=((\sim a_u)\And \text{dp}(v,0))|(a_u\And (\sim \text{dp}(v,1)))$。注意 $\text{dp}(v)$ 不包含 $v$ 本身的贡献所以还有 $\text{dp}(u,0)|=a_u|a_v$。
总时间复杂度 $O(nd)$。
给定一个凸包，点按照逆时针给出，然后求凸包内一点，想要这个点与这个凸多边形相邻点组成的 $n$ 个角的最小值最大，求这个最大值。 $(4≤n≤100)$
赛场上两分钟出思路，然后看通过率…感觉是不是有坑就没敢写…赛后听说改数据了…血亏！
显然要二分（废话）。
然后对于每一组相邻的点，这个点和这两个点组成的角大于某个角，则这个点一定在这两个点组成的大弓形内，根据圆周角求 $n$ 个圆看面积交即可，然后比赛的时候猜到会有点跑到凸包外面的情况，但是我不会写圆的交再交凸包，这也是我怂了的原因之一，谁知道改数据嘛！
所以就是个板子题…
给一个大数的质因数分解形式，设为 $c$ ，并给出 $a$ 和 $b$ ，求最小的 $x+y$ ，使得 $lcm(a+x,b+y)=c$ 。 $(1≤n≤18)$ 代表质因子个数 ，保证因子幂次和相加不超过 $18$ ， $a,b,c≤10^{32}$ 。
类似于数位 $dp$ 。我们对每一个质因子进行枚举幂次，并且状压，位为 $1$ 代表这一个因子的幂次取满，不取满为 $0$ ， $dp[con]$ 代表这个压缩状态下的相对于 $b$ 的最小代价，也就是 $b$ 最少要补多少才能到这个状态。
于是我们跑出初始每个状态下的最小代价，但是还需要处理 $a$ 。我们把每一个末状态放进 $vec$ 里，然后看哪些比 $a$ 大，代价是存的 $v$ 值减 $a$ ，剩下至少需要满足 $(1<<n)-1-con$ 的状态，于是我们需要找一个无后效性的求状态数组的方法，就是让 $dp$ 数组变成至少满足这个状态的最小代价。再处理一下就好了
考虑枚举 $S=\{p_1,p_2\cdots p_n\}$ 的所有子集。
对每个子集 $T=\{a_1,a_2\cdots a_i\}$，强制令 $x$ 取 $\{p_1,p_2\cdots p_n\}-T$ 的每个素因子的最高次幂，强制令 $y$ 取 $T$ 的每个素因子的最高次幂。
这样，就消除了 $\text{lcm}(x,y)=c$ 的限制，接下来分别考虑 $x\ge a,y\ge b$ 的限制。
不难发现 $x$ 在 $a_1,a_2\cdots a_i$ 的幂次都是自由的，设 $x=t\cfrac {c}{a_1^{q_1}a_2^{q_2}\cdots a_i^{q_i}}$，因此需要找到最小的 $t\mid a_1^{q_1}a_2^{q_2}\cdots a_i^{q_i}$，且 $x\ge a$。
一种暴力解法为直接枚举 $a_1^{q_1}a_2^{q_2}\cdots a_i^{q_i}$ 的所有因子，最坏情况下 $c$ 有 $n$ 个因子，每个因子幂次均为 $1$。
此时时间复杂度等价于子集枚举套子集枚举的时间复杂度，可以认为是
$$ \sum_{i=0}^n {n\choose i}2^i=(1+2)^n $$
考虑一个优化，将 $a_1^{q_1}a_2^{q_2}\cdots a_i^{q_i}$ 平均分成两个序列，每个序列枚举因子，对一个序列的因子进行排序，然后另一个序列进行二分查找。
这样里层子集枚举的复杂度优化为 $O\left(n{\sqrt 2}^n\right)$，总时间复杂度为
$$ \sum_{i=0}^n {n\choose i}i{\sqrt 2}^i=(1+\sqrt 2)^{n+1} $$
给定一个长度为 $n$ 的序列 $A$，接下来有 $q$ 个询问。每次询问给定 $l,r,k$，求
$$ \sum_{i=0}^{k-1}f(l-i,r+i)(n+1)^i $$
其中 $f$ 定义如下
$$ f(l,r)=\max(\{k|\exists x\forall i(0\le i\le k-1\to \exists j(l\le j\le r,a_j=x+i))\}) $$
考虑回滚莫队处理询问，难点在于怎么维护最大的 $k$。
实际上，这等价于维护数轴上的最长连续线段。可以令 $\text{vl}(x)$ 表示以数 $x$ 为左端点的线段在数轴上的右端点。
$\text{vr}(x)$ 表示以数 $x$ 为右端点的线段在数轴上的左端点。于是只需要保证每条线段的两个端点的 $\text{vl},\text{vr}$ 正确性即可，不难 $O(1)$ 维护。
时间复杂度 $O\left(n\sqrt q+\sum k\right)$。