2018-team7-T01

从 Trac 迁移的文章

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

原文章内容如下：

  * [wiki:Summer2018Team 返回上层]
  * [wiki:2018-team7 队伍主页]
  * [wiki:2018-team7 上场比赛]
  * [wiki:2018-team7-T02 下场比赛]

== 流水账 ==

比赛链接：https://vjudge.net/contest/259352

[[Image(submit01.png,500px)]]

[[Image(T01.png,800px)]]

yrb H签到'''50m1Y'''[[br]]
E题一眼看过去是个缩点，然后去重边通过度数直接判是不是一条链。交错代码T了一发然后WA了一发,然后发现有些其他情况，改用topo判，同时最多只有一个在队列里，'''133m3Y'''[[br]]
B wsh 觉得能做，就上了。J大家都不太明白正则，题意理解跑偏了很久，yrb想了dp方程，后面发现题意不对，改的时候没改全，挂了好几发。
yrb J '''264m4Y'''

== 总结 ==

感觉读题还是要好好读的，最近读题经常崩，写完发现题意错了不好改而且很伤。以后建议战术板（草稿纸）上还是要大概写一写什么题要读/存疑/已读/难度/分类之类的。


=== IDrandom(yrb) ===

太莽了我啊，总是粗心，改得不够仔细。


=== CtrlCV(wsh) ===


=== godspeedcurry(zzh) ===
dp 中间变量 long long 需要特别注意


== 题解 ==
A:

B:wsh

C:

D:

E:缩点后topo(yrb)   (DFS暴力统计)zzh

F:多源次短路(from ACetic_ACid)以点集中的点为起点跑dij，正着跑一遍反着跑一遍（以自身为起/终点，正反中间重新初始化一次），不每次都初始化dis，复杂度玄学但是跑得很快（yrb）二进制分组+多源次短路（std）

G:

H:签到题，每次找最小的点添加进原集合，然后暴力把该点和原集合的点的和删去。

I:

J:dp[i][j]表示第二个串的第i位结尾能不能匹配至第一个串的第j位，对于*的状态要观察str1[j]和之前几位相等的状态，因此额外维护一个数组用来弄这个。注意*可以匹配0个。

K:--

L:--

M:--


== 补题 ==

|| Contest Name                                                || A || B || C || D || E || F || G || H || I || J || K || L || M ||
||2017 - Multi-University Training 9 by BUPT                   || * || * || - || - || O || Ø || - || O || - || O || X || X || X ||

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补

  * [wiki:Summer2018Team 返回上层]
  * [wiki:2018-team7 队伍主页]
  * [wiki:2018-team7 上场比赛]
  * [wiki:2018-team7-T02 下场比赛]

流水账

比赛链接：https://vjudge.net/contest/259352

yrb H签到50m1Y[[br]]

E题一眼看过去是个缩点，然后去重边通过度数直接判是不是一条链。交错代码T了一发然后WA了一发,然后发现有些其他情况，改用topo判，同时最多只有一个在队列里，133m3Y[[br]]

B wsh 觉得能做，就上了。J大家都不太明白正则，题意理解跑偏了很久，yrb想了dp方程，后面发现题意不对，改的时候没改全，挂了好几发。

yrb J 264m4Y

总结

感觉读题还是要好好读的，最近读题经常崩，写完发现题意错了不好改而且很伤。以后建议战术板（草稿纸）上还是要大概写一写什么题要读/存疑/已读/难度/分类之类的。

IDrandom(yrb)

太莽了我啊，总是粗心，改得不够仔细。

CtrlCV(wsh)

godspeedcurry(zzh)

dp 中间变量 long long 需要特别注意

题解

A:

B:wsh

C:

D:

E:缩点后topo(yrb) (DFS暴力统计)zzh

F:多源次短路(from ACetic_ACid)以点集中的点为起点跑dij，正着跑一遍反着跑一遍（以自身为起/终点，正反中间重新初始化一次），不每次都初始化dis，复杂度玄学但是跑得很快（yrb）二进制分组+多源次短路（std）

G:

H:签到题，每次找最小的点添加进原集合，然后暴力把该点和原集合的点的和删去。

I:

J:dp[i][j]表示第二个串的第i位结尾能不能匹配至第一个串的第j位，对于*的状态要观察str1[j]和之前几位相等的状态，因此额外维护一个数组用来弄这个。注意*可以匹配0个。

K:--

L:--

M:--

补题

Contest Name A B C D E F G H I J K L M
2017 - Multi-University Training 9 by BUPT * * - - O Ø - O - O X X X

O:当场通过 .:尚未通过 Ø:赛后通过 #:口胡通过 X:不存在的 -:赛后待补 *:真-赛后待补

附加文件