段三园的小迷弟

题解

心得(37) 未归档(1) 模板题(7) 读书笔记(2)

/ 注册

全部文章 / 题解（共110篇）

牛客小白月赛23i寻找子串

暴力就可以完事了（数据贼小，n^2都不超），但看了官方题解以后发现可以更简单点结果一定是从某位到最后（后缀），不可能是中间段，因为假设是中间段，那么中间段加上后面的一定比中间段的要大，所以遍历0-最后，1-最后。。。。计较即可这里有个语法，&s[i]是一个地址，但s是...

oj系统

2020-03-23

2 533

牛客小白月赛23h奇怪的背包问题增加了，二进制

加数ci<2^30，所以如果加数和大于2^30，则一定有组合可以构成2^30 注意这里和一般加法不同，一般的如234+567，而这里就好比只允许加上1,10,100。。。而不允许加上567这样的数字然后就是找到这样的组合，这里从大到小排列这些ci，初始sum=2^30，如果ci...

二进制

2020-03-23

9 730

牛客小白月赛23b阶乘，因数分解+模拟+数学

先因数分解出因数和次数，然后找到最大的（因数*个数）如2*3*3*3*5*5这个数最大的（因数*个数）是5x2，所以只要遍历到10！，2和3,6,9都遍历过2，3系数都满足还有注意例如次方情况，如要满足3^14不是（3*14）！而是（3*10）！因为这里9，18里有两...

因数约数模拟数学

2020-03-22

10 888

牛客小白月赛23a膜法记录，状压

由于行的数少，所以暴力考虑删除行的方法2^n，然后看剩下的列是否符合要求mn 由于后面mn，所以我们只考虑删行机会全部用完的方法如果剩下需要删除的列<=删列机会，就找到方法break 这里用二进制数来压缩方法时间极端：情况一：25*1e5*5 情况二：...

状压

2020-03-22

1 681

牛客练习赛59d取石子游戏，博弈论

从样例中可以看出1是必败态，它无法分成两份 2是必胜态按博弈论讨论必胜态就是自己操作后是对方陷入必败态从样例上看可以转移到1的必胜态1*2,1*2+1 {1+（1+1）}即【2,3】必胜态只能转移到上必胜态的必败态 2*2，2+3，2*3...

博弈论

2020-03-16

6 671

acwing905区间选点

把所有点按右端点从小到大排序，贪心排序一般都是按右端点（从小到大）排序，因为这样全包含就会归为前面，如果按左端点排序，那么全包含就是后面，这样不管选前端点还是后端点都无法管到如果已选点<线段左端点，则把线段右端点选入（使得选择使对后...

贪心

2020-03-15

1 781

牛客练习赛59c，数学+三分

假设用方法一生成n件，那么方法二就是总件数all=n+min（（x-2n）/4，y-3n），求all的最大值一般的就是把n枚举，但是从题目x，y<=1e9 n=[0,min(x/2,y/3)]——即完全不用方法一 ->完全用方法一，时间复杂度是1e9/2 所...

三分数学

2020-03-13

12 955

pta周游世界，dfs完整还原现场重要性

思路：用vector数组存每个点的课链接点，一个数字存两点间的路段属于哪个公司 tmp是暂时存现在路线，ans是保存最优路线 vis是记录该点有没有访问过，题目说存在圈，所以用其防止重复点 dfs暴搜，如果现在路线好于历史最优路线，则ans=tmp tmp和ans存点的时候按...

dfs 最短路

2020-03-13

0 945

cf1316c Primitive Primes

首先题目保证有答案这里用到一个约数的性质 (a+b*g+c*g...)%g=a%g 这题主要是要排除掉a%p!=0,b%p!=0,但（a+b）%p==0 找到最小的不被p整除的数ai和bj，则ci+j就是符合条件的，因为如果有其他项（假设为o，p）也参与了的xi+j...

多项式质数数学

2020-03-05

0 625

P3951 小凯的疑惑，同余

因为a,b互素，所以gcd（a，b）=1，所以不定方程ax+by=可以等于任何数，任何数%1==0 但是如果x，y有一个是负数就不符合题意设a<b，答案为x 则： x=ma (mod b) (1<=m<=b-1) x=ma+n...

取余求模数论

2020-02-03

0 546