首页 > 其他分享 >#7 2023.12.4

#7 2023.12.4

时间:2023-12-11 21:26:30浏览次数:35  
标签:每个 2023.12 然后 急眼 大概 bmatrix 式子

419. arc137c Distinct Numbers

注意到如果 \(a_{n-1 } + 1 \neq a_{n}\),显然是先手必胜的。

然后一个人显然不会主动走到这个状态,于是 \([0,a_n]\) 之内的每个数都要被遍历一遍。于是答案就和 \(n - a_n\) 的奇偶性有关了。

420. arc137d Prefix XORs

大概只跟 \(n-i\) 和 \(j\) 的 and 有关。fmt 一下就做完了。

421. arc137e Bakery

怎么不会做呢?急眼了。怎么不会做呢?急眼了。怎么不会做呢?急眼了。怎么不会做呢?急眼了。

大概就是假装全都选,然后是区间覆盖模型!

422. arc136c Circular Addition

423. arc136d Without Carry

424. arc136e Non-coprime DAG

425. arc136f Flip Cells

大概是设 \(F\) 表示答案的 PGF,\(G\) 表示从终止态开始到终止态的 PGF,\(H\) 表示从起始态开始到终止态的 PGF。显然 \(H = FG\),答案是 \(F'(1)\)。所以只需要求出 \(G(1),H(1),G'(1),H'(1)\) 即可。

大概可以通过奇技淫巧搞出式子,要注意上述几个值是否都有意义。如果不是,就同乘点东西让它有意义,然后暴力推式子就草过去了。感觉很牛!

426. arc135d Add to Square

427. arc135e Sequence of Multiples

序列可以贪心。令 \(b_i = {a_i \over i}\),则 \(b_i - b_{i-1}\) 只有 \(O(\sqrt[3]{n})\) 种。找连续段需要奇技淫巧,每个连续段可以 \(O(1)\) 算。

428. loj3636 「2021 集训队互测」机器

直接费用流对偶,发现形式很好看。

大概是要求一个 \(\sum f(x_i)\),然后 \(x_u \leq x_v\) 之类的。盲猜他能套上保序回归之类的东西,那就做完了。证明不看了(我连保序回归的证明都没看,怎么会看这个呢 2333)。

429. loj3637 「2021 集训队互测」数列重排

430. arc135f Delete 1, 4, 7, ...

431. arc134e Modulo Nim

史。

大概是先通过神秘分析/打表,发现必败态长成同一个样子,并且有些小的状态是特例。并且很巧的是必败态的样子很好看,可以当场状压。然后暴力统计,做完了。

432. arc133d Range XOR

相当于 \(s_{l-1} \oplus s_r = V\)。枚举 \(i\) 的后两位,发现 \(s_i\) 是能算的。

容斥一下之后数位 dp 即可。

433. arc133e Cyclic Medians

大概可以发现很多情况是对称的,把和 A 有关的东西拉出来,发现每个模 gcd 相等的位置有性质。

434. arc133f Random Transition

看作 \(n\) 个硬币,大概是把每一位的贡献搞出来,变成一个二元 GF。暴力化简 GF 的式子,最后得到若干个形态很好看的式子,提取一下,然后发现可以直接分治 NTT 之类的做。

推式子过程和 arc136f 似乎差不多,感觉不难,所以不管了。

435. arc132d Between Two Binary Strings

436. arc132f Takahashi The Strongest

把字母看作 1,2,3。构造串 \(M(i,j)\),如果 \(a_{i,d} = b_{j,d}\),\(M(i,j)_d = a_{i,d}\)。否则 \(M(i,j) _d = 0\)。定义 0 是 1,2,3 的子集,1,2,3 互不包含。

我们想要对每个串 \(S\) 求出答案,等价于对串 \(T\) 求出所有 \((i,j)\) 的个数,满足 \(T\) 和 \(M(i,j)\) 至少一位相同,其中 \(T\) 是每把都被 \(S\) 击败的字符串。

设 \(cnt_S\) 表示 \(\sum\limits _{i,j} [M(i,j) = S]\)。发现变换矩阵是

\[\begin{bmatrix} 1 \ 0 \ 0 \ 0 \\ 1 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 1 \ 0 \\ 1 \ 0 \ 0 \ 1 \end{bmatrix} \]

那逆矩阵就是

\[\begin{bmatrix} 1 \ 0 \ 0 \ 0 \\ -1 \ 1 \ 0 \ 0 \\ -1 \ 0 \ 1 \ 0 \\ -1 \ 0 \ 0 \ 1 \end{bmatrix} \]

直接高维前缀和即可。

求出 \(cnt_S\) 之后再做一次高维前缀和即可得到答案。

437. arc131d AtArcher

显然箭的间隔一定是 \(d\),所以 \([0,d)\) 的范围内一定有一枝箭。把这支箭从 \(0\) 到 \(d\) 移动,会有 \(O(m)\) 个贡献变化时刻。暴力扫就行了。

438. arc131e Christmas Wreath

厉害题。不妨令所有 \((i,j),i < j\) 的边权都为点 \(j\) 的权值。这样每个三角形一定合法。问题转化为将 \([1,n-1]\) 分割成三个集合,使得每个集合的和相等。可以手摸出 \(n = 6,7,9,10\) 的解,后面可以用 \(n - 6\) 的方案递归构造。

439. arc131f ARC Stamp

考虑用问号把整个串塞满,那就把串用 ARC,AR,A,RC,C,R 贪心划分。每次一定是填满一整段。为了划分区域,要在相邻两个 ARC 中间塞一个 X。

之后就是 \(f_{i,j,0/1,0/1}\) 表示自己这一位和下一位的选择状态。

440. arc130d Zigzag Tree

大概看看每个点是比旁边大还是比旁边小,然后就 \(dp_{u,i,0/1}\) 就可以了。

441. arc130e Increasing Minimum

考虑按照 \(v\) 把序列分段。

记 \(f_i\) 表示 \(i\) 恰为某段结尾的最小层数。\(i\) 的前驱不超过 1 个。算答案时挑一个合法 \(i\) 里 \(f_i\) 最小的最靠后的 \(i\) 即可。

442. arc130f Replace by Average

443. xsy5071

444. xsy5072

445. arc129d -1+2-1

设 \(x_i\) 是 \(i\) 的操作次数。发现 \((x_{i} - x_{i-1}) - (x_{i+1} - x_i) = - a_i\) 之类的神奇东西。然后可以求出 \((x_i - x_{i-1})\)。然后解出 \(x_0\) 就行了。

446. arc129e Yet Another Minimization

典中典切糕题。不管了。

447. ctt2023 不知道哪个题

建出两个序列的括号树。操作相当于删掉一个点,然后它的儿子成为它的兄弟。

记 \(mat_{u,v}\) 表示 \(a\) 的点 \(u\) 能否匹配 \(b\) 的点 \(v\)。要么是 \(mat_{son,v}\),要么是 \(u\) 的每个儿子贪心匹配 \(v\) 的每个儿子。

448. arc129f Let's Play Tag

先要搞清楚题解里那个奇怪式子是怎么来的。记第 \(i\) 次调头时遇到的人的初始位置的绝对值为 \(a_i\),抓到这个人的时间为 \(t_i\)。

在抓到 \(i-1\) 时,第 \(i-1\) 个人位置的绝对值是 \(a_{i-1} + t_{i-1}\),第 \(i\) 个人位置的绝对值是 \(a_{i} + t_{i-1}\),所以 \(t_i = t_{i-1} + (t_{i-1} + a_{i-1}) + (t_{i-1} + a_i) = 3t_{i-1} + a_{i-1} + a_{i}\),那就得到了题解里奇怪的贡献式子了。

得到式子之后就可以奇技淫巧算贡献了(?不管了。

449. arc128d Neq Neq

\(f_i \leftarrow f_j ok(i,j)\),\(ok(i,j)\) 是能不能把 \([i,j]\) 区间删成 \(\{i,j\}\)。

\(j-i+1 \leq 3\) 的情况特判,其他情况下,\(ok(i,j)\) 等价于 \([i,j]\) 里至少有三种数,并且没有连续两#个相同的数。

450. arc128e K Different Values

判无解是容易的。大概就是每一位挑能放或者一定要放的集合里最小的一个。

451. arc128f Game against Robot

orz lh!

考虑一个 \(p\) 怎么搞!把序列按照 \(p\) 从小到大排序,然后不断塞序列的前两个数进一个 set,然后把 set 里最大的数拿出来扔给 snuke。

01 分段,数一下扔出来的 0,发现相当于二维走路,右上右下 coef = 1,右 coef = 2。强制把 \(y<0\) 的地方改到 \(y = 0\),数这个的个数。发现就相当于没有这个限制,路径最低点的绝对值。然后可以用卡特兰数的方法数出方案,加起来是个奇异式子,瞎搞搞可以前缀和。

452. arc127d Sum of Min of Xor

标签:每个,2023.12,然后,急眼,大概,bmatrix,式子
From: https://www.cnblogs.com/ZHANG-SHENG-HAO/p/17895569.html

相关文章

  • 2023.12 做题纪要 #1
    终于从学考中解脱出来了,做题纪要回归!11月下半个月发生的事情:考了个NOIP,游记在这,然后全力备战学考了,所以半个月没做题。本文大部分题的题单To-doList#2。题单的第一个题在上一篇做题纪要的最后。目录2023.12.10P9353[JOI2023Final]ModernMachine2023.12.11GYM102896F......
  • 2023.12.11——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.c#明日计划:学习......
  • 百度网盘(百度云)SVIP超级会员共享账号每日更新(2023.12.11)
    一、百度网盘SVIP超级会员共享账号可能很多人不懂这个共享账号是什么意思,小编在这里给大家做一下解答。我们多知道百度网盘很大的用处就是类似U盘,不同的人把文件上传到百度网盘,别人可以直接下载,避免了U盘的物理载体,直接在网上就实现文件传输。百度网盘SVIP会员可以让自己百度账......
  • 2023.12 杂题
    Ifoundithard,it'shardtofind.Ohwellwhatevernevermind.目录CF1904ETreeQueriesCF1904FBeautifulTreeABC332GNotTooManyBallsCF1904ETreeQueriesTag:T-欧拉序;S-线段树。注意到\(\sumk\)和\(n\)同级,大抵是一个和\(k\)相关的做法,虚树大概是不可行的,......
  • 2023.12.10——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.c#明日计划:学习......
  • 2023.12.03
    压线圈到了MXOI的奖学金。最近whk太忙了,还得准备月考,没太多时间整理很多东西,但是这个还是得整理一下。感觉这场比赛还是挺赚的,见识了一下lxl最近的命题思路,只能说物超所值了。A.avatar先二分,转判断问题。然后发现转成wll就是所有\(|x_i-x_j|<v(t_i-t_j)\)的连边。想......
  • 2023.12.9——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.c#明日计划:学习......
  • 2023.12.9补题
    一.关于优先队列的题目atcoder周赛题目   总结:本题利用用优先队列自动排序,首先我们需要明确的是先去更新小的,小的如果有更新不了的那么一定不会有人再和他融合了这样我们选择开一个大根堆greater,从小到大排列,然后我们开一个pair记录数值和出现次数,然后每次操作先判断他周......
  • 2023.12
    启动。DEGwer'sDoctoralDissertationCheeringContest好魔怔的比赛。E.HalfPalindromes先考虑单个\(f(l,r)\)的计算,有结论:我们一定会不断删最小的长度为\(k\)的前缀,满足前\(2k+1\)个字符是回文的。直到没有这样的\(k\)为止。证明也很容易,假设我们某一步删了长度......
  • 2023.12.7 挑战杯题解
    选择题T1有序实数对即为数,坐标系中的点\(P\)即为形。故选择A。T2\(9.46\times10^{12}=9460000000000\)为\(13\)位数所以选D。T3如图所示,过点\(D\)作\(DE\botAB\),设\(AE=x\),在\(Rt\DeltaADE\)中利用勾股定理列方程为\((x-1)^2+10^2=x^2\),解得\(x=\frac{101}{2......