杂题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$。

已有 8 条评论
  1. 大佬的妙题使我受益匪浅, 感谢大佬的帮助与支持%%%%%%%%%%

  2. 大佬的妙题使我受益匪浅, 感谢大佬的帮助与支持 %%%%%%%%%%

  3. 蒟蒻ysh 蒟蒻ysh

    %%%

  4. 大佬的妙题使我受益匪浅, 感谢大佬的帮助与支持 %%%%%%%%%%

  5. bigmurmur bigmurmur

    我是zzm的儿子

  6. Chaos Chaos

    大佬的妙题使我受益匪浅, 感谢大佬的帮助与支持 %%%%%%%%%%

  7. Orz

添加新评论