下午ARC104模拟短时赛:
T1、T2:
T1签到题。
T2签到题, \(O(n^2)\) 乱做。但是实际上可以空间换时间开桶到 \(O(n)\)。也非常简单。
T3:
考场没有做出。
思考的关键在于想到可以对于区间单独判断是否满足条件。
知道了如何判断区间是否满足条件后,可以做一次 \(O(n)\) 的 \(dp\)。每次枚举最后一个段来判断前 \(i\) 个位置能否满足条件。
现在来想如何判断区间是否合法:
对于一个完整的满足条件的区间,一定是端点重叠的形式。
比如判断 \([1, 6]\) 这个区间。如果它合法,可能的填写形式就只有 \([1,4], [2,5], [3,6]\) 这三个区间。
简而言之也就是:区间的前一半全都是进电梯,后一半是这些人按进的顺序出。
这样就可以 \(O(n)\) 判断区间是否合法。
总时间复杂度:\(O(n^3)\)。
T4:
考场没有做出。
感觉是订正后提升最大的一道题。
题面非常阴间。
英译中后大意为求对于每个 \(x\exist[1,n]\),求出集合元素在 \([1, n]\) 中任选,可以选的次数在 \([0,k]\) 间的操作组成的,满足元素平均数为 \(x\) 的多重集个数。
首先有一个经典(/jk)trick,因为需要求平均数为 \(x\) ,所以在做背包之前将每个数 \(i\) 变为 \(i-x\),这样背包只需要维护和为 \(0\),不用多维护一个元素个数求平均数。
这里赛场上就没想到。考虑了维护元素个数,空间会炸,遂放弃D死磕C。遗憾的。
感觉很多考试不能发挥好都是思维题开头的一个经典小trick导致的问题转化没有想到,输输输。
非常思维的点是,因为要对于每一个 \(x\) 求值。首先确定下来要枚举 \(x\),然后便可以考虑从 \(x-1\) 到 \(x\) 的过程中有哪些变化。
原本可选的元素是 \([1, n]\),在上一次做 \(x-1\) 的答案时被考虑成了 \([1-(x-1), n-(x-1)]\)。
而现在则是 \([1-x,n-x]\)。
注意到就是在数轴上向左移了一位。
在考虑和为 \(0\) 时,可以看做被选择元素的负数部分和正数部分绝对值之和相等。
所以可以将负数部分和正数部分看做同一个问题。
即:预处理 \(f[i][j]\) 表示可选值域在 \([1,i]\),每个数最多选 \(k\) 次,最终和为 \(j\) 的方案数。
最终对于每一个 \(x\) 的答案就是\(k + (k + 1) * ∑_{1 \leq j \leq lim}f[-(1-x)][j] * f[n-x][j]\)。
即枚举正负部分的绝对值 \(j\) 来统计方案。
这里注意到 \(dp\) 状态中的值域是从 \(1\) 开始的,实际上拍到数轴上还可以随意选 \(0\)。
对于每一个方案,可选 \(0\) 的个数是 \([0,k]\) 共 \(k+1\) 种,所以sigma外面乘上一个 \(k+1\)。而绝对值同样可以是 \(0\),此时的方案有 \(k\) 种,所以再加上 \(k\)。
即可通过此题。
感觉对我来说,写多重背包的预处理也是一个难点。因为枚举每个数选几次会T。
这里用到神秘前缀和优化。
注意到枚举选的次数的写法中,\(f[i - 1][j - p * i]\) 会加到 \(f[i][j]\) 上,即 \(f[i][j]\) 是上一层的所有 \(j'\) 与 \(j\) 关于 \(i\) 同余,且 \(j'>=j-k*i\) 的状态的和。
所以可以写出这样的代码:
for(int i = 1; i <= n; i ++) {
for(int l = 0; l <= 505000; l ++) {
f[i][l] += f[i - 1][l];
if(l - i >= 0) f[i][l] += f[i][l - i], f[i][l] %= mod;
}
for(int l = 505000; l >= 0; l --) {
if(l - (k + 1) * i >= 0) f[i][l] -= f[i][l - (k + 1) * i];
f[i][l] = (f[i][l] + mod) % mod;
}
}
注意到在第一次 \(l\) 的循环中,没有考虑 \(j'>=j-k*i\),所以在第二次循环把 \(j-k*i\) 之前的减掉。
很难不发现,在订正代码时,其他同学都早就理解了这个优化写法,只有我傻乎乎看了半个晚上再写(/kk)。
这道题就到这里了。
T5,T6
T5讲评时没有完全听懂,听懂了ywz的dp方法,但是忘记了其他部分/yiw?
T6讲评听了个开头,寄了。