2019-team666-0001

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]
== 概述 ==
七月集训第一场
签到题签的很快，tjc从前往后读，yyc从后往前读，tjc很快做出了A,B,'''A1Y6''','''B1Y23''',期间yyc做出了G，'''G1Y34''',然后换tjc写C，'''C1Y39''',之后yyc提出了一个K的做法并尝试去写，但是WA了，tjc提出了J的三分做法，于是yyc暂时放弃K去写J，'''J1Y62'''，tjc开始做F，在发现题意理解稍有问题后迅速过掉了，'''F2Y77''',yyc继续尝试K几次后发现做法是假的，在和tjc讨论中曾得出正确的做法但是没有去写，之后讨论I发现是网络流后由tjc写，但是做法由于没有把相同状态的点合并而没有通过，期间yyc得到了E的n^2^log做法，但是不能处理相同权值所以不能通过。
== 总结 ==
=== yyc ===
在最后的时候什么做法都应该尝试一下而不是对着很可能做不出来的题硬想。
=== tjc  ===
划分等价类似乎是个很有用的技巧，这次的DI两题都用到了这个思想
=== hyw  ===
=== 题解 ===
A：略
B：略
C：略
D：记忆化搜索，注意无法区分具有传递性，所以搜索时两个点同时出现就把它们放到同一个并查集里，如果两个点在同一个并查集里就不要继续搜索
E：先考虑所有元素都不同，f[i]表示考虑前i小的位置上合法序列的方案数，每次用总排列数-不合法的排列数，枚举第一个不合法的位置转移，发现有相同的稍加修改就行了。（赛时那个做法可能是没救了...）
F：略
G：略
H：做变形的dijkstra,每个点两个状态存从这个点到终点是第一步想尽可能小/大(1/0)的距离，将边反向，从终点到起点，从0到1时可以随意转移，从1到0必须与当前点相连的所有点都转移后才能转移。（道理可能与博弈问题类似？）
I：二分+网络流，一侧点数只有10个，等价状态可以合并，压缩成1024个点
J：略
K：ans=n/2上取整，dfs一遍，按叶子节点访问顺序排序，将v_i和v_{i+n/2}配对。
L：无
M：无

[/wiki/2019-team666 返回]

概述

七月集训第一场

签到题签的很快，tjc从前往后读，yyc从后往前读，tjc很快做出了A,B,A1Y6,B1Y23,期间yyc做出了G，G1Y34,然后换tjc写C，C1Y39,之后yyc提出了一个K的做法并尝试去写，但是WA了，tjc提出了J的三分做法，于是yyc暂时放弃K去写J，J1Y62，tjc开始做F，在发现题意理解稍有问题后迅速过掉了，F2Y77,yyc继续尝试K几次后发现做法是假的，在和tjc讨论中曾得出正确的做法但是没有去写，之后讨论I发现是网络流后由tjc写，但是做法由于没有把相同状态的点合并而没有通过，期间yyc得到了E的n²log做法，但是不能处理相同权值所以不能通过。

总结

yyc

在最后的时候什么做法都应该尝试一下而不是对着很可能做不出来的题硬想。

tjc

划分等价类似乎是个很有用的技巧，这次的DI两题都用到了这个思想

hyw

题解

A：略

B：略

C：略

D：记忆化搜索，注意无法区分具有传递性，所以搜索时两个点同时出现就把它们放到同一个并查集里，如果两个点在同一个并查集里就不要继续搜索

E：先考虑所有元素都不同，f[i]表示考虑前i小的位置上合法序列的方案数，每次用总排列数-不合法的排列数，枚举第一个不合法的位置转移，发现有相同的稍加修改就行了。（赛时那个做法可能是没救了...）

F：略

G：略

H：做变形的dijkstra,每个点两个状态存从这个点到终点是第一步想尽可能小/大(1/0)的距离，将边反向，从终点到起点，从0到1时可以随意转移，从1到0必须与当前点相连的所有点都转移后才能转移。（道理可能与博弈问题类似？）

I：二分+网络流，一侧点数只有10个，等价状态可以合并，压缩成1024个点

J：略

K：ans=n/2上取整，dfs一遍，按叶子节点访问顺序排序，将v_i和v_{i+n/2}配对。

L：无

M：无