补题进度:6/7(11)
遇事不决先打表 乱搞不会瞎贪心 没人过题搜论文
1001. Maximum Multiple
x+y+z=n=>x/n+y/n+z/n=1设a=x/n,b=y/n,c=z/n(a<=b<=c)则=>a<=1/3
再枚举一下即可
1002. Balanced Sequence
题解
子序列!!!
预处理出所有字符串合法的()之后会.
先把每个字符串贪心匹配下,形成若干个形如 )))((( 的字符串,并分别记为二元组 (a,b),按照一定顺序排序就可以
Johnson流水线调度规则
51nod1205 流水线调度
和这个很相似,按照b-a的正负性不同分别排序
要将 a<b放到a>=b前面
- a< b, 按照a从小到大排序
- a>=b, 按照b从大到小排序
对b-a的正负性不同分别排序
- b>=a , 按照a从小到大排序
- b<a , 按照b从大到小排序
1 | struct node{ |
1003. Triangle Partition
签到
1004. Distinct Values
可以发现最优的一定是每个数都尽可能的小,双指针枚举,用set维护一下这个过程即可
1005. Maximum Weighted Matching
留坑
1006. Period Sequence
留坑
1007. Chiaki Sequence Revisited
遇事不决先打表
打出 ai的表观察:
- ai是奇数:1次(除了1)
- ai是偶数: 2k|i=>k+1次(最大的k)
有一个很神奇的规律
末尾是x(包括全部的x)的总共项数=
20(1+2+…+x)+21(1+2+…+x/2)+22(1+2+..+x/4)+…+2k(1+2+…+x/(2k))
所以二分an,等比数列求上面数列的和即可
注意二分出来的an可能取不到所有an,要用an−1算,再把余下的an的数量加上去
1008. RMQ Similar Sequence
RMQ+分治
待补
1009. Lyndon Substring
论文题再见
1010. Turn Off The Light
大模拟再见
1011. Time Zone
签到