- 博客(715)
- 收藏
- 关注
RSS订阅
原创 SDOI 2018 R1 爆零滚粗记
Refun大爷的游记 宽爷爷的游记3月颓废，4月省选见祖宗…Day 04月5日踏上前往YT的火车，高铁好评！而且还有电（开始颓红警 抵达烟台后 30min找宾馆（也太偏了啊… 宾馆貌似还不错的样子，然而我想住核电，不想住农大哇qwqqqqqqqq7:30去试机器，这个键盘用的我浑身难受（平常笔记本键盘用多了… 紧张的一批，LCT写挂，Splay写挂（然而并不考qwq ...
2018-04-08 09:38:33
703
5
原创 NOIP 2017 游记
NOIP2017都过去了！ 咸鱼博主终于更博qwq 一个月的集训颓废结束啦，NOIP2017，窝来了。DAY 0清晨5:30匆忙起床，风一样冲向机房收拾东西。 看着机房的一切，有点悲伤：“不知下次再来是，会是怎样的心态了。” 收拾完东西，来到学校东门口，同机房的大佬们，高三补考大佬以及高一考试的三位大佬已经在东门口谈笑风生了。 7:30到达济南火车站，途经我家(WTF)，
2018-01-02 08:28:25
637
1
原创 NOIP实用技巧，让你的程序超乎寻常的快
/* U{uJUjujuJjY[>vJjJjYv>[{jYuJuJJ<<[JJjY[<v[Y{ujJYu{vi>>v>vv[v[?[LjYJ{vi^>Y[<^>{JYJYj{JLJYuJJ{JYJ{YJu[ J>[{v[v{?[><vUL<<?riYJ<^>[>v><<uj>r><^<uvi^?>v>v</>2j<r
2017-09-10 17:23:31
2378
9
原创 2023 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛）
第i名状态为参加比赛 玩手机 或者 不参加比赛 不玩手机 那么他前面的人必须是参加比赛不玩手机 或者 参加比赛 玩手机 或者 不参加比赛 不玩手机 即状态0/1 pos1.pos2/pos3来标注他是不是撒谎了。第i名状态为参加比赛不玩手机 那么他前面的人必须是参加比赛不玩手机 即状态0 pos1来标注他是不是撒谎了。因为每个人只有可能有4种状态 我们用1/0来表示 参加比赛（玩手机）/ 不参加比赛（不玩手机）状态1为 参加比赛 玩手机 或者 不参加比赛 不玩手机 因为这两种人排名谁高谁低都可以。
2023-07-18 17:59:30
1372
原创 2022.3.21 训练
A ： Glass Carving题目链接题意：给定一个矩形和一些操作 每次横切或者竖切 问你每次切完后的最大矩形题解：我们每次只需要知道横向和竖向最大的间隔是多少就可以了 先用set维护横切和竖切 然后用multiset维护横竖的最大间隔（利用set里的前驱和后继）#include <iostream>#include <cstdio>#include <set>using namespace std;set <int> s1,s2;mul
2022-03-21 22:38:10
478
原创 2022.3.20 训练
#605. 蒟蒻题目链接题意：每个元素有价格w和味道t 第一个操作加入一个w,t的元素 第二个操作删除w最小的元素 第三个操作删除t最小的元素 w和t必须一一对应题解：由于一一映射 直接两个map搞就可以了#include <iostream>#include <cstdio>#include <map>using namespace std;int n;map <int,int> s1,s2;int main(){ cin>&g
2022-03-20 22:09:30
1256
原创 2022.3.19 训练
A ：Subsequence Hate CodeForces - 1363B题目链接题意：可以把0改成1或者把1改成0 让子序列不存在010或者101 最少改变几次？题解：最后的形态一定是0000…11111 11111…0000 11111…1111 0000…0000记录01数量前缀和以及01一共的数量 On枚举即可#include <iostream>#include <algorithm>#include <string>using namespa
2022-03-19 22:04:10
829
原创 [NOI 2018]归程
题目描述：n个点，m条边的无向图，每个边有权值和高度。每次询问给出出发点和最低高度，当边的高度高于最低高度时才可以通行，问从出发点可以到达离点1最近的点距离是多少题目分析：由于是无向图，先对点1跑单源最短路。对图做克鲁斯卡尔重构树，由于是高于某个值才能通行，对边权降序排列，做小根堆，对出发的点走到最低不能走的位置，对子树内询问最小的距离即可题目链接：NOI2018 归途AC代码：#include <cstdio>#include <algorithm>#incl
2021-12-03 09:32:55
283
原创 [2021ICPC 上海] Life is a Game
题目描述：给出一张无向连通图 有点权 有边权每一次给你一个初始能量和初始点 每到达一个点可以收集点权能量 可以通过一个边的条件是当前能量大于等于边权每个询问是最多收集多少能量题目分析：这类问题肯定是建立克鲁斯卡尔重构树做的对于X点是否能通过就是能量[X的子树和]+初始能量值>=父节点点权变换得 初始能量值>=父节点点权-能量[X的子树和]这个柿子可以通过倍增快速得到答案题目链接：Life is a GameAC代码：#include <iostream>#i
2021-11-30 13:00:33
591
原创 浙大版《C语言程序设计（第4版）》题目集
第二章练习2-1 Programming in C is fun!#include <stdio.h>int main(){ puts("Programming in C is fun!"); return 0;}练习2-3 输出倒三角图案#include <stdio.h>int main(){ puts("* * * *"); puts(" * * *"); puts(" * *"); printf(" *"); return 0;}
2021-11-04 23:33:27
4915
3
原创 [牛客多校] Kuriyama Mirai and Exclusive Or
题目描述：给出一个序列操作 1 对 l - r 内数字异或一个数字操作 2 对 l - r 的数字异或一个等差数列题目分析：操作1维护异或差分即可。操作2考虑单独一个二进制位 维护一个二维差分即可题目链接：Kuriyama Mirai and Exclusive OrAC代码：#include <iostream>#include <cstdio>const int maxm=1e6+100;int val[maxm],a[maxm];bool b[max
2021-07-25 17:09:44
227
原创 [2021 HDU多校] HDU 6962 I love tree
题目描述：给定一棵树，然后有两个操作。第一个操作从U,V这个路径上的点权值依次加上路径次序的平方。第二个操作是查询点U的权值和。题目分析：首先可以树剖把路径分为logn段。对于dfn从[h,t]这段，可以维护一个二次函数(x−h)2(x-h)^2(x−h)2展开后得到x2+h2−2∗x∗hx^2+h^2-2*x*hx2+h2−2∗x∗h分别用三个线段树维护每个项的和就可以了时间复杂度O(n(logn)2)O(n(logn)^2)O(n(logn)2)题目链接：HDU 6962AC代码
2021-07-23 16:41:16
441
2
原创 [牛客] 买礼物
看到这题目最简单暴力的做法就是树套树或者带修莫队来做 然而数据范围来了 5e5做不了首先我们定义一个next数组 它的意义为与val[i]相同的数字的下一个位置是那里 每次只要查询l-r区间内next数组的最小值 假如区间最小值也在l-r内说明l-r内最少存在一对相同的数字，对于修改我们建立双向链表对线段树单点修改即可#include <iostream>#include <cstring>const int maxm=1e6+100;int pre[maxm],net.
2021-02-06 17:27:07
191
原创 [算法学习] 克鲁斯卡尔重构树
题目1：CodeForces 1417 F Graph and Queries对于一个无向图联通块内找最大值问题可以用并查集dfs序线段树来解决 但是这个题目存在删边操作 那么我们就把删边变为加边 对题目删除的边逆着进行克鲁斯卡尔重构树 即将两个节点的祖节点都连接在一个新点上 这样可以连通块内的点都是这个祖的子树节点 可以使用dfs序来解决#include <iostream>#include <cstdio>const int maxm=1e6+100;struct no
2020-10-15 23:19:23
252
原创 [Rocky Mountain Regional Programming Contest 2019] Water Later
题目描述：给你一个字串，你每次可以选择一段连续的相同的字符删去，但是你以但选择了一种类型，你就必须把这个类型的所有区间段都删去，才可以考虑选下一种类型。问最少几步可以清空字串。题目分析：对于字符串中的种类其实是特别少的 那么我们可以枚举状态 1表示在这个状态里这种字符已经全部消去了对于状态i来说 我们可以枚举其中消去的字符j 然后从i状态去除j的状态转移过来 现在的问题就是对于去除了j的状态需要花几次去消出所有的j。我们可以预处理一个cnt[sta][i]数组表示的是在sta这个状态下去除所有的
2020-09-19 14:42:00
264
原创 [2019 ICPC Malaysia National] Military Class
题目描述：给出两列士兵 第一行的i可以与第二行的j ( |i-j|<=e ) 配对 其中有k对不能匹配 现在求有多少种完全匹配方案 对1e9+7取模题目分析：看到e<=4也就是说某一个人能跟他匹配的很少 那么就可以用状压来表示第i个第一行的数字可以与其匹配的数字的匹配状态 然后加个记忆化搜索就可以了题目链接：Gym - 102219F代码：#include <cstdio>#include <iostream>#include <cstring&g
2020-09-19 13:12:03
196
原创 [HDU 多校训练] 2020 Multi-University Training Contest 2
A题：Total Eclipse题目链接题意：给出N个点M条边的无向图 每个点有权值 每次可以选择一个连通子图把每个点的权值减一，直到所有点的权值都为0，求最少的操作次数。题解：每次肯定是选择一个联通块，然后把最小值变成0，将这个点删去，分裂成多个连通块继续做。倒过来考虑，变成将B从大到小加入这个图加入每个点 x 时遍历与 x 相连的所有边 (x, y)，如果 y 在 x 之前加入且 x 和 y 不连通则将 x 和 y 合并，并将 y 所在连通块的树根的父亲设为 x，得到一棵有根树。那么每个点 x
2020-07-25 02:13:05
229
原创 [Ecfinal 2019] value
题目描述：给出N个A，B寻找一个集合使价值最大价值即为集合内A的和如果 i，j属于集合内并且 i >1 j>1 i^k=j(k>1) 则价值需要减去j的B值题目分析：每个幂根之间是不会交叉的，我们只需要把每个幂的链挑出来，用二进制去枚举所有的情况即可题目链接：牛客Ac代码：#include <cstdio>#include <iostrea...
2020-01-12 19:55:23
353
原创 [Ec Final 2018] Misunderstood … Missing
题目描述：我有两个基本属性一个 A 表示每次攻击可以造成的伤害，D为每轮自动增加的攻击力（A D初始值都为0每轮你有三种操作（任选一个1：造成 A+ai 的伤害2：给 D 增加 Bi 的数值3：给 A 增加 Ci 的数值最后求N轮后，最大的伤害数值题目分析：考虑到2 3 操作有后效性，所有我们倒着DP由于 B操作和C操作与攻击次数和攻击与这个操作的差值有关，所以状态里要有攻击次...
2019-12-10 22:58:33
177
原创 [Ec Final 2018] Eventual … Journey
题目描述：又N个车站，M条边，每个车站分为黑白两种如果两个点颜色一样，可以花1的花费到达，或者两个点有边直接连接。问每个点可以到达的点的总花费的最小值题目分析：互相到达的点花费只有三种可能1：互相连接的点或者颜色一样的点2：如果一个点链接着颜色不一样的点，我就可以通过这个点使用2的代价到达所有颜色不一样的点3：如果一个点没有链接颜色不一样的点，去的点（即终点为颜色不一样的点也没有链...
2019-12-10 22:44:26
393
原创 [Ec Final 2018] Deja vu of … Go Players
题目：QAQ…题目分析：每次都能拿完一堆，先手的堆数多余后手就输了，否则后手输了题目链接：题目分析AC代码：#include <iostream>#include <cstdio>int n,m;int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&...
2019-12-10 22:33:41
281
原创 [ICPC2019 南昌站] Eating Plan
题目描述：有一个N的全排列每个位置数的价值是他的阶乘 mod 998857459现在给出m个询问，每次给出一个数，问最短的子段区间和大于等于这个数的时候，这个最短子段的长度是多少， 不存在请输出 -1 （子段和也要 mod 998857459）题目分析：首先 对于M个询问，值大的子段区间长度一定不小于值小的，即如果我们把M个询问离线，按照值升序排列，最后的答案是一个单调不降序列由于mo...
2019-12-08 23:56:34
443
原创 [ICPC2019 南昌站] Bob's Problem
题目描述：有N个点，M条边边有权值和颜色（黑色 白色）最多选K条白边，黑色边数量不限，问在保证选出的边让图联通的情况下，边取值和最大题目分析：由于黑色边没有限制数量我们可以先把所有的黑色边扔进去，做克鲁斯卡尔然后把白边按照权值降序排列第一次我们先尽量保证图联通，因此当边链接的点不在一个连通块的时候取这条边。记录当前用白边的数量然后判断能否用少于等于K让图联通如果白边还有剩余，我...
2019-12-08 23:46:09
189
原创 [ICPC2019 南昌站] And and Pair
题目描述：给出一个数字 N (以二进制形式给出)然后寻找数对 (i,j) 满足1：1<=j<=i<=n2：i&n=i3：j&i=0题目分析：首先 第二个条件对于 n 中的二进制0位置i只能取0，1位置 i 可以取 1 或者 0对于 i 的1位置，j只能取 0 ，对于 i 的0位置 j可以取 1 或者 0对于 j<=i这个条件 我们只需要让...
2019-12-08 23:40:18
265
原创 [NOIP/CSP 2019 提高组] 括号树
题目描述：QAQ…题目分析：设 dp[i]为1-x内合法的子序列括号树num[i]表示i到根的路径上连续已经匹配的括号串数last[i]表示最后一个为匹配的 ( 位置首先 dp[i] 和 last[i] 都要承接父亲的答案如果 i 为 ( 那么更新 last[i]=i如果 i 为 ) 并且有没有匹配的左括号那么 last[i]=last[fa[last[i]]]num[i]=n...
2019-11-28 15:36:55
982
原创 [NOIP/CSP 2019提高组] 格雷码
题目描述：QAQ…题目分析：我们直接分两个情况讨论，看一个第N个格雷码第K个是从上个格雷码正序+0还是逆序+1来的，然后不停的递归就行了，需要注意的是，我们默认的顺序是顺序，在第二个情况里需要算出这个串在正序里排多少还有就是需要开unsigned long long题目链接：题目链接AC代码：#include <cstdio>#include <iostream...
2019-11-27 21:24:21
1357
1
原创 [蓝桥模拟] 蒜头君王国
题目描述：有N个点，每两个点都有P的概率建边，问最后N个点联通概率题目分析：概率DP。首先 如果只有一个点 Ans=1两个点 Ans=p我们设 F(n) 为 n个点联通的概率 G(n) 为n个点不联通的概率显然 F(n)=1.0-G(n)目前有i个点，枚举j个点为联通的，那么第i个和j-1个点联通概率即为F(j)∗Cj−1i−1F(j)*C_{j-1}^{i-1}F(j)∗Cj−1...
2019-11-27 00:32:36
192
原创 [蓝桥杯] 青出于蓝胜于蓝
题目描述：无。题目分析：就是求一个节点子树里有多少个节点编号比这个数小，直接权值线段树动态开点线段树合并就好了。题目链接：题目AC代码：#include <iostream>#include <cstdio>const int maxm=110000;int ans[maxm],root[maxm];int head[maxm],net[maxm*2]...
2019-11-26 23:40:41
176
原创 [南昌网络赛] Distance on the tree
题目描述：给出一个 N 节点 的树，N-1个边权每次求 U-V上小于等于K的边权个数题目分析：树上主席树把边权下放到深度比较深的节点转为点权求解的时候由于每个点上维护的是点到父亲的值，所以求解的时候应该是 sum[u]+sum[v]-2*sum[lca]题目链接：Distance on the treeAC代码：#include <iostream>#includ...
2019-11-07 22:43:00
115
原创 [SP10628] COT - Count on a tree
题意描述：给出一个N节点的树，每个点有点权M个询问 每次询问 U->V路径上的第k值题目分析：区间第K值主席树。树上主席树维护点权得出的当前答案应该是 sum[u]+sum[v]-sum[lca]-sum[fa[lca]]题目链接：SPOJ 10628AC代码：#include <iostream>#include <cstdio>#includ...
2019-11-07 22:38:05
122
原创 [石油大OJ] 腿部挂件
题目描述：给出 N 个数 M个询问每次询问给出 L R X 三个参量询问从L-R中的数字与X最大的异或值是多少题目分析：异或最大值问题应该是用 01 字典树来做然后关于区间直接像主席树那样搞个可持久化就OK了AC代码：#include <cstdio>#include <iostream>#include <algorithm>const ...
2019-11-01 19:30:33
165
原创 [ICPC 2019 南京网络赛] 比赛题解
持续更新中…A：The beautiful values of the palace题意：给你M个点，Q个矩形，每个点都有一个价值，求每个矩形点价值和题目分析：首先我们根据N的值和坐标可以O1的得出每个点的价值，这样就转化成了求一个二维矩阵前缀和的问题，由于我们开不了那么大的空间，我们就把第一维X排序，第二维Y扔进树状数组查询前缀和即可，把每个询问拆成四个点询问前缀和矩阵和，然后就可以得...
2019-09-03 14:33:01
706
2
原创 [POJ 2482] Stars in Your Window
题目描述：给出N个星星的坐标，以及的他们的亮度，给出一个矩形的长和宽，然后求最大值（边上的不算）题目分析：一个星星的贡献区域为 Xi，Yi，Xi+W，Yi+H我们把这个拆成两个线分别为 Xi ，Yi，Yi+H，价值为 valXi+W，Yi，Yi+H，价值为 -val然后把X升序排列，依次在线段树中加入这些线，每次取区间最大值，就可以计算出答案了题目链接：POJ 2482代码：...
2019-08-26 17:09:05
199
原创 [CodeForces-19D] Point
题目描述：一个二维平面，有三个操作Add X Y 添加 坐标为 X Y 的点Remove X Y 删除坐标为 X Y 的点Find X Y 寻找 X Y 右上第一个点题目分析：离散化 X坐标线段树套Set，同时维护一个最大值，方便优化查询过程题目链接：CF 19D代码：#include <cstdio>#include <algorithm>#in...
2019-08-26 15:08:30
149
原创 2019牛客暑期多校训练营（第九场）E All men are brothers
题目描述：有N个人M个操作，每次操作让两个人互相认识，认识关系可以互相传递，求每次操作完毕后，选4个互相不认识的人的方案数题目分析：并查集维护联通块内的人数刚开始答案一定是 C(N,4)我们定义一个数量Pre为目前选两个互相不认识的人的方案数 初始值为C(N,2)每次合并两个联通块，如果两个人本来就在一个联通块里是不需要改变答案的。如果没有在一个联通块内，我们考虑如何通过上次的答案求...
2019-08-15 21:01:08
163
原创 2019牛客暑期多校训练营（第九场） H Cutting Bamboos
题目描述：英语差题目分析：思路来自这位大佬Orz我们二分一个最高的整数，用主席树查询，满足区间内 ans及以上高度的和大于等于第x次切除的，把ans+1上的去处，然后就可以算出答案来了。主席树上查树上的数字和以及数量代码：#include <cstdio>#include <iostream>#include <cstring>#defin...
2019-08-15 20:51:39
297
原创 [CodeForces 540E] Infinite Inversions
题目描述：有一个无限长1 2 3…的序列，然后又N个操作，把 L R 两个数字换位置问调换完毕后有多少个逆序对。题目分析：离散化，我们把两个数之间没有被操作的数缩成一个数，带个数字数量的权值，然后线段树求逆序对就可以了。题目链接：CodeForces 540E代码：#include <cstdio>#include <iostream>#include ...
2019-08-07 19:32:17
220
原创 [HDU 2451] Simple Addition Expression
题目描述：给出一个N，计算[0-N-1]中有多少个符合 i+i+1+i+2不产生进位的数字题目分析：个位只能是 0 1 2其他位置只能是 0 1 2 3然后上乘法原理和加法原理统计就好了题目链接：HDU 2451代码：**在这里插入代码片**#include <iostream>#include <cstdio>#include <cstring...
2019-08-06 18:03:14
152
原创 [CF 1068D] Array Without Local Maximums
题目描述：有N个数字，有的数字为Ai（1<=Ai<=200），有的数字为-1，-1表示这个数字不确定。但是这N个数字满足两个性质。1：每个数字只能为[1,200]中的一个数字2：每个数字的旁边两个数字至少有一个是大于等于这个数字的现在让你求这N个数字的可能出现的方案数题目分析：典型的DP。dp[i][j][0/1/2] 表示第 i 这个位置填 j 数字 并且与它左边的数...
2019-08-06 17:57:32
197
原创 [HDU 2448] Mining Station on the Sea
题目描述：有N个海港，N个船只，M个矿藏点，有K条海路连接矿藏点，每条路都有一个权值，并且海路双向，有P条路连接矿藏点和海港，只能从矿藏点驶向海港，每条路有一个权值，N条船初始在N个矿藏点上，现在要求你求出N个船进入N个海港的最小代价，保证有解。题目分析：不就是个费用流吗.首先，我们从源点向每个有船只的矿藏点连一条容量为1，权值为0的边然后根据矿藏点之间的路径信息，连接容量为INF，权值...
2019-08-06 17:39:03
142
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人