总结

今天是大年初七咯，一周又要结束了。这周连着考了五天的模拟赛，太离谱了哈哈哈。今天表现稳定，但感觉还是有些题似乎是可以做出来的吧，看来还是经验不足的问题。

题解

就快速说一下，今天的题目都挺好写的？

A. 赌徒

就是有个好朋友，然后每个人有个硬币两面有正整数。然后现在主人公要订做一个硬币两面为，需要元钱，和每个人分别去抛硬币赌元，如果主人公大于等于另一个人的数就赢否则输掉这么多钱。然后问你最大期望赚的钱。

容易发现两面独立然后排个序得到暴力。通过暴力的式子容易发现刚好和四边形不等式相反，所以决策单调性毛都没有，更像一棵树。但是发现可以斜率优化。这道题凸包和一般的有点不一样，不是很会双指针，干脆直接二分了。

P.S. 好像根本不用双指针做到除排序外的，好像用一个栈，如果堆顶交点比要的位置大直接弹出就行。（我是倒着枚举的）

B. 毒假强

对于正整数，定义毒假强数满足的十进制表示不包含的正整数，你需要求出第个毒假强数。

这种题一眼数位 dp。但是没做出来。考场上只想出了枚举当时的数位 dp。结果是枚举乘积的数位 dp，从高位枚举每一位，然后看剩下的数位填法总共有多少种是倍数。然后就很好求了。这种数的倍数特征小学奥数都有，就分段，然后加起来。我们可以枚举这个和，然后数位 dp 就行。具体过程就是每一位弄个背包，然后维护一下进位就行，进位大概不会超过 18。

复杂度就是，这道题要特别注意数组越界啊，枚举的长度比实际小一点之类的问题。保险起见的话你可以直接从 36 位开始枚举，用 __int128 存。

C. 零和

标程很复杂，实际上可以很简单。是原题：QOJ1840 K-onstruction 。

就是给定，你需要构造一个长为的序列，满足：

1. 是在到之间的整数。
2. 恰有个的子集满足（含空集）。
3. 是到之间的整数。

，多次询问，你可以直接把所有情况都存下来。

标程是什么呢？就是对于一串，假设没有（的影响显然），然后正数的和比负数的和的绝对值大，设正数和是，那么加入若干个的倍数进去，容易发现数量的改变是一个线性变换。然后就暴力枚举很多个这种方式的转移，然后建个图，剪个枝跑就行。

但是……这个方法码量比较大，不好看！怎么办，有没有更优美的方法？有的！我们考虑先随机一些正数出来记为序列，然后对于负数序列，如果每个，那么肯定每个就是独立的了。因此我们随机一串序列出来，然后跑个背包，跑完背包再跑一个背包就完成啦！是不是非常优美！

注意事项：的值域不能太大看起来都可以。然后神奇的地方来了，就是这个序列的长度是 22。经过测试，小于 22 的话跑几百轮都跑不满整个（比如说 21），但当你突然增加到的话，你会惊奇的发现，大部分情况一遍就能跑满，两遍都很少。更大的没试过，你们可以试试看。

后记

最快的一天！今天的题目虽然改起来很舒服，但是还是要仔细思考为什么考场上没有想出来。思维是很重要的一环，思考是怎么思考的。拜拜。