某奇怪的题单 | miaom's Blog
miaom's Blog

lych真的0

miaom's avatar miaom

某奇怪的题单

记录一下近期开的题。。

3.9

Divisible Matching

  • 给一个二分图,有边权,问是否存在边权和为k的倍数的完美匹配。$N,k\le 100$
  • 找到$P=s\times k+1$的单位元,构造行列式

Bunny on Number Line

  • 有一个兔子在数轴上跳,初始在0,每一秒可以+1=1,数轴上有k个坏点(保证1是好的),跳到会将现在的时间加到序列末尾,要求每M跳至少有一个坏点,求不同的长为N的序列最后一项的和。$k\le 100,N\le 10^9$
  • 建立类似AC自动机的东西,然后跑矩乘

Card Collecting Game

  • 有T种卡片,第i种有$q_i$张,每获得$a_i$张就加$v_i$分。A将所有卡等分成两堆,第一堆A先手,另一堆B先手。在B希望A分数最低的情况下,A最多得几分。$T\leq 2000,\sum a_i\leq2000 ,v_i\leq 3000 , \sum q_i\leq 500000$

Balanced Strings

  • 询问有几个仅由a,b,c构成的长为N的字符串满足所有子串任意字母出现次数差小于k。模X。$N\leq 10^9,1\le k\le 5$
  • 矩乘吧

远行

拍苍蝇

  • 这个题好像很厉害啊

MST and Rectangles

  • 一张n个点的无向完全图,i,j之间的边边权为 $A_{i,j}+A_{j,i}$,每次操作将A的一个矩形加W,最后询问MST大小。$n\leq 10^5$
  • 使用Boruvka算法,用线段树维护每个点的最大边

3.12

cf的题好难啊,还是csacademy良心。

E. Iqea

  • 动态棋盘最近点,棋盘和棋盘的补各自联通。$n \le 300000$
  • 将棋盘按列切块建树

G. Cut the pie

E. Fire and Ice

  • 1~n上有火妖,每个的血量为$a_i$,你在0,每一步可以A在右边造一个冰或者消一个冰,或者R右移或者L左移,因重力掉落的冰会造成1点伤害,求打死所有火妖的最少步数的方案。$n\le 1000,a_i\le100$
  • 贪心。发现让右边一段长为x的掉下去,代价为3x+2,所以除了最长的一次,大概不会砸空。然后搞搞。

E. Verifying Kingdom

  • 交互。给一颗满二叉树,每次询问三个叶子哪两个点的lca深度最大,10n询问,求一颗同构的树。$n\le1000$
  • 类似WC2018T3。每次暴力找重心即可。

K. Roads Orientation Problem

  • 给一张无向图定向,使得没有入边的点为s,没有出边的点为t,且无环。$n\le400000$
  • 这个题可以说是很神仙了。考虑以s为根建立dfs树,t~s的路径上的边都指向父亲。对于一条返祖边x->y,设y为祖先,x在y的z儿子的子树内,令x->y方向与z->y相同(指向根或不指向根),并使x到s的一段未定向的边定向与z->y不同。使用bfs实现。感性理解一下是对的。$O(n+m)$

F. Tree nesting

  • 给两个树S,T,求S有几个子树(联通子图)与T同构。$|S|\le 1000,|T|\le 12$
  • 找到T的重心(或重心边),然后子树dp,除去同构的方案。

3.15

G. Almost Increasing Array

  • 给一个序列,问最少修改几个元素可使序列删除一个数后严格递增。$n\le 200000$
  • 考虑维护正反两个线段树表示开头(结尾)为x的最长上升的最少操作数,枚举删掉的点,对后缀的线段树支持撤销操作。由于每一步只会有O(1)个点被改动,复杂度为$O(nlogn)$。

E. …Wait for it…

F. Lena and Queries

  • 支持动态加删直线,求横坐标为x时纵坐标最大的直线的纵坐标。$n\le300000$
  • 离线,时间线段树,排序预处理。$O(nlogn)$

G. Palindrome Partition

  • 给定一个字符串,问有多少方案把他分为2k个子段${S_i}$,使$S_i=S_{2k-i+1}$。$n\le1000000$
  • 题解说可以将字符串改写为$S_1S_{n}S_2S_{n-1}…$,之后问题转化为将S分为若干偶数长度回文串的方案数,用回文树维护dp。也可以考虑border的性质,是log段等差序列,维护dp值。$O(|S|log|S|)$

F. Simba on the Circle

E. Student’s Camp

  • 给一个塔,高度为n宽度为m,每天最左边的石头与最右边的石头有p的概率吹掉,问k天之后没有倒的概率。$n,m\le1500$
  • 大力dp,细节写的时候再想吧。。感觉维护一个i层左端点为j的概率和包含j的概率就好了吧。