回复 @CH.Genius_King :
没弄明白……能举个例子吗？

因为$a=\frac{ \sum_{i=1}^{n} {Fi}}{ \sum_{i=1}^{n} {Mi}}$
可知，任意可使加速度增大的配件应满足 $\frac{F[i]}{M[i]}> \frac{F}{M}$
否则会对整体产生阻碍作用。因此F[i]/M[i]越大，越优。
得到配件按加速度降序的序列，从最大值开始扫描，若满足上述关系，则加入一次优配件仍可使汽车加速[由于汽车本身F/M决定]，可以发现，每加一次 $\frac{F}{M}$都会增加（前提是满足上式，可以用等比性质证明）。直到不满足为止。

哈哈哈。。dfs按字典序走，输出时按OOX这种走，谁知道是XOO，输出左右顺序一改就对了。。。
再顺便吐槽一下USACO练胆题系列

回复 @CH.Genius_King :
①用一个f/m值更大的配件代替某个配件显然更优，因此选取的是f/m值前若干大的配件
②加入前若干大配件导致的a值变化显然是单峰的，因此O(n)扫描

直接上贪心，竟然对了 求大神给证明

回复 @weizj :
是啊

联赛的时候一直在找规律，心想第一题什么时候这么难了
动规。字符串处理。都试过
现在发现穷举不会超时

果的二分答案题。。。没好好估计上界跪了两次- -

不开O2过掉，开了E一个点，累不爱
使用了插头DP：逐格递推，四进制括号表示法，map判重，更新时生成状态
因为没把map清空跪了一晚上

TMD没说求得的回文数的进制啊！！

依次优化的过程：
1.快速幂+1~n顺序查找(30%)
2.对数优化+1~n顺序查找(70%)
3.对数优化+2分查找(具备单调性)(100%)

从弦一定的勾股数组数说起==

又是两个变量打错了，过了八个！

求大神证明过程

分析
考虑由两两交换完成的排序过程。可以想见，对每组输入数据，存在一个划分，使该划分中每个含m个元素的子集在基于原序列的顺序的两两对换的意义下生成一个m阶置换群。取一个划分X，使得其中的每个子集S在置换群意义上是极小的，即，对任意m < card(S)，不存在S的含m个元素的子集，使其元素可以以同样方式生成一个置换群。
考虑任意S的排序过程。
定理1 对于单一的置换群G对应的子集(card(S) > 1)，将其通过两两对换排序的最小“排序代价”为：
Sum + (N-2) X LocalMin
其中，sum为G对应子集S的所有元素的和，N = card(S)，LocalMin为S的最小元素。
当然，当S中只有一个元素时，其排序代价为0.
证明：
1. 存在一种排序方案，其代价为上述公式的值。
考虑由两两对换形成的循环，每次交换最小元及其相邻元即可。
2. 最优性。
任意排序方案，其最低兑换次数为N-1，且这N-1次对换须移动S的所有元素。则这一方案的最小代价即为上述公式的值。
当数据被分为多个子集时，排序可能引入外部元素。
定理2 当引入外部元素时，G(card(S) > 1)的最小“排序代价”为：
Sum’ + (N-2) X GlobalMin + 2*(GlobalMin + LocalMin)
其中，Sum’ = Sum – LocalMin + GlobalMin;
GlobalMin 为输入数据中的最小元素。
证明：
1. 存在一种引入外部元素的排序方案，其代价为上述公式的值。
将外部最小元GlobalMin 与内部最小元LocalMin对换，再将其与剩余内部元素组成的数据按照定理1的方式排序，最后再次将GlobalMin与LocalMin对换即得。
2. 最优性。
任意引入外部元素的排序方案，与定理1类似地，其最低代价为上述公式的值。
由上述公式，如果被排序的子集包含全局最小元，则任意引入外部元素的排序方案都将具有大于内部最优方案的排序代价。是以定理1与定理2给出公式的最小值为待排序子集的最小排序代价。在上述划分方式下，原问题的解具有局部最优性，是以对每个子集的最小排序代价做和即得原问题的最优解。
From
<风和凌释>http://blog.sina.com.cn/arkpku

又对了一道题 好爽

pi值取不同精度得分不一样！！！
pi值取不同精度得分不一样！！！
pi值取不同精度得分不一样！！！
pi值取不同精度得分不一样！！！
pi值取不同精度得分不一样！！！
pi值取不同精度得分不一样！！！

一道破题，把我智商都mod没了。。

回复 @none : 一次跪8，9个点，突然过了简直不适应。。。

回复 @ch3coooh :
因为linux……