2015-C06-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(c06.png)]]

== 流水账 ==
{{{
从我E题因为错误地产生了没法推出直接公式的错觉，而且写了两个二分，再简化成一个二分；于是整个过程中需要推的公式量相当于正常的3倍，
然后又要处理TLE造成二分次数改小了，引起了后面的WA，WA了之后犹豫了很久才改了二分次数，终于过了。这题是主要卡题的开始。I题因为这
题过的晚+闽爷和sodabeta也卡了3题，我不断地被pia下去没写完代码，也花了挺久。
最后终于过了I，sodabeta也debug完C，3个人一起看了看J，终于找到问题，也过了。
然后F题一起想了想，稍微改进了一下贪心，但是似乎还是过不了。

By Bobgy
}}}

== 总结 ==
 * 题目写法比较复杂的话最好找一个队友讨论一下，避免完全是因为方法绕了远路而多了许多coding时间。这次的C和E都属于这个范畴。

== 补题列表 == 
 * ~~C 用正常姿势重写 by sodabeta~~
 * ~~ D by sodabeta~~
 * ~~ E 尝试直接推公式 by Bobgy ~~ 果然直接推公式更好写，公式也好推
 * ~~ G By Bobgy ~~
 * ~~ F By Bobgy ~~

== 题解 ==
 * F
{{{
贪心：
可以想着先处理交换，再统计需要多少个a
对原序列做一个前缀和，就可以知道各个+处缺多少个a
max(缺的a数量)就是头尾需要添加的a和+的数量
所以如果想要减少头尾需要添加的a和+数量，一定是从缺少a数量最多的+开始移动
缺少a数量最多的+后面一定是a，否则它后面的+缺少的a必然更多
于是一次移动花费1的代价，可以把一个+缺的a数量减少1
缺少a数量最多的+如果当前有n个
那么通过移动把头尾需要的a和+数量减少1，需要的代价是n（每个+往后交换一次）
而a和+数量减少1，节约的代价是2
所以当n<2的时候才需要移动
也就是把缺少a数量最多的+通过移动变得和第二多的一样
除去预处理，O(1)就能做完，不需要枚举添加多少个a
}}}
 * G
{{{
DP+容斥
拆环为链，用DP计算出方案数，这部分有点麻烦，状态是dp[n][n][4]，3维分别为
第几个位置、有几个位置是对的、最近两个位置是否被占据的mask。
dp[n][k][xxx]中k个位置是在dp过程中指定了正确的位置，把剩下的n-k个人，任意
分配到剩下的位置中，方案数就是dp[n][k][xxx]*(n-k)!。但剩下的人在任意分配
的时候，可能有些人也分配对了；于是此时位置对的人数>=k。
把前一个步骤的dp结果统计到数组b[n]中，b[i]表示刚才统计中，指定位置正确的人
数恰好为i的时候的方案数。（会重复的）
从b[n]开始往b[1]计算，计算到b[i]的时候，b[i]就没有重复了。b[j]-=b[i]*C(i,j)
就能去掉重复状态了，因为恰好有i个正确位置的方案，从中可以选出任意j个正确位置
都会在b[j]中重复出现。
}}}

流水账

从我E题因为错误地产生了没法推出直接公式的错觉，而且写了两个二分，再简化成一个二分；于是整个过程中需要推的公式量相当于正常的3倍，
然后又要处理TLE造成二分次数改小了，引起了后面的WA，WA了之后犹豫了很久才改了二分次数，终于过了。这题是主要卡题的开始。I题因为这
题过的晚+闽爷和sodabeta也卡了3题，我不断地被pia下去没写完代码，也花了挺久。
最后终于过了I，sodabeta也debug完C，3个人一起看了看J，终于找到问题，也过了。
然后F题一起想了想，稍微改进了一下贪心，但是似乎还是过不了。
By Bobgy

总结

  • 题目写法比较复杂的话最好找一个队友讨论一下，避免完全是因为方法绕了远路而多了许多coding时间。这次的C和E都属于这个范畴。

补题列表

  • C 用正常姿势重写 by sodabeta
  • D by sodabeta
  • E 尝试直接推公式 by Bobgy 果然直接推公式更好写，公式也好推
  • G By Bobgy
  • F By Bobgy

题解

  • F
贪心：
可以想着先处理交换，再统计需要多少个a
对原序列做一个前缀和，就可以知道各个+处缺多少个a
max(缺的a数量)就是头尾需要添加的a和+的数量
所以如果想要减少头尾需要添加的a和+数量，一定是从缺少a数量最多的+开始移动
缺少a数量最多的+后面一定是a，否则它后面的+缺少的a必然更多
于是一次移动花费1的代价，可以把一个+缺的a数量减少1
缺少a数量最多的+如果当前有n个
那么通过移动把头尾需要的a和+数量减少1，需要的代价是n（每个+往后交换一次）
而a和+数量减少1，节约的代价是2
所以当n<2的时候才需要移动
也就是把缺少a数量最多的+通过移动变得和第二多的一样
除去预处理，O(1)就能做完，不需要枚举添加多少个a
  • G
DP+容斥
拆环为链，用DP计算出方案数，这部分有点麻烦，状态是dp[n][n][4]，3维分别为
第几个位置、有几个位置是对的、最近两个位置是否被占据的mask。
dp[n][k][xxx]中k个位置是在dp过程中指定了正确的位置，把剩下的n-k个人，任意
分配到剩下的位置中，方案数就是dp[n][k][xxx]*(n-k)!。但剩下的人在任意分配
的时候，可能有些人也分配对了；于是此时位置对的人数>=k。
把前一个步骤的dp结果统计到数组b[n]中，b[i]表示刚才统计中，指定位置正确的人
数恰好为i的时候的方案数。（会重复的）
从b[n]开始往b[1]计算，计算到b[i]的时候，b[i]就没有重复了。b[j]-=b[i]*C(i,j)
就能去掉重复状态了，因为恰好有i个正确位置的方案，从中可以选出任意j个正确位置
都会在b[j]中重复出现。
附加文件