2020-team12-028

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W7standing.png, 1000px)]]

== 亮点 ==

在卡J的情况下，正确的安排ctc去空机上码大搜索A题，投资1.5小时空机时成功A过。

== 问题 ==

whn轻视J题，第一发出了会T签到的算法，B题.Lf和.f问题。

ctc的J题对题意理解不清晰，其实应该对两个题意都交一发就不会有中间找“错”的时间，a题中状态理解想当然，贪代码长度，导致wa多次。

== 题解 == 

A:拼图，大力dfs，码力题。ctcnb

B:水DP，dp[i][j]表示前i轮有j个只有1个机会的获得了，然后每轮计算一次这一轮我们得到票的机会。whn两个主要错误：①j和i-j不可以超过A和B。 ②c++11不可以printf（.Lf）（WA）,但是c++17可以。

C:仙人掌，待补.

D:建立根节点，先将每个单词前后字母连权为1的有向边并连向根（得到一棵符合题意但不最优的树），再对于所有的单词i和单词j满足i后缀=j前缀对应位置连权为0的有向边，然后跑最小树形图。
hdu的最小树形图(edmunds)板子可撕。

E:几何，似乎是三分套三分，待补。

F: 签到题，第一次见“文件读写”。

G:另一个几何，待补。

H: 水题，szb.

I: 交互，最重要的是跳出“二分待定区间”的思维定势而转为只考虑距离<x. 由于初始位置的取值范围不是1e9，考虑维护L[i],R[i]表示假定初始位置是i速度的上下界，每次算出可能的位置下界(min(l[i]*t+i)),和上界（同理），然后可以更新所有的速度上下界。复杂度上界是1e5*100，实际好像只需要询问log1e9次？

J: 根据题意实现，注意只需要维护每个人为结尾连出的最长链和位置即可不需要存vector.（whn犯的错误）

K: 较易题，先讨论n=1的情况（胜负只由手上的牌决定），再算出可能成为我的颜色的“对手”的最大颜色，对每个位置分其是我的颜色、对手颜色和其他颜色讨论即可。

[/wiki/2020-team12 返回]

亮点

在卡J的情况下，正确的安排ctc去空机上码大搜索A题，投资1.5小时空机时成功A过。

问题

whn轻视J题，第一发出了会T签到的算法，B题.Lf和.f问题。

ctc的J题对题意理解不清晰，其实应该对两个题意都交一发就不会有中间找“错”的时间，a题中状态理解想当然，贪代码长度，导致wa多次。

题解

A:拼图，大力dfs，码力题。ctcnb

B:水DP，dp[i][j]表示前i轮有j个只有1个机会的获得了，然后每轮计算一次这一轮我们得到票的机会。whn两个主要错误：①j和i-j不可以超过A和B。 ②c++11不可以printf（.Lf）（WA）,但是c++17可以。

C:仙人掌，待补.

D:建立根节点，先将每个单词前后字母连权为1的有向边并连向根（得到一棵符合题意但不最优的树），再对于所有的单词i和单词j满足i后缀=j前缀对应位置连权为0的有向边，然后跑最小树形图。

hdu的最小树形图(edmunds)板子可撕。

E:几何，似乎是三分套三分，待补。

F: 签到题，第一次见“文件读写”。

G:另一个几何，待补。

H: 水题，szb.

I: 交互，最重要的是跳出“二分待定区间”的思维定势而转为只考虑距离

J: 根据题意实现，注意只需要维护每个人为结尾连出的最长链和位置即可不需要存vector.（whn犯的错误）

K: 较易题，先讨论n=1的情况（胜负只由手上的牌决定），再算出可能成为我的颜色的“对手”的最大颜色，对每个位置分其是我的颜色、对手颜色和其他颜色讨论即可。

附加文件