- 博客(680)
- 收藏
- 关注
RSS订阅
原创 博客搬家声明
即将迁移博客，但是原来的文章会保存，由于CSDN的商业性广告太多，自己的分类被强行变成了专栏，而且原来的链接也用不了，现在准备要去博客园，链接是博客园但还是感谢CSDN这些年的帮助，我虽不舍，但依旧离开CSDN，希望明天会更好...
2019-12-15 14:03:41
454
原创 #链表，倍增优化dp#洛谷 1081 JZOJ 3101 开车旅行
题目链接分析什么辣鸡水题，我这种大佬做这种水题？代码#include <cstdio>#include <cctype>#include <algorithm>#define rr register#define abs(x) ((x)<0?-(x):(x))using namespace std;struct liSt{int v...
2019-04-27 15:03:31
143
原创 #容斥，组合计数#洛谷 3214 卡农
题目在集合S=[1∼n]S=[1\sim n]S=[1∼n]中选出mmm个子集，满足三点性质：所有选出的mmm个子集都不能为空。所有选出的mmm个子集中，不能存在两个完全一样的集合。所有选出的mmm个子集中，1到nnn每个元素出现的次数必须是偶数。问有多少种不同的方法，两个子集 a 和 b 同种当且仅当将 a 的子集重新排列后可以得到 b分析首先作为一道黑题，它还是具有它的难度...
2019-04-26 22:29:57
216
原创 2019.04.13【NOIP提高组】模拟 A 组
解题报告前言JZOJ 3169 生产汽车题目分析代码JZOJ 3170 挑选玩具题目分析代码JZOJ 3171 洛谷 4594 重心[题目](https://www.luogu.org/problemnew/show/P4594)[分析+代码](https://www.luogu.org/paste/cwuaw5vf)前言水分警告JZOJ 3169 生产汽车题目nnn个工人，mmm辆汽...
2019-04-17 17:36:33
165
原创 前言&留言板
网址http://codevs.cn/ http://noi.openjudge.cn/ http://ybt.ssoier.cn:8088/ http://poj.org/ http://acm.zju.edu.cn/onlinejudge/ https://www.luogu.org/ http://10.156.17.250/JudgeOnline/status https...
2018-03-02 23:46:39
1979
原创 #二分图匹配，floyd，匈牙利算法#POJ 2594 Treasure Exploration
题目给出一个无向图，问最少需要多少条可重合的路径覆盖所有点分析先跑一遍floyd传递闭包，把题目转换成最小不可相交路径覆盖，然后再跑二分图，最小不可相交路径覆盖=总点数-最大匹配即可代码#include <cstdio>#include <cctype>#include <cstring>#define rr registerusing n...
2019-12-13 22:14:42
191
原创 2019.12.07【NOIP提高组】模拟A 组
JZOJ 3918 蛋糕题目把一个矩阵横切三刀，竖切三刀，问当中的子矩阵总和最小的最大能是多少分析首先相当暴力的方法就是暴力切的位置然后用前缀和，时间复杂度应该是O(n6)O(n^6)O(n6)，但是这个东西是二分的套路，考虑二分答案，首先竖切三刀，然后O(n)O(n)O(n)判断，只要能分成4段或以上即为合法代码#include <cstdio>#include &...
2019-12-13 22:06:23
251
原创 #状压dp，容斥#JZOJ 4555 没有强联通分量的无聊世界
题目在一个有向图中问最少去掉多少条边使剩下的图是一个DAG分析容斥，用总边数减去能形成有向无环图的边数即为答案，设dp[S]dp[S]dp[S]表示选择的集合为SSS所能选的环，那么每当选一个点，就加上它的出边集合与当前所选集合的按位与的二进制位为1的个数，即dp[S∣x]=max(dp[S∣x],dp[S]+cnt[chu[x]&S])dp[S|x]=max(dp[S|x],dp...
2019-12-13 21:03:31
177
原创 CSP-J/S 自闭加憨憨记
i'm so difficultCSP-J总结day1中午day1下午考后CSP-S总结day-1晚上day0上午day0中午day0车上day0酒店day0晚上day1早上day1比赛day1赛后day1中午day1晚上（无地自容）day2早上day2赛后真正的赛后总结后续CSP-J总结（CSP-S才是主线，所以先留下一些悬念）day1中午中午午饭吃得很不爽，然后稍作休息决定去看电视，结...
2019-12-06 22:03:55
316
原创 2019.11.11【NOIP提高组】模拟 B 组
解题报告JZOJ 3888 正确答案题目分析代码JZOJ 3889 序列问题题目分析代码JZOJ 3890 长途旅行分析代码JZOJ 3888 正确答案题目试卷中共有mmm道判断题，nnn个神犇中有ppp个考了满分，qqq个考了零分，其他神犇不为满分或零分。还原出标准答案吗，如有多解则输出字典序最小的那个。无解输出-1。分析分类讨论，若ppp不为0，枚举正确答案，用STL::map\t...
2019-11-11 19:57:38
154
原创 #dp#洛谷 2467 JZOJ 1582 地精部落
题目问有多少个1∼n1\sim n1∼n的排列对于∀i\forall i∀i在1<i<n1<i<n1<i<n的情况下都满足a[i−1]<a[i]>a[i+1]a[i-1]<a[i]>a[i+1]a[i−1]<a[i]>a[i+1]或a[i−1]>a[i]<a[i+1]a[i-1]>a[i]<a[i+1...
2019-11-10 21:19:44
99
原创 #整体二分，树状数组#洛谷 3250 JZOJ 4450 网络
题目分析考虑整体二分，对于操作0在树上差分，用树状数组实现，预处理qqq个询问的Lca\text{Lca}Lca，然后对于操作2，若满足当前修改操作都符合子树里的增加，那么放在左边，否则放在右边；对于操作0、1，若重要度小于等于midmidmid，选择左区间，否则树上差分并选择右区间，但是最后修改操作要撤销，时间复杂度O(qlog2n)O(qlog^2n)O(qlog2n)代码#inc...
2019-11-10 20:39:48
155
1
原创 2019.11.09【NOIP提高组】模拟 B 组
解题报告JZOJ 1402 偷懒的小X题目分析代码JZOJ 1403 渡河代码（开O2AC的SPFA）JZOJ 1404 菱形内的计数题目分析代码JZOJ 1405 电缆建设题目分析代码JZOJ 1402 偷懒的小X题目把一组数据按一定顺序依次插入数组中（即第iii个数为a[i]a[i]a[i]），最后得出来就已经是一个堆，即不需要任何交换操作，若有多种方法，输出字典序最大的一组。满足n=2...
2019-11-09 15:21:19
144
原创 #线性动态规划，背包#JZOJ 3932 洛谷 1941 飞扬的小鸟
题目分析可以把它看成一个背包下降就是01背包，上升就是完全背包，然后超过范围的取最大值，时间复杂度O(nm)O(nm)O(nm)代码#include <cstdio>#include <cctype>#include <cstring>#define rr registerusing namespace std;const int N=1...
2019-11-08 14:57:59
102
原创 2019.11.08【NOIP提高组】模拟 B 组
解题报告洛谷 2872 道路建设代码（Kruskal）洛谷 2873 泥水坑代码（广搜）洛谷 2869 美食的食草动物题目分析代码洛谷 2870 最佳牛线题目分析代码洛谷 2872 道路建设代码（Kruskal）#include <cstdio>#include <cctype>#include <cmath>#include <algorit...
2019-11-08 14:16:17
133
原创 2019.11.07【NOIP提高组】模拟 B 组
解题报告JZOJ 3846 七天使的通讯代码（dfs染色）JZOJ 3847 都市环游代码（dp+矩阵乘法）JZOJ 3850 Fibonacci进制代码（搜索）JZOJ 3846 七天使的通讯代码（dfs染色）#include <cstdio>#include <cctype>#define rr registerusing namespace std;co...
2019-11-07 20:52:53
153
原创 USACO 3.4
解题报告洛谷 1827 美国血统题目代码洛谷 2735 电网题目分析代码洛谷 2736 破锣摇滚乐队代码洛谷 1827 美国血统题目给出一棵树的前序遍历和中序遍历，求它的后序遍历代码/*ID:lemondi1LANG:C++TASK:heritage*/#include <cstdio>#include <cstring>#define rr re...
2019-11-06 16:35:00
170
原创 2019.11.06【NOIP提高组】模拟 B 组
解题报告JZOJ 3843 寻找羔羊题目分析代码JZOJ 3844 统计损失题目分析代码JZOJ 3845 简单题题目分析代码JZOJ 3843 寻找羔羊题目给定一个由小写字母组成的字符串，寻找包含agnus的子串的个数。注意：当且仅当两个子串的起始位置和终点不同时，这两个子串属于不同的子串。分析若找到一个羔羊单词，那么计算左右可扩展的范围，乘起来再求和即可代码#include ...
2019-11-06 15:32:41
147
原创 USACO 3.3
解题报告洛谷 2731 骑马修栅栏题目分析代码洛谷 2732 商品购物题目分析代码洛谷 1930 亚瑟王的宫殿题目分析代码洛谷 2733 家的范围题目分析代码洛谷 2734 游戏分析代码洛谷 2731 骑马修栅栏题目给定一个无向图，找到一条路径，使它经过无向图的所有边，并且字典序最小分析这是一个一笔画的问题，考虑找到奇点，从奇点开始深搜，没、每经过一条边删掉一次代码/*ID:l...
2019-11-06 10:52:42
141
原创 2019.11.05【NOIP提高组】模拟 B 组
解题报告JZOJ 3831 地图的密度（水题）代码JZOJ 3832 在哪里建酿酒厂(水题)代码（O(n^2)卡常AC）JZOJ 1956 洛谷 2449 矩形题目分析代码JZOJ 3833 平坦的折线题目分析代码JZOJ 3831 地图的密度（水题）代码#include <cstdio>#include <cctype>#define rr register#...
2019-11-05 16:24:57
160
原创 #高斯消元，数学期望#CF24D Broken Robot
题目在一个nnn行mmm列的方阵中，一个机器人初始在(i,j)(i,j)(i,j)，它随机往(i,j+1),(i,j−1),(i+1,j)(i,j+1),(i,j-1),(i+1,j)(i,j+1),(i,j−1),(i+1,j)需要一个单位的时间，它也可以停留，问到达第nnn行的期望时间分析首先把初始坐标以上的部分去掉设f[i][j]f[i][j]f[i][j]表示从(i,j)(i,j...
2019-11-04 21:19:25
158
原创 #线段树，猫树#SP1043 GSS1 SP1716 GSS3 SP2916 GSS5
猫树GSS3题目分析代码GSS1题目分析1分析2代码GSS5题目分析代码GSS3题目多次询问区间最大子段和，带单点修改分析用线段树维护区间最大前缀和、区间最大后缀和，区间最大子段和，因为单点修改，所以不难（我也不会区间修改）代码#include <cstdio>struct node{int sum,lmax,rmax,w;}tree[200001];int n,...
2019-11-04 19:55:11
259
原创 2019.11.04【NOIP提高组】模拟 A&B 组(部分)
解题报告B组T4 JZOJ 1353 有趣的数列题目分析代码A组T1 JZOJ 6403 A题目分析代码A组T3 JZOJ 6405 C题目分析代码B组T4 JZOJ 1353 有趣的数列题目我们称一个长度为2n2n2n的数列是有趣的，当且仅当该数列满足以下三个条件：(1)它是从111到2n2n2n共2n2n2n个整数的一个排列{ai}\{a_i\}{ai}；(2)所有的奇数项满足a1...
2019-11-04 19:35:48
283
原创 #树链剖分，线段树#SP6779 GSS7 - Can you answer these queries VII
题目在一棵nnn个节点的树上满足两种操作：把树上一条简单路径展开成一个数列，求这个数列的最大子段和（可以为空）把树上一条简单路径上的点权同时加上一个值分析这道题其实也就是最大子段和的树上版，大同小异，妙不可言特别是求答案的部分，由于是一条链，所以必须用两个东东去分别存储最大前缀和、最大后缀和以及最大子段和，等到最后再合并，还是我太菜了代码#include <cstdi...
2019-11-03 19:02:39
142
原创 #贪心，堆，RMQ#洛谷 2048 JZOJ 2226 超级钢琴
题目分析考虑一个maxx(x,l,r)maxx(x,l,r)maxx(x,l,r)表示以左端点为xxx，右端点在[l∼r][l\sim r][l∼r]的范围内的最大值，那么维护的最大值也就是s[mx]−s[l−1]s[mx]-s[l-1]s[mx]−s[l−1]，而只有mxmxmx是变动的，所以可以用RMQ去求解，把这个三元组扔进一个大根堆里面，跑kkk次，但是处理完一个三元组后需要把它拆成...
2019-11-02 10:12:36
183
原创 #莫比乌斯反演#洛谷 5176 公约数
题目∑i=1n∑j=1m∑k=1pgcd(ij,ik,jk)×gcd(i,j,k)×(gcd(i,j)gcd(i,k)gcd(j,k)+gcd(i,k)gcd(i,j)gcd(j,k)+gcd(j,k)gcd(i,j)gcd(i,k))\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^pgcd(ij,ik,jk)\times gcd(i,j,k)\times (\frac{g...
2019-10-29 22:04:16
166
原创 #分块#洛谷 4135 作诗
题目分析首先此题好像用不了线段树什么的，只好考虑分块但是分块这种题目其实看注释会更好啊，时间复杂度O(nn)O(n\sqrt n)O(nn)代码#include <cstdio>#include <cctype>#include <cmath>#define rr registerusing namespace std;const in...
2019-10-29 21:18:57
122
原创 #主席树，树链剖分#洛谷 3313 旅行
题目分析首先如果没有宗教的限制，那么这道题就是线段树裸题，但是既然有了宗教的限制，那么得开10510^5105个线段树，那显然是不行的，想到了主席树，综合它们的空间，时间复杂度O(mlogn2)O(mlogn^2)O(mlogn2)代码#include <cstdio>#include <cctype>#define rr register#define ...
2019-10-29 20:05:01
120
原创 #回文自动机#洛谷 3649 JZOJ 3654 回文串
题目给你一个由小写拉丁字母组成的字符串sss。我们定义sss的一个子串的存在值为这个子串在sss中出现的次数乘以这个子串的长度。对于给你的这个字符串sss，求所有回文子串中的最大存在值。分析回文自动机模板，不解释代码#include <cstdio>#include <cstring>#define rr register#define max(a,b)...
2019-10-29 19:19:05
123
原创 #主席树，二分，树状数组#洛谷 2617 Dynamic Ranking
TLE分块题解题目区间第kkk大支持单点修改分析如果没有修改操作，就真的只是一道主席树裸题，但是加上修改操作，就不得不使用树状数组维护，其实思路比较简单，主要考验码题能力 (在这一点我是最菜的呀)代码#include <cstdio>#include <cctype>#include <algorithm>#define rr regis...
2019-10-28 21:49:48
100
原创 #主席树、二分、树状数组#洛谷 3157 JZOJ 2287 动态逆序对
题目分析首先如果不带修改操作那么就是一道主席树题目，但是既然有了修改，那么还必须用上树状数组维护，时间复杂度O(nlog2n)O(nlog^2n)O(nlog2n)代码#include <cstdio>#include <cctype>#include <algorithm>#define rr registerusing namespace...
2019-10-28 21:45:35
90
原创 #tarjan，树形dp，dfs序#洛谷 2515 软件安装
题目分析题目乍一看不就是树上背包O(n2m)O(n^2m)O(n2m)吗，再加个dfs序优化就可以O(nm)O(nm)O(nm)了，其实不然，因为有些软件先行条件是会形成一个环的，所以还要用tarjan缩点，由于思路比较简单，主要考码题能力，所以就不多说了代码#include <cstdio>#include <cctype>#include <cst...
2019-10-28 20:39:17
134
原创 #组合计数，动态规划#JZOJ 1523 洛谷 2481 代码拍卖会
题目问多少个nnn位数满足数位从左到右数字不下降且为PPP的倍数分析慢慢填坑吧代码#include <cstdio>#define rr registerusing namespace std;typedef long long ll;const ll mod=999911659;ll n,p,rep,cnt[501],pos[501],dp[501][501]...
2019-10-25 20:44:45
126
原创 #树链剖分，线段树#洛谷 5127 子异和
题目多组询问，每次把树上的一条简单路径中的点权扔入集合中，求该集合的子异和，子异和定义为所有非空子集的异或和的和，而且需要支持区间异或分析考虑某一位满足异或和为1的子集数，若设异或某一位为kkk为1的数量为hkh_khk，那么结果应为cntk=2n−hk×∑i=1⌊hk2⌋C(n,2i−1)=2n−1cnt_k=2^{n-h_k}\times \sum_{i=1}^{\lfloor\fr...
2019-10-25 20:25:07
107
原创 #带修改莫队，分块#jzoj 1942 洛谷 1903 数颜色
题目Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 R P Col 把第P支画笔替换为颜色Col。需要满足查询分析这道题看起来就是要离线的，需要用莫队，但是原莫队不支持修改，那么就弄一弄，当然还要用分块优化，就没有什么了（jzoj卡逐字符输入）代码#include <cstdio>#include <cmath>...
2019-10-24 21:33:48
137
原创 #主席树，二分#洛谷 2839 JZOJ 2902 middle
题目给你一个长度为nnn的序列sss。回答QQQ个这样的询问：sss的左端点在[a∼b][a\sim b][a∼b]之间,右端点在[c∼d][c\sim d][c∼d]之间的子序列中，最大的中位数。其中a<b<c<da<b<c<da<b<c<d。分析代码#include <cstdio>#include <c...
2019-10-24 21:32:04
161
原创 #二分，主席树#洛谷 2468 粟粟的书架
题目给出一个矩阵，问一个子矩阵中至少要多少个数才能使和≥h\geq h≥h，多组数据，分成1≤r,c≤200和r=1,1≤c≤5000001\leq r,c\leq 200和r=1,1\leq c\leq 5000001≤r,c≤200和r=1,1≤c≤500000分析这显然是一道以二分为核心的题目，但是这道题目二合一，对于r≠1r\neq 1r=1维护二维前缀大于等于某个值的数量以及...
2019-10-24 20:58:53
116
原创 #trie#洛谷 4098 JZOJ 3226 ALO
题目分析首先肯定会想到建一棵可持久化01trie，但是关键是次大值，所以考虑从小到大排序，那么每次该数都会有一段选择的区间，那么考虑把它合并给左右，用该值当次大值在trie中找到区间中最大的一个，其实这道题实际操作比理论还要难，至少我是这么认为的代码#include <cstdio>#include <cctype>#include <deque>...
2019-10-23 21:34:29
125
原创 #可持久化01trie，树链剖分#洛谷 4592 异或
题目现在有一颗以1为根节点的由nnn个节点组成的树，树上每个节点上都有一个权值viv_ivi。现在有QQQ次操作，操作如下：111 xxx yyy：查询节点xxx的子树中与yyy异或结果的最大值2 xxx yyy zzz：查询路径xxx到yyy上点与zzz异或结果最大值分析这道题有两种操作，所以要分成两个可持久化01trie分别求解，其它其实有点类似最大异或和那道题，然而还要求LC...
2019-10-23 19:52:55
179
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人