__故人__

题解

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20)

/ 注册

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

[SDOI2013]淘金

比较有趣(有难度)的数位。分析我们考虑表示每一位的积。那么我们先考虑一维的情况，那么我们要求出最多的一个。那么这个考虑数位解决。但是我们发现还是比较大的。直接表示状态是表示不出来的。但是就有了一个非常好的性质。。这样我们发现其实有用的状态非常少，大概个左右...

2020-11-12

7 599

2020 CCPC 长春 F

题意非常简洁，给你一个有根树。求问。分析我们发现出现的非常突兀。考虑直接枚举，由于每个点对只计算一次。所以只用计算后加入的对前者的贡献。那么一个点的贡献为，其它子树中权值为的编号。但是答案为。这个没有什么结合率和交换率。我们考虑直接拆位。那么令表示，权值为，第 ...

2020-11-11

6 942

金字塔

分析设为字符串中从到部分为一整棵树时的方案数。那么考虑子树的划分，那么，考虑子树在处回到根节点。代码 #include<bits/stdc++.h> using namespace std; #define ll long long const int mod =...

2020-11-05

5 634

P4094 [HEOI2016/TJOI2016]字符串

分析比较综合的题目，这里说几个关键点。反转字符串，前缀变成后缀。二分答案，有单调性。倍增找父亲，线段树上查找集合是否有的元素。在树上线段树合并 + 就做完了。代码 #include<bits/stdc++.h> using namespace std; ...

2020-11-04

4 608

P5212 SubString

分析考虑有动态加字符串的操作，考虑维护。然后支持一下链上加和单点查询就好了。是挺板子的。代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 400000; void change(char *s,...

2020-11-04

3 584

小A与欧拉路

分析我们对于不定根的树形结构的题目，我们首先应该考虑定根考虑。考虑从节点出发。那么我们得到的最短的欧拉路一定是，考虑到每次走完一个子树都必须回到自身，除了最后一次。所以我们在定根之后，就是要选取。那么我们只要取所有节点作为根的最大值。结合定义可以发现我们就是要求，树上的一条最长路径 ...

2020-11-03

6 780

[SCOI2011]棘手的操作

说在前面的话不要被可怕的操作吓跑，战胜恐惧的最好办法，就是面对恐惧，加油，奥利给。但冷静分析一下，好像是道大水题。分析分析一下，所有操作其实有用的就是维护一下，集合最大。支持合并。其他的操作都可以开一些标记记录一下。但是合并操作的复杂度如何分析，最值又如何维护。维护最值一般维护最值一般考虑...

2020-11-02

7 707

[TJOI2017]DNA

分析不会后缀数组实锤了。考虑求还可以使用字符串哈希。二分哈希，时间复杂度也是。代码也挺短的。代码 #include<bits/stdc++.h> using namespace std; #define ull unsigned long long const int N...

2020-11-01

4 650

2020牛客NOIP赛前集训营-普及组（第六场）来自专栏

2020牛客NOIP赛前集训营-普及组（第六场） A 七七七七分析由于每次的答案的增长是以指数增长的，所以直接枚举日期的复杂度为。那就直接暴力枚举就可以了。总的复杂度为。代码 #include<bits/stdc++.h> using namespace std; int...

2020-10-31

2 701

2020牛客NOIP赛前集训营-普及组（第五场）来自专栏

2020牛客NOIP赛前集训营-普及组（第五场） A T1 购物分析由于是买送一，所以我们考虑买只需要次花钱的购买。那么可以把个物品分成很多段，每段的长度为，然后处理一下边角就好了。代码 #include<bits/stdc++.h> using namespa...

2020-10-29

5 650