Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

05/17
22:57
kmp 一般动规与递推 二分法 决策单调性 分治 暴力 最小割 模拟

Educational Codeforces Round 21

A:

prob:

给出一个数x,找到最小的 y ,使得 y > x 且 y 只包含一个非0数字,输出 y - x

1 <= x <= 10 ^ 9

sol:

y肯定形如a0000.....,直接找x的下一个这种数就可以了

 

B:

prob:

给出 n, k,在给出一个长度为 n 的数组 a[1..n] , 计算所有 n - k + 1 个连续 k 个数的和 的平均值

sol:

用前缀和随便搞一搞

 

C:

prob:

给你k个杯子和w份水,每个杯子有一个容积ai,要求每个杯子都要有大于等于容积的一半的水,且容积大的杯子中的水大于等于任何容积比它小的杯子里的水,输出一种方案,无解输出-1

sol:

先满足大于等于容积一半的条件,然后从容积大的杯子开始能填就填

 

D:

prob:

给一个长度为 n 的数组 A,问能不能移动一个元素使得 A 的一个前缀和是 A 总和的一半

(原来some有某个的意思。。。一开始以为能移动一些元素(雾))

sol:

考虑移动后对于前缀和的影响,肯定是一段前缀和+a[i],一段-a[i],还有一段不变

那么对于每个前缀和s[i],要把它变成x,那么只要看i前面有没有s[i]-x或者i后面有没有x-s[i]就可以了

 

E:

prob:

n个物品,容量为m的背包,每个物品重量 wi<=3,价值 ci <= 1e9,问最多能装多少价值的物品

sol:

今年集训队论文题,而且原题 wi<=300.... 直接利用决策单调性分治就可以了

 

F:

prob:

n张卡片和一个权值k

每张卡片有3个属性 pi, ci, li,你需要给出一个最小的level满足:

1、只能选 li <= level 的卡片

2、若 ci + cj 是一个质数,那么 i 和 j 不能同时选

3、选出的卡片的 pi 的和应该大于等于 k

无解输出-1

sol:

二分答案之后直接最小割验证

 

G:

prob:

给出母串 S 和子串 T,S中有一些问号,问给S中的问号填上字母后,T在S中最多出现多少次(子串)

|s| <= 1e5     |t| <= 1e5     |s| * |t| <= 1e7

sol:

首先暴力预处理出 s 的每一个位置可不可能匹配 t

然后扩展kmp求出所有t的所有 border,也就是说如果 i - x 这个位置匹配上了,那么i这个位置依然可以匹配的所有的x

然后就直接dp 设 f[i] 表示 从 s 的第 i 个位置开始匹配一个 t,以及之前最多可以匹配多少个 t

直接枚举 border转移

 

Educational Codeforces Round 21