杂题LIST

本文章用于记录菜鸡 $\texttt{CXY07}$ 做到的一些有趣的题目。

链接尽量丢 $\texttt{Luogu}$ 的，统一起来。

由于文章太长了，所以改成索引。

CF662C Binary Table

给定一个 $n \times m$ 的 $01$ 矩阵，现在可以无限次对某一行或一列的每个数字取反，求最少的 $1$ 的个数。
$n \le 20\ ,\ m \le 10^5$

YACS 棋盘 & CF526F Pudding Monsters

有一个 $n \times n$ 的正方形，每行每列都恰好有一个 $1$，计算有多少子正方形满足每行每列恰好有一个 $1$。
$n \le 10^5$

[WC2020] 猜数游戏

给定长度为 $n$ 的序列 $a_i$，元素两两不相等，等概率随机选一个非空子集 $b_i$。有另一人知道 $a$ 来猜测 $b$，每次可以询问一个 $a_k$，若在 $b$ 中无此数字，则告知“无”，否则告知 $b$ 中所有满足 $a_k^m \bmod p$ 的数（$m$ 为任意正整数）
现每次一定用最优方法猜测，问猜完 $b$ 所有数字的期望次数 $\times (2^n-1)$
$n \le 5000,p \le 10^{8}$，$p$ 为素数或 $q^k$ （$q$ 是素数，$k$ 为一正整数）

Izhevsk Training Camp

给定三个长度为 $n$ 的排列 $\{a_i\},\{b_i\},\{c_i\}$，问有多少对 $(x,y)$ 满足 $a_x<a_y,b_x<b_y,c_x<c_y$
$n \le 5\times 10^6$

[NOI2020] 命运

给定一棵 $n$ 个点，以 $1$ 为根的树，现让你对边染色 $(0/1)$ 。有 $m$ 条限制，每条限制形如 $(u_i,v_i)$ ，意为 $u_i$ 到 $v_i$ 的路径上至少要有一条 $1$ 边，其中保证 $u_i$ 是 $v_i$ 的祖先。问染色方案数。
$n,m \le 5 \times 10^5$

UVA1356 Bridge

在一条长度为 $B$ 的线段 $l$ 上，等距离截取一些点（包括左右端点），令点数为 $n$，相邻两个端点间距离为 $d\ (d \le D)$。每个端点处都作一条长度为 $H$ 的线段垂直于 $l$。相邻线段之间都存在一条全等的抛物线，抛物线总长为 $L$，令其最低点与 $l$ 的距离为 $h$。给定 $D,H,B,L$，求在 $n$ 最小时 $h$ 的值。
满足 $B \le L$

[HAOI2015] 按位或

开始手上有数字 $0$ ，每秒按照一定概率选择一个 $[0,2^n-1]$ 之内的数字，将手上的数字或上他。问手上的数变成 $2^n-1$ 的期望秒数。
$n\le 20$，满足 $\sum p_i = 1$

CF961G Partitions

给出 $n$ 个物品，每个物品有一个权值 $w_i$。
定义一个集合 $S$ 的权值为 $W(S)=|S|\sum_{x\in S} w_x$，对于一个集合的划分，定义其权值为 $W'(R)=\sum_{S\in R} W(S)$。
求所有将 $n$ 个物品分为 $k$ 个集合的方案的权值和。
$n,k \le 2\times 10^5,w_i \le 10^9$

Luogu-P4756 Added Sequence

给定数组 $a_i$，定义 $f(i,j)=|\sum_{p=i}^j a_p|$，称数组的美丽度为 $\max\{f(i,j)\}(i\le j)$。每次给定一个 $x$，$m$ 次询问，每次询问在将整个数组加上 $x$ 的基础上的美丽度。询问相互独立。
$n\le 2\times 10^5$。

CF960G Bandit Blues

给定正整数 $n,A,B$，定义 $a$ 为一个排列中前缀 $\max$ 的个数，$b$ 为这个排列中后缀 $\max$ 的个数。求长度为 $n$ 的排列中，满足 $a=A,b=B$ 的排列有多少个。答案对 $998244353$ 取模。
$n \le 10^5,0\le A,B \le n$。

CF1406E Deleting Numbers

交互题。
给定 $n$，则一开始有集合 $S=\{x|x\le n,x\in \mathbb{N}^+\}$，其中有一个特殊值 $x$，你需要通过以下操作找到他。
$\texttt{A}\ a$：询问集合 $S$ 中 $a$ 的倍数个数 $(1\le a \le n)$。
$\texttt{B}\ a$：先询问集合 $S$ 中 $a$ 的倍数个数，然后删去所有还在 $S$ 中的 $a$ 的倍数，而 $x$ 不会被删去 $(2\le a \le n)$。
$\texttt{C}\ a$：回答 $x=a$。
$\texttt{A,B,C}$ 操作的个数和不能超过 $10000$。
$1 \le x \le n\le 10^5$。

CF1305F Kuroni and the Punishment

给定 $n$ 个数 $a_i$，每次可以将其中一个 $\texttt{+1}$ 或者 $\texttt{-1}$。求最少多少次操作可以让整个序列的 $\gcd > 1$。
$n\le 10^5,a_i\le 10^{12}$。

CF1305G Kuroni and Antihype

有 $n$ 个人，第 $i$ 个人年龄为 $a_i$，两个人 $i,j$ 是朋友当且仅当 $a_i\ \texttt{ AND }\ a_j=0$。现在这 $n$ 个人要加入传销组织，组织会给他们金币。
主动加入的不会得到金币。
一个人 $i$ 若在组织内，则可以邀请不在组织内的朋友 $j$ 加入，并得到 $a_i$ 的金币。一个人只能被邀请一次。
问 $n$ 个人最多得到多少金币。
$n,a_i\le 2\times 10^5$。

CF1421E Swedish Heroes

给定长度为 $n$ 的序列 $a_i$，每次可以选择连续的两个数字 $a_x,a_{x+1}$，删去他们，再将 $-(a_x+a_{x+1})$ 插入回原位置。
现在进行 $n-1$ 次操作，求最后剩下的数字的最大值。
$1\le n\le 2\times 10^5,-10^9\le a_i\le 10^9$。

CF1091H New Year and the Tricolore Recreation

现有一个 $n$ 行无限列的矩阵，每行从左往右有三个点 $b_i,w_i,r_i$，分别是蓝点、白点、红点。
$\texttt{Alice}$ 可以将蓝点/蓝点和白点向右移动 $k$ 格，$\texttt{Bob}$ 可以将红点/红点和白点向左移动 $k$ 格，不允许改变蓝白红点的相对位置，$k$ 是质数或两个质数的乘积，但是有一个值 $d$ 不能使用。无法操作者输。问先手必胜还是必败。
$n\le 10^5,-10^5\le b_i < w_i < r_i \le 10^5$。

CF1208G Polygons

给定 $n,k$，需要建出 $k$ 个有相同外接圆的正 $a_i$ 边形，其中 $3\le a_i\le 10^6$ 且 $a_i$ 两两不同。
可以旋转任意正多边形，如果多个正多边形与外接圆的交点重合，则只算与外接圆有一个交点。现问最少与外接圆有多少交点。
$3\le n\le 10^6,1\le k\le n-2$。

CF1438D Powerful Ksenia

给定一个长度为 $n$ 的数组 $a$，现在可以做最多 $n$ 次操作，每次选取三个不同的下标 $i,j,k$，将 $a_i,a_j,a_k$ 都变为 $a_i\oplus a_j\oplus a_k$，其中 $\oplus$ 是异或。求一种方案使得所有数字都相等，或判断不可能。
$3\le n\le 10^5,1\le a_i\le 10^9$。

CF1438E Yurii Can Do Everything

给定一个长度为 $n$ 的数组 $a$，求长度至少为 $3$，且满足 $a_l\oplus a_r=\sum_{i=l+1}^{r-1} a_i$ 的子区间 $[l,r]$ 的数量，其中 $\oplus$ 是异或。
$3\le n\le 2\times 10^5,1\le a_i< 2^{30}$。

CF1438F Olha and Igor

交互题。
给定一棵深度为 $h$ 的满二叉树，则其恰好有 $2^h-1$ 个节点。你可以进行以下询问不超过 $n+420$ 次：
选择三个互不相同的点 $u,v,w$，交互库将回答以 $w$ 为根的时候，$u,v$ 的 $\text{lca}$。
你需要回答原树的根。
$3\le h\le 18$。

Luogu-P4705 玩游戏

给定长度分别为 $n,m$ 的序列 $a,b$，随机取两个下标 $x,y$，定义其 $k$ 次价值为 $(a_x+b_y)^k$。
求对于 $i\in[1,t]$，一次游戏的 $i$ 次价值的期望分别是多少。
$1\le n,m,\le 10^5,\text{mod}=998244353$。

[NOI Online #3 提高组] 优秀子序列

给定长度为 $n$ 的非负整数序列 $\{a_n\}$，定义一个子序列 $\{b_i\}$ 是优秀的，当且仅当：$b_i<b_{i+1},\forall i\ne j\ a_{b_i}\text{and} a_{b_j}=0$。
一个优秀子序列的价值为 $\varphi(1+\sum a_{b_i})$，求所有优秀子序列的价值和。
$1\le n\le 10^6,\ 0\le a_i\le 2\times 10^5$。

[UOJ-207] 共价大爷游长沙

给定一棵 $n$ 个节点的树，和一个初始为空的点对的集合 $S$，有 $m$ 次操作，需要支持 $4$ 种操作：

1. 断开一条边，再加入另一条边（保证仍然是树）。
2. 在点对集合 $S$ 中加入点对 $(x,y)$。
3. 在点对集合 $S$ 中删除第 $i$ 个加入的点对。
4. 给定 $(x,y)$，询问若把集合中的点对看做树上路径，集合中所有路径是不是都经过边 $(x,y)$。

$1\le n\le 10^5,\ 1\le m\le 3\times 10^5$，任何时刻 $|S|\le 10$。

[CTSC2006]歌唱王国

$T$ 组询问，每次给出长度为 $m$ 的序列 $a$。
现在你将生成一个随机序列，字符集为 $1-n$，每次在序列末尾等概率随机一个数。当 $a$ 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
$1\le T\le 50, 1\le n,m\le 10^5$。

[NOI2016] 循环之美

给定 $x,y,k$。
求分数 $\dfrac{x}{y}$ 的个数满足：$1\le x\le n,1\le y\le m,\gcd(x,y)=1$，且在 $k$ 进制下 $\dfrac{x}{y}$ 是纯循环小数（或者整数）。
$1\le n\le 10^9,\ 1\le m\le 10^9,\ 1\le k\le 2\times 10^3$。