2020-team11-C03

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team11 返回]
== 概述 ==
solved: 6/12  dirt: 50%
rank: 7
[[Image(2020-C03.png,700px)]]
==  ==
== 总结 ==
Qza 很晚才摸到键盘，并且过掉了 D，之后 Qza 就在一边想 F 一边摸鱼。后来发现 F 的复杂度分析错了，本来的思路就是正解，遂上机开始写 F 的预处理。写完预处理后思路断掉了，故让出机位调试 I。后来 I 没调出来，Qza 上机把 F 写完并且 WA 掉了样例，便又开始调试。改了几个 bug 后，发现预处理时没有考虑 '\0' 的情况，下机思考了一会儿后（吃了顿饭），又把 '\0' 的情况补了上去。结果导致问号的地方也会被 '\0' 填充。在各种特判、手动容斥后，Qza 终于发现在预处理中补上 28 个 if 就可以解决这个问题。遂过了样例并且 WA3。手造了一组数据卡掉自己后，Qza 补了个全局变量，又换了dfs 的终止条件。然后 Qza 就在 04:53 的时候把 F 过掉了。
Zhw 一开始节奏比较好，写签到题也基本没有卡，但是写i题的时候由于一个情况没有考虑周全，所以卡了将近1h。由于没有思路所以改去切l题，很顺利就写出来了，到后来qza提供hack数据才发现问题。感觉最后一段时间机时利用不够高效。
吴剑昊主要为二位的战场提供火力支援，提供题目思路，顺便寻找各类水题。在F和I卡住时帮助二位debug，由于是Z、Q二位负责主要的代码工作，wjh认为这次的翻译工作和思路还算能够跟上。之后会多学习dp思路，使团队的合作更加顺畅。
Qza 觉得今天由于交挂而导致的罚时不多，表现还好。
== 题解 ==
A: 
B: 
C：写出公式n=(b-a+1)*(a+b)/2
D：n^2^连边，然后黑白染色，输出的时候分三种情况讨论一下即可。
E：
F：设三个字符串为s0，s1，s2。首先发现，从前向后填充问号时，当前填充的问号仅会对后面的填充产生4种影响：s0已经小于s1、s0仍然等于s1、s1已经小于s2、s2仍然等于s2。于是考虑将这四种状态放到dfs的参数里，然后对于每一个问号，枚举字符进行填充。这样显然会TLE，进一步考虑到在填充某一个问号时，某些填充情况可以合并到一起来算，故可以预处理这些合并到一起的状态的数量，在dfs的时候乘到答案里即可。注意'\0'的情况，问号不可以被'\0'填充，但是'\0'的情况一定要预处理。所以需要在预处理时加一堆特判。另外注意多组数据要清空数组。
G：
H：考虑n最大为两百那就将所有1～n是否满足处理出来
I：B和W的比值是可以直接算出来的，那么为了保证段数最多，那就从一开始循环，满足比值就断开就行了。
J：
K：
L：考虑区间dpi,j表示时间完全在i～j区间内的怪兽的cost是多少，转移就先选出cost最大的怪兽，枚举在哪一个时间去打他，然后就将区间分为两段，转移即可

[/wiki/2020-team11 返回]

概述

solved: 6/12 dirt: 50%

rank: 7

总结

Qza 很晚才摸到键盘，并且过掉了 D，之后 Qza 就在一边想 F 一边摸鱼。后来发现 F 的复杂度分析错了，本来的思路就是正解，遂上机开始写 F 的预处理。写完预处理后思路断掉了，故让出机位调试 I。后来 I 没调出来，Qza 上机把 F 写完并且 WA 掉了样例，便又开始调试。改了几个 bug 后，发现预处理时没有考虑 '\0' 的情况，下机思考了一会儿后（吃了顿饭），又把 '\0' 的情况补了上去。结果导致问号的地方也会被 '\0' 填充。在各种特判、手动容斥后，Qza 终于发现在预处理中补上 28 个 if 就可以解决这个问题。遂过了样例并且 WA3。手造了一组数据卡掉自己后，Qza 补了个全局变量，又换了dfs 的终止条件。然后 Qza 就在 04:53 的时候把 F 过掉了。

Zhw 一开始节奏比较好，写签到题也基本没有卡，但是写i题的时候由于一个情况没有考虑周全，所以卡了将近1h。由于没有思路所以改去切l题，很顺利就写出来了，到后来qza提供hack数据才发现问题。感觉最后一段时间机时利用不够高效。

吴剑昊主要为二位的战场提供火力支援，提供题目思路，顺便寻找各类水题。在F和I卡住时帮助二位debug，由于是Z、Q二位负责主要的代码工作，wjh认为这次的翻译工作和思路还算能够跟上。之后会多学习dp思路，使团队的合作更加顺畅。

Qza 觉得今天由于交挂而导致的罚时不多，表现还好。

题解

A:

B:

C：写出公式n=(b-a+1)*(a+b)/2

D：n2连边，然后黑白染色，输出的时候分三种情况讨论一下即可。

E：

F：设三个字符串为s0，s1，s2。首先发现，从前向后填充问号时，当前填充的问号仅会对后面的填充产生4种影响：s0已经小于s1、s0仍然等于s1、s1已经小于s2、s2仍然等于s2。于是考虑将这四种状态放到dfs的参数里，然后对于每一个问号，枚举字符进行填充。这样显然会TLE，进一步考虑到在填充某一个问号时，某些填充情况可以合并到一起来算，故可以预处理这些合并到一起的状态的数量，在dfs的时候乘到答案里即可。注意'\0'的情况，问号不可以被'\0'填充，但是'\0'的情况一定要预处理。所以需要在预处理时加一堆特判。另外注意多组数据要清空数组。

G：

H：考虑n最大为两百那就将所有1～n是否满足处理出来

I：B和W的比值是可以直接算出来的，那么为了保证段数最多，那就从一开始循环，满足比值就断开就行了。

J：

K：

L：考虑区间dpi,j表示时间完全在i～j区间内的怪兽的cost是多少，转移就先选出cost最大的怪兽，枚举在哪一个时间去打他，然后就将区间分为两段，转移即可

附加文件