- 博客(177)
- 收藏
- 关注
RSS订阅
原创 关于本博客
2017~2019 为noip时期，多为做题感悟现在的我并没有选择计算机，反而去向了与之不大相关的专业今后将会以兴趣爱好为目的继续学习计算机知识
2020-05-07 13:25:15
195
1
原创 闲得无聊之机器码和字符串的互相转换
有时我们会在网上看到一些人发一堆机器码，试图加密对话，虽然我们可以上网找在线转换器，但是还是自己写一个用起来方便一点机器码~字符串#!/usr/bin/env python3ans = ''while(1): t = input().split() if t == []: break for i in t: ans += chr(int(i, 2))print(ans)字符串~机器码#!/usr/bin/env python3t = input()cnt = 0for i
2020-06-13 16:21:35
1187
原创 python 一元二次方程计算器
萌新练手import mathdef qua(a, b, c): a1 = -b - math.sqrt(b * b - 4 * a * c) a2 = -b + math.sqrt(b * b - 4 * a * c) x1 = a1 / (2 * a) x2 = a2 / (2 * a) return x2, x1a1, b1, c1 = map(int, input("☆一元二次方程计算器☆，请输入a,b,c系数，以空格隔开！\n☆输入0 0 0可退出程序☆\n\n").split()
2020-05-18 15:18:57
1063
2
原创 python入门学习日记
python基本操作第一次运行python命令行：windows下输入cmd进入的操作界面python交互模式 在命令行中输入python跳转的操作界面，要注意输入python前须保证命令行目前所处盘符为于python安装盘中（一般为系统盘）。一般交互模式用作调试。可在命令行下执行一个python文件 python test.py(sublime真好用)输入和输出...
2020-05-11 16:35:14
211
原创 P2161 [SHOI2009]会场预约 - 线段树染色
是真的染色，把不同预约看做不同颜色，现在问题就是一个区间内不同颜色的数量，这个分块线段树都能做吧（不考虑复杂度用莫队也行）注意，线段树的最大边界必须是定值，不能随输入改变（一开始懒得离线动态更新右端点然后节点的编号就串了）注意数组大小，因为same和tag数组都是针对线段树节点设置的，所以其数组大小也要开4倍#include <algorithm>#include <io...
2018-10-08 11:29:01
246
原创 P2918 [USACO08NOV]买干草Buying Hay - 完全背包
枚举上界还是好确定的，至多买h + 5000磅干草，因为一捆干草至多重5000磅#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define debug(x) cerr << #x &l...
2018-10-08 08:46:12
314
原创 P3224 [HNOI2012]永无乡 - 平衡树 - 并查集
开n棵平衡树，慢慢合并成一个，用并查集处理连通关系，平衡树处理第k大就好了因为重要度是不会有重复的，而且是从1到n的，可以开一个数组，表示重要度为k所对应的编号要善于把一个新问题转化为一个已解决过的问题我甚至想自己搞出一个新算法处理连通关系，但是用并查集不就好了吗思维定势：一个题只用一个学过的算法实际上用平衡树处理了第k大之后，现在只需要思考如何处理一些点的连通关系，那么并查集就是最适合...
2018-10-07 20:04:21
245
原创 P2023 [AHOI2009]维护序列 - 线段树区间乘法加法
记得及时更新sum（每次修改都更新），写成一个update函数比较好，因为很多时候会忘了%还有懒标记是标记在这个点本身上的然后就是左儿子和右儿子一定要看清楚。。。一个是n * 2 ，一个是 n * 2 + 1 ，涉及到这部分的代码一定要专注乘法标记优先级大于加法，并且对加法标记也有作用若要增加加法标记，先让乘法标记作用一下加法标记，再增加加法标记然后注意乘法标记要初始化为乘法单位元，就...
2018-10-07 10:08:59
304
原创 P1484 种树 - 堆 - 贪心
这题想得脑阔疼。。。我只想到可以选一个点，或者不选这个点选其左右两个点的和先来特殊情况，k=1, 然后k=2可以发现由1到2的过程中，可以是一个本来被选的点，替换为他左右两边的点，收益增加了a[pos+1] + a[pos-1] - a[pos]这个题是一个个选，直到选了k个，有种递推的感觉，先确定种了前面几个，再确定这一个该怎么种然后我不会处理若有别的点也选上，并且影响到这个pos+1和...
2018-10-06 19:49:53
237
原创 P3368【模板】树状数组 2 - 差分
建立两个差分数组，套公式就好了c[i]表示i元素的“增量”，下面的式子左边是序列从1 ~ x的前缀和整体增加的值∑i=1x∑j=1ic[j]=(x+1)∑i=1xc[i]−∑i=1xi∗c[i]\sum_{i=1}^x\sum_{j=1}^ic[j] = (x+1)\sum_{i=1}^xc[i] - \sum_{i=1}^xi*c[i] i=1∑xj=1∑ic[j]=(x+1)i=1∑x...
2018-10-05 17:11:20
218
原创 P2055 [ZJOI2009]假期的宿舍 - 二分图最大匹配
把人和床分开考虑，题目说每个人只能睡和自己直接认识的人的床，就是一种边的关系，但是并不是人与人，实际上人与人之间连边是很难处理的，但是如果把人和床连边，就是一张二分图，左右两边分别是不同的东西，然后求一下最大匹配就好了没思路的时候换换角度，看能不能搞出什么“新东西”来注意多组数据不超时的情况下能用memset尽量用，有时候感觉某个数组可以不清空但实际上是需要清空的还有注意连边的时候没那么简单...
2018-10-05 16:31:04
213
原创 P1273 有线电视网 - 树上背包
树上背包看作分组背包就好了，收益临时变成负数也是可以的，并且收益的数值也很大，所以不再让收益当下标，放到数组里保存，设f[x][t]表示以x为根的子树中选择t个人观看节目，电视台的最大收益（让你求什么反而不一定要存在数组里面，可能是设为数组下标再判断可行性）这题比较特殊，一般分组背包是过不了这么大数据的，但是因为实际有效的叶子节点十分少，所以可以优化（看注释）另外注意f数组初始值的设定#in...
2018-10-04 21:14:54
149
原创 Prim模板
#include &lt;algorithm&gt;#include &lt;iostream&gt;#include &lt;cstring&gt;#include &lt;cstdio&gt;using namespace std;#define debug(x) cerr &lt;&lt; #x &lt;&a
2018-10-04 09:23:54
474
原创 P2577 [ZJOI2005]午餐 - 贪心 - dp
首先考虑只放一队的情况，显然是吃饭时间长的优先打饭，然而我没这么想直接套了国王游戏的模型，事实上还是从别的角度多想想比较好然后是dp，这道题怎么安排人到不同的窗口很难说，所以考虑用最暴力的状态和转移（反正数据范围小）设f[i][j][k]表示安排了前i人，第一个窗口的打饭总时间为j，第二个窗口打饭总时间为k，最优集合时间是多少然后决策一下每个人在哪打饭，并且注意一下答案的更新但是会爆内存，...
2018-10-04 07:59:35
166
原创 P1726 上白泽慧音 - 强连通分量模板
虽然是模板但是却提醒我有向图一定要试着从每个点出发，不仅仅是因为图不一定连通，更有可能是只从1号点出发哪也去不了的情况#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <stack>using namespace...
2018-10-03 16:21:36
171
原创 P1993 小K的农场 - 差分约束
看出不等式之后，通过移项套模型大概不等式模型是这样的：xv&amp;lt;=xu+w(u,v)x_v &amp;lt;= x_u + w_{(u, v)}xv&lt;=xu+w(u,v)xv−xu&amp;lt;=w(u,v)x_v - x_u &amp;lt;= w_{(u, v)}xv−xu&lt;=w(u,v)从减数到被减数连边长得和最短路的三角形不等式似的所以求解也...
2018-10-02 16:10:42
220
原创 P2346 四子连棋 - 迭代加深
难点是想到颜色可以为O，搜索的过程中可能会把一个O移动到另一个O上面，然后搜索的颜色参数就变成O就错了。。。也没什么好办法，就是判到O直接跳过。。。另外，要习惯把各种量写在参数表里，这样能省很多代码。。。也更好调试#include <algorithm>#include <iostream>#include <cstring>#include <...
2018-10-01 16:06:55
350
原创 BZOJ1878 [SDOI2009]HH的项链 - 莫队
交到洛谷上只有80分。。。注意初始值 l = 1， r = 0然后就是修改的部分（revise）我套用了之前的习惯，直接传值进去，直接+=k然后判断是否为1或者0，但是我没有想到1可以是0+1得来也可以是2-1得来所以想安全一点就写if和else吧。。。有时候真的难以想到这种可能指针移动的时候注意，每次移动前，l和r所在的点已经被算入答案，如果l现在的点不是所在区间里的，直接移动如果...
2018-09-30 17:46:16
176
原创 P2473 [SCOI2008]奖励关 - 期望（神奇的倒推） - 状态压缩
大力模拟各种情况k * n 的模拟出每次可能抛什么出来设f[k][s] 为前k个物品状态为s时得分最大值但是有问题啊，比如 113 和 133，状态都是f[3][101]，难道我还要多开一维存下不同情况？，不行吧？还是说取最大的？，这相当于后面选择的物品，对前面的状态强行选择了一下，但是并不是说113比133大，我就舍弃133，我舍弃133就相当于，走到这一步，后面直接都不走了，如果说我们...
2018-09-30 15:04:59
304
原创 P2596 [ZJOI2006]书架 - 无旋treap
fhq treap多么强劲。。。当用无旋treap解决区间/序列问题时，其实每个点所存的值不再对树的形态产生影响，复杂度由随机优先级和堆结构来保证。这棵树不是以点的值为关键字，而是以点的值在序列中的位置为关键字但是需要一个操作，给出点的值，我们找他在序列中第几个位置似乎用原来的那些treap操作都难以实现，这个点的位置就是第k大，但是现在没有根据来找第k大，因为不是按点值排序而仅仅是靠位置。...
2018-09-21 17:06:41
279
原创 P1108 低价购买 - DP - 基于dp数组求方案
首先求一遍最长下降子序列然后考虑到方案会重复，而避免重复是件挺难的事，不妨先考虑不管重复求方案那么如何求方案呢，设pl(i)表示以i为结尾的最长下降子序列方案数，因为表示的是最长的序列，所以只有在i前面，比i大，最长序列长度还恰好比i小1的可以方案转移到i上然后删掉那些重复的，但是重复的实在难以判断，但是仔细想想也许不必删除，只需要消除某些点的影响就好了我们在统计方案的时候，是一个转移，但...
2018-09-20 15:41:58
190
原创 Codeforces #510 1042 div2 ABC
这次比#509多考了800分左右结果反而掉rating了，据说是这次参加人数少。纠结ing &amp;gt;_&amp;lt;A. Benches给定n个正整数，现在要把数字m拆一拆分配到这n个正整数的某些上面，设k为分配后这n个数最大的一个，求k可能的最小值与最大值先求出目前最大的数maxa，k一定是maxa加上一些分配到的数，首先明确的是k一定大于等于maxa，不可能小于，那么先把其他数字分的和maxa...
2018-09-17 21:19:44
215
原创 Codeforces #509 div2 1041 ABCD
A 给你一个n个索引 键盘都是从某个数开始索引的，而被盗取会使得索引不完全 求被盗键盘的最小值 B 求w&amp;amp;amp;amp;amp;lt;=a, h&amp;amp;amp;amp;amp;lt;=b 且w/h = x/y 的正整数对(w, h)的个数 x/y就是最好的优化方式！ 满足要求的w/h 等于 k * （x/y） 也就是说(w, h) = (kx, ky) 当有一个值超越a或b时停止 有坑点！！！ 先把x/y化为最简分数...
2018-09-17 08:03:18
315
原创 P2887 [USACO07NOV]防晒霜Sunscreen - 贪心
貌似这种区间贪心题多数是排序加堆来做。。。使尽量多的奶牛被抹，需要用最贴近他下限的防晒霜去抹，考虑完他的下限是否可行之后，还要考虑那些要使用相同防晒霜的奶牛，应该优先分配给上限最低的 奶牛按下限，防晒霜按低排序后，对于每一款防晒霜，把下限符合奶牛的都放到堆里，找出上限最低的，抹上就好了这道题我一开始没贪全，因为只考虑了左端点，连右端点是否可行都没考虑。。。而考虑到了右端点可行后又没考虑多...
2018-09-16 21:40:15
386
原创 P2051 中国象棋 - DP - 包含了一些dp时常见的小错误
可以三进制状压，写个进制转换函数，可以存在整数型数组里，然后预处理一下，跟二进制没啥差别。。。 但是难写，数据范围也不够一个化繁为简的思维方式我们不需要知道棋盘具体的状态，准确来说，对于“同构”的棋盘状态(虽然同构不是这个意思，但是我找不到别的形容词了。。。)，可以用一个棋盘状态去代替，只要这个状态所对应的值是所有“同构”的方案之和，就可以等效替代比如说目前有三种棋盘状态，但是可以忽...
2018-09-16 13:26:19
181
原创 洛谷9月 T1 反思
思路要灵活，要灵活，要灵活，灵活地发现自己走的方向错了，灵活地解决目前的难题 要区分目前是遇到问题还是求解速录不对 别一条道走到黑，也别看到困难就放弃，如果说有一种方法可行只是应用的范围小时间长，想办法解决，因为这种方法至少能解决很小范围内的问题（比如这道题开longlong也只能解决m很小时候的情况），那么应该试着找到一种办法扩展这种做法，使得其能解决更大范围，而不是遇到困难就换方向。 同...
2018-09-16 08:37:17
174
原创 P1169 [ZJOI2007]棋盘制作 - 单调栈
这题真是难想。。。按奇偶性分类其实是套路。。。 把坐标和为奇数的^=1一下，然后满足要求的棋盘要么全1要么全0，然后求解答案，把矩阵全^=1一遍再求一次答案就好了，两次求解总有一次棋盘是全0 对每个点预处理以下他往右最多有几个0，枚举一下矩形左边界所在的列，然后枚举矩形下边界的行，用预处理的东西往上跑一下取个可行的，但是这样有点慢，可以用单调栈维护一下每个点的预处理值。。。因为当栈里进了个小于...
2018-09-15 07:24:41
271
原创 P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper - 状压
似乎状压也可以有阶段？看做广义的线性dp，这道题是以“组数”为阶段，对比互不侵犯，那题是以行为阶段。 这类题有个特点，每个阶段不是一个单纯的数，而是一行，一列，一个待填充的东西 而我们状压，一次填充一个阶段（在同一个阶段中有多个元素进行了转移），再进行下一个阶段，就又成了“线性问题”阶段应该是最外层循环这题可以看出来阶段是电梯数（想象最优解方案是先坐满一个电梯，剩下的再坐别的电梯），电...
2018-09-14 17:34:42
200
原创 P4427 [BJOI2018]求和 - 预处理 - 树上前缀和/树剖
因为k是动态的所以难以维护，但是发现每个点的权值是深度，但是发现了又如何。。。还是难以动态维护。 但是发现k太小了。。。时限又比较大，直接预处理出来1~50次方和，线段树搞一下就行了#include &amp;amp;amp;amp;lt;algorithm&amp;amp;amp;amp;gt;#include &amp;amp;amp;amp;lt;iostream&amp;amp;amp;amp;gt;#include &a
2018-09-14 08:25:00
350
原创 树链剖分模板
注意 求子树时，要用子树dfs序连续这个特性，但是不能用如下方法（sub表示x的子树中最大的dfs序）：void dfs2(int x, int t) { top[x] = t; dfn[x] = ++cnt; subcnt = max(subcnt, cnt); rnk[cnt] = x; sub[x] = cnt; if(!son[x]) ...
2018-09-14 07:13:12
128
原创 分块 学习笔记
分块是一种通用的暴力算法，可以用暴力的思想维护一些值，但复杂度却不是很高 把区间每n−−√n\sqrt{n}个分成一个块，最后不足的也算一个块 分块的思想大体是“大段维护，局部朴素” 对于小区间朴素修改，对于大区间结合懒标记进行维护 因为可能询问和修改的区间十分大，l，r之间会有许多块，这个时候把l和r不足一整个块的部分直接暴力（朴素）遍历一遍，对于那些一整个块都被包含在l，r之间的可以进...
2018-09-13 16:59:50
220
原创 set和multiset 找前驱后继
multiset适用于元素可重，set中的元素不会重复。 找x的前驱后继的时候，建议用lower_bound和upper_bound来找，而不是用find，因为x可能不是multiset中的元素。 set :: iterator it 找前驱：lower_bound（val）之后 it-- 我不知道为什么it--找到了前驱而不是和一个值也为val的元素 找后继：upper_bound之...
2018-09-12 17:02:51
3116
原创 洛谷P3396 哈希冲突 - 根号复杂度算法
我一开始打了个暴力，直接n^2枚举。。。看哪个同余x，但是有个办法能更快一点，复杂度取决于模数p。可以发现其实不用一个个去检验哪个同余x，因为是从1开始到n找出所有同余x的正整数，由题意x一定小于等于p，所以所有和x模p同余的整数就是x+k*p 从另一个角度来说，做题的时候一定要从原本描述中抽象出核心含义，这道题问x池内的综合，就是问所有模p同余的下标对应的数之和（抽象出题意有助于帮助我们想起以...
2018-09-12 10:47:59
339
原创 POJ2443 Set Operation - bitset
题意：给出n个集合(n<=1000)，每个集合中最多有10000个数，数的范围：1~10000，给出q个询问(q<=200000)，每次给出两个数a，b判断是否有一个集合中同时含有a，b两个数 因为集合数少而集合所含的数多，在位运算时若加快速度，就要减少bitset存的位置 所以我们开10000个bitset，每个bitset存数字i所在哪个集合，比如集合1，2，3中都有数字5，...
2018-09-12 08:52:05
152
原创 fhq treap（无旋treap） 学习笔记
首先最好要会写treap（也先了解一下笛卡尔树是什么。。。） fhq treap和treap同样有一个随机分配的rnd值，用于平衡，但fhq treap不需要旋转操作来维持平衡，因为有两个神奇的操作merge和split在两种操作之前，要明确的一点是fhq treap依靠rnd值来维护平衡，把每个点按照小根堆的方式放置，即根rnd小于子rnd，并且在任何时候都要保证有二叉搜索树的性质，即左子...
2018-09-11 19:32:59
1819
1
原创 P4880 抓住czx - 最短路
首先求一遍最短路，若我们最后在某个节点能抓到czx，那么我们从起点到这个节点一定是走的最短路，没有必要走更长的路，那样只会更加浪费时间。 而我们到这个点的时间dis[x]是否一定是czx在这个点停留的时间区间【l, r】内？ 不一定吧，我在l之前到也是可以的，因为我可以停下等着，但在r之后到就不行了 题意的“抓”其实有一种误导的感觉，不过样例很好，提示了另一种情形：czx自己找到我们 所以...
2018-09-10 10:16:59
214
原创 P4879 ycz的妹子 - 线段树
对于D操作，我当时开了个sep数组，sep为0（初始值）表示没分，为1表示分了，但这样严重不对！！！ 原因是这道题城市数不是n，而只有一开始的n个妹子都喜欢ycz，所以若未来有一个n+5城市的妹子喜欢ycz，如果用0（初始值）来判断的话，n+1~n+4都被算上了 所以要先读题，然后解释样例，然后想算法，然后写代码，不然容易误解题意，而若后来修正了题意之后，原先根据错误题意写的代码可能有许多错误...
2018-09-10 08:14:44
332
原创 P1441 砝码称重 - 搜索+dp
你会发现 对于这种很像背包的DP。。。不打滚动数组很有可能错，因为很多时候可能会忘记保留以前状态的答案，体现在f[i][j] = max(f[i-1][j], f[i][j]);上，因为f[i][j]可能被f[i][b[i]]更新，所以要取max，若想不取max，则必须保证这个状态只会被更新一次 这题刷表比填表更好写，刷表你的初始化只需要让f[0] = 1 然后用目前的0去更新其他状态 总结...
2018-09-09 16:44:01
170
原创 P1865 A % B Problem - 欧拉筛 - 前缀和
注意筛法的MAXN和MAXNUM之间有差别#include &lt;algorithm&gt;#include &lt;iostream&gt;#include &lt;cstdio&gt;using namespace std;const int MAXN = 1000000 + 100;const int MAXNUM = MAXN - 10;int pri[MAXN],tot...
2018-09-06 17:04:00
135
原创 P1373 小a和uim之大逃离 - DP - 同余
抽象出数学表达，题意求的是使k1≡k2mod(k+1)k1≡k2mod(k+1)k1 ≡ k2 \mod (k+1) 成立的方案数 注意模数是k+1啊，都说了k+1时算作0，k+2时算作1了 其实是数学题。。。 那么k1≡k2mod(k+1)k1≡k2mod(k+1)k1 ≡ k2 \mod (k+1) 其实是比较难求的，除非记录状态，那就要多开一维，思考一下，同余还是可以移项的，现在就是求...
2018-09-04 21:30:34
172
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人