cqbzzl-CSDN博客

原创 LuoguP3327 [SDOI2015]约数个数和

∑i=1n∑j=1md(ij)\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)i=1∑nj=1∑md(ij)∑i=1n∑j=1m∑x∣i∑y∣j[gcd(x,y)=1]\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[gcd(x,y)=1]i=1∑nj=1∑mx∣i∑y∣j∑[gcd(x,y)=1]∑i=1n∑j=1m∑x∣i∑y∣j∑d∣x,d∣yμ(d)\

2020-09-05 10:31:08 174

原创概率期望中高斯消元的几种用法

前置知识：高斯消元法博主理解浅显，只能膜piao别人的总结https://blog.csdn.net/u011815404/article/details/88890702咳咳……还是简单介绍两句它可以用 O(n3)O(n^3)O(n3) 的复杂度解出 n 元方程组表示方法：矩阵tips：一般情况下高斯消元可能出现无解、无穷解的情况，我的做法里面没有判断，由于矩阵对角线上不会出现0。...

2020-02-09 17:09:59 821

原创逆元详解

逆元作用模意义下的除法在大多数时候都不适用。当题目中要求对答案取模，但我们又不得不使用一般的除法的时候，就需要用逆元的乘法来代替除法。逆元定义在模意义下，a mod m的逆元（下文中用inv[a]代替）就是一个数inv[x]使得：inv[x] ≡ x-1 (mod m)那么除法就可以转换成：a / b = a * b-1 ≡ a * inv[b] (mod m)注意逆元是定义在x与...

2019-08-06 21:59:16 7213 1

转载 UVA10817 Headmaster's Headache

题目大意 m教师，n求职者，共同竞聘s门课程。要求：每门课程须有两名科任老师，教师必须聘用。解题思路直接给出状态转移方程，具体含义详见代码。 d[i][s1][s2] = min(d[i+1][s1’][s2’]+c[i], d[i+1][s1][s2]); The headmaster of Spring Field School is considering emplo...

2018-08-14 10:45:27 209

原创【DP】UVA1347-Tour

这道题十分美妙啊，刚开始完全没看出是DP。题目描述UVA1347 总之呢，讲的就是一个有强迫症的飞行员在一个景区游览完所有景点并成功返航的故事，他不仅非要从左往右（xl < xr）飞，因为穷还必须省油。。。飞到达最右边的景点后，他可以在返航时游览那些没有被游览的景点。问他最少飞多远。他刚开始在最左边的景点，输入保证x为升序排列。输入样式n x1 y1 x...

2018-08-10 07:53:52 247

原创 [树链剖分]Query On Tree IV

题意理解给出一颗含有n个结点(全为白点)的含有边权（可为负）的树，询问q次，有两种操作类型： C x ：将结点x反色（白->黑 or 黑->白） A ：询问图中路径边权和最大的两个白点的路径边权和（此后用“距离”代替）本题难点注意不要把线段树和原树和在一起理解 C x 操作使问题动态，需要维护，增加复杂度。 A操作没有固定询问关于某一个结点的距离，可能...

2018-08-02 19:10:47 337 4

原创 Polycarp's Practice

Polycarp’s Practice题目大意：给定一个长度为n的数列，将它分成k段（不改变原序）。求一种分法，使得每段中的最大值之和最大。（分法的描述形式为每段长度） Special Judge输入格式：n k a1 a2 a3 … an输出格式：maxsum t1 t2 t3 … tk样例输入输出：Input1:8 3 5 4 2 6...

2018-07-22 18:52:53 337

原创 Median on Segments (Permutations Edition)

Median on Segments (Permutations Edition)题目大意：给定一个长度为n的数列{p1,p2,…,pn}∈{1,2,…,0}。求满足中位数为m的闭区间[l,r]的个数。输入格式：n m p1 p2 p3 … pn输出格式：count样例输入输出：Input1:5 4 2 4 5 3 1Output1:4...

2018-07-22 18:52:14 327

原创割点与割边

◇◆◇概念◇◆◇联通块：任意两个点之间存在至少一条路径可以到达对方的一个点集。说白了就是某一块里面的点是连起来的。割边：割掉某一条边能使整个图分为两个联通块的边，又称关键边（桥）。割点：割掉某一个点（这意味着失去所有连向这个点的边）使整个图分为两个联通块的点。◇◆◇目标◇◆◇ 找出一个无向图中的割点、割边◇◆◇怎么找◇◆◇ 先在这里插入两个概念。在我们DFS的时候，...

2018-03-24 17:08:01 1013

原创 NOIP2017总结——过眼云烟皆不顾

时光易逝，风雨兼程。 NOIP来得很快，如一场战争般划过我的生活但很不幸，还是跪了……既然 * 了，总是有原因的，也避免后来再次发生这样的错误，就记录下原因吧！总结1.对代码实现能力不够——体现（记忆化搜索、广搜、DP）2.对基础知识掌握不够——体现（函数、头文件、freopen写错）3.写代码速度比较欠缺——体现（刷题量少、做题慢）反思1.可以刷一些代表性的题目2.可以把原来做过的基础题多背

2017-11-23 14:07:51 237

原创 NOIP2017——真题总结

NOIP来了又去了于是他留下了四道题……（你以为我要抒情？）1.成绩(score) 题目描述牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩 = 作业成绩× 20% + 小测成绩× 30% + 期末考试成绩× 50% 牛牛想知道，这门课程自己最终能得到多少分。输入只有1 行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。

2017-11-23 14:05:20 2776

原创 c++动态规划基础——最长上升子序列

这次博主带来的是动态规划的一道基础题——最长上升子序列希望可以对比较迷茫的小伙伴带来帮助！以下为题目最长上升子序列：描述一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。

2017-09-29 14:04:34 5806 1

原创做题笔记——“动态规划”：子集的和

经过了许久的学习，就应该将所学沉淀下来。那么今天小编记录的，是一道挺有趣的编程题——挖地雷。这道题有着多种解法，可以用动态规划（DP），搜索等算法解决。这次我做的是新学的动态规划的挖地雷……如果大家实在想要看更多的做法，请在评论里提出建议o~但在做题之前，我还是想要吐槽几句：“为啥要在地窖里埋雷啊？”“为啥俺要去挖雷啊？”“我是不是每到一个地窖，就要玩一次‘扫雷

2017-08-26 09:11:58 2142

原创贪心算法——删数问题

已经很久没有和大家见面了！今天给大家带来的是贪心算法中的一类问题——删数问题。那么首先我们要了解：贪心算法是什么？？？所谓贪心算法，当然是很贪心的算法。就是鼠目寸光地从局部看全局，首先得到局部的最优解，从而推导出全局的最优解。但是这种算法有时候并不适用，乱用会导致进入误区。例如这一道题：在一个长n宽m的矩形中，有n*m数，若要从左下角走到右上角，且只能向右或向上走，问经过的数字之和最

2017-08-18 14:00:00 31337 7

原创 sort函数的点点滴滴

大家好！今天小编要给大家带来的是有关于sort的c++介绍~ sort是一种排序，可以在头文件中调用形式如：sort（a+0,a+10）;a属于整型数组；意思是在a[0]~a[9]间从小到大排序需要注意的是sort(a+0,a+n)排的是a[0]~a[n-1] 2. sort也可以自定义，只要这样： sort（a+0，a+n, comp）;这里的“comp”可以是任意的一个

2017-05-20 17:45:25 287

原创 c++版高精度加法

大家好！今天给大家带来的是有关于高精度加法的模板希望可以给大家带来帮助#include基本输入输出库#include由于我们的高精度数很长所以要用到关于字符数组的头文件int a[203],b[203],c[203];char a1[203],b1[203];用字符数组输入用整型数组存储、计算、输出int main(){int lena,lenb,le

2017-05-18 14:05:20 497

Locke的博客