- 博客(78)
- 收藏
- 关注
RSS订阅
原创 笔记【持续更新遇到的小东西】
c++:1bool a=[-128,-1]U[1,127];在这个范围内bool值都会等于1，也就是说本身接受2^8范围数字的赋值，但是所有非零数都会赋值为1；
2020-04-27 09:32:58
220
原创 GDUT_寒假训练题解报告_专题I_K题 个人题解报告：杭电题目Error Curves【裸三分】
GDUT_寒假训练题解报告_专题I_K题 个人题解报告题目：Josephina is a clever girl and addicted to Machine Learning recently. Shepays much attention to a method called Linear Discriminant Analysis, whichhas many interesti...
2020-01-13 22:22:50
549
原创 GDUT_寒假训练题解报告_专题I_G题 个人题解报告【bfs预处理+bfs走迷宫】
GDUT_寒假训练题解报告_专题I_G题 个人题解报告题目：你要玩一个新的角色扮演。图中的世界地图由n × m个单元格组成的网格表示。任何在某个单元格中的角色都可以从该单元格向四个方向移动-向左、向右、向前和向后移动单元格，但不能离开世界地图。怪物生活在一些牢房里。如果在某个时刻，你在一个可以被一个d步或更小步数的怪物接近的牢房里，他会立刻跑过去杀死你。你必须从游戏场的一个单元活...
2020-01-13 19:47:41
216
原创 GDUT_寒假训练题解报告_专题I_A题 个人题解报告【尺取模板题目详解】【poj题目Subsequence】
GDUT_寒假训练题解报告_专题I_A、B、C、D题 个人题解报告A题：尺取（模板题目给出了一个N个正整数序列(10<N<1e5)，每个正整数小于或等于10000，以及一个正整数S(S<1e8)。编写一个程序，以求序列的连续元素的子序列的最小长度，其和大于或等于S。输入第一行是测试用例的数量。对于每个测试用例，程序必须从第一行读取数字N和S，用间隔分隔。序列的数目在测试用...
2020-01-13 08:56:41
464
原创 acm常识入门（给即将进队或者刚刚进队的新生）（仍在更新）
模意义（同余）同余为数论中的重要概念：一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余。记作: a≡b(modm)a≡b(mod m)a≡b(modm)或者说 a%m=ba\%m = ba%m=b 。其中 %就是取模运算符；对模m同余是整数的一个等价关系。同余有很多奇妙的性质和玩法（）首先我们约定：大写字母如A≡a(modp)A ≡ a(mod p)A≡a(modp)乘法：若：AB = C ， 则ab %p= c%p乘
2021-08-04 23:47:19
298
原创 2021牛客暑期多校训练营3B
题目题意：矩阵，n行m列(5e3)，点有权在1e5以内，2*2小矩阵染三另一免费，求全染权和；我：四个方向DP一下吧，应该没错吧，怎么这么多人wa，通过率血马低，不对劲，开始换做法。一个半小时后，终于yy出来了：2*2小矩阵染三另一免费这是唯一一个约束，那易想到一个万能解法，那就是选一列全选了，然后之后每一列都选一个点，剩下的点都是免费的，那么一共选了n+m-1个点；显然这个并不是最优解，因为没有考虑点权。继续yy：(i,j),(i+1,j),(i,j+1)都选了，那么第四个点就能取了,考虑
2021-07-24 20:12:02
228
1
原创 2014 - 2015东京区域赛：Problem G Flipping Parentheses【线段树变种】
比赛链接本题题意：给你一个合法的括号串，比如(())()()()()然后会改变q次，每次改变一个括号的朝向，然后你要输出一个数ans表示你要翻转第ans个括号的朝向使得新的串仍然是合法的；同时如果存在多个ans，请对最左边的括号操作。即要求找一个leftest 下标翻转后能保持括号信息正常；括号匹配容易想到栈和前缀和。栈排除，因为有q次操作；前缀和设左括号为+1，右括号为-1，于是能得到一个前缀和串；容易知道，括号串合法的充要条件是前缀和串处处不为负数；又双叒叕容易想到：如果翻转了pos位置的一
2021-05-18 09:51:32
139
原创 HDU - 6315 / 2018杭电多校第二场G - Naive Operations【线段树变种】
题目链接不放，杭电一搜就有线段树作为区间可加性信息的分治数据结构，通常用于解决具有可加性的区间信息统计，这玩意非常好用。本题题目：要求维护的是∑i=LR⌊AiBi⌋\sum_{i=L}^{R}{\lfloor \frac{Ai}{Bi} \rfloor}∑i=LR⌊BiAi⌋更新操作只有[L,R]表示，区间内A的值+1；,然后B保证是一个1到n的置换，即B大小为n，且1<=Bi<=n且Bi两两不同；设定ai初始值全0；解法本题是非常灵活的线段树用法，可以说是铜牌题了；容易想
2021-05-18 09:33:00
134
原创 树上启发式合并【含2020CCPC长春F题等稍微变种】
学习了树上启发式合并一段时间了，我来写一个总结吧；树上启发式合并叫做Dsu On Tree被某个毒瘤大佬称为静态链分治；树上启发式合并我也不知道为什么叫启发式。但是在我的理解中树上启发式合并和莫队分块都是一样的暴力的机制。是一种合理分配查询的顺序来节省资源的做法；莫队分块可以在多次询问中合理安排询问的顺序，导致时间变成n*sqrt(n)；而树上启发式合并则更加强悍，时间复杂度为nlogn；首先来一手板题：给你一个树，询问每一个结点子树中含有不同颜色的数有多少种；颜色也是与n一个数量级，设都是
2021-04-29 13:51:39
209
原创 Codeforces Round #716 (Div. 2) CD题解证明
4.19CF题解；关于CD的证明：C：本题求的是一个1到n-1的序列，请找出一个最长的满足要求的子序列，求任意方案：要求为：子序列元素乘积mod n为1；赛时觉得结论为：子序列元素如果尽量都和n互素那么会是最好的取法吧，依照这个引理的话我们就很容易可以联想到所有和n互素的数都丢出来：n = 9,那么最大互素集合就是1 2 4 5 7 8 这6个数；又双叒叕可以联想到互素集合子集乘积一定是与n互素的。那么依照上述引理可以简单分为两类：1 答案为ϕ(n)\phi(n)ϕ(n)2 答案为ϕ(
2021-04-20 09:28:39
237
原创 B - Operation线性基入门：【条件动态维护区间线性基】【前缀线性基】
题目链接VJ题目链接HDU（本文是对%%%%%的学习笔记，同时使用了本题作为例题学。）线性基真是个简单而强大的东西，然而我因为很少遇到线性基的题目基本没有怎么学习，线性基是一个基于贪心的数据处理技巧。如果定义原序列通过若干个元素异或的到的新集合为序列的异或域，那么线性基就是一个异或域与原序列异或域相同的极小集合。线性基三大性质：1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到2.线性基里面的任意一些数异或起来都不能得到 0 003.线性基里面的数的个数唯一，并且在保持性质一的前
2021-03-22 15:19:54
196
原创 阶段总结
寒假毫无例外又是一个颓废的假期，家里学习环境极差的同时，自己也没有积极克服这个困难。假期6,7场cf只打了一场，寒假前半段时间有组队训练但是并没有取得很好的效果。归根结底还是自己松懈了。 家附近十分多噪音，大环境就是吵闹，午觉是没有的，不可能睡得着。于是作息便与在校期间完全相左。作息的颠倒导致本来就不怎么样的睡眠质量直线下降。于是许多念头连同一些借口都浮于心头。即使我知道这些都是消极的，都是借口，但是我还是接受了。 诚然居家学习有各种困难，但是理论上还是可以多少学一些，比如cf上2000完全是没问题
2021-03-06 17:30:07
1921
12
原创 Educational Codeforces Round 102 C/D题解【构造】和【维护乱搞】
题目链接C题目链接DC.题意为：给定n,k , (n<=k<2n)求构造出来一个长度为k的p序列，使得：b序列 = p1,p2,p3,p4......pk,pk−1......pk−(n−k)p_1,p_2,p_3,p_4......p_k,p_{k-1}......p_{k-(n-k)}p1,p2,p3,p4......pk,pk−1......pk−(n−k)的逆序数小于等于a = 1,2,3,4.....k,k−1......k−(n−k)1,2,3,4.....k
2021-01-15 11:16:28
201
原创 Codeforces Round #695 (Div. 2)D. Sum of Paths【计数题】
题目链接___题意：给定n个长度小格子，每步可以走到-1或+1下标，不能越界。走k步产生一个序列：c0,c1,c2……ckc_0,c_1,c_2……c_kc0,c1,c2……ck对应Ac0+Ac1+Ac2.....A_{c0}+A_{c1}+A_{c2}.....Ac0+Ac1+Ac2.....求所有这样序列总和。即：路径下标权值和为路径权值，求所有路径权值和本题难以从逐个递推角度求解。我设了一些函数都难以处理这个状态的转移。最后设了一个：f(i,j)f( i, j )f(i,j)表
2021-01-14 21:46:36
129
原创 Dsu on tree树上启发式合并经典例题算法代码剖析
题目链接：E. Lomsat gelral树上启发式合并合并，初见这个名字，我和大部分人一样望文生义觉得应该是子树信息的合并使用了一种“启发式”，相当于区间操作的线段树的Lzay标志一般，仅仅启发而不去真的合并。然后我兴高采烈的学了一下发现其实就是一个暴力。一个优雅的暴力优化。dsu on tree，dsu就是并查集，直译为树上并查集。(某L称该算法为静态链分治。首先我们审视一下题目暴力的写法：对于每个子树开一个桶或者对每个子树都清空一次桶，然后暴力跑得出空间为N2N^2N2 或者时间为N2N^2
2020-11-11 11:27:38
203
原创 2020.11.8 CCPC赛后总结(包括阶段总结【ccpc长春分站赛铜总结】
2020CCPC长春137名喜提铜尾，跟我们一开始目标一样：无论是尾巴还是头，只要有牌子就是完成任务。然而，这一拳像是打在棉花上，根本没有用力，棉花融化了。跟我们一开始想的对铜牌门一顿激烈猛冲，才破门而入的成就感不太一样。2题低罚时就能铜尾只能说题目前半部分区分度并不好。概括我们水平的话，期望大概也在铜尾，所以对题目也没啥好可惜的。反倒是师傅队因为2题罚时高了点就打铁了，平常训练基本都有银牌的发挥的。总结一下这场比赛，其实也没什么好总结的。第一题爆搜过，并不快也不慢的13分钟稳健1a，然后D题zf做过
2020-11-08 21:09:23
1158
8
原创 ACM0基础动态规划启蒙：Dp是个啥
动态规划：DP：Dynamic Programming是算法的设计方法，是一种编程思想，主要用于解决最优解、计数类型的问题。Dp是一种思想！！！是一种没有固定代码的算法。如果不是一定要有严谨的记忆化，状态意义，状态转移方程，步数合并的过程才叫Dp，那么不妨把一些奇奇怪怪的东西也和Dp扯上关系0基础新人的第一个启蒙算法应该大部分都是 Dfs ，好我现在就把这个东西叫做Dp。Question:Dfs为什么叫Dp？Dp需要步数合并对吧，把一些没必要的操作给省略掉或者一些可以合并的操作給合并。举个例子
2020-10-19 18:56:58
911
原创 【板子库】P3384 【模板】轻重链剖分 / 树链剖分模板题
P3384 【模板】轻重链剖分code:#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <climits>#include <queue>#include <stack>#include <m
2020-09-10 15:06:55
123
原创 【班子库&数据结构笔记】平衡树入门之AVL树 NOI2004 郁闷的出纳员
题目链接平衡树是平衡的二叉搜索树，平衡树能够很好地解决暴力BST的一大缺点：某些子树肥大臃肿导致了查询速度的退化。其中旋转操作是灵魂，能够通过旋转操作做到平衡两个子树的结点数量。当一方比较肥大的时候就会进行zig左旋 / zag右旋 /zigzag双旋/zagzig双旋来平衡；同时添加size维护子树大小，还有插入的数字大小一样的时候，开一个cnt记录数量。Code:#include <iostream>#include <algorithm>#include <
2020-09-03 15:40:04
123
原创 bfs序上建线段树维护树层信息/dfs序上建线段树维护子树信息
dfs过程中遍历到栈中某个结点是先完成全部子树的过程才会出栈。这个过程的得到的dfs序每个个点出现两次中间就是其子树bfs序不同，为先出队列再压进新的结点，如此得到的每个数出现两次间就是树层信息，也就是同高度。...
2020-09-03 14:21:20
153
原创 Codeforces Round #666 (Div. 2)D.Stoned Game【奇偶和博弈 + 制高点】
题目链接上面有题目链接，这个题乍一看是一个很裸的奇偶和博弈：给n个数，先后手轮流取1，那么当总和为奇数，先手为优势局面。题目朴素解法就是求和得出来sum的奇偶性，if(sum%2)先手胜利；但是存在一个制高点问题，博弈论制高点指的是有一个状态的元素为强制优势局面。那么这个题的制高点是什么呢？如果是3100 2 2这组数据，先手选第一个堆，那么后手只能选取后面两个，先手继续取第一个堆。如此一来先手永远处于一个强制优势局面，哪怕现在的sum是偶数，先手总能在第一堆继续取，直到后手没有东西可以取了
2020-08-31 09:35:11
270
原创 数论笔记：杂篇
没有摘录到本子上的斐波那契结论式子：1：f(0)-f(1)+f(2)-…+(-1)n·f(n)=(-1)n·[f(n+1)-f(n)]+1
2020-08-05 15:59:34
167
原创 2020暑假杭电多校第三场：05/E : Little W and Contest【路径压缩并查集+数学式子】
题目链接：杭电problems6795题解太过于玄乎，我写一下直接用数学式子解决的方法把：我们把1能力的选手和2能力的选手分成两堆：能力1选手数量为：n能力2选手数量为：m每一次操作其实就是两个连通块给连起来对不对？我们初始化：每一个点都是一个连通块，能力为1的选手的连通块我们在根节点用a=1,b=0表示这个连通块的能力为1选手数量为1，能力为2选手数量为0；那么我们0次操作后的答案是很容易求出来的：C(2,m)*n+C(3,m)。我们用last变量存上一次操作的答案。在某次操作，我们把a1
2020-07-29 16:46:02
185
原创 【板子库(没有解释，萌新绕路)】全局第k小，权值线段树做法+离散化解决带修改问题的离线做法【待验证，不保证代码无误】
如果要看权值线段树是啥的萌新绕路，为你们节省时间，文章仅对代码进行解释.main函数内对point数组有序，pos函数是二分查出值对应的离散化后的值(排名)。以此来对所有数都离散化处理，为存起来询问的离线做法。#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#include <string>
2020-07-28 00:19:25
128
原创 Codeforces Round #658 (Div. 2) C2 Prefix Flip (Hard Version)【构造匹配】[规定步数内达成目标的题目]
题目一种操作，可以选择前缀长度为k，翻转前k的01值然后顺序再倒一下。要求在2n步内把给定a串变成b串做法：a:01101 01001b:10000 10001以这个为例，因为要求是2n步内，很容易就想到每个点搞最多两次搞出来，于是就可以2步之内缩小一次问题规模，从n一直缩小到0；a[1]和b[n]要对上，直接前k翻转.现在变成谁和谁对上？b[n]和a[n]现在都可以不用管了，于是来到了b[n-1]，那b[n-1]和谁对上了，当然还是a[1],a[1]可不就是上一个a[n]吗？可是我们还要用
2020-07-22 10:02:30
337
原创 杭电多校第一场05 杭电6755：Fibonacci Sum【斐波那契通项公式】
题目事先说一下：我是多校的时候ac的，比赛一停就当场换机子了，赛时是1800ms过的，赛后就TLE了，自己加速一下。题目就是求斐波那契的：这个题我和队友思索了很长时间，从各种性质到代换式子都不能解决。然后最后一点时间刚一下通项公式就做出来了。通项公式：Fn=(5)5∗((1+(5)2)n+(1−(5)2)n)F_n=\frac {\sqrt(5)}{5}*((\frac{1+\sqrt(5)}{2})^n+(\frac{1-\sqrt(5)}{2})^n)Fn=5(5)∗((21+(5)
2020-07-21 20:56:31
577
原创 2020牛客暑期多校训练营 (第三场)E Two Matchings【排序后按照 4或6个分成1块的选择 来dp】
题目链接这个题我搞出来一个贪心，看起来对的一批，一选是最小，然后二选也是最小，但是不能这么搞的。因为一选最小不能保证一选+二选的结果也是最小的。然后比完赛发现师兄们一开始也是这样，搞出来假贪心，还觉得正确的一批。先对a数组sort一下，就是从a[1]到a[n]递增。头尾取法：对于最大是必为正数的，最小是必为负数的，那么中间错开来就是说ans=2a[n]-2[1]；为了得出这个期望，应该是按照连续两个a，或者是连续4个a进行分块，然后使用这个头尾取法。当n=16；决策如果是2分块：16 15进行万
2020-07-18 22:48:52
195
原创 牛客算法周周练15-D树上求和【dfs序上建线段树】【模运算的问题】
题目链接此算法暴露了一个问题：模运算求答案的错误示范{//选看，与题目做法无关要求求出ans(mod p)你有一个算法能够实现求出来ans2;但是千万不要在算ans2的过程中使用模数p。然后对结果除以二，这是不行的。举个例子：求出来了res = 7p+16 = ans2;然后res/=2 = 3*p + (8+p/2) = ans;这就出问题了，因为答案是8+p/2，而不是8;为了解决这个问题我们要同步模数：计算ans2时候使用p=2p作为模数；如此算得模数为2p的结果
2020-07-17 17:33:46
132
原创 板子库：单调队列实现的一维滑动窗口(模板题)
经典题目：洛谷acwingcode:#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <climits>#include <queue>#include <stack>#include <m
2020-07-14 17:29:03
158
原创 Codeforces#642 (Div. 3) D. Constructing the Array
题目链接题意：给一个长度为n的空序列，然后往里面填1-n的数字；int cnt=1;找序列中最长(如果多个最长则取最左边的序列)的连续全空区间：并且赋值cnt++;循环这个操作n次：eg：Consider the array a of length 5 (initially a=[0,0,0,0,0]). Then it changes as follows:Firstly, we choose the segment [1;5] and assign a[3]:=1, so a become
2020-05-15 09:54:36
274
原创 东北林业大NEFU 五一欢乐水题 F&H题解
比赛链接H卡迪亚的游戏这题一看，零一背包的皮，然后无论是回溯做法的O(2^n)还是正常dp的O(VN)都满足不了这些毒瘤数据，过于生草，然后神勇的队友竟然设dp[i][j]为前i个物品价值为j的情况下的最小重量。时间复杂度一下子变成O(n*价值最大值),才1e4。代码：#include<cstdio>#include<iostream>#include<a...
2020-05-03 19:06:12
227
原创 5.2日训练赛题解【2019 USP-ICMC】
以后一并全写到一个地方去了。顺便存代码A.Jumping Buildings题目链接题目链接题目链接单调栈例题，我竟然差点没想起来，得把这些复习一下了。代码：#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cst...
2020-05-03 10:30:53
406
原创 HDU-A - Oulipo【板子库_KMP算法】
题目链接……………………………………KMP算法匆匆看完板子一知半解，然后看了整整一天原理才懂了一些，记录一下板子#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#include <cstring>#include <stri...
2020-05-02 11:54:48
177
原创 NCD 2019题解M. NCD Salary【数学式子处理】
题目题意，求ab和cd大小关系。均是大数做一下数学处理：两边取对数，变成blog(a) 和 dlog©；底数是什么无关紧要，为了方便，用c++自带的log10函数就很棒。这里需要特判一下b和d等于0的情况。int a,b,c,d; double last,now; scanf("%d%d%d%d",&a,&b,&c,&d); if(a==0)las...
2020-04-29 08:51:35
342
原创 NCD 2019题解C. Hasan and his lazy students【dp求lis，顺序维护方案数】
题目链接题意，给序列，求最长上升子序列长度和方案数。n<=1000,因为n小于1e3，所以可以使用复杂度为n2的dp做法，然后使用一个结构体来维护方案数就行了：先定义一个结构体，包含dp求lis基本的len，还有就是方案数cnt。struct func{ int len; LL cnt;};int a[1001];func dp[1001];读完数据和基础初始化之后开...
2020-04-29 08:47:44
282
原创 ArabellaCPC 2019 B. Road to Arabella
题目这个题题意弄明白就会了，也就是对手有一个正整数n，你有一个正整数k<=n，每一次都能对n执行n-=x,(1≤x≤max(1,m−k));把0摆在对方面前就是赢了。如此我们很容易想起奇偶性博弈，总能把偶数摆在对方面前，我们就行了，所以对所有n,k；我们要做的是，能不能总是把偶数摆在对方面前。则当k+1== n，或者k== n，每次都只能减去1，所以n为奇数我们才能总是把偶数摆在对方面...
2020-04-22 09:05:40
382
原创 ArabellaCPC 2019 J. Thanos Power题解
题目链接题目大意：给一个101e5以内的数字,你要通过两种操作凑出来；执行两种操作：一种是加上10x，一种是减去10x.这个题很容易联想到01背包，每一步都可以选择通过10-k+1做法或者是直接k的做法，简而言之,9可以通过先加上10,再减去1来实现。但是这是每一步影响都是下一步，我们可以在每一步都用两个数值表示上一位是第一个做法实现还是第二个做法实现，这样就可以完美优化了：做法如下：f...
2020-04-22 08:51:36
251
原创 A. Rooms and Passages【区间问题】
题目链接：https://codeforces.com/gym/102215/problem/A题目：There are (n+1) rooms in the dungeon, consequently connected by n passages. The rooms are numbered from 0 to n, and the passages — from 1 to n. The...
2020-04-17 11:00:20
472
原创 4.15Codeforces Round #635 (Div. 2)C.Linova and Kingdom题解
题目链接：https://codeforces.ml/contest/1337/problem/C大意：给出n，k和一个点数量为n的树，让其中k个结点变为工业城市，其余为旅游城市。而每个工业城市到根节点1的路径上存在的旅游城市数量之和求最大，并输出最大值。样例：ExamplesinputCopy7 41 21 31 43 53 64 7outputCopy7inputC...
2020-04-16 09:07:06
591
5
原创 2019 ICPC Malaysia National J.Kitchen Plates
题目：https://codeforc.es/gym/102219/problem/J题意：给ABCDE 5个盘子的5组比较大小，输出完整大小。这个题应该蛮经典的，题解清一色都是说拓扑排序，可怜我不知道拓扑排序是啥，于是就用了floyd暴力搞的，然后一比较，代码量还差不多。源代码：#include <iostream>#include <algorithm>#...
2020-04-12 17:55:06
194
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人