• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021.10.11pm

开发技术 开发技术 3小时前 5次浏览

10.11PM

预期 实际
A 100 100
B 30 70
C 50 50
S 180 220

可能水,一定菜

A [SCOI2010]生成字符串(blacktriangle!blacktriangledown)

  1. “简单组合数学”。
  2. 先说说我是怎么蒙的吧:
    • 首先是写了个 (O(n^2)) 的暴力。
    • 然后从结果推回式子。
    • 然后由于当 (m=1) 时,答案为(n+1-1) ,于是想到用两个组合数相减。
    • 再小数据通过适当枚举,就能蒙出组合数算法
[mathrm{C}_{n+m}^{m}-mathrm{C}_{n+m}^{m-1}
]

  1. 再说说谢巨是怎么推的:
    • 对于每一个不成立的方案,显然存在一个位置 (2k+1) ,使得 (sum_{i=1}^{2k+1}a_i=k),对于这个位置后方的数之和为 (n-k) 。把前半段取值翻转((0 to 1,1 to 0)),能得到另一个序列,使得(sum_{i=1}^n a_i=n+1)。而后面的序列有多少种,不成立的有多少种,全部-不成立=成立。

B [SCOI2010]序列操作(blacktriangle!blacktriangledown)

  1. 好奇暴力为啥有70
  2. 首先看着操作就知道是个数据结构。
  3. 而我们没学过多少数据结构那只能是线段树。
  4. 这道题我维护了这几个变量:1的个数,1,0的最大连续区间长度,左侧右侧最长连续区间,左右侧种类(0 or 1),和一个延迟标记,维护很像最大区间值求法。
  5. 最大的问题还是延迟标记。对于区间覆盖是没问题的,但是对于异或操作很有问题,如果直接覆盖标记会导致下传出大问题,所以对lazytag也要修改:如果之前传的是1,改为0;之前是0,改为1;之前是2,则不下传;若之前没有标记,则为2。
  6. 当然,由于这道题维护很复杂,建议牺牲一定效率,多写函数,直接调用,这样修改时不会只修改了一部分然后调半天····

C [SCOI2010]连续攻击游戏(blacktriangle!blacktriangledown)

  1. ZAT贪心YYDS!
  2. 这道题有一个非常简单的做法:
  3. 找连通块,如果连通块是一棵树,说明除最大点外全部都能选上;若有办法不从入边回去(环),则一定都能选上。易证。

2021.10.11pm

(cal {Made} {by} {YuGe})


程序员灯塔
转载请注明原文链接:2021.10.11pm
喜欢 (0)