- 博客(143)
- 收藏
- 关注
RSS订阅原创 每日一题 Paint Box
Paint Box题目链接题意：给出n个格子和m种颜色，从m种颜色中选出k种颜色，对n个格子进行涂色，其中k种颜色种的每一种颜色都要用上，而且相邻的格子不能涂相同的颜色。1≤n,m≤1e9,1≤k≤1e6,k≤n,m1 \leq n,m \leq 1e9,1 \leq k \leq 1e6,k \leq n,m1≤n,m≤1e9,1≤k≤1e6,k≤n,m做法：这道题应该是容斥原理容斥原理这个东西很难的，我也不是很懂，只能靠猜。首先我们想象一个总的集合，那就是有k种颜色然后相邻的格子不能涂相
2021-12-02 17:43:07
251
原创 每日一题 CF1029E-Tree with Small Distances
CF1029E-Tree with Small Distances牛客链接CF链接很好找，就不贴了题意：给你一颗树，要求你加入最少的边，使得1节点到任意节点的距离不超过2数据范围，点数 20万注意，这道题可能需要效率比较高的输入和树的遍历方式做法：我也好久没写过题了，虽然之前写过但不过都没有记录，现在还是记录一下，为了找工作做准备。我拿到这道题，我一脸懵逼，WC怎么这么难，想了想不可能是贪心，因为我觉得贪心越复杂肯定是错误的，但不过贪心能不能做，我不知道，好像能做吧。于是我就想到了
2021-12-01 17:07:09
234
原创 HDU6834 Yukikaze and Smooth numbers
题目链接题意：给出一个n和k，要求输出1到n中有多少个数的最大质因子都小于等于kT组输入，n和k的范围都是1e9.做法：如果n≤kn \leq kn≤k 那么答案是nnn.如果 k<nk< nk<n:首先考虑一个容斥很容易得到答案的表达如下：ans=n−∑i1pi+∑i<j1pipj−...(−1)k1p1p2...pk(min(p)>k)ans =n -\sum_{i}\frac{1}{p_i}+\sum_{i<j}\frac{1}{p_ip_j} -..
2020-08-07 20:15:36
557
原创 HDU6796 X Number(数位DP)杭电多校
题意：定义对于一个数字，那一个位数的数字出现最多，就定义为那个数字。比如133344就是状态3，111122就是状态1，对于出现次数不唯一的，定义为状态10.现在给一个区间问(l,r)(l,r)(l,r)中有多少状态为ddd的数，ddd不为10.做法：看一眼数位dp，然后状态怎么记录，考虑记录0-9每一个数字出现的次数，可以使用字符串，vectorvectorvector等使用mapmapmap标记，可以赌一下状态不会很多，甚至使用哈希，但不过这道题显然不会让你这么做，那么就需要优化。首先对于记录状态.
2020-07-29 20:47:56
631
原创 Quadratic Form(约束条件下的最值)牛客多校第一场D题
Quadratic Form题意：给出一个正定n×nn \times nn×n矩阵，和一个nnn维的向量bbb,现在叫你找到一个x1,x2,x3,...,xnx_1,x_2,x_3,...,x_nx1,x2,x3,...,xn满足如下条件：x1,x2,...,xn∈Rx_1,x_2,...,x_n \in Rx1,x2,...,xn∈R∑i=1n∑j=1nAi,jxixj≤1\sum_{i=1}^n\sum_{j=1}^n A_{i,j}x_ix_j \leq 1∑i=1n∑j=1n
2020-07-15 17:20:05
435
原创 B-Suffix Array (sort排序)牛客多校第一场A题
B-Suffix Array题意：给你一个字符串，同时定义一个BBB函数，对于一个字符串他的B函数为：B(s1s2s3...sn)=t1t2t3...tnB(s_1s_2s_3...s_n) = t_1t_2t_3...t_nB(s1s2s3...sn)=t1t2t3...tn其中ti=minj<i,s[j]=s[i],(i−j)t_i = min_{j<i,s[j]=s[i],}(i-j)ti=minj<i,s[j]=s[i],(i−j)如果前面没有出现s[i]s[
2020-07-13 21:34:31
544
原创 2020 年 “游族杯” 全国高校程序设计网络挑战赛
我同学叫我去打的。不说了，题还是不错的，但奈何我英语差。。。A. Amateur Chess Players不想解释。#include "bits/stdc++.h"using namespace std;#define ll long long#define SZ(x) ((int)(x.size()))#define all(x) (x).begin(),(x).end()const ll mod = 998244353;const int maxn = 100000 + 10;
2020-05-28 17:24:24
712
原创 Codeforces Edu 85 G. Substring Search（FFT字符串匹配）
题目连接题意：给你一个s和t串，然后用s去匹配t串中的每一个长度与s相等的子串。如果si=tjs_i=t_jsi=tj或者pidx(si)=idx(tj)p_{idx(s_i)}=idx(t_j)pidx(si)=idx(tj)则可以匹配，输出每一个位置可以匹配的情况。做法：显然是不能用常规的字符串匹配去解决。这里如果你做过洛谷上的带有通配符的字符串的匹配，可能知道怎么做，就是用...
2020-04-22 17:42:54
336
原创 点分治学习模板及一些例题
点分治这里没有动态点分治。。点分治是解决树上问题的一类算法，很多复杂度能从暴力的O(n2)O(n^2)O(n2)降低到O(nlogn)O(nlogn)O(nlogn).具体做法是就是求一个树的重心，树的重心的性质，其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。就是说子树的大小可以lognlognlogn的降低，这样复杂度就降下来了。如...
2020-03-25 12:13:09
264
2
原创 P4103 [HEOI2014]大工程
题目题意：给出一个树，给出k个关键点，这k个点每一对点的路径和，最小值以及最大值。做法：首先我们看见多组询问并且k和n同阶，应该就知道是虚树的处理了。首先考虑怎么树上dp。设dp[u]dp[u]dp[u]表示当前uuu为根的子树中关键点之间的和，接下来按照每一个子树的遍历顺序可以得到总的代价可以通过如下关系得到：ans+=(dp[u]+sz[u]∗dis)∗sz[v]+dp[v]∗sz[u...
2020-03-21 14:23:34
148
原创 虚树——P2495 [SDOI2011]消耗战
好久没有学习新的知识了。https://www.luogu.com.cn/problem/P2495今天我学习了一下虚树。虚树就是一个不存在的树。用来简化问题。它只包括一些关键点和他的LCA我们来看看上面这一道题题意给出一棵树，含有边权。每次询问给出k个点，然后询问每个点与根断开的最小代价。做法因为数据的关系肯定没法直接dp过去的。首先我们可以发现可以与根到其他点的路径没有关系...
2020-03-18 22:14:22
134
原创 UOJ188【UR #13】Sanrd (Min_25筛)
这里题意：说白了就是求这个∑i=1npsmax(i)\sum_{i=1}^{n}p_{smax}(i)∑i=1npsmax(i)其中psmaxp_{smax}psmax表示次小质因子，规定1和质数的次小质因子为0做法：这道题是一道min25筛法的题，但不过不是普通的积性函数求和，需要对该算法有一定的理解。首先我们还是以s(n,j)s(n,j)s(n,j)表示在1−n1-n1−n范围内...
2020-02-18 15:28:22
251
原创 Min_25筛 代码及模板
LOJ简单的函数以这道题为例子，讲一下min_25筛如何用代码实现。首先min_25是一种亚线性筛，可以处理1e9以上的数据，老版min_25筛的复杂度为O(n0.75logn)O(\frac{n^{0.75}}{logn})O(lognn0.75)，新版已经优化到O(n23)O(n^{\frac{2}{3}})O(n32)，复杂度，我也不会证明。据说常数比较大，确实是跑得快，但不过差距...
2020-01-19 15:54:17
565
原创 The 2019 ICPC Asia-East Continent Final(部分题解)
这是今年我的最后一场，顺便写一下游记，第一场因为发挥打铁，心里很郁闷，加之最近学业加(我们学院都是硬件专业) 。那天考了四级（不能过）就和另外一个队一起坐高铁来到西安，到的时候时间还有还可以打一打热身赛，不得不说志愿者服务真好。第一天热身赛，看了一眼，旁边都是比我们好的学校，直接签了A题，C++，JAVA都试了一下还不错，Clion好用，B题刚刚开始想对了，但不过被自己干掉了，然后试了一试机器，...
2020-01-12 20:30:37
3214
7
原创 Common Substrings POJ - 3415(后缀自动机)
https://vjudge.net/problem/POJ-3415其实很早以前这道题就过了，但不过因为后缀数组的方法自己也不是很懂就没有写。今天我学了一下后缀自动机，我们利用后缀自动机解决。首先对A串建立后缀自动机，然后对每一个非克隆结点进行标记， 然后建一颗fail树，用一个dfs进行计数，这个步骤就是其他博客上写的拓扑排序。首先对于一个结点，他所包含的子串个数为 len[i]−...
2020-01-11 20:35:28
313
原创 树链剖分 入门题（洛谷）
最近学习了树链剖分。发现这个东西其实并不是很难，而是因为代码量比较长，在码的过程中容易出错。但不过其中还是用套路可循的，如果要学习树链剖分必须要知道DFS序和线段树。这里就不详细讲了，只给出一些入门题，供个人参考。https://www.luogu.com.cn/problem/P3384这是一个模板题首先树链剖分有两个dfs其中一个dfs是处理轻重儿子的，另外一个dfs是维护重链上的...
2020-01-09 10:13:55
383
原创 P5840 [COCI2015]Divljak【AC自动机+fail树+树上乱搞】
https://www.luogu.com.cn/problem/P5840题意：中文题，给你n个串，然后m次操作，两种操作。1操作，集合T加入一个串。2操作，询问集合T中出现上面的n个串的第i个几次。首先听说解法挺多的，如果有幸学会了，后来补上吧。做法：这里用AC自动机做吧，首先对n个串建立AC自动机，建立fail树，然后每一次往T集合中加入一个字符串，就让他到AC自动机中跑，跑到的点对...
2020-01-07 16:02:47
279
原创 E. Tree-String Problem (AC自动机+fail树)
https://codeforces.com/problemset/problem/291/E题意：给你一颗树，然后每一条边有一个字符串，然后给你一个字符串，问这个字符在所有的树的根到叶子结点练成的串中，出现了多少次。做法：建立AC自动机，每个点进行计数，在对询问串建AC自动机时不需要计数，然后dfs遍历fail树进行计数就可以了。#include "bits/stdc++.h"usin...
2020-01-07 09:35:40
335
原创 「TJOI2015」弦论
https://loj.ac/problem/2102只是一道后缀自动机的题目做法：首先当T=0时，就相当于从空串出发的有多少条路径，相当于每一个点都是1，然后dfs进行计数，在后缀自动机上进行贪心的输出就行了。当T=1是，就相当于对于每一个非clone的点都为1 ，然后在建fail树，进行计数就可以了，再用dfs进行计数，在贪心的输出就可以了。#include "bits/stdc++....
2020-01-03 13:44:23
279
原创 「SDOI2016」生成魔咒
https://loj.ac/problem/2033题意：这道题是中文题。就是给你一个字符串，询问每一个前缀中有多少个不同子串。做法：说到不同子串的数量，应该想到的是某种字符串算法。这道题应该用后缀自动机解决。首先一个字符串中不同子串的数量就是从空串起点t0t_0t0出发有多少条路径。我们可以利用SAM的树形结构跑一个动态规划 dp[u]=1+∑vdp[v]dp[u]=1+\sum_...
2019-12-31 18:54:51
261
原创 P3804 【模板】后缀自动机 (SAM)
https://www.luogu.com.cn/problem/P3804很早以前就想把这个坑补了，最近终于把他补了。后缀自动机是对一个字符串信息高度压缩后的产物。这次把这个坑了补了。建议从这些博客入门https://www.cnblogs.com/xzyxzy/p/9186759.htmlhttps://oi-wiki.org/string/sam/https://www.luo...
2019-12-31 17:12:26
414
原创 Codeforces Round #610 (Div. 2) 简要题解
http://codeforces.com/contest/1282坚持下去谁也不知道结果是什么，但不坚持我肯定会后悔的。这场比赛自闭了，对我极其不友好，读不懂，读懂了又做不来。A.Temporarily unavailable题意：给一个区间[a，b]，以及一个基站c，以及信号覆盖范围半径r，一个人以单位速度从a到b运动，问过程中有多少时间不再基站信号范围内。做法：直接模拟即可，求出信...
2019-12-25 15:02:56
337
原创 gym-102452 香港区域赛部分题解
gym-102452 香港区域赛部分题解本人水平有限只会这几道题B - Binary Tree题意:给出一颗二叉树，Alice和Bob轮流删除子树，子树要求是完全二叉树。在这里想了很久，什么模拟都来了，最后想了一下，好像退了几个样例找到了结论。根据n的奇偶判答案#include<bits/stdc++.h> using namespace std;typedef lo...
2019-12-19 14:28:55
1032
原创 Codeforces Round #594 (Div. 2) 简要题解
http://codeforces.com/contest/1248A. Integer Points做法：统计两条垂直线的截距的奇偶性就行了#include "bits/stdc++.h" using namespace std;typedef long long ll;const int maxn = 100000 + 10; int main() { i...
2019-10-31 22:05:21
223
原创 P4980 【模板】Polya定理
https://www.luogu.org/problem/P4980题意：很简单的，就一个最简单的polya定理。做法：网上随便看看吧，写得都不错。我们要求的就是上面的式子，我们容易知道|G|=n，|B|=n；但不过重点就是c(g)；但不动的时候c(g)=n这点没有毛病吧，因为都没有动。但动k个点时候，这个时候就要看k了，随便找一找规律就知道这个就是 gcd(n,i...
2019-10-10 21:08:32
228
原创 E.Counting Sequences II (2019上海网络赛)指数生成函数
https://nanti.jisuanke.com/t/41413题意：给出一个1*n的方格，和1-m的数，每一个数有无限多吧，要求，把方格填满，但不过偶数必须出现偶数次，求方案数。做法：首先，我当时不知道这是一道生成函数，给一个学习生成函数的博客https://blog.csdn.net/wu_tongtong/article/details/78854572这道题如果用组合数学的...
2019-09-18 20:42:22
284
原创 P1231 教辅的组成 (最大流)
https://www.luogu.org/problem/P1231题意：给出书，答案和练习册，以及每本书可以匹配的答案和练习册，问最大有多少匹配。做法：很简单，应该能想到是最大流，但不过建图也很简单，源点-》答案-》书(拆点)-》练习册-》汇点。但不过每一本书只能用一次，必须要拆点，相当于限流。跑一个最大流就可以了。#include "bits/stdc++.h"usin...
2019-09-12 16:52:43
193
原创 P2763 试题库问题 最大流
https://www.luogu.org/problem/P2763题意：很简单，都是中文，给出每种类型试题的数量，同时，给出每道题，可以充当的试题种类。做法：设一个源点，与每一个试题类型建边，容量为试题的数量，同时每种试题类型在对每一个题型建立一条边，容量为1，最后在连接汇点。跑一个最大流即可。#include "bits/stdc++.h"using namespace s...
2019-09-10 20:18:43
215
原创 HDU6683 Rikka with Geometric Sequence 多校九(推导+杜教筛+分块)
http://acm.hdu.edu.cn/showproblem.php?pid=6683题意：问1-n这些数字中有多少子序列是等比数列。做法：这道题有点悬。。。。。我们接下来来一下，数学推导（瞎JB乱搞）：我们设等比数列的公比,等比数列的长度为，首项末项这个必定是一个整数，所以可以得到,这个是显而易见的。但不过这个好像不好弄。因为如果你统计p的数目，这只是n范围内的...
2019-08-20 17:11:47
377
原创 P1005 矩阵取数游戏 (高精度)
https://www.luogu.org/problem/P1005尽管这道题不算很难，但不过我还是差点没有想到。首先这道题很容易看出来，每一排互不相干，每一排算自己的。因为涉及到先后，而且只能取两个端点的。因此很容易想到区间dp，有一个小的区间去推一个大的区间。因为正着推，是错误了，自己yy吧。而到着推，很容易想到地推方程的。这个方程也不是很难的。这道题一看数据...
2019-08-17 10:43:37
214
原创 P1120 小木棍 ［数据加强版］(暴力)
https://www.luogu.org/problem/P1120尽管这道题可能不算很难，但不过我还是错了很多发，看了题解，其中一下剪枝，优化没有想到。首先我们确定应该枚举什么，肯定是枚举木棍的最小长度拉。然后判断能不能凑齐总的长度sum/len根了。首先就是求出sum，然后枚举的时候上界只需要枚举到sum/2就可以了，下界就是最长的那一根，每次就是sum/len能被整除，这个...
2019-08-17 08:59:06
533
原创 HDU 6661Acesrc and String Theory (多校第八场) 字符串hash
http://acm.hdu.edu.cn/showproblem.php?pid=6661多校被虐得自闭，我还是太菜了题意：很简单，就是问你有多个子串，能过被分割成相等的k个子串部分，不能有重复，比如aa可以分成两个a，ababab这能分成三个ab。做法：首先想怎么做，肯定子串的长度是k的整数倍，我们枚举长度显然是不合理的。我们换一种思路，枚举一个长度len的整数倍，判断有多少个...
2019-08-15 09:51:56
455
原创 P4173 残缺的字符串(带通配符单模式串匹配)
https://www.luogu.org/problem/P4173题意：很简单，不说了。做法：这道题就是FFT在字符串匹配中的应用。单模式串匹配中的一种。首先简单说一下，不带通配符的单模式串匹配算法。可以用KMP，或者哈希。这里我们不用这个。对这道题貌似没有帮助我们定义一个匹配函数，对于A串的x位和B串的y位：，如果A串的x位和B串的y位的字符相同，则这个函数为零。...
2019-08-13 19:20:56
328
1
原创 Grisaia (推公式) 2018 第十届四川省程序设计竞赛
https://www.oj.swust.edu.cn/problem/show/2810题意：很简单就是求题目上面那个式子的和。做法：直接开始推公式。然后，将前后两部分分开然后对于前面的一部分直接可以由公式计算得到：我们现在考虑后面一部分怎么计算。我刚刚拿到的时候一点头绪都没有。但不过我们做题做多了，经常可以发现这种式子一般可以化成，两个上界为n的和...
2019-08-10 15:59:35
343
5
原创 线性基模板 HDU 3949
线性基是哪里除以一堆数的异或的最值的情况的。其实基底就是线性代数中的无关组，线性基应该是最小无关组。最近也学习了一下，网上的博客也讲得很好，今天在这里写一个模板。#include "bits/stdc++.h"using namespace std;typedef long long ll;const int vmx = 66;ll a[66], p[66];int ze...
2019-08-10 09:15:49
139
原创 P3768 简单的数学题(杜教筛+欧拉函数反演或者莫比乌斯反演)
https://www.luogu.org/problem/P3768题意很简单就是求这个：为了方便我们用（i，j)表示gcd（i，j），然后开始快乐的推公式吧：看见后面那一坨直接莫比乌斯反演：然后根据套路枚举t:后面一部分就是等差数列通项公式，所以后面就是变形为然后再根据套路令T=td，枚举T:我们观察这部分刚好是狄利克雷卷积的标准形式因此这部...
2019-08-08 20:09:46
278
2
原创 洛谷P4721 分治FFT(多项式求逆模板+生成函数)
https://www.luogu.org/problem/P4721这道题不算是一道裸的多项式求逆模板。首先这道题题目说的是分治FFT，我反正弄了几天，开始学FFT就看到这道题了，没有弄出来，到处瞎想，太弱了。随着知识的深入后来发现这是一道模板题。其实这道题和生成函数应该不是很大，即使你不知道，我想可能乱搞也会出来。。。。。我们来开始推导一下。首先有这个式子：然后...
2019-08-06 21:00:00
309
原创 HDU 多校 6625 three arrays
http://acm.hdu.edu.cn/showproblem.php?pid=6625题意很简单不说了。直接说怎么做，首先建两颗字典树，把a和b数组都放进去。然后想了想是贪心，然后想了很多比如dfs还写了很久，最后是选择了对两颗字典树同时进行BFS.分为四个方向，两颗树都是1，两颗树都是0，一颗0一颗1，一颗1一颗0.这四个方向，优先满足1和0；然后这个可能写着巨麻烦...
2019-08-06 16:33:15
135
原创 Steins;Gate(原根+FFT)
http://newoj.acmclub.cn/problems/2072题意：给出一个数组a，问对于每一个元素ak有多少个二元组(i,j)满足.做法：求出p的原根g，然后上面的式子就变成如下形式即求解有多少对bi+bj等于bk；这个就好办首先我们队每一个数对P取模,然后得出他的指数，并对指数进行计数。然后就用快速傅里叶变换，解决这个计数问题。卷积后面的大于P的需要归入...
2019-08-03 16:25:22
236
原创 HDU 4609 3-idiots 组成三角形的概率
http://acm.hdu.edu.cn/showproblem.php?pid=4609题意就是给你n根线段，问任意选三根，能够构成三角形的概率。首先总的选择方案很容易得到，直接组合数公式就可以得到。然后就是关于三角形的怎么组成。对于一个每一个长度len[i]，记录一个num数组。然后num与num相卷积，就可以得到，任意选两条线段，得到的长度的组合方案数。比如 1 3...
2019-08-02 14:12:58
284
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人