越早的NOIP题目越神啊，NOIP2012的题目做的真是累死了。可恶的出题人。
T1 Vigenère 密码
T1还是很水的，加加减减随便搞一下就行了。
代码在此。
T2 国王游戏
这题是贪心的思路，按$a_i\times b_i$排序得到的序列是最优的，证明如下：
对于任意的i，设$w_i$为第i个大臣得到的金币数，设$f_i=w_{i-1}\times a_{i-1}\times b_{i-1}$。
则有$w_i=f_i/b_i,\, w_{i+1}=f_i\times a_i/b_{i+1}$。
若交换第i个和第i+1个大臣，则有$w'_i=f_i/b_{i+1},\, w'_{i+1}=f_i\times a_{i+1}/b_i$。
$a_{i+1}\times b_{i+1}\geq a_i\times b_i,\, b_i>0,\, b_{i+1}>0\Rightarrow a_{i+1}/b_i\geq a_i/b_{i+1}$
$\Rightarrow w'_{i+1}\geq w_{i+1}$
$a_i>0\Rightarrow w_{i+1}\geq w'_i\Rightarrow w'_{i+1}\geq w'_i$
$a_{i+1}>0\Rightarrow w'_{i+1}\geq w_i$
综上所述$\max{w_i,w_{i+1}}\leq\max{w'_i,w'_{i+1}}$。
所以交换后不会比交换前更优。易知若任意两个相邻大臣交换位置，对前面和后面都没有没有影响，所以这样排列一定是最优的。
这个数据范围需要高精度，然而我网上找的高精度模板太慢了，过不了官方数据。。。
代码在此。
T3 开车旅行
首先预处理出从某个城市出发，小A和小B分别会走到哪个城市，用list或set可以做到$\mathcal{O}\left( n\log_2{n}\right)$的复杂度，然后做倍增，跑出从某个城市出发走$2^i$步能到达的城市及两人各自走的距离。这样的话已知出发城市和最远距离就可以在$\mathcal{O}\left( \log_2{n}\right)$的时间内得出答案。
代码在此。
评论 (0)
