2014 年信息学奥林匹克
中国国家队候选队员论文集
教练：胡伟栋
中国计算机学会
目录
MSS 命题报告 ·················································································· 1
山东省东营市胜利第一中学 王子昱
矩阵 命题报告 ·················································································· 9
湖南省长沙市长郡中学 余行江
多变的多边形 ·················································································· 19
浙江省绍兴市第一中学 董宏华
对置换群有关算法的初步研究 ···························································· 35
浙江省镇海中学 岑若虚
浅谈线性相关 ·················································································· 45
湖南省长沙市雅礼中学 匡正非
关于三维最小乘积生成树的一些研究 ··················································· 57
浙江省绍兴市第一中学 张恒捷
浅谈回文子串问题 ············································································ 65
江苏省常州高级中学 徐毅
浅谈维护多维数组的方法在数据结构题中的应用 ···································· 77
安徽省合肥一中 梁泽宇
线段树在一类分治问题上的应用 ························································· 91
浙江省杭州学军中学 徐寅展
根号算法——不只是分块 ·································································105
江苏省南京外国语学校 王悦同
浅谈动态树的相关问题及简单拓展 ····················································· 115
湖南省长沙市雅礼中学 黄志翱
随机化算法在信息学竞赛中的应用 ·····················································137
湖南师大附中 胡泽聪
精细地实现程序——浅谈 OI 竞赛中的常数优化 ····································155
天津南开中学 何琦
回归本源——位运算及其应用 ···························································169
浙江省镇海中学 沈洋
寻找第 k 优解的几种方法 ································································195
浙江省绍兴市第一中学 俞鼎力
MSS ·Kw
ÀE½‘|1˜¥Æ fr
MSS ·Kw
ÀE½‘|1˜¥Æ fr
1 K8£ã
1.1 ¯K£ã
²¡þkN‡:§z‡:kŠ§m©žz‡:áu˜‡ØÓ8Ü" Ø
”:P
i
áu8ÜS
i
"‘oêâ(|±±eo«öŠµ
• ”Merge x y”µò8ÜS
y
¥:£ÄS
x
¥¶
• ”Split i d v”£d ∈ {0, 1}¤µMï#8ÜS
c+1
§S
c+2
§ƒò8ÜS
i
¥¤k:
¥§1d‘‹I؇Lv£Ä8ÜS
c+1
¥§‡Lv£Ä8ÜS
c+2
¥§
Ù¥c•yk8Ü꣕)ƒcÜ¿Ú©•¥)˜8¤¶
• ”Query i”µÎ8ÜS
i
¥:Š•ŒŠ§•Š9Ú¶
• ”Add i d”µò8ÜS
i
¥¤k:ŠO\d"
•B儧éud ∈ {0, 1}§Ñ\¤k:1d‘‹IØ-E" ¤köŠ
98Üš˜"
1.2 Ñ\‚ª
1˜1˜‡êNL«:ê"
e5N1§z13‡ê©OL«P
i
‹I†Š"
e5˜‡êQL«öŠê"
e5Q1§z1£ã˜‡öŠ§‚ªXþ¤ã"
2014c&EÆcšŽ¥II[èÿÀèØ©
1
