- 博客(14)
- 收藏
- 关注
RSS订阅原创 Dirchlet后缀和的应用 Codeforces 1614D2
Dirchlet前缀和和Dirchlet后缀和基础知识可以查阅blog学习一下，以前一直用不知道叫这名……其实本质也就是质因数分解以后指数的高维前缀和……cnt[i]表示{a[i]}中i的倍数的个数，dp[i]表示选出i的倍数的数，前缀gcd的和最大是多少显然前缀gcd一定是前一个前缀gcd因子，所以dp[i]要么等于i * cnt[i]要么一定存在某个位置前缀gcd为j，使得j为i的倍数，dp[i]=max{dp[j]+i*(cnt[i]-cnt[j])}，一定是前面gcd是个i倍数，后面填了一些i的
2021-12-22 20:40:37
332
原创 codeforces 1608
codeforces 1608cf1608D这类题套路就是先按一维排序，按着一维搞另一维。第一维排序以后倒着做，预处理第二维前缀最大值，i能屠场的条件是第二维前缀最大值>(i,n]中能屠场的位置的第二维最小值，一开始当成最大值，wa了几次……...
2021-12-17 18:49:50
409
原创 2019.12.summary
2019.12.6BZOJ4726: [POI2017]Sabota?只想到了带log的二分做法，听说5e5要卡常才能卡过去然后翻题解，发现有O(n)的dp做法，感觉这个状态设计还是挺合乎逻辑的，却没有想到，说明这一方面很有问题啊dp[i]表示i没有成为叛徒，最小的x，dp显然然后最后把子树大于k的状态取一个max2019.12.14BZOJ3812: 主旋律好题！！！对着题解y...
2020-01-16 16:43:05
226
原创 2019.11.summary
2019.11.10BZOJ2653: middle挺好的题，要先知道一个二分求中位数的trick然后上主席树就好了，懒得多嘴了qwq调了2天，因为以前写const没感觉，现在写define直接写的20000+10然后下面N*40，#define是直接把你写的带入，然后就GG了（虽然调题的时候发现自己最近弱智到主席树模版也挂了一次，捂脸）2019.11.14BZOJ1303: [...
2019-12-06 22:35:19
172
原创 2019.10.summary
2019.10.2最近比较喜欢补CF的题吧qwqCF1228E其实我原来的想法是跟hongzy一样的方法然后发现其实一个区块里面的点它的邻接表是一样的，直接用map压vector即可CF1228F首先根肯定还是重心，多个重心就都试然后从下往上比较显然，只有儿子个数是1或3才有可能为什么我的代码怎么卡时都卡不过去，一个同样写法还没有写inline，register的yyr随便就艹过去...
2019-11-07 21:49:31
181
原创 2019.9.summary
2019.9.1BZOJ3238: [Ahoi2013]差异后缀自动机好题好像想到这个结论就不难，但是不太好想QAQ把串倒过来建，则两个前缀的最大公共后缀就是pre树上的lca的step因为一个点的pre代表的肯定也是这个点代表的后缀，记住就行了P.S刚看了一眼SA+单调栈的写法，挺思维的啊，想不出来，还有那个单调栈一端设可以等于，一端设不可以的要注意一下很有启发性2019.9.2...
2019-10-02 21:12:23
178
原创 2019.8.summary
2019.8.1BZOJ4664: Count我去，这道题想了两天终于想明白了QAQ好题啊……！首先肯定从小到大的放，dp[i][j][k][0/1/2]表示放了前i个数，这些数被分成了j个段，贡献和为k，整个序列的两边有几个能填数因为如果直接把统计每一个数的贡献，可能会出现负数所以我们给每一段的两端（两个边界看第四维）都加上h[i]-h[i-1]，相当于把那个数提到了h[i]，保证...
2019-09-01 22:46:58
249
原创 2019.7.summary
2019.7.1颓了几天，该回来了BZOJ2749: [HAOI2012]外星人phi操作的本质就是把每一个pi的指数-1，然后在乘上(pi-1)显然最后2的指数最多而只有phi(2)=1（不算phi(1)的话）如果pi不等于2的话，pi-1一定会分出至少一个2的对吧所以我们筛出把i分成只剩2需要几次f[i]ans就是f[p[i]]*q[i]的和注意一个细节，若果n是奇数，ans...
2019-08-01 13:44:13
740
2
原创 2019.6.summary
2019.6.1BZOJ3028: 食物生成函数题，母函数乘起来就好了BZOJ3544: [ONTAK2010]Creative Accounting嗯，就是可以用set维护前缀和，取后继或最小数贪心就好啦BZOJ2820: YY的GCD莫比乌斯反演BZOJ4173: 数学https://blog.csdn.net/zhhx2001/article/details/52300924...
2019-07-04 23:02:11
326
原创 2019.5.summary
2019.5.1CF C. Prefix Sum Primes感觉CF就是训练妳如何养成对题目强大的YY能力的QAQ我们构造如果只有一种，没辙，只能这样放否则先放一个2，再放一个1接下来把2放完再用1填因为所有质数除了都是奇数，所以这样尽可能让前缀尽量多的是奇数最有可能……CF D. Three Religions一开始题目读不懂，mdzz，不然应该会写题意就是说能不能把三个串...
2019-07-04 22:59:49
385
原创 2019.4.summary
2019.4.1BZOJ1061: [Noi2008]志愿者招募真心有点难QAQhttps://www.byvoid.com/zhs/blog/noi-2008-employee看void爷的博客看了三遍才懂。这种网络流建模看不出来啊首先可以列出一些数相加减的式子然后可以考虑差分，得到一些式子和为0的情况这不就很像每一个点流量平衡对吧正的是流进来的，负的是流出去的常数是关于s，t...
2019-07-04 22:58:56
905
原创 2019.3.summary
emmmm，把以前写的2b总结丢上来吧，不过应该也不会有人看QAQ（注：因为用txt写的，有一些公式打的很随意，放到markdown上公式自动排版，有可能会显示出错误！可在下方留言）2019.2.24如石子堆交换这种改变状态的可以尝试看看差分在取数使满足某一条件最小或最大时可以先假设原来状态，然后表示出取某一个的状态，用作差或作商看在什么情况下更优2019.2.26对于最短路问题，题...
2019-07-04 22:57:47
387
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人