2016-E42-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<pre class="wiki" style="font: normal 13px Consolas">
┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│ 2017/03/24 14:00-19:00 · Siunaus · Akalm/JTJL/sfiction │
├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│H [0:19]│ 1 2 3 OooOoOo!# │
│I [0:09]│ 1 23o. o# │
│K [0:28]│ 1 o2ooOOoo..3..! !.o# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│C8[1:02]│ 1 oooo.ooOo. .OOoOOoo.oO! o.!!o!. .O!. # │
│E [0:48]│ .OoOOOoOO1 Oooo...o!.2 o!.. ! 3ooo# │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│A [0:03]│1o# │
│B [0:07]│ 12 3OO# │
│D [0:25]│ 1 oooOoOOo2o# 3 │
│F [0:23]│ 1 OO!. 2 oOOoooo# 3 │
├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤
│* [3:46]│ oOoOoOOOooOoOOOoOOOOooOOoo..oOooo..OooOOoOooOoOooo.oOOoooooooooooo.ooOoOooOoOOoOooOOoOOoo.oO. o...oo. .Oo. o │
├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│G [0:00]│ 1 2 │
│J2[0:00]│ 1 │
└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
</pre>
}}}
||#||When||Problem||Lang||Verdict||Time||Memory||
||163||4:34:44||4146||3||g++0x||OK||N/A||
||162||4:27:07||4136||3||g++0x||Time-limit exceeded||12||
||161||4:12:37||3906||3||g++0x||Wrong answer||22||
||160||4:07:07||3606||3||g++0x||Wrong answer||10||
||159||4:04:10||3606||3||g++0x||Time-limit exceeded||2||
||158||3:53:52||3604||3||g++0x||Wrong answer||2||
||157||3:26:20||1949||4||g++0x||OK||N/A||
||156||2:37:51||4599||5||g++0x||OK||N/A||
||155||2:28:38||949||6||g++0x||OK||N/A||
||154||2:18:58||3785||5||g++0x||Time-limit exceeded||9||
||153||2:06:50||1594||8||g++0x||OK||N/A||
||152||2:05:50||3812||5||g++0x||Time-limit exceeded||2||
||151||2:03:36||1594||8||g++0x||Wrong answer||4||
||150||1:44:52||715||6||g++0x||Wrong answer||2||
||149||1:38:25||1201||11||g++0x||OK||N/A||
||148||1:35:33||3749||5||g++0x||Time-limit exceeded||2||
||147||1:32:59||1126||11||g++0x||Time-limit exceeded||12||
||146||1:20:47||1105||11||g++0x||Time-limit exceeded||10||
||145||0:26:39||490||9||g++0x||OK||N/A||
||144||0:25:47||490||9||g++0x||Wrong answer||10||
||143||0:23:47||822||2||g++0x||OK||N/A||
||142||0:07:57||507||1||g++0x||OK||N/A||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010355
start at 14:00
== 流水账 ==
== 总结 ==
== 题解 ==
AB略去不表。
=== C. Triangle [JTJL, sfiction] ===
先求出6个坐标，这一步两维可以独立考虑。首先根据是否为(1,0)/(0,1)求出坐标最大值最小值，然后根据每一格的面积变化率正负性求出中间值。最大值最小值约束得到一个矩形范围，检查矩形的四个顶点是否是三角形顶点之一，分类讨论即可。
=== D. Wires [sfiction] ===
相互交错的边不能在同侧。如果将两侧点离散化后，左侧[1..r]恰与右侧[1..r]连边，则这一部分与其他边互不干扰，用这种方法求出所有极小化的边集。对于每个边集，用LIS判断至少需要分为多少类才会互不相交，=1必定只有1条边，>2则不可能实现，=2时可以暴力分组，然后判断哪一组在内代价更小。O(nlogn)。
=== F. Finite Automaton [sfiction] ===
显然可以用对当前数模n的值作为状态。然后考虑最小化DFA，一种方法是检查u和v后继所组成的多元组是否相同且终止标记是否相同，是则两个结点可以合并。本题中则为u*B+i=v*B+i(mod n)，即(u-v)*B=0(mod n)。因此当且仅当(u-v)|n/gcd(B,n)时两点可以合并。注意到0和其他结点终止标记不同，不能合并，因此会得到n/gcd(B,n)+1个结点。注意到所得DFA可能还可以继续最小化，因为gcd(n/gcd(B,n),B)可能不为1。由于每次节点数大致会减半，因此用map<vector>暴力最小化即可。O(nBlogn)。
=== G. Scene management [Akalm] ===
阅读理解题。由于题目中种种限制，记录一下哪些点被操作过，暴力dfs就可以了。。。
=== H. A system of balance scales [Akalm] ===
转成dfs序后维护区间和。
=== K. Test Generation [sfiction, Akalm] ===
计算一下每个后缀的值suf[i]，把他们丢到stl里，枚举右端点，在stl中查找需要的左端点。┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ 2017/03/24 14:00-19:00 · Siunaus · Akalm/JTJL/sfiction │├────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│H [0:19]│ 1 2 3 OooOoOo!# ││I [0:09]│ 1 23o. o# ││K [0:28]│ 1 o2ooOOoo..3..! !.o# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│C8[1:02]│ 1 oooo.ooOo. .OOoOOoo.oO! o.!!o!. .O!. # ││E [0:48]│ .OoOOOoOO1 Oooo...o!.2 o!.. ! 3ooo# │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│A [0:03]│1o# ││B [0:07]│ 12 3OO# ││D [0:25]│ 1 oooOoOOo2o# 3 ││F [0:23]│ 1 OO!. 2 oOOoooo# 3 │├────────┼════════════════════════────────────────────────════════════════════════────────────────────────════════════════════════┤│* [3:46]│ oOoOoOOOooOoOOOoOOOOooOOoo..oOooo..OooOOoOooOoOooo.oOOoooooooooooo.ooOoOooOoOOoOooOOoOOoo.oO. o...oo. .Oo. o │├────────┼────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│G [0:00]│ 1 2 ││J2[0:00]│ 1 │└────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
| # | When | Problem | Lang | Verdict | Time | Memory |
| 163 | 4:34:44 | 4146 | 3 | g++0x | OK | N/A |
| 162 | 4:27:07 | 4136 | 3 | g++0x | Time-limit exceeded | 12 |
| 161 | 4:12:37 | 3906 | 3 | g++0x | Wrong answer | 22 |
| 160 | 4:07:07 | 3606 | 3 | g++0x | Wrong answer | 10 |
| 159 | 4:04:10 | 3606 | 3 | g++0x | Time-limit exceeded | 2 |
| 158 | 3:53:52 | 3604 | 3 | g++0x | Wrong answer | 2 |
| 157 | 3:26:20 | 1949 | 4 | g++0x | OK | N/A |
| 156 | 2:37:51 | 4599 | 5 | g++0x | OK | N/A |
| 155 | 2:28:38 | 949 | 6 | g++0x | OK | N/A |
| 154 | 2:18:58 | 3785 | 5 | g++0x | Time-limit exceeded | 9 |
| 153 | 2:06:50 | 1594 | 8 | g++0x | OK | N/A |
| 152 | 2:05:50 | 3812 | 5 | g++0x | Time-limit exceeded | 2 |
| 151 | 2:03:36 | 1594 | 8 | g++0x | Wrong answer | 4 |
| 150 | 1:44:52 | 715 | 6 | g++0x | Wrong answer | 2 |
| 149 | 1:38:25 | 1201 | 11 | g++0x | OK | N/A |
| 148 | 1:35:33 | 3749 | 5 | g++0x | Time-limit exceeded | 2 |
| 147 | 1:32:59 | 1126 | 11 | g++0x | Time-limit exceeded | 12 |
| 146 | 1:20:47 | 1105 | 11 | g++0x | Time-limit exceeded | 10 |
| 145 | 0:26:39 | 490 | 9 | g++0x | OK | N/A |
| 144 | 0:25:47 | 490 | 9 | g++0x | Wrong answer | 10 |
| 143 | 0:23:47 | 822 | 2 | g++0x | OK | N/A |
| 142 | 0:07:57 | 507 | 1 | g++0x | OK | N/A |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010355
start at 14:00
流水账
总结
题解
AB略去不表。
C. Triangle [JTJL, sfiction]
先求出6个坐标，这一步两维可以独立考虑。首先根据是否为(1,0)/(0,1)求出坐标最大值最小值，然后根据每一格的面积变化率正负性求出中间值。最大值最小值约束得到一个矩形范围，检查矩形的四个顶点是否是三角形顶点之一，分类讨论即可。
D. Wires [sfiction]
相互交错的边不能在同侧。如果将两侧点离散化后，左侧[1..r]恰与右侧[1..r]连边，则这一部分与其他边互不干扰，用这种方法求出所有极小化的边集。对于每个边集，用LIS判断至少需要分为多少类才会互不相交，=1必定只有1条边，>2则不可能实现，=2时可以暴力分组，然后判断哪一组在内代价更小。O(nlogn)。
F. Finite Automaton [sfiction]
显然可以用对当前数模n的值作为状态。然后考虑最小化DFA，一种方法是检查u和v后继所组成的多元组是否相同且终止标记是否相同，是则两个结点可以合并。本题中则为u*B+i=v*B+i(mod n)，即(u-v)*B=0(mod n)。因此当且仅当(u-v)|n/gcd(B,n)时两点可以合并。注意到0和其他结点终止标记不同，不能合并，因此会得到n/gcd(B,n)+1个结点。注意到所得DFA可能还可以继续最小化，因为gcd(n/gcd(B,n),B)可能不为1。由于每次节点数大致会减半，因此用map
G. Scene management [Akalm]
阅读理解题。由于题目中种种限制，记录一下哪些点被操作过，暴力dfs就可以了。。。
H. A system of balance scales [Akalm]
转成dfs序后维护区间和。
K. Test Generation [sfiction, Akalm]
计算一下每个后缀的值suf[i]，把他们丢到stl里，枚举右端点，在stl中查找需要的左端点。