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

链接尽量丢 Luogu 的,统一起来。

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

CF662C Binary Table

给定一个 n×m01 矩阵,现在可以无限次对某一行或一列的每个数字取反,求最少的 1 的个数。
n20 , m105


YACS 棋盘 & CF526F Pudding Monsters

有一个 n×n 的正方形,每行每列都恰好有一个 1,计算有多少子正方形满足每行每列恰好有一个 1
n105


[WC2020] 猜数游戏

给定长度为 n 的序列 ai,元素两两不相等,等概率随机选一个非空子集 bi。有另一人知道 a 来猜测 b,每次可以询问一个 ak,若在 b 中无此数字,则告知“无”,否则告知 b 中所有满足 akmmodp 的数(m 为任意正整数)
现每次一定用最优方法猜测,问猜完 b 所有数字的期望次数 ×(2n1)
n5000,p108p 为素数或 qkq 是素数,k 为一正整数)


Izhevsk Training Camp

给定三个长度为 n 的排列 {ai},{bi},{ci},问有多少对 (x,y) 满足 ax<ay,bx<by,cx<cy
n5×106


[NOI2020] 命运

给定一棵 n 个点,以 1 为根的树,现让你对边染色 (0/1) 。有 m 条限制,每条限制形如 (ui,vi) ,意为 uivi 的路径上至少要有一条 1 边,其中保证 uivi 的祖先。问染色方案数。
n,m5×105


UVA1356 Bridge

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


[HAOI2015] 按位或

开始手上有数字 0 ,每秒按照一定概率选择一个 [0,2n1] 之内的数字,将手上的数字上他。问手上的数变成 2n1 的期望秒数。
n20,满足 pi=1


CF961G Partitions

给出 n 个物品,每个物品有一个权值 wi
定义一个集合 S 的权值为 W(S)=|S|xSwx,对于一个集合的划分,定义其权值为 W(R)=SRW(S)
求所有将 n 个物品分为 k 个集合的方案的权值和。
n,k2×105,wi109


Luogu-P4756 Added Sequence

给定数组 ai,定义 f(i,j)=|p=ijap|,称数组的美丽度为 max{f(i,j)}(ij)。每次给定一个 xm 次询问,每次询问在将整个数组加上 x 的基础上的美丽度。询问相互独立。
n2×105


CF960G Bandit Blues

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


CF1406E Deleting Numbers

交互题。
给定 n,则一开始有集合 S={x|xn,xN+},其中有一个特殊值 x,你需要通过以下操作找到他。
A a:询问集合 Sa 的倍数个数 (1an)
B a:先询问集合 Sa 的倍数个数,然后删去所有还在 S 中的 a 的倍数,而 x 不会被删去 (2an)
C a:回答 x=a
A,B,C 操作的个数和不能超过 10000
1xn105


CF1305F Kuroni and the Punishment

给定 n 个数 ai,每次可以将其中一个 +1 或者 -1。求最少多少次操作可以让整个序列的 gcd>1
n105,ai1012


CF1305G Kuroni and Antihype

n 个人,第 i 个人年龄为 ai,两个人 i,j 是朋友当且仅当 ai  AND  aj=0。现在这 n 个人要加入传销组织,组织会给他们金币。
主动加入的不会得到金币。
一个人 i 若在组织内,则可以邀请不在组织内的朋友 j 加入,并得到 ai 的金币。一个人只能被邀请一次。
n 个人最多得到多少金币。
n,ai2×105


CF1421E Swedish Heroes

给定长度为 n 的序列 ai,每次可以选择连续的两个数字 ax,ax+1,删去他们,再将 (ax+ax+1) 插入回原位置。
现在进行 n1 次操作,求最后剩下的数字的最大值。
1n2×105,109ai109


CF1091H New Year and the Tricolore Recreation

现有一个 n 行无限列的矩阵,每行从左往右有三个点 bi,wi,ri,分别是蓝点、白点、红点。
Alice 可以将蓝点/蓝点和白点向右移动 k 格,Bob 可以将红点/红点和白点向左移动 k 格,不允许改变蓝白红点的相对位置,k 是质数或两个质数的乘积,但是有一个值 d 不能使用。无法操作者输。问先手必胜还是必败。
n105,105bi<wi<ri105


CF1208G Polygons

给定 n,k,需要建出 k 个有相同外接圆的正 ai 边形,其中 3ai106ai 两两不同。
可以旋转任意正多边形,如果多个正多边形与外接圆的交点重合,则只算与外接圆有一个交点。现问最少与外接圆有多少交点。
3n106,1kn2


CF1438D Powerful Ksenia

给定一个长度为 n 的数组 a,现在可以做最多 n 次操作,每次选取三个不同的下标 i,j,k,将 ai,aj,ak 都变为 aiajak,其中 是异或。求一种方案使得所有数字都相等,或判断不可能。
3n105,1ai109


CF1438E Yurii Can Do Everything

给定一个长度为 n 的数组 a,求长度至少为 3,且满足 alar=i=l+1r1ai 的子区间 [l,r] 的数量,其中 是异或。
3n2×105,1ai<230


CF1438F Olha and Igor

交互题。
给定一棵深度为 h 的满二叉树,则其恰好有 2h1 个节点。你可以进行以下询问不超过 n+420 次:
选择三个互不相同的点 u,v,w,交互库将回答以 w 为根的时候,u,vlca
你需要回答原树的根。
3h18


Luogu-P4705 玩游戏

给定长度分别为 n,m 的序列 a,b,随机取两个下标 x,y,定义其 k 次价值为 (ax+by)k
求对于 i[1,t],一次游戏的 i 次价值的期望分别是多少。
1n,m,105,mod=998244353


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

给定长度为 n 的非负整数序列 {an},定义一个子序列 {bi} 是优秀的,当且仅当:bi<bi+1,ij abiandabj=0
一个优秀子序列的价值为 φ(1+abi),求所有优秀子序列的价值和。
1n106, 0ai2×105


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

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

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

1n105, 1m3×105,任何时刻 |S|10


[CTSC2006]歌唱王国

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


[NOI2016] 循环之美

给定 x,y,k
求分数 xy 的个数满足:1xn,1ym,gcd(x,y)=1,且在 k 进制下 xy 是纯循环小数(或者整数)。
1n109, 1m109, 1k2×103

标签: 位运算, 计数, 生成树, 线段树, dp, 数学, 多项式, 自适应辛普森法, 单调栈, 原根, 容斥, 线段树合并, Min-Max 容斥, 斯特林数, 反演, 凸壳, 交互, 质因数分解, 随机化, 归纳法, 博弈论, bitset

已有 10 条评论

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

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

  3. 蒟蒻ysh 蒟蒻ysh

    %%%

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

  5. bigmurmur bigmurmur

    我是zzm的儿子

  6. Chaos Chaos

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

  7. Orz

  8. ywjj ywjj

    听我家zcdh说你很强,确实很强!

  9. qhl qhl

    cxy好强!!!!!

添加新评论