- 博客(70)
- 收藏
- 关注
RSS订阅原创 牛客多校第九场部分题题解
中国剩余定理-循环节题目:The power of Fibonacci链接:https://ac.nowcoder.com/acm/contest/889/A大意:给定n<=1e9,m<=1e3求(∑i=0nFim)mod1e9(\sum_{i=0}^nF_i^m)mod 1e9(∑i=0nFim)mod1e9分析:有一个要注意的地方就是取模用的是1e9而不...
2020-01-12 12:45:25
213
原创 CF-round#599-1257
link: Educational Round 76E: The Contest重要的是要沉得下去，把ans分解，然后找出与R无关的部分固定，剩下来的有关的部分求一个maxF:Make Them Similar首先输入下来要先去重这题有两个思路:一个是暴力,O(2^32)次方，常数小点就能过，但一定要加蜜汁编译优化：#pragma optimization_level 3#pra...
2019-11-16 18:50:23
181
原创 字符串经典问题三解:后缀数组/后缀自动机/Hash
Kuangbin后缀数组专题:C - Distinct Substrings SPOJ - DISUBSTR本质不同子串的个数:后缀数组:ans=（∑i=2nn−sa[i]+1−height[i])+n−sa[1]+1（\sum_{i=2}^{n}n-sa[i]+1-height[i])+n-sa[1]+1（∑i=2nn−sa[i]+1−height[i])+n−sa[1]+1后缀自...
2019-11-12 20:05:03
215
原创 CF-round#599-1242
图论-BFS题目:0-1 MST链接:https://codeforces.com/contest/1242/problem/b大意:给你一张完全图,n<=1e5个结点,其中最多有m<=1e5条边权为1的边，剩余的边边权全为0分析:求无向补图最少构成几个连通分量:如果不是补图，那我们就直接BFS了，。。。。然而不是补图还是只能BFS,但BFS的方法要发生变化，原...
2019-11-07 19:06:31
142
原创 ACM-ICPC-2018Beijing虚拟赛后部分题题解
B.模拟题目:Heshen’s Account Book链接:https://vjudge.net/problem/2026237/origin大意:就是一个字符串模拟分析:麻烦的是理解题意和排坑，这里学到一个好的代码的写法，就如果字符串要设计行之间的拼接，就将字符串全部读取到一个一维的字符数组中，最后进行字符数组的区块划分。#include<bits/stdc...
2019-10-08 17:09:12
179
原创 牛客多校第七场部分题题解
B.线性基的交题目:xor链接:https://ac.nowcoder.com/acm/contest/884/B大意:n(5000)个int的集合,每个集合最大32,m(5000)个询问[l,r],val,问[l,r]内的每个集合是不是每一个都能用线性基表示出val分析:首先要补个板子，板子是线性基求交。其次，用线段树，用线段树的时候有个要注意的地方,因为我刚开始想的就是...
2019-10-07 17:15:52
223
原创 牛客多校第五场部分题题解
E.矩阵快速幂-十进制题目:generator 1链接:https://ac.nowcoder.com/acm/contest/885/B大意:告诉你x0,x1,a,b,且xi=a∗xi−1+b∗xi−2,n∈[1,10106],mod,让你求出an%modx_0,x_1,a,b,且x_i=a*x_{i-1}+b*x_{i-2},n∈[1,10^{10^6}],mod,让你求出a...
2019-09-24 12:03:36
180
原创 牛客多校第六场部分题题解
E.回文自动机上dfs题目:Palindrome Mouse链接:https://ac.nowcoder.com/acm/contest/886/C大意:给你一个1e5的串,要求串的回文子串A是回文子串B的子串,求(A,B)串对的个数分析:首先是跑一段回文自动机了然后遍历回文自动机中的串,加上该串的子串个数。回文自动机的fail和ch两种指针是分别够成两棵树的。在回文树中,...
2019-09-15 10:20:58
195
4原创 牛客多校第八场部分题题解
C.构造题目:CDMA链接:https://ac.nowcoder.com/acm/contest/888/C大意:给你一个k([1,10]),让你输出一个 2k∗2k2^{k}*2^{k}2k∗2k的由1,-1组成的矩阵,使得矩阵的每一行的∑j=12kai1j∗ai2j=0\sum \limits_{j=1}^{2^k}a_{i_1j}*a_{i_2j}=0j=1∑2kai1...
2019-08-11 16:33:38
252
原创 牛客多校第四场题解
A. 换根DP题目: meeting链接:https://ac.nowcoder.com/acm/contest/884/A大意:从一棵树(n=1e5)上,选一个点,使这个点到其他点的距离的最大值最小分析:2种做法:树形dp,暴力dp,换根dp这个做法大家都能想到就是不好写,换根dp写起来太麻烦了,所以后来我弄了个换根dp的板子,因为在dp的时候更新信息其实都是一...
2019-08-11 14:37:33
227
原创 牛客多校第三场
1.思想: 指数循环节-欧拉函数的性质-数论题目:Graph Games链接:https://ac.nowcoder.com/acm/contest/883/D大意:求有多少个(i,j)满足i∈[1,n],j∈[1,m](n∈[1,1e9],m∈[1,1e9]),A(i^j)=0modp(p是质数,p∈[1,1e9]),其中A(x)表示一个十进制数字，由x个'1'组成分析...
2019-07-26 16:25:37
119
原创 牛客多校第二场
A:暴力打表找规律概率问题总是会遇到状态的概率相互依赖的,如:dp[i]=Kj * dp[j]+balabala dp[j]= Ki *dp[i]+balabala暴力都不好暴力怎么打表?这次问了蓝心老师这种问题怎么搞，原来说是可以撒点.撒点？好像有道理，这好像是一种打表找概率的一个不错的方法。特别是在随机决策的时候https://ac.nowcoder.com/acm/con...
2019-07-23 13:08:58
205
原创 dp-线段树进阶-几何转dp-点集划分
https://ac.nowcoder.com/acm/contest/881/I大意:给n(1e5)个点给定每个点的x坐标,y坐标,a属性,b属性，求:让你将所有点划分到2个点集A,B(其中一个可以为空),划分要求为:不存在点C∈A,点D∈B,xC>=xD&&yC<=yD,划分的权值为A内所有点的a属性和B内所有点的b属性之和分析:这他喵?????怎么...
2019-07-23 11:08:32
164
原创 dp-缩小维度-限制条件-牛客多校第一场-ABBA
https://ac.nowcoder.com/acm/contest/881/E题目大意:让你构造一个字符串(长度2n+2m,全部由'A'和’B'构成),字符串可以拆分为n个"AB"串,m个"BA"串，问这样的串有多少种.比赛的时候完全没想到怎么搞，只想到可以用想类似括号序列的方法:每个A代表1,B代表-1,于是一个AB串就具有一个前缀和dp[i]代表串的前缀和为i的方法...
2019-07-21 11:25:33
132
原创 贪心-牛客多校第一场
https://ac.nowcoder.com/acm/contest/881/C貌似只把问题带到了数列上就会变简单一点？？？？先把原题读一遍，再看下面的解释有一个长度为n(1e4)的序列a:每个元素的范围是[1,1e3]你需要构造一个序列b:b中的每个元素要大于等于0，sum：b[1,n]要等于m求min于是，类似于你可以花费b[i]的和来减少某个a[i]的...
2019-07-21 10:17:01
91
原创 单调栈-笛卡尔树-序列-2019牛客多校第一场A
https://ac.nowcoder.com/acm/contest/881/A题意:给定两个长度为n(1e5)的排列a,b,求最大的m使a,b的前缀[1,m]的所有子区间的最小值的下标相同分析:对a,b来说，每个区间都对应着一个确定的下标，相反地，每个下标都对应着一些区间，这些区间是可以求出来的,利用单调栈求出min(le),max(ri)使 a[le,ri]>=a[i]...
2019-07-21 10:08:40
146
原创 寻找解题方向-猜系数-配凑法-2019牛客暑假多校第一场
首先给个D神的博客的传送门:https://www.cnblogs.com/Dillonh/p/11209476.html题目链接:https://ac.nowcoder.com/acm/contest/881/B(背景好评!)这题呢:我想了想，我里出题还有2点差距:1.要相信题都是可解的:"这TM不是废话吗，但是我太菜了我不会呀！我我咋知道怎么写"看到这个第一点，不用说是这个...
2019-07-18 20:45:37
110
原创 最小树形图-hdu4966
https://vjudge.net/contest/311526#problem/G大意:给定n(50)门属性，每门属性有a[i](500)个级别,同时有M(2000)门课程,参加j号课程需要c属性达到d,这样就可以把你的e属性提升成f,同时花费g元钱,问要把属性升满要多少钱分析:第一眼看到这题，有种网络流的感觉，于是欻欻欻开始写，还好隔壁xmk大佬的提示“你可以试试网络，流，然...
2019-07-18 09:16:55
87
原创 暴力-n*sqrt(n)
https://vjudge.net/contest/311526#problem/B其实题目很简单，给一个数列a,求每一个元素它左右两边最近的j使a[j]是a[i]的倍数,怎么说呢,暴力,完了因为n∈[1,1e5],a[i]∈[1,1e5]最后这样做复杂度就是n*sqrt(n)写这篇博客是因为我不够自信，总是觉得这样的复杂度过不了，然而其实是过的了的说不定我应该更加莽才对...
2019-07-18 09:07:42
288
原创 Colorful Tree-树形dp-树上连通块-树上路径统计
http://acm.hdu.edu.cn/showproblem.php?pid=6035题意:有n(2e5)个结点的一棵树，每一个结点上都有一个颜色c[i],设一条路径的value为这天路径上点的颜色的种类数，求树上所有路径的value和。分析:树上所有路径，那显而易见是要算贡献的，那怎么算每个颜色/每个点对ans的贡献呢？首先看，要算每个点对ans的贡献和很难算的,因为路径上...
2019-07-15 23:20:11
1120
原创 区间dp-拓扑排序种类数
https://vjudge.net/contest/311202#problem/L之前在CF上做过类似的题，所以这次就被这种思维带过去了后来看题解知道这题可以用到区间dp一个排列，对每个元素给定le[i]和ri[i],表示[le[i],ri[i]]内的元素都大于等于p[i],而le[i]-1和ri[i]+1的元素都小于p[i]这有点像之前的CF上的线段树的题，但是可以用到区...
2019-07-15 16:09:58
285
原创 贪心-暴力-CF
https://codeforces.com/contest/1190/problem/C题目不长一种思想:因为可以模仿对手的行为，如果如果之前对手走了一步，自己可以不动所以如果不是第一走的，那就肯定不会输所以对于先手者，有几种情况1.可一步到位，那就直接赢了2.不可一步到位，这种情况下再看后手者，如果他不可以一步到位，那他肯定不会输，因为他可以模仿，但是无论他怎么...
2019-07-14 11:29:47
205
原创 HDU-6222 2017长春 找规律
设t=2*k发现S=t*sqrt(3*k*k-3)打表,得到数列(前4项为2,4,14,52)，我和cyy找了半天一直找出来，最后当等比数列算的，居然过了然后写下我对找规律类题目的看法这类规律有哪些(我现在遇到了哪些)A.多项式:这个应该不用说了，其实大家都很熟悉就是f(n)是关于n的一个多项式，一般这种问题的多项式次数不会超过4,因为次数太高就不好出题了，为了鉴定一个通项公式是一...
2019-07-11 22:28:23
113
原创 ZOJ-1309-圆的切线
题意:给一个点，多个圆，求多个圆在某条直线上的投影的并典型的求切线的题目旋转向量法:求出切线向量在坐标轴中的角A(三角函数求)再算出切线与中心连线之间的夹角B,两个切线的角就是A+B和A-B但是呵，几何题我遇到了如下坑点:1.用反三角函数求角度，要用asin或者acos，用这两个就能A，用atan就会WA2.这题最后算结果有两种做法,一种是乘tan，一种是除tan，...
2019-07-10 09:52:13
130
原创 hdu-4821 String
一道水题，做不出来是我菜了不熟悉字符串Hashhash主要有两个用处1.建立字符串到int的映射2.特异化(确定)一个字符串本题属于下一种https://vjudge.net/problem/HDU-4821写这篇主要是为了让自己记住教训附：代码/////////////////////////////////////////Info/////////////...
2019-07-01 14:43:56
259
原创 弱智-水题-排列-计算之道-撑起信息安全“保护伞”
知识点:1.关于排列的知识:一个排列的下一个排列:类似与数字，在最右边加一，然后在变动位置的右边尽量小上一个:在最右边减一，然后在变动位置的右边尽量大2.next_permutation,prev_permutation的方法跑得很快，求上一个或者下一个排列的时候可以暴力3.可以暴力的时候就一定要暴力，暴力安全多了题目:给定一个括号序列，求比它字典序和刚好大1或小1的...
2019-06-19 14:16:43
102
原创 计蒜客-星云系统--贪心--字典序
额额额额额额我怎么这么菜呀!居然爆零了https://nanti.jisuanke.com/t/39614给定一个字符串s长度5e6,求它的 最小字典序 定长k([1,|s|])子序列妈呀...这是啥呀，我TM只求过最长上升子序列，这个不好搞呀，1.刚开始想着弄个堆维护所有可选择的点,然而O(nlogn)爆炸了,,,,隔壁老王玄学常数优化，过了,扎心2.优化下...
2019-06-18 15:00:57
171
原创 1028D - set与lower_bound的食用方法
https://codeforces.com/contest/1028/problem/D这里先讲2个知识点吧:1.set,map都有序容器自定义结构体的方法:‘ 方法1:struct node { int a, b; bool operator<(node c)const { if(a!=c.a)return a<c.a; ...
2019-06-14 21:14:23
217
原创 奇妙的倍增法
写这篇博客是因为做某一题的时候用到了倍增法，发现了倍增法的强大之处。https://www.lydsy.com/JudgeOnline/problem.php?id=4568意思不麻烦，2e4个点有点权，组成一棵树，2e5个询问，问u到v路径上的点组成的线性基可获得的最大元素是什么。我用倍增法做得，后来想想树链剖分+线段树应该也可以谈到倍增法的好处，就是它:记录(建树)是...
2019-05-26 09:13:58
207
原创 ACM特定算法的卡常优化
今天做一道树链剖分的题目，发现被卡常了，于是修改了很久，打印出运行时间，发现有这3个地方对常数的影响特比大1. I/O: 用输入外挂所消耗的时间大概是用关同步+tie的cin的一半 测试:输入了1e5*3的数据,cin用了0.2s,IN用了0.1s2. vector[]/链式前向星 不得不说cache友好真...
2019-05-21 19:31:17
611
原创 三分与精度问题
今天想到做一点三分的简单题，就看到了这个:https://vjudge.net/problem/HDU-3400于是去做这个三分套三分的题,但是不知道为什么，总是WA，然后对拍，发现是哪里存在精度问题，找半天没找出来最后对比我和AC的代码，发现了这个地方我的:double dis(PDD A, PDD B){ return sqrt(pf(A.x - B.x) + pf(A....
2019-05-20 08:35:22
198
原创 线段树-扫描线
作用: 1.计算若干个矩形覆盖的面积 2.普通的线段树区间更新，查询可以将某一段的每个点的权都当成1查询 3.麻烦，不懂了，之后再更新板板: //6_5-线段树(扫描线)//////////////int n;typedef double tp;tp xs[maxn * 2];//记录x坐标int num_x;...
2019-05-08 16:28:54
88
转载 【题解】 AtCoder ARC 076 F - Exhausted? （霍尔定理+线段树）
【题解】 AtCoder ARC 076 F - Exhausted? （霍尔定理+线段树）其他·发表2018-08-23r+ uil mat amp con pan com cnblogs 找出最大值题面题目大意:给你\(m\)张椅子，排成一行，告诉你\(n\)个人，每个人可以坐的座位为\([1,l]\bigcup[r,m]\)，为了让所有人坐下，问至少还要加多...
2019-05-07 23:32:01
202
转载 倍增法思想[转载]
白话讲解：转载原地址【序言】 我认为吧，所有能够优化复杂度的算法都是神奇的，所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西，所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER，我非常讨厌在看别人的算法解析时整版的i，j，k等我看到鼠标就惯性移到右上角的符号语言，所以我想用最...
2019-04-22 19:16:50
181
原创 学习倍增法得到的启示 - LCA倍增法学习
学习了神牛键盘艺术家写的博客:https://blog.csdn.net/lw277232240/article/details/72870644后，看到大神说有很多类似的数组想到的确，树这玩意也可以不是树，就是拼接起来的链，数组因为有树链剖分这样的东西，树上路径的复杂度可以降到nlog2n,有了倍增法，对于树的向上求解貌似也可以降低到O(logn),他提到的思想，就是在树的向上的...
2019-04-21 21:24:34
138
原创 简单DP 华科十五届 J
https://ac.nowcoder.com/acm/contest/560/K难道我连DP怎么写都忘了???看代码吧//Problem://Date://Skill://Bug://///////////////////////////////////////Definations//////////////////////////////////////////////...
2019-04-18 20:26:21
87
原创 功能最全带正负,代码简洁150行的---ACM大数四则运算模板
BigNum类封装了所有的功能:包括输入intput(),输出prin(),还有+-*/,其中的+-*/还涵盖了左操作数和右操作数正负与大小的所有情况另外还附带封装了两个数字之间进行比较的辅助函数里面包含了2个宏定义,RE表示循环和PB表示push_back求赞,希望转载要带原地址#include<iostream>#include<vec...
2019-04-14 20:30:20
246
原创 1153C 括号序列
https://codeforces.com/contest/1153/problem/C题目大意:给出1个带有'(',')','?'三种字符的序列，可以将?转换为)或(若存在转换后的护法序列为'(xxxxxx)'则打印，不存在则输出':('思路:学到了一个思路把'('转换为+1,')'转换为-1,对于一个合法序列[1,n]，任意前缀和[1,i]>=0,i∈[1,i...
2019-04-14 14:00:57
265
原创 940E 利用不是更糟糕的情况简化情形
https://codeforces.com/problemset/problem/940/E题目大意:给你一个长度n(n<=1e5)的数组a(1<=ai<=1e9)和一个值c([1,1e5])定义一个子数组[le,ri]的权值大小为sum[le,ri]减去[le,ri]中最小的(ri-le+1)/c个数的和问将数组分为子数组，使得所有子数组的权值和最小。分析:...
2019-04-11 08:25:57
65
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人