- 博客(44)
- 收藏
- 关注
RSS订阅原创 CSP2020
感觉自己心态挺好的，就是没什么分看看t1感觉有点大模拟的意思，直接看t2了，写加调十分钟然后看t3，想了半小时正解没想出来，然后去写t1了，五点半左右写完然后没时间了，t4 70没写完，t3写了个20微笑着退役...
2020-11-07 20:47:15
152
原创 LuoguP1389
简单区间dp观察合法序列定义等价于以下条件对于一个序列，有且仅有一个kkk使得ai=ai−1+1,i<=ka_i=a_{i-1}+1,i<=kai=ai−1+1,i<=k且ai=ai−1−1,i>ka_i=a_{i-1}-1,i>kai=ai−1−1,i>k考虑算出删除某段区间的最大价值fi,jf_{i,j}fi,j在序列自动机上遍历即可转移注意：直接转移难以通过，考虑如下优化Vi=max(Vi,Vj+Vi−j)V_i=max(V_i,V_j+V_
2020-06-05 16:39:19
156
原创 csp2019
Day0还行Day1环境十分好，没 有 不 适看完t1，十分傻逼，两分钟写完了看看t3，不太行啊，好像不太会，滚回去了看看t2，很像一个dp啊，开始推一个n^2dp，然后想优化，想 不 出 来再回头看t3，感觉链部分分很好写啊然后就10分滚粗辣Day2t1看起来是个数数题，但是我不会数，直接抛了t2看起来很清新很可做啊，再看看t3t3 55分很好写啊 写了半小时写完了，虽然...
2019-11-17 17:29:27
388
原创 20190729
分治普通分治：通过将区间分成两个区间，来将问题分成两个⼦问题二分：对答案分治整体二分&CDQ分治：离线分治算法点分治：找重心分治图论Dijkstra：找最小的dis[x]，x一定确定了最短路，只可解决正权（可用堆优化）Bellman-Ford：枚举并不断进行松弛SPFA已死 ：队列优化的Bellman_Ford，可用于判负环Floyd：设F(K,X,Y) 表示X 到Y 的...
2019-07-29 19:34:44
652
原创 20190728
基础概念随机变量：有多种可能的取值的变量P(A)P(A)P(A)：事件A发⽣的概率E(X)E(X)E(X)：随机变量X 的期望值，E(X)=∑P(X=i)∗iE(X)=\sum P(X=i) * iE(X)=∑P(X=i)∗i独⽴事件：互相不影响的事件，满⾜P(AB)=P(A)P(B)P(AB)=P(A)P(B)P(AB)=P(A)P(B)对于独⽴事件，有E(AB)=E(A)E(B)E(...
2019-07-29 19:06:45
83
原创 20190531
四题暴力一题找规律T1给出一个正整数 n，现在问存在多少个 x，使得 x在十进制下的每一位之和加上 x 等于 n看了半分钟之后发现n位和必定小于等于81，直接枚举**T2 **蓝月商城出新技能书了！！如果古天乐想购买“旋风斩”，则他需要花费A元；如果古天乐想买“半月弯刀”，则需要B元；如果古天乐两个一起买，则需要C元。蓝月的设计师非常有头脑，每样商品的利润都是相同的。即假设旋风斩和...
2019-06-01 13:36:26
146
原创 20180818模拟赛
T1: 有一个区间，将一个区间[l,r]分裂为若干个区间（可有间隙）（允许区间与下一个区间相交1长度），使得价值若干个区间的ar−alar−ala_r-a_l的和最大 操作： 1.询问分裂[l,r]区间的价值 2.将[l,r]变为等差数列n,m&lt;=200000一开始想到将大区间划分为一堆递增区间，然后用类似于分块的处理方法处理，后来觉得不一定对，而且处理下降序列比较复杂，还比...
2018-08-18 15:37:08
246
原创 20180625模拟赛
暴力AC还行T1 statistics 数列统计看到这个题莫名想到昨天晚上死命想优化的车厢重组就知道应该是个数据结构，但是由于车厢重组线段树写挂了觉得比较难搞，所以写了个暴力=_= O(n2)O(n2)O(n^2)蜜汁80还行 for (int i = 2 ; i &lt;= n ; i ++) { long long duang = 0; ...
2018-06-25 20:12:40
190
1
原创 20180624模拟赛
（锅真多）（起码没坑）T1 sum（保护血槽）看起来非常基础，事实上也很基础有一定的思维难度 （听说有人枚举点O(n3)O(n3)O(n^3)做=_=）我写的是O(n2)O(n2)O(n^2)的，先破环成链，就可以乱搞了： for (int i = 1; i &amp;lt;= n ; i ++) { int sum = 0 ;//血量 ...
2018-06-24 17:37:51
222
原创 USACO 2010 ice题解
一道比较水（恶心）的bfs题 【题面自行度娘】 在当前位置时，找出上下左右的石头，拓展状态即可。 为了优化时间可以使用二分找石头。 （自行脑补代码复杂度）需要这么多的二分，那怎么办呢？ C++的STL又不是白开放的 （P党就只能写一堆二分了）（由于代码蜜汁不能A，只发不大可能错的代码段）首先，可以使用两个map让每块石头的坐标互相关联for (int i = 1; ...
2018-06-24 13:07:57
228
原创 莫队算法 无修
无修莫队无修的莫队算法，是用来处理没有修改操作的序列的询问操作的离线算法 莫队算法的本质是什么？ 大概就是分块加上一个大家可能都想到过的东西 也就是一个区间1l-r，其左边的区间2 (l - 1) - (r - 1)的和转化到区间1的和只需要O(1)的时间复杂度 也就是sum1=sum2+a[r]−a[l−1]sum1=sum2+a[r]−a[l−1]sum1 = sum2 + a[r...
2018-06-02 20:55:19
398
原创 Dirichlet卷积和Mobius反演的一些基础知识整理
Mobius函数如果d = 1，μ(d)=1μ(d)=1\mu(d) = 1 如果d为k个互异质数乘积 则μ(d)=(−1)kμ(d)=(−1)k\mu(d) = (-1)^k 否则μ(d)=0μ(d)=0\mu(d) = 0Dirichlet卷积两个函数f,g的Dirichlet卷积为(f∗g)(n)=∑d|nf(d)g(n/d)(f∗g)(n)=∑d|nf(d)g(n/d)(f...
2018-06-02 15:01:05
311
原创 CQOI2007 余数求和
给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29设G(n,k) =∑ni=1kmodi∑i...
2018-06-02 14:10:21
257
原创 左偏树的简单实现
左偏树，顾名思义，就是向左倾斜的树这棵破树就是用来实现可并堆的，也就是说，是比堆多出了一个合并的操作左偏树的定义是：左边的节点个数大于右边的节点个数这就使其可以资瓷合并的操作比二叉堆的O（size1 + size2）快多了 这是O(logsize1 + size2)三个性质（代码中要维护的三个性质）【还是从1开始吧】当前节点的键值小于等于或大于等于它的左右儿子的键值（堆性质）当前节点的左儿子的深度...
2018-06-01 16:06:01
404
原创 18/4/19赛【个人】【ACM赛制】
又壮烈牺牲了A 观察题目描述，容易得出i和j两根串串能插min(L_i,L_j)块肉的结论。 则可以对L进行从小到大的排序，L的奇数和即为答案（奇数和为答案是因为奇数<=下一个偶数，将每个奇数和下一个偶数配对）（懒得证）B 一个显而易见的姿势：-x+x=0 所以我们可以得知：向左x步后，再向右x步，会回到原点；向上x步后，再向下x步，也会回到原点。 （好像数轴也可以说） （先说判...
2018-06-01 12:35:30
1914
原创 矩阵切割 【二维DP】
这是一道二维DP的水题设置状态：dp[i][j]表示i*j的矩形最少能切割的正方形预处理：1*1的矩形必定只能切割成1个正方形，所以预处理可以这么做 for (int i = 1 ; i <= min(n, m) ; i++ ) dp[i][i] = 1;DP：可以设置dp[i][k] + dp[i][j - k]表示第一种切矩形方法的最少正方形 dp[k][j...
2018-06-01 12:33:26
1821
原创 基础贪心题选讲
#171. 智力大冲浪题目描述小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti时时间段之前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣...
2018-05-31 18:05:57
387
原创 20180531考试
又双叒叕炸了。T1 lucky从x + 1 枚举到 10 ^ 6 - 1即可T2 gcd一般思路：O（n ^ 2）求gcd(a[i], b[j] )文艺思路：不知道2B思路：O（n ^ 2）求gcd(a[i], b[i] ) （然后就只过了两个点（还能过两个点））T3 purchase一看只有五个品牌，想写个可并堆骗分然后是个可并堆的都被我忘了然后就写了个priority queue暴力查找完就T...
2018-05-31 13:42:48
213
原创 网络流-费用流
这个好像不考没事可以骗分费用流，顾名思义，就是有费用的流，也就是说，给一个网络流图中的每条弧增加一个单位流量费用。一般来说求解的费用流都是最大流最小费用。好像没什么好BB的这里推荐使用zkw算法求解最小费用流，看着代码理解就行，应该还是很好理解的。（zkw算法在稠密图上跑得飞快，在稀疏图上还不如直接SPFA）#include <bits/stdc++.h>using namespac...
2018-05-28 19:52:01
660
原创 状态压缩DP
状态压缩，就是用二进制来作DP的状态，用位运算来转移状态二进制操作左移x<<y表示将二进制x的每一位向左移y位，在末位补0例：001011<<2=010110<<1=101100x<<y=x*2^y右移x>>y表示将二进制x的每一位向右移y位，末位为1时舍去例：01010>>2=00101>>1=00010由于会舍
2018-05-26 20:14:47
427
原创 网络流-最小割
割割是一种对网络流点的划分方式 对于一个网络流图G(V,E)，划分为S和T两部分，其中T=V-S，源点s∈S，汇点t∈T 净流f(S,T)表示穿过割(S,T)的流量之和 f(S,T)=Σf(u,v) | u∈S,v∈T 割的容量C(S,T)为所有从S到T的边容量之和 C(S,T)=Σc(u,v) | u∈S,v∈T f(S,T)算穿过割(S,T)的正反向边，而C(S,T)只算正向边...
2018-05-26 17:51:49
449
原创 网络流-最大流
网络流在有向图G(V,E)中 有一源点S，入度为0 有一汇点T，出度为0 任一弧(u,v)有一非负流量c(u,v)最大流可行流：在容量网络G中满足以下条件的网络流f,称为可行流. 0&lt;=f(u,v)&lt;=c(u,v)（弧流量记为f(u,v),弧容量记为c(u,v)） 流入一个点的流量等于流出这个点的流量（除源点和汇点）最大流：在容量网络中，具有最大流量的可行流，...
2018-05-24 16:02:14
961
原创 分治的一些基础应用
分治，通常是有分和治，对于“分”来“治”，再合并，就是分治的思想。二分查找这是一种O(logn)的查找方法。在单调的序列中，查找一个数，有个猜数字的游戏是酱紫的：给出一个范围1-1000 让你猜一个数，会告诉你这个数是大于答案还是小于答案通过二分查找的思想，这个游戏可以在10次内猜出答案。转化为二分的模型是酱紫的：一个数列{1,2,3,4,5,……,1000}，找到...
2018-05-22 17:08:35
391
原创 20180522考试
combo范围很小，朴素就行 for (int j=0;j<=B;j++) { int a=A-j,b=B-j; if (a+b+j==C) { printf("%d\n",j); break; } } surface这破题题面看了一年终于发现输入要从上面往下看。。对于(i,j)上的柱子（暂...
2018-05-22 13:13:00
238
原创 栈与队列三题
作弊的发牌者：贝茜正在与她的N-1(2 <= N <= 100)个朋友打牌。她们玩的牌一副为K(N <= K <= 100,000，K为N的倍数)张。所有牌中，一共有M(M = K / N)张“好牌”，其余的K - M张为“差牌”。贝茜是游戏的发牌者，很自然地，她想把所有好牌都留给自己。她热衷于获胜，即使为此必须采取一些不正当的手段。在若干局游戏后，贝茜的朋友们开始怀疑贝茜...
2018-05-15 14:55:19
566
原创 20180515考试
T1mai书【我也不知道哪个mai】直接模拟即可，但要注意：两张5元比一张10元更加灵活，所以在处理20元时，优先选择找一张10元和一张5元的，3张五元的是下策。T2立方体p坐标没什么卵用，不管在哪里答案都是一定的，没有边界啥的。根据样例可用显然法推出答案是组合数。然后再用快速幂和费马小定理一搞就星。T4函数最值没想AC，写了个暴力递推，一个一个+1再瞎处理就没了 if (++newnum[1]=...
2018-05-15 13:22:43
202
原创 基础图论梳理
图的存储：目前主要的方式有三种：邻接矩阵定义：bool b[max_l][max_l];插入：b[x][y]=true;查询：if (b[x][y]);邻接表定义：struct hazaking{ int y; int next;}e[max_l];int linkk[max_l];插入：e[++t].y=Y;e[t].next=linkk[X];linkk[X]=t;遍...
2018-05-14 15:53:16
326
1
原创 20180513测试
这次竟然没爆炸T1立方数给出T个数p询问是否是立方数。直接一个二分就OK（然后就差点忘记了long long）while (l+1<r){ long long mid=(l+r)>>1; if (hzk(mid)<x) l=mid; else r=mid;}T2立方差给出T个质数p询问是否可以表示成立方差的形式这里先对立方差a^3-b^3进行因式分解，得...
2018-05-14 13:14:44
222
原创 经典区间DP
区间DP，就是在区间上做DP（谁都知道）要搞一个区间，就需要一个双重循环：（写法一大堆，这是其中一种）for (int len=2;len<=n;len++)//枚举区间长度len for (int i=1;i<=n;i++)//枚举区间左端点 int j=i+len-1;//计算区间右端点 然后balabalaDP就好了石子合并：在操场上沿一直线排列着n堆石子。现要将石子有次序...
2018-05-13 18:31:47
288
原创 四道树状数组模版题
概念与实现就（lande）不写了，反正一大堆#532. 数星星（严格来说其实不是模版题，但由于实际编码接近模版题，当作模版题来说）题目描述天文学家经常要检查星星的地图，每个星星用平面上的一个点来表示，每个星星都有坐标。我们定义一个星星的“级别”为给定的星星中不高于它并且不在它右边的星星的数目。天文学家想知道每个星星的“级别”。 5 ...
2018-04-17 15:52:41
355
原创 入门DP练习赛第二次爆炸记
本来想补上一次，然后懒得补了 忘掉了马拉松拿到手觉得是SB题f[i][j]表示通过第i个检查点后且已经跳了j个检查点时的最小时间然后………………然后就暴力顺推然后就炸了（手动和DFS对拍了几次，都没有出错，这只能说明非酋了）养周奕博拿到题的感觉是这样的：这NM什么题看完之后感觉要排个序，不然感觉无从下手啊。排完序之后：这NM什么玩意儿，感觉要套个完全背包啊。下面没有了Bessie的派（这题了不得，...
2018-04-17 15:02:05
248
原创 线段树瞎搞
#501. 【线段树模板题】序列操作1操作1：单点替换操作2：求区间最大值单点替换不用写tag炒鸡开森单点替换void tinsert(int p,int l,int r){ if (r<k1 || k1<l) return; if (l==r) { nodes[p]=k2;//替换 return; } int mid=(l+r)>>1; ti...
2018-03-17 09:53:30
247
转载 转 超有爱的并查集
原http://blog.csdn.net/niushuai666/article/details/6662911例子就是杭电上的畅通工程：http://acm.hdu.edu.cn/showproblem.php?pid=1232首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你
2017-12-21 09:39:52
233
原创 莫名其妙的神奇背包
今天要谈论的是一堆奇形怪状、莫名其妙、精灵可爱的背包。416.采药最基础的01背包模板题，随随便便DP即可。for (int i=1;i<=n;i++) for (int j=m;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+b[i]);417.集合求和01背包求方案数。for (int i=1;i<=m;i++)//从1-m枚举使用的
2017-11-09 13:02:44
321
原创 11.8模拟赛总结
今天又打了一场挫信心赛，感觉对一等奖更有(mei)信心了呢。 1.字串比较（5分钟 100分） 读入字符串巴拉巴拉，全部处理成大写巴拉巴拉巴拉，从3-n判断是s[i]s[i-1]s[i-2]s[i-3]组不组成“NHOI”巴拉巴拉巴拉巴拉，统计个数巴拉巴拉巴拉巴拉巴拉。 2.两个数（25分钟 60分） 看到这道题就知道肯定不简单，当然了，连字体颜色都变了能不简单吗。
2017-11-08 19:46:11
231
原创 DFS优化
DFS是常用的暴力方法，但由于其O（n!）的效率，有时难以通过较多数据点，所以需对其进行剪枝。范围剪枝：（一种可行性剪枝，拉出来单独讲） 有时DFS的范围较大会导致TLE，这时需根据题意缩小搜索的范围。例如：需要搜索一个n位数，但需要其低位数字保证比高位数字大。例如12345是合法的，但12354是不合法的。 比较差的思想是先做一遍全排列，如果已经做完一遍，再判断这个排列是否满足条件。 优
2017-11-08 10:34:00
1901
原创 11.7正睿OI第八场模拟赛总结
真的恶心购物（10分钟 100分）(shop.cpp/c/pas)【问题描述】YJC最近在steam上氪了不少金，但他还想氪更多。steam保证了不同的两款游戏的价格一定不同，并且游戏的价格一定是正整数。现在YJC已经买下了n款不同的游戏，价格分别为a1、a2、...、an。YJC手头还有m元，他想知道他最多还能入手多少款他没有的游戏？【输入格式】第一行包含两个
2017-11-07 19:24:23
516
原创 11.7计划
上午 练习暴搜大法DFS大法，巩固并熟练BFS大法。下午 打正睿OI的第八场NOIplus普及组模拟赛。晚上 修改程序写模拟赛总结巴拉巴拉。
2017-11-07 07:36:32
205
原创 二分总结
几年几个月没打二分感觉都不会打了。擦护栏题目描述Jzyz的所有学生获得了一个大扫除的机会——去大街擦护栏。 Jz市大街被分成了M段，每段的长度不一定相同。Jzyz一共有N名学生参加劳动，这些学生将分成M组来完成这项工作，因为长度不同，分配的任务量肯定不同，现在，负责这次大扫除的老师想知道，擦护栏长度最多的同学最少必须擦多长的护栏，这样才能保证尽可能的公平。当然，可以有学生当拉拉队，
2017-11-07 07:14:47
546
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人