UNR 参赛小结()

Day 0

咕了,喜提笔试 \(0\) 分。

Day 1

T1

hehe 蚤面基了一个人之后,可以认为这个人一直贴着他走,那么终状态一定是所有人齐聚一堂。

而所有人齐聚一堂时,一定可以直接光速依次面基所有人,故找一个点,到所有人最短路距离最长即可。

但我没开 ,白挂 \(35\) 分。

long long

T2

对最终串计数,最终串是长度为 \(2t+n\),并且 , 的数量都是已知的。

0
1

考虑如何判断一个最终串 \(T\) 是否合法,一个自然的思路是,把 \(S\) 放上去贪心匹配:在两字符相等的情况下匹配之,反之若匹配之能使得未匹配的字符中 的个数不小于 的个数则匹配,否则不匹配。

0
1

但是这样有一个问题,若 \(S\) 当前需要匹配的字符是 ,最终串当前位是 ,肯定匹配不了,但如果加上这个 的话会使未匹配的字符中 的个数比 的个数少,就寄了。

0
1
1
0
1

我直接爆猜一个结论:如果遇到这种情况,就把 \(S\) 的匹配从后往前退掉,一直退到第一个位置,使得未匹配的字符 , 个数相等。

0
1
  • 必要性:此时 \(S\) 匹配的最长前缀,一定满足未匹配字符 0, 1 个数相等,这个位置是最右的一个;
  • 充分性:我退掉的东西,除了最后一个退的 0 外,一定是括号序列,与原未匹配字符合并肯定没影响。

然后就可以直接压进状态 DP 套 DP 了。

T3

没有时间了,没仔细想。

————————

Day 0

咕了,喜提笔试 \(0\) 分。

Day 1

T1

hehe 蚤面基了一个人之后,可以认为这个人一直贴着他走,那么终状态一定是所有人齐聚一堂。

而所有人齐聚一堂时,一定可以直接光速依次面基所有人,故找一个点,到所有人最短路距离最长即可。

但我没开 ,白挂 \(35\) 分。

long long

T2

对最终串计数,最终串是长度为 \(2t+n\),并且 , 的数量都是已知的。

0
1

考虑如何判断一个最终串 \(T\) 是否合法,一个自然的思路是,把 \(S\) 放上去贪心匹配:在两字符相等的情况下匹配之,反之若匹配之能使得未匹配的字符中 的个数不小于 的个数则匹配,否则不匹配。

0
1

但是这样有一个问题,若 \(S\) 当前需要匹配的字符是 ,最终串当前位是 ,肯定匹配不了,但如果加上这个 的话会使未匹配的字符中 的个数比 的个数少,就寄了。

0
1
1
0
1

我直接爆猜一个结论:如果遇到这种情况,就把 \(S\) 的匹配从后往前退掉,一直退到第一个位置,使得未匹配的字符 , 个数相等。

0
1
  • 必要性:此时 \(S\) 匹配的最长前缀,一定满足未匹配字符 0, 1 个数相等,这个位置是最右的一个;
  • 充分性:我退掉的东西,除了最后一个退的 0 外,一定是括号序列,与原未匹配字符合并肯定没影响。

然后就可以直接压进状态 DP 套 DP 了。

T3

没有时间了,没仔细想。