ioi2009集训队第一次作业yxnsu

1、IOI2009 中国国家集训队第一次作业筹筸筮筳筵 李骥扬筊筡筮筵筡筲筹 笱笱第 笲笰笰笹筃筯筮筴筥筮筴笮笱筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笲 笨筚筏筊笲笳笳笷 筴筯笲笳笴笴 笩笴笴笴笴笵笵笵笵笶笱笮笱笱笮笲笱笮笳笱笮笴笱笮笵笱笮笶笱笮笷笱笮笸笲笳笳笷 筎筯筮 筁筢筳筯筲筢筩筮筧 筄筆筁笮 笮 笮 笮 笮笲笳笳笸 答筨筥 答筯筷筥筲 筯筦 筈筡筮筯筩 筒筥筶筩筳筩筴筥筤笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮

2、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笳笳笹 筈筹筰筥筲筨筵笋筭筡筮 笮 笮 笮 笮 笮笲笳笴笰 筌筩筴筴筬筥 筊筵筭筰筥筲 笮 笮 笮 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笳笴笱筺筡筴筩筯筮 筐筲筯筢筬筥筭笲笳笴笲 筒筯筡筤筳 笮 笮 笮 笮笲笳笴笳 筒筯筢筢筥筲筳 笮 笮 笮笲笳笴笴 答筯筲筡筬 答筩筣筫筥筴筳笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴笳笮笮笮笮笮笮笮笮笮笨筚筏筊笲笳笶笱 筴筯笲笳笶笹 笩笶笶笶笷笷笷笷笸笸笸笲笮笱笲笮笲笲笮笳笲笮笴笲笮笵笲笮笶笲笮笷笲笮笸笲笮笹笲笳笶笱 筁筲筥筡筳 笮 笮 笮 笮 笮 笮 笮笲笳笶笲 筂筥筬筯

3、筶筥筤 筓筯筮筳 笮 笮笲笳笶笳 筓筴筲筡筮筧筥 筃筯筵筮筴筥筲 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笳笶笴 筄筡筲筡筮筳筭筩筳笲笳笶笵 筓筴筲筯筮筧 筄筥筦筥筮筣筥笮笮笲笳笶笶 筗筥筩筲筤 筄筩筳筳筩筭筩筬筡筲筩筴筹笲笳笶笷 筐筌笯筃筯筯筬 笮 笮 笮 笮 笮笲笳

4、笶笸 筒筯筹筡筬 筆筥筤筥筲筡筴筩筯筮笲笳笶笹 答筷筯 筃筹筬筩筮筤筥筲筳 笮 笮笮笮笮笳筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴笴笮笮笨筚筏筊笲笵笵笹 筴筯笲笵笶笹笩笸笸笹笹笹笳笮笱笳笮笲笳笮笳笳笮笴笲笵笵笹 答筨筥 筓筭筡筲筴 筂筯筭筢 笮 笮 笮笲笵笶笰 等 筊筵筳筴 筃筡筬筬筥筤 笮笮笮 笮 笮 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笵笶笱 筏筲筤筲筥筳筥筲筶筩筮筧 筃筯筤筥筳笲笵笶笲 筍筯筲筥 筄筩筶筩筳筯筲筳 笮 笮 笮 笮 笮 笮笱笳笮笵 笳笮笶 笳笮笷 笳笮笸

5、 笳笮笹 笳笮笱笰笳笮笱笱笲笵笶笳 筌筯筮筧 筄筯筭筩筮筯筥筳 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笹笱笰笱笰笱笰笱笰笱笱笱笱笲笵笶笴 答筨筥筗筨筥筥筬笲笵笶笵 筃筲筡筣筫筩筮筧 筓筓筈 笮笲笵笶笶 筐筥筲筩筯筤筩筣 答筩筬筩筮筧筳笲笵笶笷 答筲筡筤筥 笮 笮 笮 笮 笮 笮笮笮笮笲笵笶笸 筃筯筵筮筴筩筮筧 答筲筩筡筮筧筵筬筡筴筩筯筮筳笲笵

6、笶笹 筕筮筦筡筩筲 筃筯筮筴筥筳筴 笮 笮 笮 笮 笮 笮笴筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笵笨筚筏筊笲笵笸笷 筴筯笲笵笹笴笩笱笱笱笱笱笱笱笲笱笲笱笲笱笲笱笳笱笳笴笮笱笴笮笲笴笮笳笴笮笴笴笮笵笴笮笶笴笮笷笴笮笸笲笵笸笷 筕筮筩筱筵筥 筁筴筴筡筣筫 笮 笮笲笵笸笸 筂筵筲筮筩筮筧 筂筲筩筤筧筥筳 笮笲笵笸笹 筃筩筲筣筬筥筳 笮 笮 笮 笮 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮

7、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笵笹笰 筌筩筮筥筡筲 筐筲筯筧筲筡筭筭筩筮筧 筄筵筡筬笲笵笹笱 筄策筄 笮 笮笲笵笹笲 答筨筩筮筫笮 笮 笮 笮筩筴筩筶筥 笮笮 笮 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笵笹笳 筒筩筮筧笲笵笹笴 筄筲筩筶筩筮筧 筓筴筲筡筩筧筨筴笵筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴笶笮笮笮笮笨筚筏筊笲笵笹笵 筴筯笲笶笰笳笩笱笳笱笳笱笴笱笴笱笴笱笴笱笵笱笵笱笵笱笵笵笮笱笵笮笲笵笮笳笵笮笴笵笮笵笵笮笶笵笮笷笵笮笸笵笮笹笲笵笹笵 筁筣筫筥筲筭筡筮笧筳 筆筵筮筣筴筩筯筮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮

8、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笵笹笶 答筨筥 筍筩筮筩筭筡筬 筁筮筧筬筥笲笵笹笷 筙筥筬筬筯筷 筃筯筤筥 笮 笮 笮 笮笲笵笹笸 筙筥筴 筁筮筯筴筨筥筲 筄筩筧筩筴 笮笮笮笮笲笵笹笹 筇筲筡筤筵筡筴筥筤 筌筥筸筩筣筯筧筲筡筰筨筩筣筡筬 筏筲筤筥筲筩筮筧笲笶笰笰 筇筓筍 笮 笮 笮 笮 笮 笮 笮 笮笲笶笰笱 筗筡筲筥筨筯筵筳筥 筋筥筥筰筥筲 笲笶笰笲 筄筯筮笧筴 筇筯 筌筥筦筴 笮 笮 笮笲笶笰笳 筒筡筩筬筲筯筡筤

9、筓筯筲筴 笮 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笶筁筮筤筲筥筷 筓筥筶筩筣筨笧筳 筃筯筮筴筥筳筴笹笮笮笮笮笮笮笮笮笨筚筏筊笲笶笹笶 筴筯笲笷笰笳笩笱笵笱笵笱笶笱笶笱笶笱笶笱笷笱笷笱笷笶笮笱笶笮笲笶笮笳笶笮笴笶笮笵笶笮笶笶笮笷笶笮笸笲笶笹笶 筃筨筩筰 筄筥筳筩筧筮筩筮筧 笮 笮 笮笲笶笹笷 筅筬筥筣筴筲筩筣筩筴筹 笮 笮 笮 笮 笮 笮笲笶笹笸 筎筵筭筢筥筲筳 筴筯 筎筵筭筢筥筲筳笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮

10、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笶笹笹筃筩筴筩筥筳 笮 笮 笮 笮 笮笲笷笰笰 筑筵筡筤筲筡筴筩筣 筅筱筵筡筴筩筯筮 笮笲笷笰笱 筒筥筳筴筯筲筥 筴筨筥 答筲筥筥 笮 笮 笮笲笷笰笲 筕筮筲筨筹筭筡筢筬筥 筒筨筹筭筥筳笲笷笰笳 筓筥筬筬筩筮筧 答筩筣筫筥筴筳 笮 笮 笮 笮笲笷筍等答 筐筲筯筧筲筡筭筭筩筮筧 筃筯筮筴筥筳筴 笲笰笰笵 笨筚筏筊 笲笶笸笸 筴筯 笲笶笹笵笩笱笸笱笸笱笸笱笸笱笸笱笹笱笹笱笹笱笹笷笮笱笷笮笲笷笮笳笷笮笴笷笮笵笷笮笶笷笮笷笷笮笸笲笶笸笸 筒筥筱筵筩筲筥筭筥筮筴筳

11、笮 笮 笮 笮 笮笲笶笸笹 筃筯筮筳筴筲筵筣筴筩筮筧 筒筯筡筤筳 笮 笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笶笹笰 筁 筃筩筴筹 筯筦 筓筫筹筳筣筲筲筳 笮笲笶笹笱 答筨筥 答筲筡筶筥筬筩筮筧 筓筡筬筥筳筭筡筮笲笶笹笲 筄筩筡筬筩筮筧 筄筩筣筥 笮 笮笲笶笹笳 筐筲筯筣筲筡筳筴筩筮筡筴筩筯筮笲笶笹笴 筃筯筮筥筯筬筯筧筹 笮 笮 笮笮笮笮笮笮笮

12、笮笮笮笮笮笮笮笮笮笲笶笹笵 筅筸筰筬筡筩筮筩筮筧 筴筨筥 筓筴筯筣筫 筍筡筲筫筥筴笸筍等答 笱筳筴 答筥筡筭 筃筯筮筴筥筳筴 笲笰笰笷 笨筓筐筏筊笲笳笱笸筴筯笲笳笲笵笩笲笰笲笰笲笰笲笰笲笰笲笱笲笱笲笱笲笱笸笮笱笸笮笲笸笮笳笸笮笴笸笮笵笸笮笶笸笮笷笸笮笸笲笳笱笸 筏筶筥筲筬筡筰笲笳笱笹 筓筥筱筵筥筮筣筥 笮筗筯筲筤筳笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮

13、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笲笳笲笰 筍筡筮筨筡筴筴筡筮 笮笲笳笲笱 筓筥筧筭筥筮筴筳 笮 笮笲笳笲笲 答筲筥筥 筇筡筭筥 笮笲笳笲笳 筂筲筯筫筥筮 筃筯筭筰筡筳筳 笲笳笲笴 筍筡筲筩筯笮 笮 笮 笮 笮 笮笲笳笲笵 筓筴筲筩筮筧 筄筩筳筴筡筮筣筥 笮笹筍等答 等筮筤筩筶筩筤筵筡筬 筃筯筮筴筥筳筴 笲笰笰笷笨筓筐筏筊 笱笹笶笰筴筯笱笹笶笶笩笲笲笲笲笲笲笲笲笲笲笲笳笲笳笲笳笹笮笱笹笮笲笹笮笳笹笮笴笹笮笵笹笮笶笹笮笷笱笹笶笰 筒筥筣筴筡筮筧筬筥筳 笮 笮笱笹笶笱 筒筯筭筡筮 筒筯筡筤筳笱笹笶笲 筃筩筲筣筬筥筳 笮 笮 笮 笮笮笮笮笮笮

14、笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笮笱笹笶笳 等筭筡筧筥 筐筲筯筪筥筣筴筩筯筮筳笱笹笶笴 答筲筥筥 筣筵筴 笮笱笹笶笵 筓筥筴 筃筯筶筥筲笱笹笶笶 筓筫筩 策筡筬筬筥筹笮笮笮笮笮笮笮笮笮笮笮笮笳笱筁筮筤筲筥筷 筓筴筯 笲笳笴笴 笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笲 笨筚筏筊 笲笳笳笷笱笮笱笲笳笳笷 筎筯筮 筁筢筳筯筲筢筩筮筧

15、 筄筆筁题目大意给出一个自动机第其中一些边在走过之后不会删去命令串的当前字符第求长度为筬的串，使得从初始节点开始，执行此串的命令能够到达终止节点且命令串结束。算法讨论首先将给出的自动机转化为一般的自动机。将不删除命令串当前字符的边更新为从此走下去第一次删除命令串当前字符之后所到达的节点，注意有可能产生环，需要特殊判断。然后进行动态规划笮筤筰筥筲筛筩筝筛筪筝表示长度为筩的串使得执行后到达筪节点的方案数目第每次进行递推即可。注意答案有可能很大，需要使用高精度。复杂度为O笨K|Z| 笫 KNG笩 其中G表示高精度加法复杂度笱笮笲笲笳笳笸 答筨筥 答筯筷筥筲 筯筦 筈筡筮筯筩 筒筥筶筩筳筩筴筥筤题目大

16、意经典汉诺塔问题。多个柱子，多个盘子。要求输出方案。算法讨论先筄筐。Fi,j表示筩个柱子筪个盘子将所有盘子从笱号移动到筩号的最少步数。然后通过筄筐得出的分配方式，输出方案即可。笱笮笳笲笳笳笹 筈筹筰筥筲筨筵笋筭筡筮题目大意给出一些字符的出现次数。求包含这些字符的哈夫曼编码文件的长度笨筩筮 筢筩筴笩。算法讨论建立一个小根堆，每次从堆中弹出最小的两个数a、b，求和 c 笽 笨a 笫b笩，令答案加c，再将c插入堆中。算法的复杂度为O笨nlogn笩笴笱笮笴笲笳笴笰 筌筩筴筴筬筥 筊筵筭筰筥筲题目大意一只青蛙从原点开始连续跳跃两个到达某给定点。每个是筸为某值时只有纵向给定的区间可以通过。 两次起跳的速度

17、和角度可以不同。最小化两次起跳速度的最大值。算法讨论问题可以转化为两只青蛙从两侧向中间跳。可以二分最大初速度，判断时分别算出初速度v 笨笰, vmax筝时能够到达区间，通过区间是否相交判断可行与否。笱笮笵笲笳笴笱筺筡筴筩筯筮 筐筲筯筢筬筥筭题目大意给出长度为筮的一个序列筓、一个m s的矩阵筍。开始筰筱均为笱，每次选择筸，代价为|Mq,x Sp|，然后p 笽 p 笫 笱第q 笽 x 筭筯筤 m。最小化代价和，输出方案。算法讨论明显的动态规划。fi,j表示p 笽 i, q 笽 j时的最小代价。转移时记录路径即可。笱笮笶笲笳笴笲 筒筯筡筤筳题目大意给出筎个点筍条边的一个带权的无向图。求一方案，改变最

18、少的权值笨各个边权值改变量的绝对值之和最小笩，使得前筎笭笱条边成为此图的最小生成树。算法讨论显然对于前筎笭笱条边应该减小其权值，之后的边应加大权值。设出各个边权值的改变量的绝对值，没一条ei|i N 会与前筎笭笱条边中一部分一个环。 改变后该边的权值大于等于其余各边权值。发现和筋筍中顶标一致，对前筎笭笱条边和之后的边作为两个点集的二分图做最佳匹配即可。笱笮笷笲笳笴笳筒筯筢筢筥筲筳题目大意给出N MPNY X 笮笮X 求解一组数K 笮笮K 使得XK取值最小|ii1n1ni=1YM笵算法讨论PN笨XiKXiK注意到笩 笽 笰 则的正数项和最小时原式最小iii=1 YMYM于是，先令X M则 各项均

19、为正XK通过向其中一些项的K 加使K 笽bc笮笮笱iiiiiYYM得XiKiXiKi正项和尽量减小笮显然，应尽量将笱加到较大的项的Ki笮如YMPYMN此添加bc次即可X MM i笮i=1Y复杂度O笨nlogn笩笱笮笸笲笳笴笴 答筯筲筡筬 答筩筣筫筥筴筳题目大意给一张长方形格纸的大小笨N M 笩，由黑白两色涂满各个格子，先将长边粘合，再将形成的圆柱体的底边粘合，得到筄筯筮筵筴筳形状的东西。求这种本质不同的筄筯筮筵筴筳笮算法讨论筐笓筯筬筹筡定理。变换方式有循环左移、下移，旋转笱笸笰度。对正方形的还有旋转笹笰度。笲筁筮筤筲筥筷 筓筴筯 笲笳笶笹 笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笳 笨筚筏筊 笲笳笶

20、笱笲笮笱笲笳笶笱 筁筲筥筡筳题目大意给出平面上一些直线，求直线划分出的有限区域面积。算法讨论先求出直线交点。以及直线上两相邻交点的向量。找一个区域时，先挑出一个向量然后从它的终点开始寻找从此点连出的一条最向右偏的向量，直到封闭区域。笲笮笲笲笳笶笲 筂筥筬筯筶筥筤 筓筯筮筳题目大意给出一个二分图第对于筁点集每个点有一个权值。求解一二分匹配，使得筁点集中匹配点的权值平方和最大。算法讨论按权值从大到小做二分图最大匹配即可。笶笲笮笳笲笳笶笳 筓筴筲筡筮筧筥 筃筯筵筮筴筥筲题目大意给出一个筎位的笲幂次数，每一位可以为笰或笱或笲，表示的数为各位乘以笲的位数次幂。有筍次操作，每次要求它表示的数字加上笲的一个

21、整数次幂。要求每次操作改动不超过笴位数字。算法讨论维护一个相邻两个笲之间至少有一个笰。可以使每次操作改动最多笳位数字。具体维护方法参见程序。笲笮笴笲笳笶笴 筄筡筲筡筮筳筭筩筳题目大意给出一个单源单汇分层网络。求一个可行流，使得不考虑反向边时，没有增广路。算法讨论先贪心得到一个初始流。然后筄筩筮筩筣，由于题目特殊性，筄筩筮筩筣的筄筆筓跑一遍就可以了。笲笮笵笲笳笶笵 筓筴筲筯筮筧 筄筥筦筥筮筣筥题目大意给出一个筎点筍边的网络，求一个方案将筍条边划分成尽量多的割。算法讨论对给定源求单源最短路，每条边分配到的组别为两端与原点的距离的最小值。笲笮笶笲笳笶笶 筗筥筩筲筤 筄筩筳筳筩筭筩筬筡筲筩筴筹题目大意

22、给出两个串S1S2，和一个矩阵表示的任两字符见距离DISTi,j。求两个等长串S10 S20 满足S1是S10 的子序列，S2是S20 的子序列，最小化S10 S20 的距离P DISTS10 (i),S20 (i)算法讨论经典动态规划，Di,j表示匹配到前串第筩位、后串第筪位的最小距离。转移有三种：保持二者不变、向第二个串中插入第一串中当前字符的最优匹配字符、向第一个串中插入第二个串中当前字符最优匹配字符。笷笲笮笷笲笳笶笷 筐筌笯筃筯筯筬题目大意输入一些筄筥笌筮筥和表达式。要求输出表达式的值。算法讨论使用并查集维护筄筥笌筮筥信息。然后表达式求值即可。笲笮笸笲笳笶笸 筒筯筹筡筬 筆筥筤筥筲筡筴

23、筩筯筮题目大意给出筎个城市的树，要求划分成大小属于筛B, 笳B筝的区间的省，每个省有一个省会，可以不在省内，每个省加上其省会在树上一定联通。要求给出一种方案。算法讨论构造。从叶子节点向上合并成省，维护留上一层的节点个数在筛笰, 笲B筝的区间内。若某此合并后未合并节点不足筂个，则取消当前合并操作，将所有剩余节点合并。笲笮笹笲笳笶笹 答筷筯 筃筹筬筩筮筤筥筲筳题目大意给出两个圆柱半径r1r2，求二者对称轴正交时公共部分算法讨论经过推导，所求体积等于Zmin(r1,r2) q22笸笨r x 笩笨r x 笩dx22120将min笨r1, r2笩分为适当份数，使用筓筩筭筰筳筯筮求积公式计算即可。笳筁筮筤

24、筲筥筷 筓筴筯 笲笵笶笹笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笴 笨筚筏筊 笲笵笵笹笳笮笱笲笵笵笹 答筨筥 筓筭筡筲筴 筂筯筭筢题目大意给出平面上三点 求以各点为圆心的一组圆第使得相互之间不相交且半径之和最大笸算法讨论显然半径之和小于等于三点为顶点的三角形笨含长第可构造出取等的解复杂度为O笨笱笩为线段的情况笩周笳笮笲笲笵笶笰 等 筊筵筳筴 筃筡筬筬筥筤 笮笮笮题目大意给出一个答筯筷筮笭筚筯筮筥笭筓筵筰筥筲筚筯筮筥的三层结构、网络覆盖范围以及一份电话帐单，要求根据十六种资费计算总费用。算法讨论使用筴筲筩筥维护电话号码，然后直接模拟即可。笳笮笳笲笵笶笱 筏筲筤筲筥筳筥筲筶筩筮筧 筃筯筤筥筳题目大意给出

25、筮个字符出现频率，求特殊筈筵笋筭筡筮编码，字符的顺序与编码的字典序一致。算法讨论经典的石子合并问题。动态规划笫四边形不等式即可。笳笮笴笲笵笶笲 筍筯筲筥 筄筩筶筩筳筯筲筳题目大意给出数字筎，求出小于等于筎的数字中拥有最多约数的数字算法讨论生成满足下列条件的数列笺数列中每个数是比前一个数有中最小的一个笮则所求的数必在此数列中第读入筎后在数列中查找即可因子的数生成数列复杂度笺O笨g笨maxN 笩2 f 笨maxN 笩2笩 其中g笨maxN 笩表示所求数列中小于等于筭筡筸筎的项数第f 笨maxN 笩表示生成数列中小于等于筭筡筸筎的项的质因子个数笳笮笵笲笵笶笳 筌筯筮筧 筄筯筭筩筮筯筥筳题目大意给出筮

26、第筭笨n 6 笹笩 求用笱 笳的骨牌覆盖n m的棋盘的方案数笹算法讨论动态规划。使用三进制表示状态。某位为笰表示没有覆盖骨牌，为笱表示覆盖骨牌且其下方没有覆盖，为笲表示覆盖骨牌且它下面一格覆盖了骨牌。复杂度为O笨mk笳n笩第其中筫为某一状态最多转移数目第本题条件下k 笽 笱笹笳笮笶笲笵笶笴 答筨筥筗筨筥筥筬题目大意一个圆柱上给出三层各筎个点，求匹配使得，每个匹配包括上中下各一个点，代价为上中两点的距离笨圆柱面笩笫中下两点距离笨圆柱面笩，最小化代价和。算法讨论显然不会出现交叉情况，因而可以枚举上层第一个节点对应中层第几个，然后计算求出最小情况，对中下层同样处理。笳笮笷笲笵笶笵 筃筲筡筣筫筩筮筧

27、筓筓筈题目大意求一个长为筬的字符串，字符为前筭个小写字母，给出矩阵筃和序列筐笨长Pl1为，最小化。筬笭笱笩|P C|iS ,S +1i=1ii算法讨论动态规划。fi,j表示Si 笽 j得到的局部最小代价。递推即可。笳笮笸笲笵笶笶 筐筥筲筩筯筤筩筣 答筩筬筩筮筧筳题目大意给出一个图形，问这种图形能否通过平移覆盖整个平面。算法讨论枚举两个平移量笺笨a, b笩和笨c, d笩，用他们和笨a, b笩笨c, d笩笨ac, bd笩笨ca, d b笩是否完全覆盖原图形周围所有格子且不与原图形重叠。笳笮笹笲笵笶笷 答筲筡筤筥题目大意给出一个二分图，求最小边集，使每个点的度最少为笲。笱笰算法讨论左边的点连到源，右

28、边的连到汇，流量为对应顶点原始度减笲。二分图中的边流量设为笱。做一遍最大流。二分图中没有流量的边即为所求。笳笮笱笰笲笵笶笸 筃筯筵筮筴筩筮筧 答筲筩筡筮筧筵筬筡筴筩筯筮筳题目大意给出平面上筮个点坐标，任意三点不共线。先对凸包进行三角剖分，若某个三角形内有点，选择一个连向三个顶点，直到任意三角形内均没有点。求这样的三角剖分的方案数。算法讨论首先记忆化搜索，得到各个三角形的剖分数，然后求出凸包，再在凸包上动态规划即可。结果好像要用高精度。笳笮笱笱笲笵笶笹 筕筮筦筡筩筲 筃筯筮筴筥筳筴题目大意给出筭个题目以及各队做题顺序的规则以及评分规则，要求从中选择筮个题目使得第一个队伍的最靠前。算法讨论简单模拟

29、。先枚举选择的题目，然后计算第一队的，取最佳即可。笴筁筮筤筲筥筷 筓筴筯 笲笵笹笴笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笵 笨筚筏筊 笲笵笸笷笴笮笱笲笵笸笷 筕筮筩筱筵筥 筁筴筴筡筣筫题目大意给出一个无向图，问起点到终点的最小割是否唯一。算法讨论分别以起点和终点为源求最小割判断是否相同。笴笮笲笲笵笸笸 筂筵筲筮筩筮筧 筂筲筩筤筧筥筳题目大意给出一个无向图，求桥。笱笱算法讨论通过筄筆筓求桥。若某个边连向已经访问过的结点，则出现环，环上的结点都不是桥。标记所有环之后，剩余的结点就是桥。笴笮笳笲笵笸笹 筃筩筲筣筬筥筳题目大意给出平面上筎个圆，求所有圆将平面划分成多少部分。算法讨论利用欧拉公式即可。注意此

30、问题是平面上多联通块。笴笮笴笲笵笹笰 筌筩筮筥筡筲 筐筲筯筧筲筡筭筭筩筮筧 筄筵筡筬题目大意输入一个线性规划，求其对偶形式。算法讨论按照题目叙述模拟即可。输入处理稍稍麻烦一些。笴笮笵笲笵笹笱 筄策筄题目大意给出一些影碟，每张有一个地区限制，要求挑出尽量多的影碟，按照年份排序笨同年可随意排笩，顺序看下来地区的更改次数不超过笵。算法讨论动态规划。fi,j,k表示第筩年，当前地区为筪，更换过筫次地区时的最大值。转移过程记录方案。笴笮笶笲笵笹笲 答筨筩筮筫筩筴筩筶筥题目大意给出筮个数字一个环上，求起点个数，以它开始的所有子串数字和为正。算法讨论将环拆成链并复制一遍，形成笲n长的线性串，算一下部分和，从

31、后向前维护部分和最小值，更新部分和的最小值时若该位是前筮个，则从此位满足条件。笱笲笴笮笷笲笵笹笳 筒筩筮筧题目大意给出一些选手的比赛信息，以及的公式，求。算法讨论模拟。按照题目叙述模拟即可。笴笮笸笲笵笹笴 筄筲筩筶筩筮筧 筓筴筲筡筩筧筨筴题目大意给出N M 的街道。求从坐下到右上的最短路，每次尽量直走。算法讨论先算下最短路，然后构造解，优先考虑直走。笵筁筮筤筲筥筷 筓筴筯 笲笶笰笳笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笶 笨筚筏筊 笲笵笹笵笵笮笱笲笵笹笵 筁筣筫筥筲筭筡筮笧筳 筆筵筮筣筴筩筯筮题目大意给出一个函数笺Ack笨n, m笩 笽 笲m 筷筨筥筮 n 笽 笱 筯筲 m 笽 笱Ack笨n, m

32、笩 笽 Ack笨n 笱, Ack笨n, m 笱笩笩 筷筨筥筮 n 笱 筡筮筤 m 笱求Ack笨n, m笩 筭筯筤 t算法讨论Ack笨n, m笩 笽 笲m 筷筨筥筮 n 笽 笱 Ack笨n, m笩 笽 笲m 筷筨筥筮 n 笽 笲 Ack笨n, 笱笩 笽 笲Ack笨n, 笲笩 笽 笴算Ack笨笳, m笩时用一下欧拉函数即可。Ack笨n, m笩 筭筯筤 t从Ack笨笴, 笴笩开始收敛，直接输出Ack笨笳, 笱笰笰笩 筭筯筤 t即可。笱笳笵笮笲笲笵笹笶 答筨筥 筍筩筮筩筭筡筬 筁筮筧筬筥题目大意给出平面上筎个点，依次连接形成筎笭笱个向量。求一个角度使得图形逆时针旋转此角度后，各向量对筸正半轴仰角笨 筛

33、笰, 笲笩笩之和模笲最小。算法讨论将初始时的仰角和模笲的值算出来， 记为。则2( mod 2)即为答N 1案，可使得解为。笰笵笮笳笲笵笹笷 筙筥筬筬筯筷 筃筯筤筥题目大意输入筎，输出所有筎为二进制的一个排序，相邻两个笨含第一个和最后一个二进制至少有b c位不同。N笩2算法讨论构造。若筎为奇数，则第一位首先为笰然后为笱，之后各位按两次N 笱位的做即可。若筎为偶数，给出前两位的构造，然后算后筎笭笲位构造即可。笵笮笴笲笵笹笸 筙筥筴 筁筮筯筴筨筥筲 筄筩筧筩筴题目大意给出数字筎，求筎有多少种笳进笭笲幂次数笨各位为笰或笱或笲，表示数大小为各位乘以笲的位数次幂的和笩。算法讨论f 笨笲 N 笫 笱笩 笽

34、f 笨N 笩f 笨笲 N 笩 笽 f 笨N 笱笩 笫 f 笨N 笩后一个式子拆成的两项连续，其中一个为奇数，另一个为偶数，再拆一次仍然得到如下形式：af 笨M 笱笩 笫 bf 笨M 笩。 依次拆分，算到边界即可。笵笮笵笲笵笹笹 筇筲筡筤筵筡筴筥筤 筌筥筸筩筣筯筧筲筡筰筨筩筣筡筬 筏筲筤筥筲筩筮筧题目大意前筎个数进行排序，第一关键字是各位数码和，第二关键字是字典序。求排序后筫在第几位以及第筫位是几。笱笴笵笮笶笲笶笰笰 筇筓筍题目大意给出正六边形边长和圆半径，求当二者中心重合时，公共部分面积占正六边形面积的比例。精确到小数点后笱笰笰位。算法讨论高精度小数运算。反正切函数使用分。展开笨|x| 笱笩的

35、式子即可。高除和高开方使用二笵笮笷笲笶笰笱 筗筡筲筥筨筯筵筳筥 筋筥筥筰筥筲题目大意给出一个二分图。在已经匹配了部分的二分图上做最大匹配使得改动的边最少。若左边点集中某点开始时有匹配，最终仍要求有匹配。笵笮笸笲笶笰笲 筄筯筮笧筴 筇筯 筌筥筦筴题目大意给出一个自动机的描述。有筵个状态和筳的字符集。给出一个纸带以及转移方程。要求判断这一自动机对于任意的输入指针是否都不会左移。笵笮笹笲笶笰笳 筒筡筩筬筲筯筡筤 筓筯筲筴题目大意给出筮以及笱到笲n的一个排列 这组数从右向左运动 运动过程中有筮个栈可以使用 求解一种出入栈顺序 使得运动到左边后变为顺序递增排列算法讨论简单构造。对于某个栈，先通过较小的一

36、半，再通过较大的一半。复杂度O笨笲n笩笶筁筮筤筲筥筷 筓筴筯 笲笷笰笳笩筥筶筩筣筨笧筳 筃筯筮筴筥筳筴 笹 笨筚筏筊 笲笶笹笶笶笮笱笲笶笹笶 筃筨筩筰 筄筥筳筩筧筮筩筮筧题目大意笱笵平面上给出笨笰第笰笩第笨笱第笰笩第笮笮笮第笨筎笭笱第笰笩与笨笰第笱笩第笨笱第笱笩第笮笮笮第笨筎笭笱第笱笩的一个匹配。求一种连线方式讲匹配点连起来，要求连接线为与坐标轴平行的线段顺次连接而成的，且不相交。输出方案。算法讨论特殊构造。笶笮笲笲笶笹笷 筅筬筥筣筴筲筩筣筩筴筹题目大意给出一个有向无环图。以及其中哪些边需要反向。求解一个改变边方向的顺序达到目标状态，过程中要求不出现环。笶笮笳笲笶笹笸 筎筵筭筢筥筲筳 筴筯 筎

37、筵筭筢筥筲筳题目大意将输入英文文章中的数字转换为阿拉伯数字。多义时要求翻译出的尽量大。被翻译出的数字的向量字典序最大。笶笮笴笲笶笹笹筃筩筴筩筥筳题目大意给出一个有向图。要求从中选择筋个点，使得任何点都能到达这筋个点笨之一笩，任何点也都能由这筋个点笨之一笩到达。求方案数。笶笮笵笲笷笰笰 筑筵筡筤筲筡筴筩筣 筅筱筵筡筴筩筯筮题目大意给出三个多项式A笨t笩B笨t笩C笨t笩，求多项式X笨t笩使得F 笨t笩 笽 A笨t笩X2笨t笩 笫B笨t笩X笨t笩笫 C笨t笩各项系数为偶。筁笨筴笩、筂笨筴笩、筃笨筴笩是已知的三 个多项式，让你求出一个最 高次不超笵笱笲的多项式筸笨筴笩 使筦笨筴笩笽筁筸笲笨筴笩笫筂笨筴

38、笩筸笨筴笩笫筃笨筴笩 的每一项的系数都为偶。所 有多项式中系数非笰 即笱。 对于筸笲笨筴笩，展开后仅需考虑筫筩 笲筴笲筩 这种项。将所有多项式运算起 来后，合并同类项。因为多项 式系数非笰 即笱，故筫筩笽筫筩笲。于 是针对每个同类项列出一 个模笲 下的方程，最后解方程 组即可。 筏笨筎笲筍笩 筎 为变量数；筍 为方程数，都 可以根据题目得出算法讨论将多项式展开，考虑各项系数，解异或线性方程组即可。笱笶笶笮笶笲笷笰笱 筒筥筳筴筯筲筥 筴筨筥 答筲筥筥题目大意给出一棵树上所有叶子之间的笨树上笩距离。求这棵树。算法讨论先设笱为树根，加入笨笱第笲笩这条链，然后每次将新的叶子插入已经树上适当位置引出的链

39、的末尾。最后判断一下即可。的笶笮笷笲笷笰笲 筕筮筲筨筹筭筡筢筬筥 筒筨筹筭筥筳题目大意给出一个数列，要求从中选出长为笴筍的子序列，使得子序列顺次构成筍个笴个数字组成的节，每节数字恰形成两对相等的。最大化筎，并输出子序列。算法讨论动态规划。Fi,j表示到目前为止最多能分多少节。笶笮笸笲笷笰笳 筓筥筬筬筩筮筧 答筩筣筫筥筴筳题目大意给出若干组人，每组有一个满意度权重，要求将他们分到笹个隔间，每间最多笴人，满意度为所有人同组且同隔间人数目与对应组满意度权重之积的和。最大化满意度。算法讨论对于笴人组，有三种有意义的分法：笨笴笩 笨笳第笱笩 笨笱第笱第笱第笱笩对于笳人组，有三种有意义的分法：笨笳笩 笨笲

40、第笱笩 笨笱第笱第笱第笱笩对于笲人组，有两种有意义的分法笺 笨笲笩 笨笱第笱笩对于单个人，不增加满意度，忽略。对于分出的笳至笴人的小组，必然占用单独隔间。两个两人小组可以共用一个隔间。动态规划。fi,j,k表示分完前筩组，占用了筪个单独隔间，分出了筫个两人小组的情况下的最大满意度。笱笷笷筍等答 筐筲筯筧筲筡筭筭筩筮筧 筃筯筮筴筥筳筴 笲笰笰笵 笨筚筏筊 笲笶笸笸筴筯 笲笶笹笵笩笷笮笱笲笶笸笸 筒筥筱筵筩筲筥筭筥筮筴筳题目大意给出笵维空间筎个点，求最大的曼哈顿距离。算法讨论同筓筐筏筊笲笳笲笰。笷笮笲笲笶笸笹 筃筯筮筳筴筲筵筣筴筩筮筧 筒筯筡筤筳题目大意有筎个城市以个子的速度向距离它最近的城市建设公路。每次询问筴时刻至少还需要建多少路才能使得各个城市联通。 或者询问还需建设筬长的公路时，至少已经过了多久。还需要建设的路要求属于最小生成树。笷笮笳笲笶笹笰 筁 筃筩筴筹 筯筦 筓筫筹筳筣筲筲筳题目大意给出一个M N 的城市，给出每一列从北望出最高楼层以及每行从出的最高楼层，每层楼最少筣人，最多筃人，求城市人口范围。算法讨论最少为：XXmax笨a,b笩 c最多则贪心取最大可满足题目叙述的即可。笷笮笴笲笶笹笱 答筨筥 答筲筡筶筥筬筩筮筧 筓筡筬筥筳筭