2018-team7-E04

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
[wiki:2018-C04 比赛资源链接][[br]]
[[Image(submit.png,500px)]]

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

这场比赛从两个半小时以后才开始陆陆续续的过题，实在是签到最慢的一次了。yrb日常读L，zzh读A，wsh读D，yrb读了L感觉这题应该是能做的，但没想出做法，于是给wsh讲了题意，于是三个人并没有一下看到签到题，这个时候场上B有人过了，但是Bzzh还没读完，yrb继续想L，wsh继续读题，zzh读完B给我们讲了题意，于是yrb思考了一下B，wsh也读完了K，是个几何体，与yrb交流了一下，yrb嘴巴了一个做法，但是细节上觉得有些问题，wsh表示能做就上了，zzh读了I，不过yrb并没有听懂，而且感觉B有点思路了于是就先放着I，后来B想到了做法，wsh也卡了K，yrb就上去敲，但是出现了一些奇怪的错误，fix了以后wsh出了几组数据，发现segmentfault，于是加了个print调，调了很久没调出来，wsh debug了K，yrb就把B打印下来调，在此期间wsh没注意文件读入pe两发然后加了读入就过了K，yrb上机继续调B，调了几分钟感觉莫名其妙于是把print删了打算测一下小数据发现没问题，去测之前的几组数据发现居然也没问题了，黑人问号？？？直接交了1Y，然后读了I，yrb和wsh都有点想法，yrb先想了个n^3^的dp，维护一下变成了n^2^,上去写了一小半发现好像推错了，wsh想了个奇怪的贪心，上去挂了两发，yrb重新推了一下感觉没问题了然后上去因为各种傻逼错误挂了两发然后过了，然后zzh继续去写J的构造，交了一发挂了，yrb听了一发做法感觉直觉上是错的，但一时也没想到做法，最后wsh YY出了做法后1Y

== 总结 ==

感觉这场开题顺序不太对，K是几何题全队都比较烂但是因为先有想法就先上了，B边界抠的也有一点麻烦但是也是直接上了，而且这个时候一个人在写另一个人居然还在想这题怎么做，我（yrb）觉得有点浪费，这时候应该要么开题要么构造样例的。I同时两个人上多挂了好几发，还好队友想出了J并且顺利过掉，死相没有太难看。

 * 凡事都要谋定而后动，如果能估计出代码量或者细节有些麻烦的时候，应该多看看其他题目
 * 在队伍里某人敲定了某题比较科学的做法的时候，这时候其他队友应该停止主要思考这题的其他解法，而是应该去试图构造样例/读一读其他题目

=== IDrandom(yrb) ===
今天基本没有读到什么有用的题目，都是队友读题我在想，不过B类似数位dp，我数位dp有点稀，但是I这种dp还是比较有把握的，应该认真把I理解一下先的

=== CtrlCV(wsh) ===
今天发现自己对于几何方面还是不熟练，正常的一个求叉积加一个two point都调了一个多小时，最后发现是一个傻逼的>=写成>的错误。不过庆幸的是自己对于构造类题目还是有灵机一动的潜质的，十分钟写出代码直接通过我自己都怕了hhh。今天我的侧重点搞错了，我应该是队伍里负责翻译题目和负责构造样例的，由于我的疏忽导致全队卡题的情况出现

=== godspeedcurry(zzh) ===
zzh：今天题目难度较大，所以只能通过多开题找合适的题下手，我的任务基本局限于读题后思考算法，然后告诉队友题意，他们主写代码，现在知识非常薄弱，有时候也会头铁去乱搞一发，WA是自然的，坚持训练下去，一定会有反弹的


== 题解 ==
A:

B:顺序序列字典序是最小的，而维持原序列尽量长的前缀不变一定更小，而符合题意的合法序列一定满足把序列划分成若干段，然后将段末的数字提前到段首。那么长度为n的划分数为2^(n-1),于是依次枚举不变的长度，将固定这一段不变的情况数剪掉，然后问题被划分成相同的子问题（类似数位dp）（IDrandom）

C:

D:

E:

F:

G:

H:

I:如果从前往后不好想前面的对当前位的贡献，于是从后往前考虑，dp[i]表示i~n所需要的最小花费，于是转移的时候枚举k，dp[i]=max(dp[k]+t[k-1]*(n-i+1))(i<k<=n+1) (IDrandom)

J:n=3时只用一种颜色，n=4、5、6时使用两种颜色间隔涂色，n>6时最小色数为3，这里给出两种构造方案：第一种，外层按1, 2, 3, 1, 2, 3, ...的顺序涂色，内层每条边都和该点在外侧的边不同，构造好后也是形如1, 2, 3, ...。第二种：外层全部涂3，内层按1, 2, 1, 2, ...间隔涂色 (CtrlCV)

K:

L:

M:--


== 补题 ==

|| Contest Name                                                || A || B || C || D || E || F || G || H || I || J || K || L || M ||
||2013 Winter Petrozavodsk Camp - Andrew Stankevich            || - || O || - || - || - || - || - || * || O || O || O || * || X ||

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


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

流水账

比赛资源链接[[br]]

这场比赛从两个半小时以后才开始陆陆续续的过题，实在是签到最慢的一次了。yrb日常读L，zzh读A，wsh读D，yrb读了L感觉这题应该是能做的，但没想出做法，于是给wsh讲了题意，于是三个人并没有一下看到签到题，这个时候场上B有人过了，但是Bzzh还没读完，yrb继续想L，wsh继续读题，zzh读完B给我们讲了题意，于是yrb思考了一下B，wsh也读完了K，是个几何体，与yrb交流了一下，yrb嘴巴了一个做法，但是细节上觉得有些问题，wsh表示能做就上了，zzh读了I，不过yrb并没有听懂，而且感觉B有点思路了于是就先放着I，后来B想到了做法，wsh也卡了K，yrb就上去敲，但是出现了一些奇怪的错误，fix了以后wsh出了几组数据，发现segmentfault，于是加了个print调，调了很久没调出来，wsh debug了K，yrb就把B打印下来调，在此期间wsh没注意文件读入pe两发然后加了读入就过了K，yrb上机继续调B，调了几分钟感觉莫名其妙于是把print删了打算测一下小数据发现没问题，去测之前的几组数据发现居然也没问题了，黑人问号？？？直接交了1Y，然后读了I，yrb和wsh都有点想法，yrb先想了个n3的dp，维护一下变成了n2,上去写了一小半发现好像推错了，wsh想了个奇怪的贪心，上去挂了两发，yrb重新推了一下感觉没问题了然后上去因为各种傻逼错误挂了两发然后过了，然后zzh继续去写J的构造，交了一发挂了，yrb听了一发做法感觉直觉上是错的，但一时也没想到做法，最后wsh YY出了做法后1Y

总结

感觉这场开题顺序不太对，K是几何题全队都比较烂但是因为先有想法就先上了，B边界抠的也有一点麻烦但是也是直接上了，而且这个时候一个人在写另一个人居然还在想这题怎么做，我（yrb）觉得有点浪费，这时候应该要么开题要么构造样例的。I同时两个人上多挂了好几发，还好队友想出了J并且顺利过掉，死相没有太难看。

  • 凡事都要谋定而后动，如果能估计出代码量或者细节有些麻烦的时候，应该多看看其他题目
  • 在队伍里某人敲定了某题比较科学的做法的时候，这时候其他队友应该停止主要思考这题的其他解法，而是应该去试图构造样例/读一读其他题目

IDrandom(yrb)

今天基本没有读到什么有用的题目，都是队友读题我在想，不过B类似数位dp，我数位dp有点稀，但是I这种dp还是比较有把握的，应该认真把I理解一下先的

CtrlCV(wsh)

今天发现自己对于几何方面还是不熟练，正常的一个求叉积加一个two point都调了一个多小时，最后发现是一个傻逼的>=写成>的错误。不过庆幸的是自己对于构造类题目还是有灵机一动的潜质的，十分钟写出代码直接通过我自己都怕了hhh。今天我的侧重点搞错了，我应该是队伍里负责翻译题目和负责构造样例的，由于我的疏忽导致全队卡题的情况出现

godspeedcurry(zzh)

zzh：今天题目难度较大，所以只能通过多开题找合适的题下手，我的任务基本局限于读题后思考算法，然后告诉队友题意，他们主写代码，现在知识非常薄弱，有时候也会头铁去乱搞一发，WA是自然的，坚持训练下去，一定会有反弹的

题解

A:

B:顺序序列字典序是最小的，而维持原序列尽量长的前缀不变一定更小，而符合题意的合法序列一定满足把序列划分成若干段，然后将段末的数字提前到段首。那么长度为n的划分数为2^(n-1),于是依次枚举不变的长度，将固定这一段不变的情况数剪掉，然后问题被划分成相同的子问题（类似数位dp）（IDrandom）

C:

D:

E:

F:

G:

H:

I:如果从前往后不好想前面的对当前位的贡献，于是从后往前考虑，dp[i]表示i~n所需要的最小花费，于是转移的时候枚举k，dp[i]=max(dp[k]+t[k-1]*(n-i+1))(i

J:n=3时只用一种颜色，n=4、5、6时使用两种颜色间隔涂色，n>6时最小色数为3，这里给出两种构造方案：第一种，外层按1, 2, 3, 1, 2, 3, ...的顺序涂色，内层每条边都和该点在外侧的边不同，构造好后也是形如1, 2, 3, ...。第二种：外层全部涂3，内层按1, 2, 1, 2, ...间隔涂色 (CtrlCV)

K:

L:

M:--

补题

Contest Name A B C D E F G H I J K L M
2013 Winter Petrozavodsk Camp - Andrew Stankevich - O - - - - - * O O O * X

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

附加文件