- 博客(58)
- 收藏
- 关注
RSS订阅
原创 「NOIP2016」蚯蚓
description传送门solution因为每次蚯蚓长度的变化是对除去剪断的蚯蚓外，所有蚯蚓同时变化的，所以容易想到用一个大根堆维护所有蚯蚓的长度，并使用一个变量deldeldel维护蚯蚓长度的变化，每次操作时取出堆顶蚯蚓长度xxx，得到该蚯蚓的真实长度x=x+delx=x+delx=x+del，再将⌊px⌋−del−q\lfloor px \rfloor-del-q⌊px⌋−del−q与x−⌊px⌋−del−qx-\lfloor px \rfloor-del-qx−⌊px⌋−del−q插入
2020-10-08 17:08:23
211
原创 LOJ#539. 「LibreOJ NOIP Round #1」旅游路线
description题面较长，这里给出题目链接solution考虑预处理出f[i][j]f[i][j]f[i][j]表示在第iii个点加满油后，从第iii个点出发，至多消耗jjj元钱走过的最大路程，那么对于每一个询问就可以二分答案O(logq)O(logq)O(logq)查询了可以得出转移方程f[i][k]=max(f[j][k−p[j]]+g[i][j],f[i][k])f[i][k]=\max(f[j][k-p[j]]+g[i][j],f[i][k])f[i][k]=max(f[j][
2020-10-07 19:45:21
200
原创 LOJ#541. 「LibreOJ NOIP Round #1」七曜圣贤
description题面很长，这里给出题目链接solution用队列维护扔掉的红茶，同时若后扔出的红茶比先扔出的红茶编号更小，那么先扔出的红茶不可能成为答案，所以可以用单调队列维护故每次询问的答案只可能是单调队列的队首或者没有出现过的红茶中编号最小的，后者可以O(b)O(b)O(b)暴力计算code#include<bits/stdc++.h>using namespace std;namespace IO{ int c; unsigned int seed; u
2020-10-07 19:26:17
141
原创 LOJ#538. 「LibreOJ NOIP Round #1」数列递推
descriptionsosusosu 虐爆 OI 之后成为了一名文化课选手。一天，他做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：给定一个下标从000开始，无限长的整数列ai{a_{i}}ai，i∈Ni \in Ni∈N ，已知a0,a1a_{0},a_{1}a0,a1 的值，以及递推式ai+2=kai+1+aia_{i+2}=ka_{i+1}+a_{i}ai+2=kai+1+ai，i∈Ni \in Ni∈N ，k∈N+k \in N^+k∈N+。sosusosu 研
2020-10-07 17:32:36
285
原创 LOJ#537. 「LibreOJ NOIP Round #1」DNA 序列
descriptionNOIP 复赛之前，HSD 桑进行了一项研究，发现人某条染色体上的一段 DNA 序列中连续的kkk个碱基组成的碱基序列与做题的 AC 率有关！于是他想研究一下这种关系。现在给出一段 DNA 序列，请帮他求出这段 DNA 序列中所有连续 kkk个碱基形成的碱基序列中，出现最多的一种的出现次数。n≤5∗106,k≤10n\le5*10^6,k\le 10n≤5∗106,k≤10solution直接找出所有连续kkk个碱基形成的碱基序列的哈希值，哈希值求出每种哈希值出现的次数
2020-10-07 17:15:32
316
原创 【LOJ 3153】 「JOI Open 2019」三级跳
题面LOJ 3153solution对于任意一对A,BA,BA,B,若区间[A,B][A,B][A,B]中存在一个数权值大于AAA或BBB，则用这个数来替代AAA或BBB显然更优。故只需要考虑每一个区间的最大值与次大值分别作为A,BA,BA,B。可以用单调栈O(n)O(n)O(n)找到每一对这样的A,BA,BA,B。考虑f[i]f[i]f[i]表示以iii作为CCC时最大的A+B+CA+B+CA+B+C，对于每一对A,BA,BA,B，他们对应的CCC一定≥(2∗B−A)\ge (2*B-A)≥
2020-09-16 20:13:15
379
1
原创 【LOJ 6287】诗歌
题面Solution枚举中间点jjj，题目即求是否存在mmm使a[j]−ma[j]-ma[j]−m与a[j]+ma[j]+ma[j]+m分别在jjj两侧。对于jjj左侧任意一个点iii，都将t[a[i]]t[a[i]]t[a[i]]赋值为1，那么若以jjj为中心的lenlenlen最大的字符串不是回文子串，则必然有解。建2棵线段树维护哈希值即可判断回文子串Code#include<bits/stdc++.h>using namespace std;const int N=3e
2020-09-09 22:49:40
133
原创 常犯错误
近日，某蒟蒻在校测中多次犯烧杯错误，再加上本身实力有限，于是多次垫底，便有了这篇博客。没开long long数组开小/开大未考虑图中的自环。。。
2020-09-07 13:44:07
100
原创 【凸包模板】POJ3348 Cows
【题目描述】传送门【代码】凸包模板#include<bits/stdc++.h>using namespace std;const int N=1e5+10;struct Point{ double x,y;}a[N],s[N];int n,top=1;double ans=0,t;inline double check(Point a1,Point a...
2020-02-10 13:56:02
83
原创 【POJ1066】【UVA754】【计算几何】Treasure Hunt
【题目描述】POJ传送门UVA传送门一句话题意：从起点出发，至少要穿过多少墙才能走出正方形【解析】这道题有些类似最短路，但终点不确定。于是想到：虽然题目中要求通过每一个区间的中点，但实际上走这一区间的任意一个点都是一样的，因此只需要枚举每堵墙的端点。此时，路线已经确定，由于数据范围很小，直接枚举与每堵墙是否相交，用叉积判断即可。此题坑点众多：poj 上不能使用bits库...
2020-01-19 16:01:24
159
原创 【整体二分】Dynamic Rankings
【题目描述】传送门一句话题意：带修改区间第k大【解析】带修改的整体二分模板不会整体二分模板?将修改拆分为减去原来的数，加上新的数即可【代码】#include<bits/stdc++.h>using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(...
2019-12-07 17:00:45
98
原创 【cdq分治】[BOI2007]Mokia 摩基亚
【题目】传送门【题解】看一遍题，咦，这不二维树状数组吗？慢着，W<=2000000·····这时我果断打开了标签：“分治”？难道是cdq？再仔细看题，先按过去做二维树状数组的方法，将矩阵求和转化为求四个前缀子矩阵和而在t时间求前缀子矩阵(x,y)(x,y)(x,y)的和，只用考虑时间在t以前，修改位置x1<=x,y1<=yx1<=x,y1<=yx1&...
2019-11-30 16:00:50
98
原创 CSP-S 2019 D1T2 括号树
【题目描述】洛谷【题解】题目中已经清楚地告诉你怎么用n位格雷码推n+1位格雷码，直接二叉树模拟即可注意要使用unsigned long long（如果这道题没有95分部分分，不知道有多少人要凉，反正我是会凉的。。。）【代码】#include<iostream>#include<cstdio>#include<cmath>#include&...
2019-11-30 15:42:17
251
原创 CSP-S 2019 D1T1 格雷码
【题目描述】洛谷【题解】题目中已经清楚地告诉你怎么用n位格雷码推n+1位格雷码，直接二叉树模拟即可注意要使用unsigned long long（如果这道题没有95分部分分，不知道有多少人要凉，反正我是会凉的。。。）【代码】#include<iostream>#include<cstdio>#include<cmath>#include&...
2019-11-30 08:40:14
326
原创 洛谷P3425 【网络流】【二分答案】[POI2005]KOS-Dicing
【题目描述】KOS-Dicing题解：二分+网络流看到"最大值最小",显然要二分最少赢多少场。源点向每一个比赛连一条流量为1的边，表明每个比赛只能赢一次每个比赛向2位选手各连一条流量为1的边，表明每个比赛只能有一个人赢最后每个选手向汇点连一条流量为mid的边，如果总流量>=比赛数，那么这个做法可行等等，要输出方案！每一个比赛向哪一个选手连的边流量是1，就代表这个选手赢了好...
2019-08-12 13:35:08
184
原创 【最短路】 CF507E Breaking Good
【题目描述】CF507E Breaking Good 【题意】给出一个无向图，有些边需要修复，设一条路径的影响值为路径上需修复的路数+其他完好的路数，找出影响值最小的最短路【分析】维修的路数=最短路长度-最短路上完好的路数炸毁的路数=总完好路数-最短路上完好的路数只需要选择一条完好路数最多的最短路即可...
2019-06-08 20:52:40
126
原创 【最短路】CF545E Paths and Trees
【题目描述】CF545E Paths and Trees 【题意】一个n个点m条边的无向图和一个点u找出若干条边组成一个子图使u到其他点的最短距离与在原图中的相等，并且使边权和最小，求这个最小值【分析】先膜一下想出正解的CSH巨佬与LJY巨佬求u到所有节点的最短路，则答案就是一棵以u为根的最短路树。怎么记录？记录下每个节点最短路上最后一条边...
2019-06-08 20:44:18
204
原创 【并查集】冷战
【题目描述】bzoj4668or WOJ3776描述1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁 幕演说”，正式拉开了冷战序幕。美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其 盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都 尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通 过局部代理战争、科技和军备竞赛、太空...
2019-06-08 20:30:55
188
原创 【最短路】CF715B Complete The Graph
【题目描述】CF715B Complete The Graph【题意】一张无向图，其中一些边的边权你可以自己设置，但要最终使s到t的最短路为L，求任意一种方案【分析】f[i][j]表示从s到点i经过j条无边权边的最短路对于某不可修改边（x,y）f[x][j]−>f[y][j]（x,y） f[x][j]->f[y][j]（x,y）f[x][j]−>...
2019-06-08 20:23:14
314
原创 【图论】【连通块】Usaco2012Jan. Bovine Alliance
【题目描述】[洛谷P3043 Usaco2012Jan. Bovine Alliance](https://www.luogu.org/problemnew/show/P3043)【分析】题意：给出一个n个点m条边的图，现把点和边分组，每条边只能和相邻两点之一分在一组，点不可以和多条边一组，但点可以单独一组，问分组方案数通俗理解：每个组要么一条边以及它相邻的一个点，要么一个单独的点。...
2019-06-08 19:31:50
276
原创 【最短路】CF449B Jzzhu and Cities
【题目描述】CF449B Jzzhu and Cities 【分析】题意：n个点，m条带权边的无向图，其中有k条特殊边连接1和i问最多能删除多少条特殊边，能使每个点到1的最短距离不变解答：直接在原图上跑最短路，得到dis[x]表示x到1的最短路。对于每个用特殊边k连接的点i，如果dis[x]<w[k]，那么k可以被删除如果dis[x]=w[k],看x的其他出边如果也在最短路上...
2019-06-08 19:14:25
728
原创 树形DP
二、步骤确立状态三、例题例1.由根分为左子树与右子树情况 二叉苹果树大意：first.本题权值在边上->将边权转移到儿子节点上second.状态定义设f[i][j]f[i][j]f[i][j]表示以i为根的子树上保留j个节点时最多能保留的苹果数量设ch[i][0],ch[i][1]分别为i的左右儿子ch[i][0],ch[i][1]分别为i的左右儿子ch[i][0]...
2019-05-18 19:53:14
132
1
原创 数位DP浅谈
【参考资料：信息学奥赛一本通 提高篇】为什么说是浅谈呢？因为楼主对于数位dp也不过只有很浅薄的理解，也就只能浅谈一下了。。。一、简介“在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。”——刘聪《浅谈数位类统计问题》对于这样的问题，我们需要借用DP的思想，以数位为阶段，在数位上进行递推，这就是数位DP二、...
2019-05-12 22:01:24
129
原创 树上操作杂题
1.给定一个树T，有点权，查询路径点权和分析与解：树上前缀和：预处理每个点到根的路径：dis[i]dis[i]dis[i]dis(x,y)=dis[x]+dis[y]−dis[lca(x,y)]−dis[fa[lca(x,y)]]dis(x,y)=dis[x]+dis[y]-dis[lca(x,y)]-dis[fa[lca(x,y)]]dis(x,y)=dis[x]+dis[y]−dis[...
2019-04-22 19:05:55
132
原创 [dp][单调队列优化dp](洛谷p2027)修剪草坪
题面【题目描述】在一年前赢得了小镇的最佳草坪比赛后，Farm John变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farm John希望能够再次夺冠。然而，Farm John的草坪非常脏乱，因此，Farm John只能够让他的奶牛来完成这项工作。Farm John有N(1 <= N <= 100,000)只排成一排的奶牛，编号为1…N。每只奶牛的效率是不同的...
2019-04-06 11:36:04
342
原创 单调队列优化dp
一、1D/1D动态规划有一些动态规划，有着状态数为O(n)，每一个状态决策量为O(n)的动态规划方程。直接求解的时间复杂度为O(n^2)，这便是1D/1D动态规划。绝大多数这样的方程通过合理的组织与优化都是可以优化到O(nlogn)乃至O(n)的时间复杂度。二、dp优化之单调队列优化在1D/1D动态规划中，有一种dp，转移方程一般为：dp[i]=min(f[j])+g[i],(...
2019-04-06 10:23:49
860
原创 二分图匹配
一、二分图定义：一个图，它的顶点可以分成2个集合X和Y，使所有的边连接的2个顶点中，一个属于X，一个属于Y。那么这就是一个二分图。二分图的匹配：给定一个二分图G,M为G边集的一个子集。若M的任意2条边都不依附于同一个顶点。则M是一个匹配。最大匹配：图中包含边数最多的匹配。完美匹配：如果所有点都在匹配边上，则这个匹配是完美匹配。二、二分图判定染色法：从任意节点开始染色，进行深搜...
2019-04-05 20:55:13
148
原创 [dp][概率与期望dp]Dumb Bones
UVA10529(洛谷)【题目描述】你正在尝试用多米诺骨牌搭成一条直线，以便最后试验时推倒它们（确实，搭建某些东西仅仅为了推倒看上去没啥意义，但你有一些奇怪的爱好）然而你在搭建过程中可能会弄倒骨牌，这将波及到邻近的部分现在需要你来求将骨牌搭建完成所需的期望步数【输入】若干组数据，以0结尾一个整数n(1 \leq n \leq 1000)(1≤n≤1000) 表示你需要搭的骨牌数量...
2019-04-05 17:15:19
171
2
原创 【dp】【概率与期望dp】百事世界杯之旅
洛谷P1291【题目描述】 “……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？【输入】整数n（2≤n≤33），表示不同球...
2019-04-05 15:59:17
221
原创 期望基本概念
一、数学期望如果X是一个离散的随机变量，输出值为 x1,x2,…和输出值相应的概率为p1,p2,…（概率和为1）, 那么期望值E[x]=∑ip i x i E[x]=\sum_{i}^{}{p~i~x~i~}E[x]=∑ip i x i 二、期望的运算E(φ)=Σφ i P ...
2019-04-05 15:30:13
1381
原创 【dp】【概率与期望dp】骰子
【题目描述】 骰子是一个六面分别刻有一到六点的立方体,每次投掷骰子，理论上得到1到6的概率都是1/6有骰子一颗,连续投掷n次,问点数总和大于等于X的概率是多少【输入】输入一行2个证书，分别表示n,X，其中1<=N<=24,0<=X<150【输出】1行，一个分数，要求用最简的形式精确的表达投掷n次骰子，总数大于等于x的概率。如果是0/1，则输出0，如...
2019-04-05 14:32:10
502
原创 概率基本概念
一、基本概念1.随机事件与概率自然界中各种现象可以区分为两种：确定性现象随机现象确定性现象:在一定情况下一定会出现的现象随机现象 :在一定的条件下，可能出现多种结果，而在试验之前无法预知其确切的结果，也无法控制 概率论与数理统计是研究和揭示随机现象统计规律性的一门数学学科 2.随机事件及其运算(1)随机试验与随机事件随机试验：具有以下特点的试验（用E表示）...
2019-04-05 12:24:15
1073
原创 【dfs序】【lca】【树状数组】树上修改
【题目描述】有n个节点N-1条边，这是一颗树，有2个操作：1 x y v：表示将节点x到y最短路径上所有的点的权值+v2 x：表示查询节点x的权值开始的时候每个节点的权值是0【输入】第一行是数N，表示N个节点 接下来n-1行，每行描述了n-1条边。接下来是一个数q表示有q次查询与询问 接下来q行，格式如题【输出】若干行【样例输入】31 22 331 1 2 51 1...
2019-03-30 18:57:18
241
原创 【dfs序】【线段树】【树状数组】苹果树
【题目描述】 here is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.The tr...
2019-03-30 18:34:10
204
1
原创 组合数学
一、计数原理1.加法原理：分类计数2.乘法原理：分步计数二、排列1.线排列——排列数公式：Pnm=n!(m−n)!\frac{n!}{(m-n)!}(m−n)!n!——全排列：P=n!2.条件排列：符合一定条件的排列方案3.圆排列：从n个数选取m个，不分首尾排成一个圈的方案（P(n,m))4.相异元素可重排列：从n个不同元素可重复选出m个元素排列5.错排问题：n封信编号1-n...
2019-02-18 20:09:59
184
原创 扩展欧几里得算法（一）
扩展欧几里得算法（一）一、应用: 不定方程：ax+by=c 求逆元 同余方程二、求解线性不定方程1.对于ax+by=c设gcd(a,b)=d;if(c%d!=0) 无解；设c=c1*d,求出一组解（x0,y0），则ax0+by0=d则a(c1x0)+b(c1y0)=c,(c1x0,c1y0)为一组解因此：核心问题是：求ax+by+c=gcd(a,b)的解...
2019-02-15 20:52:20
514
原创 【欢乐赛】【优先队列】 蜀石经
【题目描述】 今年是石室中学2160年校庆年。CCTV国家宝藏节目联合中国国家图书馆赠送给学校一份珍贵的礼物——蜀石经拓本的复制本，让蜀石经重回石室。同学们听说了这个消息后，纷纷希望一睹真容。学校在校史馆展出了这件国宝，今天有N个同学去参观，排起了长龙。因为学习紧张时间宝贵，我们决定让这个同学登记自己的时间安排。你现在拿到了这份时间表，知道了对于第i个同学 他计划在ai时间来看到这件国宝...
2019-01-28 16:09:44
116
原创 【欢乐赛】【线段树】做作业
【题目描述】 文翁班上有N(1<=N<=500)N(1<=N<=500)个学生，编号1...N1...N。对于第i个学生他们需要在[Si,Ti][Si,Ti]时间段中做作业，且需要bibi支笔。可能在一个时刻有多个同学在写作业，但是他们不能同时使用一支笔。一个人写完作业后，他的笔就可以给别人用。问，至少需要多少支不同的笔。数据保证所有的si,ti各不同。...
2019-01-28 15:39:38
126
原创 【背包DP】（WOJ 2970)声音辨数
题目（声音辨数）：【题目描述】 一条线上有N个点，每个点可能若干B类动物，每个动物会发出声音，声音由左向右传递，如果第i个点发出的声音总和为L，则传到i+1为L-1,每个点的音量总和是上个点传递的音量加上这个点动物发出的声音总和问：一共最少有多少个动物【输入】第一行是2个整数N,B，表示n个点，B类动物接下来是B行，每行一个整数Vi表示每类动物发出的声音音量接下来是N...
2018-12-23 22:17:48
122
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人