jzq233jzq-CSDN博客

原创身为蒟蒻而找到的好诗！

以下是摘抄：我好菜啊模拟只会猜题意贪心只能过样例数学上来先打表 D P 一般看规律组合数学靠运气计算几何瞎暴力图论一顿套模板数论只会 GCD对我就是这种蒟蒻啦~

2017-09-15 20:24:41 833

原创博客搬家辣~

其实很久以前就已经搬了…… 新博客地址：jzqjzq’s blog 同时的话，这个博客可能就此停更了吧再见，CSDN

2018-04-03 09:35:28 440 1

原创入坑OI一年记事

在此之前，我不算真正的入坑，直到 2016.12.21 我来到sxyz，开始了我真正的OI生涯认识了不少的神犇和dalao，还有一堆找阿的同学。。。 2016.12.24 第一场模拟赛，不知道都打了些什么，貌似挂了。。。 2017.1 正式转C++语言，开始学习新的算法和奇技淫巧。。。 2017.2 寒假只放了7天，据说lc233在除夕夜还在奋勇刷题666 真正学习了一些有趣的

2018-01-04 15:40:36 661

原创倍增+树状数组——BZOJ4551 [Tjoi2016&Heoi2016]树

题面：BZOJ4551 这题在线最优复杂度O(nlogn)O(nlogn)，离线则是O(nα)O(nα)，具体做法网上都有然而我有一个神奇的O(nlog2n)O(nlog^2n)的想法其实和在线线段树差不多如果有一个点被标记，我们把这棵子树的权值全部+1 然后查询的时候向上找到最上面的权值和这个点相同的点倍增一下就好了我大概是石乐至了QAQ#include <cstdio>

2017-12-15 15:49:43 443

原创分块二分——BZO3343 教主的魔法

题面：BZOJ3343 分块二分大暴力！以前初三刚学分块的时候以为这题很难QAQ，现在认为…… 这题实在是water到不知道哪里去了666 我们对于数据分块，然后对块内的数进行排序修改的时候发现如果整个块都被覆盖在区间里面的话，那么就对整个块进行标记（因为整个块内的数都被加上了）两边多出来的暴力修改，然后再次对块内进行排序排序的原因是询问时要对块进行二分询问还是老办法，对于

2017-12-12 15:54:29 224

原创乱搞向——二维坐标系曼哈顿距离和切比雪夫距离转换的简要数学证明

当然这个东西有更好的解释方法。。。这里纯属娱乐233 说正事之前，先定义一些东西定义a(x1,y1),b(x2,y2)(x1<=x2,y1<=y2)a(x1,y1),b(x2,y2)(x1<=x2,y1<=y2)a(x1,y1),b(x2,y2) (x1dist(a,b)dist(a,b)dist(a,b)表示i，j两点的曼哈顿距离注意：这不是在推出来两者的关...

2017-12-05 22:39:21 1601

原创 NOIP2017

一个很简短的标题，也是不想带上情绪写这篇blog。哎呀…… 和去年差不多，又是一次很悬的NOIP（不过应该还没有AFO）day0(11.10) 早上的模拟赛。。。题目是蛮水，然而我又忘记判0啦QAQ 中午出发去衢州，晚上没有试机QAQ，只能和zyy在宾馆复习+颓废这一天就这么平淡地过去了。。。day1(11.11) 昨天晚上没睡好QAQ 考场电脑真心有点废。。。2.4

2017-11-23 21:41:22 336

原创线段树——51nod1466 三角巧克力

题面：51nod1466 想了很久经过点拨之后才想到做法……（NOIP要爆零啦）其实找到关键突破点就知道这题怎么做了。。。这题的关键突破点就是保证起点在反对角线上我们把行和列分开来，记录该行（列）目前还剩下多少巧克力每次对一行进行操作时，我们去找到列上在这一列前面的离这一列最近的剩下的巧克力少于这一列的位置（对列进行操作同理）听起来很拗口是不是？就拿样例解释吧比如我

2017-11-08 23:04:26 213

原创 Codeforces Round #442 (Div. 2) 题解（877A~F）

比赛传送门前几天并没有打这场比赛，但是听说这场题目蛮水的（我的一位初三dalao朋友直接AK了），所以昨天打了打Virtual participation 先上题解： A：直接暴力枚举匹配即可，就是我写得麻烦了一点#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <ios

2017-10-29 22:00:00 311

原创缩点+树上差分——Codeforces555E Case of Computer Network

题面：cf555e 简要题意：给出一个无向图，给出q个询问S，T表示从S走到T。问能否给这张图的边定向，使得满足q个询问我们首先发现对于每一个边双连通分量，两两之间是可以随便到达的，包括去到外面的点。所以我们把边双都缩成一个点，这张图就变成了一棵树对于树进行操作就简单多了，我们只要在S，T，LCA位置打上差分标记（S打向上，T打向下，LCA打消除），然后一遍dfs从下往上扫一遍，如果某个节点向

2017-10-21 07:44:04 368

原创字符串hash——Codeforces533F Encoding

题面：cf533f 简要题意：有A串和B串，两个串被判为相似的条件是满足在多个二元组 (x, y)表示将串中的所有x换成y，y换成x（x，y代表某个字母）之后，两个串相同。问有多少A的子串与B相似一开始想到KMP，但是KMP的话时间复杂度显然不对，那么就想到hash 我们把A串中每一个字母在A串中的位置下标做hash，举个例子，某串形如：abaacba 那么对于字母a，我们把a出现的位置下标的

2017-10-18 20:59:49 487

原创 Codeforces Round #439 (Div. 2) 题解（869A,869B,869C,869E）

比赛传送门 A：我们用s[i]s[i]表示ii这个数在2n个数中是否出现过然后O(n2)O(n^2)枚举每种情况即可要注意s数组一定要开到2∗max(x[i],y[i])2*max(x[i],y[i])左右，否则WA到你怀疑人生。。。#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#i

2017-10-07 12:26:20 283

原创循环矩乘——Luogu3746/BZOJ4870 [SHOI2017]组合数问题

题面：BZOJ4870 Luogu3746 第一次接触循环矩乘。。。首先我们可以考虑DP，f[i][j]f[i][j]表示在i个物品中选取modkmodk下余j的方案数。状态转移很好想，f[i][j]=f[i−1][j]+f[i−1][(j−1+k)modk]f[i][j]=f[i-1][j]+f[i-1][(j-1+k)mod k] 然后发现这个DP可以用矩乘优化，矩阵大概长这个样子：

2017-10-06 08:20:46 339

原创 LCA+二分+树上差分——Luogu2680 [NOIP2015]运输计划

题面：luogu2680 真受不了。。。这么多人AC的一道题目又花了我一个晚上时间做QAQ 所以这种题目就是近年来NOIP压轴题（也不一定是压轴题）的命题趋势？ 13年的货车运输，15年的运输计划，16年的天天爱跑步，所以17年会是啥？如果是这样，NOIP考场上这种题我还能在考试时间内切掉么？简要思路：首先我们肯定要求的给出的计划的LCA和距离啦（这个随便你怎么求）接下来我们二

2017-10-03 22:49:15 241

原创暴搜——Luogu3123 [USACO15OPEN]Bessie Goes Moo

题面：Luogu3123 额为什么这题一开始会没有想到这种很暴力的做法呢？？？因为取模满足分配律，所以这题的暴力复杂度一下子就可以到可以接受的情况了我们用a[i][j]表示字母为i（转化），这个数取模为j的个数所以接下来就是直接O(77)O(7^7)暴力dfs就可以解决问题啦统计答案就是乘法原理辣#include <cstdio>#include <algorithm>#inc

2017-10-02 20:57:51 330

原创可持久化Trie——51nod1295 XOR key

题面：51nod1295 第一次yy出了可持久化Trie哈哈哈…… 这题xor其实就是老套路了，其实就是在Trie树上跑一下就好了我们按照从高位到低位的顺序找，如果这一个二进制位有不同的，那么就往这边走，xor值加上2i2^i即可这题的关键就是区间的问题了，所以就是一个可持久化Trie就可以了具体是怎么yy出来的？按照主席树的写法就可以了#include <cstdio>#incl

2017-09-23 22:26:21 215

原创单调栈+树状数组——51nod1249 近似有序区间

题面：51nod1249 这题题解蛮少的（我没有看官方题解）而且貌似都是线段树，但是讨论里给出了一个很巧妙的做法我们可以先求出第ii位数作为最大值最远能延伸到的左端点b[i]b[i]，和作为最小值最远能延伸到的右端点c[i]c[i]，这个用单调栈就可以了然后我们可以发现对于任意一组i,j(i<j)i,j(i<j)，如果b[j]<=ib[j]<=i而且c[i]>=jc[i]>=j，区间[i,

2017-09-22 21:55:40 506

原创 DP——51nod1486 大大走格子

题面：51nod1486 至于CF原题是什么，我们不去管它这题的DP思路很有趣。首先如果没有不能走的格子的话，n∗mn*m的棋盘的走法数就是Cm−1n+m−2C_{n+m-2}^{m-1}，因为通过转移方程可以很直观地发现是一个杨辉三角现在考虑到有不能走的格子的问题，我们发现只有这个格子左上的不能走的格子会对走法数产生影响，所以我们只要考虑这些格子就可以了。然而我们不能直接枚举行和列，

2017-09-18 13:40:04 441

原创二分+dfs——51nod1307 绳子与重物

题面：51nod1307 看讨论都是说要卡掉O(nlogn)O(n log n)做法的，真是害怕 O(nlogn)O(n log n)就是二分断掉的那根线，check在这之前的绳子有没有断掉的，这个dfs遍历一遍记录重量就好了然而我也很想知道O(n)O(n)的做法啊（并查集）！！！这里只有O(nlogn)O(nlogn)的程序：#include <cstdio>#include <al

2017-09-17 21:36:33 215

原创单调栈+STL——51nod1952 栈

题面：51nod1952 首先数据范围是1e7，复杂度上界肯定是O(n)O(n) 所以我们可以直接往单调栈（或者也可能是队列）这个方面想然而这个东西要资瓷两端插入，一端弹出，这貌似是个双端单调栈我一开始的想法是，维护一个单调递减的栈，如果从后面插入，那就从后面插入维护单调性，如果从前面插入，那就与栈底判断是否要插进去，答案就是栈底啦。。。然而这样有一个很大的Bug，就是弹出的时候就G

2017-09-12 23:14:13 961

题面：51nod1188 emmm就是前一道题的升级版了。。。首先建议去看一下我的前一篇题解：传送门。前一篇题解（就是“最大公约数之和”）是这篇题解的基础首先一维变成了两维，我们还是可以按照原来的思路来做。上一篇讲到求∑ni=1gcd(i,n)我们转成了∑nx|nphi(n/x)∗x，这题继续用本题要求∑ni=1∑i−1j=1gcd(i,j)，那我们可以先转成∑ni=1∑i−1x|iphi(i/x)

2017-09-10 22:43:31 388

原创数论——51nod1040 最大公约数之和

题面：51nod1040 这篇题解只是为了纪念一下好久没有刷数论题的我终于又刷了一道数论水题的题解初一看没有思路（我是数学蒟蒻QAQ）后来发现可以算贡献。。。我们发现本质上是让我们求gcd(n,i)=xgcd(n,i)=x的数目（x是n的因数）再乘上xx就可以了那么如何求gcd(n,i)=xgcd(n,i)=x的数目呢？其实呢gcd(n,i)=xgcd(n,i)=x的数目就是gcd(n

2017-09-10 21:09:42 247

原创 DP——51nod1020 逆序排列

题面：51nod1020 虽然这是5级题的第一个题目，但是作为这种水平的DP的话…… 真的好神啊！！！（我貌似从来没有做过这种推状态转移方程的。。。首先状态就是f[i][j]f[i][j]表示前i个数的排列逆序数的个数从i−1i-1推到ii的话我们可以考虑到ii排在第i−pi-p个位置上，这样就可以产生p个逆序对所以朴素的状态转移方程就是f[i][j]=∑p=0i−1f[i−1][j

2017-09-08 22:08:27 194

原创贪心+线段树（优先队列）——51nod1191 消灭兔子

题面：51nod1191 哈哈哈……脑回路清奇首先我们可以很快想到贪心，我们把兔子的血量从大到小排序，箭按照伤害值从小到大排序，那么我们就可以先做血量多的兔子，这样就可以为血量少的兔子留出箭了因为数据范围有5W，所以可以想到RMQ 其实只要一个堆就可以了，我清（zhi）奇（zhang）地想到了线段树。。。#include <cstdio>#include <algorithm>#in

2017-09-08 13:38:25 231

原创莫队——Luogu3709 大爷的字符串题

题面：Luogu3709 像我这种语文烂到不行的人啊……看题看了个把小时总算看懂了它的操作就是在保持这个集合的严格单调性，如果加进来的数不单调了，这个序列就清空并rp– 这个过程相当于在区间内构造了若干个严格递增序列，贡献就是负的序列个数因为严格递增，所以可以想到答案就是负的区间众数的个数这个用莫队就可以了。貌似主席树也可以做？本题重在语文水平！！！#include <cstdi

2017-08-31 13:15:13 335

原创 Trie——Luogu3879 [TJOI2010]阅读理解

题面：Luogu3879 一开始我感觉好像可以用set搞一搞的然后发现迭代器我实在不太会用。。。而且到底set怎么存我也不大有数后来想了想，还是Trie靠谱就是在结束标记记录一下这里有多少文章有这个单词就好了感觉set原理也是一样的#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>

2017-08-26 19:16:11 398

原创线段树——Luogu3870/BZOJ1230 [Usaco2008 Nov]lites 开关灯

题面：Luogu3870 BZOJ1230 首先让我扯淡一会。。。新高一开学的恐惧。。。 20号开学之后因为一直没有请到晚自修请假来机房的机会一直在教室。。。还有军训QAQ。。。今天我总算回到机房啦！！！回到机房的第一件事当然是先刷道水题啦回到正题。首先你会发现luogu是TJOI的题。。。其实原题就是usaco月赛题其实非常简单，其实就是区间翻转操作所以我们维护一个翻转

2017-08-25 19:32:59 212

原创异或——LibreOJ6087 毒瘤题/LibreOJ6232 毒瘤题加强版

题面：loj6087 我是不会告诉你SW_Wind（就是那个小江）是我同学嘿嘿嘿。。。然而题好像是一个叫做SHENZHEBEI的dalao（也是我同学）出的。。。首先xor有个性质，一个数被xor两次之后等于0 所以k=1的情况就很好搞了，直接一个一个xor过去最后剩下的就是答案了那么k=2怎么做呢？首先我们还是一个一个xor过来，设为p。我们可以发现p=数1 xor 数2（就那两个

2017-08-19 17:06:23 915

原创数位DP——HDU6148 Valley Number

题面：hdu6148 比赛的时候调到快结束的时候才A掉。。。（我真是太弱了。。。其实就是数位DP，状态也很简单： f[i][j][k]表示i位数字开头数字为j，当前状态为k的数量，k=1表明已经有过递增，k=0表明没有过递增。。。然后先把f求出来之后直接统计答案就行了还是很简单的。。。要是早调出来几分钟说不定文化衫就有了呢QAQ#include <cstdio>#include <algorit

2017-08-18 18:12:48 653

原创主席树维护dfs序——BZOJ3653/Luogu3899 谈笑风生

题面：BZOJ3653 Luogu3899 被luogu难度等级骗了。。。首先看到子树的题就是dfs序了，我们用L[i]L[i]表示i的初访问戳，R[i]R[i]表示i的末访问戳我们设size[i]size[i]表示子树大小（不包括i），deep[i]deep[i]表示深度首先我们可以发现a,b,c在一条链上，所以我们考虑这几种情况：b是a的祖先，根据乘法原理我们可以得到答案是siz

2017-08-18 11:09:12 284

原创线段树——BZOJ1858/Luogu2572 [SCOI2010]序列操作

题面：Luogu2572 BZOJ1858 （傻逼）题？我不会告诉你我写了调了一个晚上才A掉。。。（逃思路真的挺简（sha）单（bi），其实就是线段树维护区间和，区间最长连续段。但是细节实在太多。。。代码太难写。。。首先关于这个标记的问题，覆盖标记的优先级比反转的高，所以我们一旦加上覆盖标记之后，这个节点之前有的标记都可以清除掉了。。。还有，如果在这个节点加上反转标记的时候，这

2017-08-16 23:02:21 232

原创二进制乱搞——Luogu3917 异或序列

题面：Luogu3917 我的做法好像比较傻。。。看到这种题首先想到前缀。首先前缀xor是不是很资辞？我的做法呢就是先把所有数按二进制位拆开，然后每一位都做两次前缀。首先对数位做一次前缀xor，记到ss数组里，再对s数组做一次前缀和，记到ssss里。然后我们可以对于每一位枚举起始位置i，然后从i开始向后到n统计答案。首先考虑到ss数组非0即1，所以这里处理将会非常方便。我们

2017-08-16 10:46:09 654

原创数位DP——Luogu3413 SAC#1 - 萌数

题面：Luogu3413 这好像是我写的第一篇数位DP的blog吧。。。半原创吧，参考的是我的同学lc233的blog：传送门首先看到这个数据范围和样例就可以知道这题的主体思路了吧。我们可以定义状态f[i][j][k]f[i][j][k]表示位数为i的，最高位为j，次高位为k的萌数个数。一开始推的话很简单：首先回文串嘛>2就好啦所以我们只要判断2情况 aa或

2017-08-15 23:09:24 448

原创 Trie+拓扑排序——Luogu3065 [USACO12DEC]第一!First!

题面：Luogu3065 我们首先考虑一种情况，如果某一字符串的某个前缀是另外一个字符串，这个字符串不可能字典序最小。所以我们来考虑相同前缀的问题。如果某一字符串字典序最小，和它同前缀的字符串的相同前缀之后一位字母的大小顺序就可以确定。如果这一系列的关系没有矛盾的话，这个串就可以是最小的，反之不行。判断有无矛盾的话我们可以通过建连边跑拓扑排序解决。至于找前缀这种问题，交给Trie树就好了。#includ

2017-08-13 16:45:45 491

原创 Floyd+最大流——Luogu2402 奶牛隐藏

题面：Luogu2402 二分+最大流看到这种题嘛直接做啊，首先Floyd求出两两之间最短路，然后我们考虑二分这个时间TT，接着建图这个图啊首先把每个点拆成牛和棚，超级源点ss向每个点的牛连流量为牛数的边，每个点的棚向超级汇点tt连流量为容纳数的边，最后考虑牛到棚的边，如果点ii的牛到点jj的棚最短路<=T<=T，那么就连一条流量无限的边最后用最大流判断一下流量是否是奶牛数就好了#in

2017-08-03 19:21:04 184

原创暴力+map——Codeforces831C Jury Marks

题面：cf831c 简要题意：给出k个数a[i]，给出n个b[i]，每个b[i]值为a[1]+a[2]+…+a[不知道位置]+某一未知初始值（每种情况初始值是一样的），求可能的初始值有多少n<=2000n<=2000，直接暴力即可我们枚举b[1]这个值出现的位置在哪里，然后往左往右一一匹配，如果每个b[i]都出现过了说明这个初始值是合法的，判断去重后答案加1 时间复杂度O(n2)O(n^2)

2017-07-14 08:12:32 468

原创暴搜——51nod1400 序列分解

题面：51nod1400 真的是大暴力有人说直接暴搜加一个小剪枝就能过。。。我的搜索策略有点奇怪先讲一个错误的贪心：我们开个数组q[i]记录一个子序列的状态用一个指针p表示另一个子序列目前匹配到q[i]的第几位然后匹配下一位的时候往后找到和这一位数值相同的最近位置然后匹配上就好了，复杂度O(n)O(n) 但是这是错的，比如这组数据： 8 1 1 4 3 1 1

2017-07-12 19:52:53 313

原创欧拉回路+无极卡常——51nod1967 路径定向

题面：51nod1967 辣鸡出题人卡边表差评。。。卡常数卡啊卡交了35发才过QAQ 当然底下还有，反正占了两页本题的主题思路就是求一个欧拉回路，我们把有向图暂时先看作无向图首先第一问其实就是度为偶数点的个数第二问我们把其他度为奇数的点两两连起来，然后整张图跑欧拉回路定向就好了啊没有卡常的能看的代码：#include <cstdio>#include <algorithm>

2017-07-11 15:29:56 419 1

原创位运算贪心——BZOJ3668/Luogu2114 [Noi2014]起床困难综合症

题面：Luogu2114 BZOJ3668 既然都是一堆位运算了，我们按位来搞好了一个很显然的贪心策略，高位选0对接下来选择更有利所以我们直接按位从高到低贪心，计算这一位是0或1对答案的贡献，如果选1贡献大于0，选1，否则选0 大于m了选0 然后就好了。。。#include <cstdio>#include <algorithm>#include <cmath>#include <cstrin

2017-07-11 09:45:23 251

原创斜率优化DP——BZOJ1010/Luogu3195 [HNOI2008]玩具装箱TOY

题面：Luogu3195 BZOJ1010 本来以为斜率优化是个什么高级东西。。。这题入门之后…… 发现也没什么难的吧O(n2)O(n^2)做法： f[i]f[i]表示选完1~i个物品所花最小花费转移：f[i]=min(f[j]+(i−j−1+s[i]−s[j]−L)2)f[i]=min(f[j]+(i-j-1+s[i]-s[j]-L)^2) s[i]s[i]表示从1~i的c[i]c[i

2017-07-11 08:23:58 231

空空如也

空空如也