熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

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

势能线段树、李超线段树专题（补来自专栏

下面是OI Wiki对吉司机线段树（势能线段树的一种）和李超线段树的详解：吉司机线段树李超线段树在信息学中，势能被用于计算某一个过程，或者某一类过程时间复杂度的总和。我们知道，线段树能够通过打标记实现区间修改的条件有两个：1.能够快速处理标记对区间询问结果的影响2.能够快速实现标记的合并但...

2021-09-04

0 1621

树状数组、线段树专题（待完善来自专栏

下面是OI Wiki对树状数组和线段树原理的详解：树状数组线段树动态 DPupd: 线段树非递归的单点写法：（需要维护每个元素所在的叶结点的位置） int mp[N];//a[i]放在哪个叶结点 void build(int u,int l,int r){ tree[u].l=l,tr...

2021-08-27

0 1000

前缀和专题(C学完多项式后补代码来自专栏

前言: 之前对前缀和的了解仅仅局限与一维前缀和、二维前缀和以及前缀和的变形如前缀积、前缀异或。经过zngg的讲解后，才发现我对前缀和的了解远远不够。很喜欢智乃上课讲过的一句话：“不能把前缀和仅仅看作是前缀和，而是看成一种思想。” OI Wiki对于前缀和的详解：https://oi-wiki.or...

2021-08-17

3 1050

逆序对

做法任意交换两个数后，逆序对数的奇偶性改变先求出原始序列的逆序对数的奇偶性(可以通过归并排序或者树状数组的方法求逆序对数) 对于操作1==>交换1次(l与r不相等)对于操作2==>对半交换对于操作3==>依次向左（或向右）逐位交换代码 #include <iostr...

2021-06-05

0 739

最短路

做法：把二进制中的每一位看作是一个点，改位为1就建立长度为的边跑dij即可代码 // Problem: 最短路 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11233/D // Memory Limit: 52...

2021-06-05

2 750

Rating

做法每次用最小的号来上分掉分即可用优先队列或者multiset维护当前最小的号即可代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(a...

2021-06-05

1 722

子序列

做法对于寻找一个"aab"的子序列只要枚举“b”，并在'b'之前的'a'中取两个就能求出子序列的数量。因为可以在任意位置中插入一个字符。很容易想到最优的插法：1.在最前面插入'a';2.在最后面插入'b'在这两种方案中取到最大的一种即可注意：答案会爆long long 代码 ...

2021-06-05

1 726

平行四边形

做法根据平行四边形的判定条件：一组对边平行而相等然后套用几何板子就能解决问题代码 #include <bits/stdc++.h> using namespace std; const double eps=1e-8; const double PI=acos(-1.0); co...

2021-06-05

2 658

[CQOI2013]二进制A+B 来自专栏

做法：构造思路：说不明白，参考了别人的题解，给几组情况就能够理解明白了设x,y,z是a,b,c二进制中1的个数假设x>y 分类讨论 1) z=1 000001111111111011110000000001100000000000000 2) 1<z<y 00011111...

2021-05-09

0 873

奇怪的背包问题增加了来自专栏

做法先记录每种体积的背包数以及下标因为每两个体积为的背包能合成一个体积为的背包所以我们只需要把背包从小到大开始合并，判断体积为的背包数是否大于等于2个即可然后按照体积从大到小开始找背包，初始是需要2个体积为的背包，该层不满足则需要调到下一层，并且数量是当前的两倍代码 // Problem: 奇怪...

2021-05-07

2 807