2020-team12-C12

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

== Ranklist ==

[[Image(2020-C12-rank.png)]]

== Submisson ==

[[Image(2020-C12-status.png)]]




== 概述 ==

solved: 9/13  dirt: 50.0%

rank: 1！

题解和反思：
A.给一个算Π的公式，第i项是一个长长的分数除以16^k,让你用它来算pi的十六进制表达
（本题要不是vjudge上的代码长度限制只有30k其实直接打个表就过了）
正解就是按位考虑贡献：第i位的贡献算到i+100位足够了。还有一个挺重要的trick：把一个实数“对16取模”很不好做，那我们可以就题论题算整个除以16，然后只需要对所有运算保留小数部分，到最后在×16取个整即可，这样还可以在处理很大的16的幂时直接使用快速幂取模。


B.SZB

C.三发罚时都是因为读错了题，百度了一个空凸包板子。 这部分还需要再准备一下。
空凸包的大致思路：
1.首先枚举一个点作为凸包C中最下方的点O，抛弃O以下的所有点；

2.对于在O上面的点做一次极角排序，如果有同样极角的条件下，根据距离排序（第二个方法中处理共线要求根据距离排序）。

3.dp[i][j]表示凸包C从O开始，最后的两条边为(i,j),(i,O)的最大可能面积，其中i和j为上述排好序的点集中的点，且排序顺序中i>j，且O,i,j不共线，且O,i,j之中无任意点。
那么有
dp[i][j]=area(i,j,O)+min(dp[j][k],jk和ij组成的折线为凸,且j>k)

如图所示，只需枚举在k/in[0,j)，且用叉乘判断其是否在向量ij的右侧。

D. 待补

E.题意：俩人玩德州扑克，拿了25张牌，每次出5张只比牌型，问谁能先赢或平局。
思路很好想，构造“字典序最大”牌型即可。搜索处理如何做到出最大牌型（而不错拆后面的一些牌）。
这种题目感觉只有其他题目卡死了才会有队伍去写0.0就和之前那个2阶魔方一样

F.szb做的签到

G.szb的字典树，罚时全都是处理读入问题。

H.ctc，三国杀，暴力模拟。听说卡精度，听说会MLE，然而ctcnb.

I.签到，四个数相加

J.官方题解：[[Image(2020-C12-Jpic.jpg)]]
完善解读：
题解的第一句话反映出的一个核心思想：由于每次加的数比较小，在n比较大的时候前几位是固定的，于是就有an到an+m你只需要考虑后面位的贡献，然后可以O（1）算前面的贡献，可以考虑数位dp。

dp(len, pre, init) 所表示一个pair是很新的思想；还需要补充一个sum[len][pre][init]记录和。但是从这里开始，题解说的我就看不懂且没听。我设计具体的转移是这样的：


注意pre它表示的就是前面固定下来的位的贡献，也包括马上要进的一位。于是它对应着很多情况（例如123000000+x->124000000+y的过程,len = 6, pre = 1+2+3=6, init=x, 期望得到的结果是pa(100000y,m))。(m为某一步转移经历的数的数目）

然后还是上面这个例子，我们的转移需要经历123000000+x->123100000+x1->123200000+x2....123900000+x9->124000000+x10这样的过程。因此要枚举dp(len-1,pre+(0to9),in')的情况，其中in需要根据上一个枚举到的状态的结果转移而来，最后得到的m是10个状态下的m之和，init则是从123900000过来的。而sum可以跟着一起转移，每部分贡献就是sum(len-1..)那一串的答案加上m*num*10^(len-1)^.

在处理完dp之后，我们考虑从高位到低位考虑，记录高位已经确定的digitsum之和，每次枚举当前的位，根据n和dp().se的大小关系来准确确定这一高位应该填什么，同时更新sum: 贡献为对应的sum+m*now+digit*10^(len-1)^

(now为已经填进去的那些位的答案,digit表示这一位你想填什么，比如从120000+x->124000+y,那么就会有要分别加上120000，121000，122000，123000才能转移的sum）

细节：
1）涉及到的很多数都是1e17,1e18级别，所以每算一步都要严谨的考虑取模。

2）最大的问题：当前面的pre堆得很高，做到一个低位（十位）时，可能出现前一个数<10^len^后面一个数一下到达>2*10^len^的情况，这可能会给转移尤其是sum的计算带来麻烦。

我发现问题后，在算dp时每个转移还是默认最后的init的最高位会是1，然后因为相邻项之差不会超过18×9=162，最最保险的就是做到千位以下开始暴力模拟题目给的式子。代码当中算dp时只考虑len=1时开始暴力，（递推从x=init算到超过10，算了什么就是什么，无视题解的初值）；而算sum时发现还必须从千位以下直接暴力算，从百位开始算就会得到**一份过了极限数据、全部能和暴力拍起来的数据和大样例还是wa的数位dp代码**。 这一方面只能说以后处理类似的数位dp细节包括类似的初始状态很复杂的题目不能吝啬这一点复杂度，


K.ctc做的签到

L.逐边调整思想。和之前我们队因为没集训过做出的C有点神似，肯定有方案可以让所有两头size大于k的边构成贡献。

M.whn看了半天理解不了为什么答案会是分数表示，和szb一起想出应该是一个很大的高斯消元。结果队伍在顺风情况下，明智的做出打暴力以10000次左右的行动强行模拟来寻找在无限次情况下出现的规律，最后也确实找到每个点的存在情况是度数+1的重要规律，代码也一下子就写了A了。
事后发现，列出高斯消元式之后，由于已经知道每个点的概率会为1，根据题目给的等概率性质确实是每一项填入“（度数+1）/总可能”就可以使方程成立了。

[/wiki/2020-team12 返回]

Ranklist

Submisson

概述

solved: 9/13 dirt: 50.0%

rank: 1！

题解和反思：

A.给一个算Π的公式，第i项是一个长长的分数除以16^k,让你用它来算pi的十六进制表达

（本题要不是vjudge上的代码长度限制只有30k其实直接打个表就过了）

正解就是按位考虑贡献：第i位的贡献算到i+100位足够了。还有一个挺重要的trick：把一个实数“对16取模”很不好做，那我们可以就题论题算整个除以16，然后只需要对所有运算保留小数部分，到最后在×16取个整即可，这样还可以在处理很大的16的幂时直接使用快速幂取模。

B.SZB

C.三发罚时都是因为读错了题，百度了一个空凸包板子。 这部分还需要再准备一下。

空凸包的大致思路：

1.首先枚举一个点作为凸包C中最下方的点O，抛弃O以下的所有点；

2.对于在O上面的点做一次极角排序，如果有同样极角的条件下，根据距离排序（第二个方法中处理共线要求根据距离排序）。

3.dp[i][j]表示凸包C从O开始，最后的两条边为(i,j),(i,O)的最大可能面积，其中i和j为上述排好序的点集中的点，且排序顺序中i>j，且O,i,j不共线，且O,i,j之中无任意点。

那么有

dp[i][j]=area(i,j,O)+min(dp[j][k],jk和ij组成的折线为凸,且j>k)

如图所示，只需枚举在k/in[0,j)，且用叉乘判断其是否在向量ij的右侧。

D. 待补

E.题意：俩人玩德州扑克，拿了25张牌，每次出5张只比牌型，问谁能先赢或平局。

思路很好想，构造“字典序最大”牌型即可。搜索处理如何做到出最大牌型（而不错拆后面的一些牌）。

这种题目感觉只有其他题目卡死了才会有队伍去写0.0就和之前那个2阶魔方一样

F.szb做的签到

G.szb的字典树，罚时全都是处理读入问题。

H.ctc，三国杀，暴力模拟。听说卡精度，听说会MLE，然而ctcnb.

I.签到，四个数相加

J.官方题解：

完善解读：

题解的第一句话反映出的一个核心思想：由于每次加的数比较小，在n比较大的时候前几位是固定的，于是就有an到an+m你只需要考虑后面位的贡献，然后可以O（1）算前面的贡献，可以考虑数位dp。

dp(len, pre, init) 所表示一个pair是很新的思想；还需要补充一个sum[len][pre][init]记录和。但是从这里开始，题解说的我就看不懂且没听。我设计具体的转移是这样的：

注意pre它表示的就是前面固定下来的位的贡献，也包括马上要进的一位。于是它对应着很多情况（例如123000000+x->124000000+y的过程,len = 6, pre = 1+2+3=6, init=x, 期望得到的结果是pa(100000y,m))。(m为某一步转移经历的数的数目）

然后还是上面这个例子，我们的转移需要经历123000000+x->123100000+x1->123200000+x2....123900000+x9->124000000+x10这样的过程。因此要枚举dp(len-1,pre+(0to9),in')的情况，其中in需要根据上一个枚举到的状态的结果转移而来，最后得到的m是10个状态下的m之和，init则是从123900000过来的。而sum可以跟着一起转移，每部分贡献就是sum(len-1..)那一串的答案加上m*num*10(len-1).

在处理完dp之后，我们考虑从高位到低位考虑，记录高位已经确定的digitsum之和，每次枚举当前的位，根据n和dp().se的大小关系来准确确定这一高位应该填什么，同时更新sum: 贡献为对应的sum+m*now+digit*10(len-1)

(now为已经填进去的那些位的答案,digit表示这一位你想填什么，比如从120000+x->124000+y,那么就会有要分别加上120000，121000，122000，123000才能转移的sum）

细节：

1）涉及到的很多数都是1e17,1e18级别，所以每算一步都要严谨的考虑取模。

2）最大的问题：当前面的pre堆得很高，做到一个低位（十位）时，可能出现前一个数<10len后面一个数一下到达>2*10len的情况，这可能会给转移尤其是sum的计算带来麻烦。

我发现问题后，在算dp时每个转移还是默认最后的init的最高位会是1，然后因为相邻项之差不会超过18×9=162，最最保险的就是做到千位以下开始暴力模拟题目给的式子。代码当中算dp时只考虑len=1时开始暴力，（递推从x=init算到超过10，算了什么就是什么，无视题解的初值）；而算sum时发现还必须从千位以下直接暴力算，从百位开始算就会得到**一份过了极限数据、全部能和暴力拍起来的数据和大样例还是wa的数位dp代码**。 这一方面只能说以后处理类似的数位dp细节包括类似的初始状态很复杂的题目不能吝啬这一点复杂度，

K.ctc做的签到

L.逐边调整思想。和之前我们队因为没集训过做出的C有点神似，肯定有方案可以让所有两头size大于k的边构成贡献。

M.whn看了半天理解不了为什么答案会是分数表示，和szb一起想出应该是一个很大的高斯消元。结果队伍在顺风情况下，明智的做出打暴力以10000次左右的行动强行模拟来寻找在无限次情况下出现的规律，最后也确实找到每个点的存在情况是度数+1的重要规律，代码也一下子就写了A了。

事后发现，列出高斯消元式之后，由于已经知道每个点的概率会为1，根据题目给的等概率性质确实是每一项填入“（度数+1）/总可能”就可以使方程成立了。

附加文件