- 博客(169)
- 收藏
- 关注
RSS订阅
原创 ACM学习参考博客
OI大神博客 https://www.cnblogs.com/TheRoadToTheGold/category/985514.htmlOI届的小混混（dalao）:https://www.cnblogs.com/zwfymqz/p/9338689.htmlcodeforces-Petr ：http://petr-mitrichev.blogspot.com/WJMZBMR-clj...
2018-11-21 15:38:32
11717
转载 ACM训练史上最详细计划（大神养成记）
看完人家的博客，发现任重道远。。。一位高手对我的建议：一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。 下面给个计划你练练：第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示...
2018-07-24 16:58:02
6882
1
原创 HDU 6659 Acesrc and Good Numbers
题意求<=x<=x<=x最大的nnn，满足1−n中的所有数的数位中数d1-n中的所有数的数位中数d1−n中的所有数的数位中数d出现了n次从网上找了个板子，是求1−n1-n1−n中ddd出现的次数,这里叫它count(n,d)count(n,d)count(n,d)因为我们要找<=x<=x<=x最大的nnn我们先算一下co...
2019-08-15 10:48:57
774
10
原创 AtCoder Beginner Contest 137 E - Coins Respawn
E - Coins RespawnTime Limit: 2 sec / Memory Limit: 1024 MB配点 : 500500 点問題文11 から NN までの番号がつけられた NN 頂点と MM 辺からなる有向グラフがあります。 ii 番目の辺は頂点 AiAi から頂点 BiBi へと向かい、この辺の上には CiCi 枚のコインが置かれています。 また、頂点 NN に...
2019-08-13 21:03:23
553
原创 CF1200E Compress Words KMP or Hash
这个题就是求字符串拼接后的字符串，中间重复的不要https://codeforces.com/problemset/problem/1200/EHash或者KMP解决就是匹配新出现的串与原来串的（长度与新出现串相等的）后缀的匹配KMP做法#include <bits/stdc++.h> using namespace std;const int max...
2019-08-13 09:13:59
553
原创 Codeforce 1202E You Are Given Some Strings.. 后缀自动机
先给一个串 t再给 n 个串 s将俩 s 拼接 （可以相同） 求 t 中有多少个这样的串 的和我们把问题转化为这样对于 把他分割成两部分 也就是求设前半部分的后缀是多少个S乘以后半部分的前缀是多少个S的和我们看样例 1 1*2 2*1 1*1 所以答案就是5将...
2019-08-09 18:59:42
432
原创 HDU 6624 fraction 辗转相除法
fraction Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 467Accepted Submission(s): 249 Problem Description Many pr...
2019-08-08 21:02:40
251
原创 P3384 树链剖分
题目描述如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z操作4： 格式： 4 x 表示求以x为根节点的子树...
2019-08-08 10:53:32
176
1
原创 P3128 [USACO15DEC]最大流Max Flow 树上差分
https://www.luogu.org/problem/P3128Farmer John has installed a new system of N−1N-1N−1 pipes to transport milk between the NNN stalls in his barn (2≤N≤50,0002 \leq N \leq 50,0002≤N≤50,000), convenie...
2019-08-07 10:32:24
147
原创 HDU 6583 Typewriter 后缀自动机
http://acm.hdu.edu.cn/showproblem.php?pid=6583题意就是让你拼字符串在后面添加任意一个字符的代价是p,将原串的子串复制到后面的代价是q，怎么做呢设DP[i]代表着拼成前i个字符的 最小花费我们假设 在 j--i 的字符串 是 0--j-1部分的子串那么有dp[i]=min( dp[i-1]+p , dp[j-1]+q...
2019-08-01 10:01:11
387
7
原创 P3975 [TJOI2015]弦论 第K小子串
题目描述https://www.luogu.org/problem/P3975为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?输入格式第一行是一个仅由小写英文字母构成的字符串s第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同...
2019-07-30 11:04:38
1317
原创 HDU 6598 Harmonious Army 网络流建图
Harmonious Army Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 221Accepted Submission(s): 89 Problem Description N...
2019-07-25 11:22:48
672
1
原创 HDU6588 Function 公式推导 积函线筛
先附一个积性函数线筛的linkhttps://www.cnblogs.com/zhoushuyu/p/8275530.html 讲的巨好这个公式分为两部分求一部分是这里的n指小于等于的最大值这个咋来的呢 好像是归纳整理推导来的另一部分呢，是就多出来的部分对于第一部分显然就是中间的那个可以筛出来在求个前缀和预处理完成设多出来的...
2019-07-23 12:27:53
366
2
原创 Power oj 2810 Grisaia 杜教筛
2810: GrisaiaTime Limit: 12000 MS Memory Limit: 1048576 KBTotal Submit: 83 Accepted: 15 Page View: 131Submit Status Discuss×Submit Problem 2810:Grisaia×Sorry, youd don't have permission to ...
2019-07-19 20:18:58
321
2
原创 牛客小白月赛16 I 石头剪刀布 期望
链接：https://ac.nowcoder.com/acm/contest/949/I来源：牛客网石头剪刀布时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld题目描述小阳和小石玩石头剪刀布的游戏，他们在地上画了 n 个长度为 1 的格子。小阳一开始在 1 号格子，如果小阳赢了...
2019-07-14 08:50:34
499
1
原创 POJ2154 Color polya计数 欧拉函数
ColorTime Limit: 2000MS Memory Limit: 65536K Total Submissions: 12707 Accepted: 4049 DescriptionBeads of N colors are connected together into a circular necklace of N beads (N&...
2019-07-12 09:44:52
171
原创 牛客练习赛49 B 筱玛爱阅读 子集DP
链接：https://ac.nowcoder.com/acm/contest/946/B来源：牛客网筱玛爱阅读时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262875K，其他语言525750K64bit IO Format: %lld题目描述筱玛是一个热爱阅读的好筱玛，他最喜欢的事情就是去书店买书啦！一天，他来到一家有nn本书的书店，筱玛十分快乐，决...
2019-07-11 11:05:51
186
原创 牛客OI周赛11-普及组 D 凸包的交 斜率优化
链接：https://ac.nowcoder.com/acm/contest/942/D来源：牛客网时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 262144K，其他语言524288KSpecial Judge, 64bit IO Format: %lld题目描述小A出了一道只有题目和计算几何有关的题给出整数数组A，求长度大于等于L的连续子段中，平均数最大的...
2019-07-10 16:39:12
171
原创 牛客练习赛49 D筱玛爱线段树 后缀差分
链接：https://ac.nowcoder.com/acm/contest/946/D来源：牛客网筱玛是一个热爱线段树的好筱玛。筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：给定一个长度为nn的数组AA，刚开始每一项的值均为00。支持以下两种操作，操作共mm次：1 l r1 l r：将Al∼ArAl∼Ar的每一项的值加上11。2...
2019-07-10 10:51:46
263
原创 “华为杯”中国矿业大学程序设计学科竞赛 H 毕业生的序列游戏 (概率DP)
链接：https://ac.nowcoder.com/acm/contest/948/H来源：牛客网题目描述 对于三个给定的正整数k, PA, PB, 现在有一个序列构造算法： 在初始条件下，有一个空序列，之后每次你会在该序列的末尾添加一个字母'a'或'b'，添加'a'的概率是PA/(PA+PB)，添加'b'的概率是PB/(PA+PB)。当在该序列中有至少k个子序列为'ab'的时候...
2019-07-10 09:24:50
253
原创 Count Pairs CodeForces - 1188B 推式子
You are given a prime number pp , nn integers a1,a2,…,ana1,a2,…,an , and an integer kk .Find the number of pairs of indexes (i,j)(i,j) (1≤i<j≤n1≤i<j≤n ) for which (ai+aj)(a2i+a2j)≡kmodp(ai+aj)...
2019-07-08 09:55:33
466
转载 状压DP枚举子集
原文 https://blog.csdn.net/yanzhenhuai/article/details/81572028刚才发现自己已经不记得如何枚举一个状压集合的子集（因为之前本身就没有怎么理解枚举子集的方法完全就是背下来的所以忘掉很正常），所以写下这篇博客做个提醒或者叫做警示吧，很多东西还是要理解透彻不然会吃亏的。我们现在要枚举状压集合S的子集，代码实现就是：fo...
2019-07-08 07:56:15
656
原创 牛客OI周赛11-普及组 C Colorful
链接：https://ac.nowcoder.com/acm/contest/942/C来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述小A最近学习了最小生成树的算法，觉得非常神奇。他现在在研究一个更加神奇的问题给定nn个点mm条边的无向图，每条边都有一个颜...
2019-07-07 18:53:24
326
3
原创 HDU 5528 Count a × b
Count a * b Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1571Accepted Submission(s): 523 Problem Description Marr...
2019-06-13 16:07:22
303
原创 Codeforces Round #566 (Div. 2) E Product Oriented Recurrence（矩阵快速幂 + 欧拉降幂）
E. Product Oriented Recurrencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet fx=c2x−6⋅fx−1⋅fx−2⋅fx−3fx=c2x−6⋅fx−1⋅fx−2⋅fx−3 ...
2019-06-12 00:13:06
390
原创 Educational Codeforces Round 66 (Rated for Div. 2) E. Minimal Segment Cover 倍增
E. Minimal Segment Covertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given nn intervals in form [l;r][l;r] on a numbe...
2019-06-06 21:22:56
263
原创 莫队玄学奇偶优化
莫队玄学奇偶性排序在分块排序时，采用以下奇偶排序(两种写法)实测1e5数据大约优化 150ms 居家旅行卡题必备参考https://blog.csdn.net/weixin_43907802/article/details/86773471bool cmp4(const node &c, const node &d) { return (c.blo...
2019-06-04 10:36:58
2325
原创 BZOJ1257: [CQOI2007]余数之和 (整除分块)
i是什么呢就是积性函数求个前缀和(等差数列)#include<bits/stdc++.h>#define N 6000010using namespace std;typedef long long ll;template<typename T>inline void read(T &x){ x=0; static...
2019-06-03 16:27:35
161
转载 计算机网络试题库(计算机网络试题库—选择、填空)
版权声明：转载请注明：http://blog.csdn.net/update7?viewmode=contents https://blog.csdn.net/update7/article/details/79072992 </div> <link rel="stylesheet" hr...
2019-05-30 17:57:08
31909
7
原创 牛客 勤奋的杨老师（二）(最大权闭合子图)
链接：https://ac.nowcoder.com/acm/problem/15828来源：牛客网题目描述众所周知，杨老师是一位十分勤奋的老师，他非常的热爱学习。勤奋的他为自己罗列了一个学习清单，共有n个知识点，他可以有选择的进行学习。每个知识点都会对应0个或1个或多个先修知识点（只有学会了先修知识点才能学习该知识点），同时每个知识点都有一个智慧值和一个智力消耗值。杨老...
2019-05-23 14:01:31
233
原创 POJ 3281 Dining(最大流)
Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.Farmer John has cooked fabulous meals for his cows, but he forgot to check his me...
2019-05-22 09:28:35
146
原创 hdu4656 Evaluation NTT
非常好的推式子的题用到了很多知识点推式子，先交换 i j 目的是把K放到外面来后面先卷积预处理得到p[j]然后继续推式子利用得到瞎卷一波就可以了。注意一下 k−j 可能是负数，所以要倍长一下要么三模数NTT，要么拆系数FFTFFT 更快些 #include <algorithm>...
2019-05-16 19:21:36
377
原创 Power oj 2781: 上决╇ф的黑科技 (任意模数NTT|拆系数FFT)
https://www.oj.swust.edu.cn/problem/show/2781式子很好推很明显卷积即可可以使用NTT或者拆系数FFT这里使用的是NTT#include <algorithm>#include <cstdio>#include <cstring>#include<iostr...
2019-05-16 14:19:09
506
原创 POJ - 2311 Cutting Game sg函数 二维
Q - Cutting GamePOJ - 2311 两个人在玩游戏。游戏规则如下：准备一张分成W x H的格子的长方形纸张，参与游戏的两个人轮流沿着格子的边界线切割纸张，水平或者垂直的奖纸张切割成两个部分。切割了n次之后就得到了n+1张纸，每次都选择切得的某一张纸再次进行切割。首先切出只有一个格子的纸张（1 x 1的各自组成的纸张）的一方获胜。Input输入包含多组测试样例。每组...
2019-05-15 09:33:05
222
转载 树上点分治详解
本蒟蒻想要给大家写一篇尽可能详细的树上点分治的文章，以便刚入门的各位能够理解树上点分治，就不用像我一样在网上看了十几篇大佬的文章后还很蒙逼了（我太菜了QAQ），那么，我们就进入正题吧！ &nbs...
2019-05-12 19:00:55
429
原创 P3157 [CQOI2011]动态逆序对 三维偏序 CDQ分治
题目描述对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。输入输出格式输入格式：输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删...
2019-05-11 16:57:59
168
原创 P3810 三维偏序 cdq分治
题目背景https://www.luogu.org/problemnew/show/P3810这是一道模板题可以使用bitset，CDQ分治，K-DTree等方式解决。题目描述输入输出样例输入样例#1： 复制10 33 3 32 3 32 3 13 1 13 1 21 3 11 1 21 ...
2019-05-09 16:03:21
269
转载 CF1156D 0-1-Tree 换根DP
参考https://www.luogu.org/problemnew/solution/CF1156DD. 0-1-Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a...
2019-05-08 15:32:32
488
转载 Codeforces Round #554 (Div. 2) D Neko and Aki's Prank（记忆化DFS）
D. Neko and Aki's Pranktime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputNeko is playing with his toys on the backyard of Aki's hou...
2019-05-07 21:03:41
143
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人