- 博客(75)
- 收藏
- 关注
RSS订阅原创 在树状数组上倍增（广东省赛2023）
假设从x出发，以找区间的左端点l为例。那么我们可以提前计算出在前x个位置颜色集合中颜色出现的总次数（如果为x则l肯定为1），然后直接减去color数组中nxt位置的贡献（因为nxt中未计算的部分一定为2的幂次处的贡献），就可以计算出区间[nxt+1,x]中出现的颜色次数。根据上面的描述，最后的结果l’应该是最靠近x的使得[l’+1,x]中出现的颜色次数比区间长度小的点，所以真正的l应该是l’+2。对于询问，本质上就是要找到一个尽量长的包含x的区间，使得区间中出现的目标颜色总次数与区间长度相等。
2023-06-30 23:02:43
146
原创 计统大作业
P2P过程：程序员写好代码hello.c（Program）后由编译器驱动程序GCC进行进行处理。在程序员于终端中输入gcc -m64 -Og -no-pie -fno-PIC hello.c -o hello之后，GCC读取hello.c,按以下四个步骤得到可执行目标文件hello。1、预处理。GCC调用预处理器cpp。它会根据以字符#开头的命令修改hello.c，得到处理后的程序文本hello.i。2、编译。GCC调用编译器cc1。它会将hello.i翻译成文本文件hello.s。
2023-05-28 15:56:21
1031
原创 【Codeforces 1367F】 Flying Sort (Hard Version)
注意到给定的序列中一定有一个子序列是最后不降序列的一部分。所以，如果我们能确定这个部分，就可以比较轻松地解决这个问题。所以原问题转化为：求原序列与所得的最长公共子序列。每次操作可将任意一个数字移动至序列最开始或最末尾。求使得序列不降所需的最少操作次数。存在的目的是保证求得的最长公共子序列满足中间那一段的性质。为以i为结尾的最长公共子序列长度，为至今为止i出现的次数，则。为以i为结尾的包含第一个。的最长公共子序列长度。给定一个正整数序列（
2022-09-28 22:25:41
304
原创 【20191102】考试
T1 最大K段和考场上想了一个贪心：处理出所有仅含正数的极大区间。如果区间数量≤m\leq m≤m，直接把所有正数的和输出即可。否则，我们选取前mmm大区间，进行以下操作使结果最大化：· 合并两个已选区间，尝试选取更多未选区间· 合并一个已选区间和一个未选区间实现比较繁琐，敬请参考代码：#include<bits/stdc++.h>#define ll long long...
2019-11-02 23:03:42
214
原创 【学习笔记】动态DP
引子如果把修改扔开，这就是一道十分经典的树形DP入门题。然而加上修改，这道题瞬间毒瘤了起来。先把转移方程摆在下面：f[i][0]=∑j∈sonmax(f[j][0],f[j][1])f[i][1]=∑j∈sonf[j][0]+w[i]f[i][0]=\sum_{j \in son}max(f[j][0],f[j][1]) \\f[i][1]=\sum_{j \in son} f[j]...
2019-10-29 13:14:06
198
原创 【Codeforces 364E】Empty Rectangle
给一个n∗mn*mn∗m的01矩阵，求其中恰含KKK个1的子矩阵的方案数。1≤n,m≤2500,0≤K≤61\leq n,m \leq 2500, 0 \leq K \leq 61≤n,m≤2500,0≤K≤6做这个题时完全没有往分治的方向想。面对这种矩阵的分治，不妨像K-D Tree那样行列交替切割。边界条件很容易确定。这样一来，恰位于两半边的子矩阵全部处理完毕，考虑处理跨过切割线的子...
2019-10-27 22:25:53
358
原创 【Codeforces 364D】Ghd
给你nnn个数，求一个尽量大的数，使得数列中有超过n2\frac{n}{2}2n个数能被该数整除。数ai≤1012a_i \leq 10^{12}ai≤1012发现每一个数出现在能被整除的集合中的概率均≥12≥\frac{1}{2}≥21，于是考虑随机。每一次猜测一个数在这个集合中，然后计算与其它数的gcd。最后查找一个最大的出现次数超过n2\frac{n}{2}2n的gcd即可。（...
2019-10-27 21:57:00
168
原创 【20191025】考试
T1 嘟嘟噜经典的约瑟夫问题。虽然这个题暴力一分不给。不难发现第一个被处决的人的编号是m mod n−1m\ mod \ n-1m mod n−1。那么，如果我们把下一个人的编号看做000，其他人的编号为前一个人+1+1+1，这个问题的规模就被缩小了。我们画个表：mmod n0mmod n+11......mmod n−2n−2\begi...
2019-10-25 17:18:28
172
原创 【学习笔记】立体计算几何
【基本知识】向量运算：模长：len=x2+y2+z2len=\sqrt{x^2+y^2+z^2}len=x2+y2+z2加减：对应坐标加减，结果为一个向量；点积：依旧定义为a⃗\vec{a}a到b⃗\vec{b}b的投影，计算方式为将对应坐标相乘后相加，结果为一个值。如(x1,y1,z1)⋅(x2,y2,z2)=x1x2+y1y2+z1z2(x_1,y_1,z_1) \cdot(x_2...
2019-10-22 22:02:23
219
原创 【BZOJ 1179&luoguP3627】ATM&劫掠计划
Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆...
2019-10-21 17:05:05
131
原创 【BZOJ 2721】
通分：xyx+y=n!\frac{xy}{x+y}=n!x+yxy=n!移项并打开括号：xy=n!x+n!yxy=n!x+n!yxy=n!x+n!y合并同类项：(y−n!)x=n!y⟹x=n!yy−n!(y-n!)x=n!y \quad \Longrightarrow \quad x=\frac{n!y}{y-n!}(y−n!)x=n!y⟹x=y−n!n!y令t=y−n!t=y...
2019-10-20 22:29:41
185
原创 【学习笔记】Miller-Rabin素性测试与Pollard-Rho大数分解
【BZOJ 3667】第一行：CAS,代表数据组数（不大于350），以下CAS行，每行一个数字，保证在64位长整形范围内，并且没有负数。你需要对于每个数字：第一，检验是否是质数，是质数就输出Prime第二，如果不是质数，输出它最大的质因子是哪个。检验一个数是否是质数的朴素方法是O(n)O(\sqrt{n})O(n)的，并不能满足这道题的需求。其实直到现在，人们对一个数的素性判定依旧没...
2019-10-20 17:28:07
397
3
原创 【并查集】银河英雄传说
题目描述公元5801年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。宇宙历799年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域...
2019-10-18 20:23:39
489
原创 【学习笔记】拉格朗日插值法
已知这样一个方程。{f(1)=y1f(2)=y2f(3)=y3⋯f(n)=yn\left \{ \begin{array}{c}f(1)= \large y_1 \\f(2)= \large y_2 \\f(3)= \large y_3 \\\cdots \\f(n)= \large y_n\end{array}\right.⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧f(1)=y1f(2)=y2...
2019-10-18 19:55:58
260
原创 【BZOJ 2301】problem b
【题目描述】对于给出的nnn个询问，每次求有多少个数对(x,y)(x,y)(x,y)，满足a≤x≤b，c≤y≤da≤x≤b，c≤y≤da≤x≤b，c≤y≤d，且gcd(x,y)=kgcd(x,y) = kgcd(x,y)=k.【分析】记f(a,b)=∑i=1a∑j=1b[gcd(i,j)=k]f(a, b)=\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=k]f(a,b...
2019-10-18 15:29:04
185
原创 【学习笔记】LaTeX
\newline\newline\newline\newline\newline\newline快来康康这个julao的博客！
2019-10-17 16:15:04
140
原创 【BZOJ 3884】上帝与集合的正确用法（新知识）
【题目描述】根据一些书上的记载，上帝的一次失败的创世经历是这样的：第一天， 上帝创造了一个世界的基本元素，称做“元”。第二天， 上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。第三天， 上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。第四天， 上帝创造了新的元素“γ”，“γ”被定...
2019-10-17 16:11:31
176
原创 【数据结构】 配对堆&BZOJ 3040
【引子】（BZOJ3040）有一个m边有向图，节点从1~n编号，求从1到n的最短路。n≤106,m≤107n \leq 10^6,m \leq 10^7n≤106,m≤107显然是一个dijkstra+堆优化的板题。然而一般的堆会被卡空间。所以我们需要一个更高效的堆。网上找了半天，可选的数据结构好像只有斐波那契堆和配对堆。然而前者好难写啊ε=(´ο｀*)))唉。接下来介绍一下配...
2019-10-13 21:30:43
295
2
原创 【BZOJ 4892】DNA
又一个DNA【题意】加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列S，有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列S，任意修改其中不超过3个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在DNA链S0上的位置。所以你需要统计在一个表现出吃藕性状的人的DNA序列S0上，有多少个连续子 串可能是该基因，即有多少个S0的连续子串修改小于等于三个字母...
2019-10-07 21:51:56
215
原创 【20190915】多校联考
T1【题目描述】Akari 的学校的校门前生长着一排 n 棵树，从西向东依次编号为 1 ∼ n。相邻两棵树间的距离 都是 1。 Akari 上课的教学楼恰好在树 1 旁，所以每个课间，Akari 都很想走出教室，上树活动。Akari 会依次经过 m 棵树，从树 1 一路向东跳到树 n。临近上课时，Akari 会再次上树，经过 m 棵树从树 n 一路向西跳到树 1 ，准备上课。由于 Akari ...
2019-09-16 17:47:40
386
原创 BZOJ2456 mode
【题意】给一个含n个数的数列（n≤5∗105n \leq 5 * 10^5n≤5∗105），求这个数列的众数（出现次数大于n/2，保证有解）。【分析】光看题面很简单的吧？很简单的吧？简单的吧？单的吧？的吧？吧？巴？？？啥？内存2M？您没事了既然是要找众数，那么就应该想办法让它被其它的数抵消掉。所以用两个变量：sum用来表示当前的这个数被其它数抵消后还剩几个，另一个a用来存...
2019-09-14 22:25:25
146
原创 【20190907】七校联考
T1#include<bits/stdc++.h>#define ll long longusing namespace std;const int mn = 100005;bool vis[mn];int sum, a[mn];ll f[mn];int main(){ freopen("plus.in", "r", stdin); freopen("...
2019-09-07 23:08:53
334
原创 Codeforces 739B Alyona and a tree（树上差分）
【题意】nnn个节点的树，每个节点、每条边有权值，定义dist(u,v)dist(u,v)dist(u,v)为路径<u,v><u,v><u,v>的边权和。如果uuu在子树vvv内且dist(u,v)≤val[u]dist(u,v) \leq val[u]dist(u,v)≤val[u]，则称vvv控制uuu。问每个节点控制多少个...
2019-08-30 11:54:38
254
原创 【SCOI2007】修车
【题意】同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。【分析】...
2019-04-21 12:52:37
161
原创 扩展BSGS算法
先来康康这个问题。给定三个正整数A,B,PA,B,PA,B,P，求关于xxx的方程的最小正整数解：Ax≡B(mod P)A^x\equiv B(mod\ P)Ax≡B(mod P)我们令x=a⌈P⌉−b,a∈N,b∈Nx=a\lceil \sqrt{P}\rceil-b,a \in N,b \in Nx=a⌈P⌉−b,a∈N,b∈N由欧拉定理：Aϕ(P)≡1(mod...
2019-03-30 23:51:22
538
2
原创 树状数组的区间修改与区间查询
【题意】【分析】学了带懒标记的线段树后，这就并不难了。#include<cstdio>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const int mn = 100005;struct seg{ int l, r; ll...
2019-03-09 11:00:45
820
2
原创 【BZOJ 1076】奖励关
【题意】你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。 宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。 获取...
2019-02-24 21:00:28
310
原创 【BZOJ3812】主旋律
【题意】【分析】这题真是毒瘤这道题要我们求这张图的强连通子图的数目。正面做有些困难，所以倒着做。首先我们知道一个图如果不是强连通，则对它进行缩点后，一定会形成一个包含多个节点的DAG。于是，我们想到枚举强连通分量，缩成一个点后计算它们构成一个包含多个节点的DAG的方案数。所以，我们设f[S]表示缩点后的点集S构成包含多个节点的DAG的方案数。由于这样的DAG一定有若干个节点的出度为0，...
2019-02-23 00:51:07
278
原创 【BZOJ4145】The Prices
【题意】你要购买mmm种物品各一件，一共有nnn家商店，你到第i家商店的路费为d[i]d[i]d[i]，在第iii家商店购买第jjj种物品的费用为c[i][j]c[i][j]c[i][j]，求最小总费用。【题解】很容易想到状态转移方程。设f[i][S]f[i][S]f[i][S]为去了前iii家商店，已购买物品的集合为S，则：f[i][S]=min{f[i−1][S],f[i−1][S′]...
2019-02-22 23:24:54
227
原创 【bzoj4029】定价
【题意】在市场上有很多商品的定价类似于 999 元、4999 元、8999 元这样。它们和 1000 元、5000 元和 9000 元并没有什么本质区别，但是在心理学上会让人感觉便宜很多，因此也是商家常用的价格策略。不过在你看来，这种价格十分荒谬。于是你如此计算一个价格 p（p 为正整数）的荒谬程度：1、首先将 p 看做一个由数字组成的字符串（不带前导 0）；2、然后，如果 p 的最后一个字...
2019-02-20 21:03:42
333
原创 对状态转移方程的理解（【HNOI2013】游走&【hdu4035】Maze）
先来看一道例题：【HNOI2013】游走一个无向连通图，顶点从1编号到N，边从1编号到M。小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。【分析】设d[i]为走上i...
2019-02-19 23:35:27
495
原创 【hdu4352】XHXJ's LIS
【题意】将一个数x当成一个数串，对其做最长上升子序列。记结果为axa_xax。对一个区间[l,r][l,r][l,r]，求有多少个数xxx，使ax=ka_x=kax=k。【分析】先提一提LIS的O(nlogn)O(nlogn)O(nlogn)的做法：维护一个数列tail[i]tail[i]tail[i]，表示长度为i的LIS的最后一个元素最小的数。当新加入一个数a[i]a[i]a[i]...
2019-02-19 12:23:42
131
原创 计算几何大模板（持续更新）
计算几何说起来都是一套一套的，写起来却让人二楞二楞的qwq接下来直接粘代码，稍微高级的算法讲解详见超链接【基本的定义&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;算法】#include&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;cmath&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;const dou
2019-02-13 22:36:51
279
原创 【CF 70D】Professor's task
【题意】维护一个凸包，支持：1、向凸包内新加入一个点；2、询问某个点是否在当前凸包中。【题解】平时求凸包的时候，要用上极角排序。那么，就排序吧。然而，极点应该在哪里呢？考虑到开头保证能给出一个没有退化的三角形，那么，就用这个三角形的重心作为极点。为了避免精度误差，就不除以333了，改为将所有点的坐标乘333。由于不求面积什么的，所以后面的操作就跟未乘333的时候一样。接下来先想如...
2019-02-13 19:52:17
383
原创 【BZOJ1997】Planar
【题意】给定一个含哈密顿回路（回路将给出）的图。判断它是不是一个平面图。【分析】居然是2-SAT。由于有一个哈密顿回路，我们先不管其它不在回路上的边，把这幅图围成一个媛。接下来再考虑其它边。对于其中的任意两条边，如果它们不相交，则必定一个边在圆外，一个边在圆内。而圆外与圆内是一对相对的状态，又由于状态的选取受其它状态的限制，所以考虑用2-SAT。将每一个不在回路上的...
2019-02-11 13:34:43
397
2
原创 主席树
【问题引入】给定一个长度为n的数列，询问区间第k大的数。【分析】在正式介绍主席树之前，先来介绍一下“值域线段树”。为便于讲解，举个例子，对于下图的数列，我们可以对它构造这样的“值域线段树”：后面的数字表示数列在[l,r]中有多少个不同的数。有了这棵树，我们可以很方便地求出第k大的数。那么，怎么求区间第k大呢？我们建立n棵“值域线段树”。第i棵线段树表示[1,i]...
2019-02-06 22:14:16
130
原创 【poj2728】Desert King
【题意】给定一个含nnn个点，每个点的空间坐标已知，现将它们两两相连构成一个完全图。对每一条边(i,j)(i,j)(i,j)，规定：c[i][j]=∣z[i]−z[j]∣,d[i][j]=(x[i]−x[j])2+(y[i]−y[j])2c[i][j]=|z[i]-z[j]|,d[i][j]=\sqrt{(x[i]-x[j])^2+(y[i]-y[j])^2}c[i][j]=∣z[i]−z[j]...
2019-02-02 22:58:19
289
原创 【poj3613】Cow Relays
【题意】给定一个含T条边的无向图，求从s到e的恰好经过n条边的最短路（可以经过重复边）。【题解】我们先来回想一下floyd。它的本质实际上是DP。设f[k][i][j]f[k][i][j]f[k][i][j]为从i开始，经过1~k的某些点到达j的最短路的总权值，则：f[k][i][j]=min{f[k−1][i][k]+f[k−1][k][j]}f[k][i][j]=min\{f[k-...
2019-02-02 22:24:31
184
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人