UOJ Logo oi_loser的博客

博客

正睿NOIP普及组模拟赛第3场题解

2017-09-24 20:14:32 By oi_loser

由于出题人并不会评估普及组题目难度,这次的题目还是偏难了……

下面是题解。


祖玛

关键字:模拟

首先可以用循环语句,从字符串的第 $x$ 个字符开始往左找第一个不是 $c$ 的字符,假设它是第 $l$ 个字符(如果找不到则 $l=0$),然后从第 $x+1$ 个字符开始往右找第一个不是 $c$ 的字符,假设它是第 $r$ 个字符(如果找不到则 $r=n+1$)。

如果 $r-l < 3$,说明把珠子射入以后,射入的珠子所在的连续段不足 $3$ 个珠子,这时候,应该先输出前 $x$ 个字符,再输出字符 $c$,最后输出第 $x+1$ 到第 $n$ 个字符。

如果 $r-l\ge 3$,说明射入之后 $l+1$ 到 $r-1$ 这一段会消失。如果 $l,r$ 两个位置是不同字符,过程结束;如果是相同字符,设其为 $c'$,从 $l$ 往左找第一个不是 $c'$ 的位置 $l'$,从 $r$ 往右找第一个不是 $c'$ 的位置 $r'$,如果 $(l-l')+(r'-r)\ge 3$,那么 $l'+1$ 到 $l$、$r$ 到 $r'-1$ 会消除,否则不会消除;如果会消除,令 $l=l'$,$r=r'$ 重复此过程即可。可以用 while 循环来实现。最后应该先输出前 $l$ 个字符,再输出第 $r$ 到第 $n$ 个字符。


数列分割

关键字:枚举,减少枚举量

显然可以用两重循环枚举两个切割点 $p,q$ 的位置,再用一重循环计算三个段的最大值,求出最大和最小的答案。但是这样运算量是 $n^3$ 级别的,太慢了。

当然可以少枚举一些东西。比如我们可以开两个数组 L[i]R[i] 分别存储前 $i$ 个数的最大值和第 $i$ 到第 $n$ 个数的最大值。

for(int i = 1; i <= n; i++) L[i] = L[i-1] > a[i] ? L[i-1] : a[i];
for(int i = n; i >= 1; i--) R[i] = R[i+1] > a[i] ? R[i+1] : a[i];

还可以一边枚举 $q$ 一边更新中间段的最大值:

for(int p = 1; p < n; p++){
    int m = 0;
    for(int q = p; q < n; q++){
        if(a[q] > m) m = a[q];
        // m 即为 [p,q] 段的最大值
    }
}

这样左段、中段、右段的最大值不需要额外计算了。这样的运算量还是 $n^2$ 级别的(只要枚举 $p,q$),尽管能得到很多分,但由于超时的缘故还是不能得到满分。

先考虑三段和的最大值怎么求,它就是数列中前三大的数的和

  • 比如数列 $3,5,1,4,3$ 前三大的数是 $5,4,3$,那么不管怎么切,三段加起来不会超过 $5+4+3$。让三段加起来等于 $5+4+3$ 只要一刀切在第2项和第4项之间,一刀切在第4项和第5项之间就好了,$[3,5],[1,4],[3]$ 之类的都行,答案就是 $5+4+3=12$。

再考虑三段和的最小值怎么求,我们只要枚举中段只有1个数或者左右两段都只有1个数的分割方法。因为如果整个数列的最大的数是 $a_k$(如果有几个数都是最大的,随便找一个),那么 $a_k$ 被分到的段肯定越长越好:

  • 若 $a_k$ 在左段或右段,可以让中段只有1个数。比如[3,5],[4,1],[3]显然把左段加长更好:[3,5,4],[1],[3]。这种用一个 for 循环枚举中段包含哪一个数,用刚才处理出的 L[]R[] 数组求答案。
  • 若 $a_k$ 在中段,可以让左右两段都只有1个数。比如[3],[5,1],[4,3]显然把中段加长更好:[3],[5,1,4],[3]。这种直接按 $1,n-2,1$ 分割然后算答案就好了。

在这些情况中求最小的三段和即可,这样枚举量只有 $n$ 级别了,可以得到100分。


秋游

关键字:贪心,问题转化

如果 $m=0$,只要考虑学生的满意度。对每个 $k$,要让 $k$ 个学生秋游,一定是让 $a_i$ 最大的那 $k$ 个学生去。于是把 $a_i$ 排序以后,从大到小一边累加一边输出。(下面这个代码要 #include <algorithm>

std::sort(a + 1, a + n + 1);
int s = 0; // 总满意度
for(int i = n; i; i--) printf("%d\n", s += a[i]);

如果 $m>0$,需要考虑朋友关系,看起来不是很好处理。

可以用搜索算法(如深度优先搜索)搜索所有可能的情况,对每种情况计算满意度。然而 $n$ 个学生一共有 $2^n$ 种选取方式,对于 $n=100000$ 的数据搜索是一定会超时的。我们需要一些更好的处理方法。

对于一对朋友关系 $j$,它对满意度的影响可以表示成 $(t-1)\cdot w_j = t\cdot w_j - w_j$,其中 $t$ 表示 $u_j,v_j$ 两人中,有几个人去了秋游。因此在计算总满意度的时候,可以先把总满意度减掉 $w_j$,然后 $u_j$ 和 $v_j$ 每有一个人去秋游,总满意度加 $w_j$。

所以只要对于每对朋友关系 $j$,把 $a_{u_j}$ 和 $a_{v_j}$ 加上 $w_j$,最后答案减掉 $w_j$,就可以不管这条边了。这样就把问题转化成了 $m=0$ 的情况。排序以后输出 $a$ 累加的结果减去所有 $w_j$ 的和就行了:

int s = 0; // 总满意度
for(int j = 1; j <= m; j++) a[u[j]] += w[j], a[v[j]] += w[j], s -= w[j];
std::sort(a + 1, a + n + 1);
for(int i = n; i; i--) printf("%d\n", s += a[i]);

这样就可以轻松得到满分了。


兔子繁殖

关键字:递推,前缀和

1. 80分算法

稍微有点常识就会发现,兔子的繁殖数量是指数级增长的,用简单的模拟法,记录每对兔子的年龄,计算机内存无法接受。

注意到所有兔子的年龄都在 $0$ 到 $n-1$ 之间,不妨换一种模拟方法:记录每个月,年龄为 $0$ 的兔子有多少对,年龄为 $1$ 的兔子有多少对,……,年龄为 $n-1$ 的兔子有多少对。开一个数组 f[i] 表示年龄为 $i$ 的兔子数量,那么每个月所有兔子的年龄增加 $1$ 就是这个操作:

for(int i = n - 1; i >= 0; i--) f[i + 1] = f[i];
f[0] = 0;

繁殖则是这样的操作:

for(int i = 0; i < m && k + i * t < n; i++) f[0] += f[k + i * t];

这样你会发现一个问题:使用32位整数 int 类型甚至64位整数 long long 类型都会溢出!这时候仔细看题目,题目只要输出答案除以 $10007$ 的余数,也就是如果答案为 $x$,输出的是 $x\bmod 10007$。并且我们知道模运算有很好的性质,那就是对任意整数 $a,b$ 和正整数 $p$,有:

$$(a+b)\bmod p=a\bmod p+b\bmod p$$

所以任何时候我们都只要记录当前的兔子数量除以10007的余数。只要把繁殖操作改一改:

const int mod = 10007;
for(int i = 0; i < m && k + i * t < n; i++) f[0] = (f[0] + f[k + i * t]) % mod;

这样就能求出第 $m$ 个月每种年龄的兔子有多少对,把未死亡的兔子数量加起来以后求出除以10007的余数输出就是答案了。

很好,这样的运算量是 $n^2$ 级别的,可以轻松通过 $n\le 2000$ 的测试数据了。当然我们注意到这题有一类特殊的测试数据:$k\le 4,t=1,m=n$。这意味着什么?每对兔子出生至多 $4$ 个月以后,每个月都会生出兔子,且 $n$ 个月以内不会死亡。那么年龄在 $4$ 以上的兔子都是一样的,只要记录年龄为 $0,1,2,3,4$ 的兔子数量这五个信息就行了,只要 $5n$ 级别的运算量。

把 $n\le 2000$ 和 $k\le 4,t=1,m=n$ 的两个程序用 if 语句拼起来,可以获得80分。

2. 100分算法

遗憾的是上面的算法并不能通过一般的 $n=10^7$ 的测试数据,毕竟用 for 循环从 $1$ 遍历到 $10^7$ 都需要不少的时间了。

其实我们只要考虑刚出生的兔子就行了。因为兔子的出生时间确定了,繁殖和死亡时间也就确定了。第 $n$ 个月未死亡的兔子就是出生在第 $n-k-(m-1)t+1$ 个月到第 $n$ 个月的兔子数量。

开一个数组 $f[i]$ 存第 $i$ 个月出生的兔子有多少对(注意还是只要存除以10007的余数),显然 $f[1] = 1$。当 $i>1$ 时怎么计算 $f[i]$ 呢?

对于第 $i$ 个月,可以发现,第 $i-k,i-k-t,i-k-2t,\cdots,i-k-(m-1)t$ 这些月份出生的每对兔子恰好生出一对第 $i$ 个月出生的兔子,而其余月份出生的兔子不会生成第 $i$ 个月出生的兔子。因此可以得到递推式

$$f[i]=f[i-k]+f[i-k-t]+f[i-k-2t]+\cdots+f[i-k-(m-1)t]$$

如果下标是负的就当成 $0$。如果直接用这个式子递推,求和需要花费比较多的时间。不过等号右边的 $f$ 的下标除以 $t$ 的余数都相同。比如 $t=3$,如果我们把 $f$ 数组摆成这样:

f[1]        f[4]        f[7]        f[10]            ...
    f[2]        f[5]        f[8]        f[11]        ...
        f[3]        f[6]        f[9]        f[12]    ...

那么对某个 $f[i]$,它的值是上面这个数组某一行的某一个连续段的和

这可以用前缀和技巧来加速计算,也就是我们开一个数组 $g[i]$ 存上面的 $f[i]$ 往左的所有数之和。

例如当 $t=3$ 时,$g[11]=f[11]+f[8]+f[5]+f[2]$。这样用前缀和相减就可以快速得到一段区间的和。还是假设 $t=3$,比如要算 $f[5]+f[8]+f[11]$,只需两端的 $g$ 相减,即 $g[11]-g[2]$。

处理这个 $g$ 数组非常简单,如果 $i\le t$,那么 $g[i]=f[i]$,否则 $g[i]=f[i]+g[i-t]$ 这样递推就好了。

于是按 $i$ 从小到大依次推出 $f[i],g[i]$,最后统计第 $n-k-(m-1)t+1$ 个月到第 $n$ 个月的兔子有多少对就做完了,注意负下标要当成 $0$。可以获得100分。

评论

shaodanyu
第二题现在终于发现我的思路是正确的但是没有判断ak所在的区间
  • 2017-09-24 21:13:57