烟大(内部)ACM赛题解
论罚时其实比YTU最强的那个队多好多的....
但是最后切了9个题/se全场唯一过E
然鹅不是正式选手没有5000奖金了
A
一个大环,为1234567....rrr,r是特殊字符,前面的数字代表颜色各不相同
然后我们有两个操作,第一个是找一个圆,两个位置断开,形成两个新的圆,但新圆内所有人不改变相对顺序
第二个操作是找两个圆,每个圆断开一个位置然后拼起来,所有人不改变相对顺序
问到目标颜色状态要最少几次操作....
目标颜色状态有2000组,然后环长20,r最多5个
不会做啊,全场唯一最难题,赶上省选难度了
B
序列中ACM子串个数
枚举C,统计他前面A的个数后面M的个数
C
问最小的和大于k的子集和是什么
考场上这个题错了,没有保证N<=S
枚举即可,错了的题目最后输出S....
D
a,b字符串,找一个位置断开,满足a前面的和b后面的,或者b前面的和a后面的拼起来能是回文串
会发现我们一定是在两个串的中间成为回文中心
所以我们也在那个位置断开判断一下即可
E
我手切的全场唯一过的题...
二分答案,因为小的可以大的一定可以
然后判断的时候先把所有我们的串长为x的子串哈希值搞出来
然后再能从T串一个位置匹配就匹配
说好的25000最长我数组开1e6才过是为什么呢???
F
sb贪心
不是我切得...
G
sb模拟
注意n=1无解
也不是我切的...
H
f(x)=所有数位上的非零数数乘起来
最后区间查询g值等于某个数个数
显然可以递推,因为所有数位上的数乘起来小于原数
然后把每个数的g值递推一下,统计前缀和即可
I
.....一个柱子能攒的水量是左边最大值和右边最大值二者取min-中间柱子高
J
字符串相似dp
表示s前i个然后匹配t前j个最小花费
转移带系数瞎转移一下即可,滚动数组优化
结果A还是不会???/kk