Pikaaachu

分类

日常做题记录(4) 题解(7)

/ 注册

全部文章（共11篇）

一些CF&AT de 好题记录【年轻人训练 # Round11 + 周末做的题】

选自年轻人训练 # Round11 and 一点周末做的题都是非常锻炼思维或者值得积累的题ww前排%龙哥A - Nastia and Nearly Good Numbers CodeForces - 1521A 【思维】题意：构造3个不同的数x,y,z,使得x + y = z,且x, y只能被A整...

树状数组线段树 cf 做题记录 dp 区间合并

2021-05-24

0 777

树链剖分的边权转点权问题

将边权->点权，只需要在dfs的时候求出两个点的深度，把边权下方到深度更深的节点上即可。但是转化完之后，最后query_path的时候要注意，是求的son[u]和v之间的信息（因为点u保存的是u点到他的father节点之间的那条边，不应该算在u->v内）Housewife Windtip...

线段树树链剖分日常

2021-04-11

0 1078

线段树区间合并问题

线段树维护区间信息的题单dalao的博客最长区间带修改的严格最长上升子序列长度。【练习线段树做法】要深入理解线段树的l, r是指的数组下标这句话emm.一个节点保存：左边的LIS长度，右边的LIS长度，区间总体的LIS长度，区间的元素个数（其实可以算出来）。关键在于pushup函数：先更新区间...

线段树做题记录树状数组区间合并

2021-04-11

0 1012

牛客练习赛 80

不降数这个题很有意思哇有很多的解法emm记录一下做题过程qwq如果n的范围小一点，可以直接用数位dp过掉，但是n太大会mle.于是写了一个线性dp递推+滚动数组，复杂度是1e10的emmmdp[i, j]表示第i位以j结尾的数的个数。可以留着对拍： #include<bits/stdc++....

做题记录 dp 组合数学数位dp

2021-04-11

2 638

Codeforces Round #655 (Div. 2)（补题ing)

D. Omkar and Circle 【前缀和，区间DP思想】题意：在一个圆上排布着奇数个点，连续的3个点，可以合并为1个点，这个点的值由左右2个点的和决定【例如1 2 3可以合并成4,2的两侧1 + 3】，只要有3个以上的点，就可以不断进行合并，最后，圆上只会剩下一个点，要求这个点的值最大。思...

cf 做题记录 dp

2021-04-08

0 583

Codeforces Round #651 (Div. 2)（补题ing)

B. GCD Compression【思维】题意：给出一个2n数组a，从a数组选出2（n-1），每次取两个数，其和加入b数组，使b数组构成一个n-1长且gcd(b1,b2,...,bn)>1，输出n-1对数在a数组的下标。思路：奇数两两配对，偶数两两配对， gcd至少是2. void s...

cf 做题记录日常

2021-04-08

0 609

Codeforces Round #654 (Div. 2)（补题ing)

C - A Cookie for You【贪心】题意： if the guest of the first type: if v>c the guest selects a vanilla cookie. Otherwise, the guest selects a chocolate coo...

cf 做题记录日常

2021-04-08

0 681

Codeforces Round #652 (Div. 2) （补题ing）

cf补题 652B - AccurateLee 题意：如果一个字符串有连续10，可以去掉1或者去掉0,问最短的字典序最小的串。思路：前面的0和后面的1一定去不掉。中间的10无论怎么排列，都可以消成一个0，所以前后找一遍即可。注意特判00001111这种一个都消不掉的。 void solve(){ ...

cf 日常

2021-04-08

0 735

最近做的一点题的整理emm

G. Maximize the Remaining StringCF 1506G 【2000 贪心单调栈】题意：给一个字符串，每个字符只能保留一个，要求字典序最大。自己写的时候写假了emm 因为每次判断的时候并不知道后面的字母是不是已经被选过了qwq辣鸡wa2代码： void solve()...

单调栈字符串做题记录组合数学日常

2021-03-29

0 599

一些值得看的题目记录qwq

白兔的字符串【字符串hash】思路：根据题目描述，可以把T串扩展成2倍，然后每lenT段求一个字符串hash值，这样就可以求得所有同构串的hash值了。然后对于新串，每隔长度为lenT段求一个hash，看这个hash值是否出现即可。tips:这题听说map会T, 可以手写一个二分查找，起到一样的效...

字符串做题记录树形dp 日常

2021-03-25

0 633