- 博客(65)
- 收藏
- 关注
RSS订阅
原创 csp复试备考——BY Xzhhng
位运算的基础知识1<<i->2^ix=x<<(1<<i)->将x的i+1位强行变为1if(x&(1<<i))->判断第i位是否为1x>>1->将x的最后一位删掉for(int i=S;i;i=(i-1)&S)->枚举S的子集lowbit(x)---x&(-x)->取x...
2020-08-21 14:50:31
558
原创 一道比较不错的组合思想题
方法一(O(n3))方法一(O(n^3))方法一(O(n3))将原数组进行排序，二重循环枚举两个数的值，但是发现很难计算方案数将原数组进行排序，二重循环枚举两个数的值，但是发现很难计算方案数将原数组进行排序，二重循环枚举两个数的值，但是发现很难计算方案数所以就再加上一个这个值所在的位置，记为k所以就再加上一个这个值所在的位置，记为k所以就再加上一个这个值所在的位置，记为k可以将原数组进行排序，较小的数为x，较大的数为y，比x小的数为sm，比x大的数为bg，在两个中间的为mid可以将原数组进行排序，.
2020-11-28 15:31:48
97
原创 Shik and Travel
题目传送门第一次过黑题，才打了48行发现每一条边只能且必须遍历两遍，手动模拟或直接证明可以知道一个结论发现每一条边只能且必须遍历两遍，手动模拟或直接证明可以知道一个结论发现每一条边只能且必须遍历两遍，手动模拟或直接证明可以知道一个结论如果遍历到一颗子树，那么就一定要把这棵子树遍历完才能遍历下一棵如果遍历到一颗子树，那么就一定要把这棵子树遍历完才能遍历下一棵如果遍历到一颗子树，那么就一定要把这棵子树遍历完才能遍历下一棵这样就很容易想到利用树形DP的方法，同时又具有单调性，可以用二分,记二分的数值为v
2020-11-28 14:37:00
104
原创 uoj套路
题目传送门暴力很好打暴力很好打暴力很好打有没有人性，才给7分！！！看了一下没有给太大的值域，显然是要从值域着手看了一下没有给太大的值域，显然是要从值域着手看了一下没有给太大的值域，显然是要从值域着手对于子任务3（和正解有关）可以用一个dp解决对于子任务3（和正解有关）可以用一个dp解决对于子任务3（和正解有关）可以用一个dp解决dp[i][j]表示以i为左端点，j为右端点的最小的差值dp[i][j]表示以i为左端点，j为右端点的最小的差值dp[i][j]表示以i为左端点，j为右端点的最小的差值
2020-11-27 20:25:35
356
原创 缩进优化
题目传送门首先以为这题有啥单调性的，硬是没看出来首先以为这题有啥单调性的，硬是没看出来首先以为这题有啥单调性的，硬是没看出来没办法就先写了一个暴力，就发现可以优化了没办法就先写了一个暴力，就发现可以优化了没办法就先写了一个暴力，就发现可以优化了首先可以将枚举的方案优化，对于一段区间，首先首先可以将枚举的方案优化，对于一段区间，首先首先可以将枚举的方案优化，对于一段区间，首先...
2020-11-27 19:31:57
127
原创 Solution of Luogu September competition
题目传送门显而易见地就可以发现，这个其实就是统计最多的字符的个数#include<bits/stdc++.h>using namespace std;const int N=1e7+10;char s[N];int a[30],Max;int main(){ scanf("%s",s+1);int len=strlen(s+1); for(int j=1;j<=len;j++) a[s[j]-'a']++; for(int i=0;i<27;i++)
2020-09-22 16:39:19
82
原创 刷题杂记之Bindian Signalizing
题目传送门首先考虑如何处理这个环可以先找出最大的数，然后最大的数放在第一位，按顺序依次下派，最后再加上这个最大数，那么就不需要处理冗杂的计算了，直接就可以线性计算思考如何在这个链上处理对于一个点i，设它的左边的第一个比i大点为leftileft_ilefti,右边第一个比他大的点为rightiright_irighti，那么有i的区间就是leftileft_ilefti~rightiright_irighti（如果在这个区间的左边或者右边还有，那么a[i]一定小于a[leftileft_i
2020-09-09 15:07:28
112
原创 刷题杂记之Cows in a Skyscraper G
题目传送门首先n小于18，就能很快地想到状压DP。不是暴力dfs吗f[i]=min(j∈i){f[i−(1<<j−1)](可以放的时候)f[i−(1<<j−1)]+1(不可以放的时候)f[i]=min(j\in i)\begin{cases}f[i-(1<<j-1)](可以放的时候) \\f[i-(1<<j-1)]+1(不可以放的时候)\end{cases}f[i]=min(j∈i){f[i−(1<<j−1)](可以放的时候)f[i−(
2020-09-01 15:39:46
139
1
原创 刷题杂记之Coloring Brackets
题目传送门首先看到这个题目，一定要用栈，废话我们可以发现对于一个括号，不管它是左括号还是右括号，对他有影响的只有3个位置1. 他的左边括号的颜色2. 他的右边括号的颜色3. 他的对应的括号的颜色对于1,2两个问题，可以利用普通的dp枚举，对于第3个问题，处理这个问题的括号，就可以处理把这个问题删掉的这个区间，所以就可以区间dpf[l][r][x][y]表示lf[l][r][x][y]表示lf[l][r][x][y]表示l~r这个区间,l的颜色为x,r的颜色为y的方案数r这个区间,l的颜色
2020-09-01 14:18:14
107
原创 刷题杂记之树上启发式合并
吐槽在还没学启发式合并时的wo——什么神奇玩意，一定很nb看完之后的wo——这。。。。树上启发式合并的原理就是暴力，我也不知道为什么要取这么一个好像需要rand等一些随机数的名字，大概是搞得神秘化一点吧核心就是在暴力上进行优化，询问一般都是一个点的子树内的一些询问，过程就是通过一些联系计算出每一个的子树，最后输出就行了，一定程度上，这也不是一个离线算法（如果是对于询问进行强制在线的话）题目传送门这道题有很多的解法，比如说dfs序+回滚莫队，dfs+分治…这里就讲讲启发式合并怎么做首先
2020-08-28 08:05:20
140
2
原创 刷题杂记之密室
题目链接一开始看这题，我还以为哈利能给罗恩开门呢(哈利怎么会这么好心)无法开门，那么罗恩能走的哈利也能走罗恩真是个废物，但是哈利能走的罗恩不一定能走，那么就分成了3种情况1，罗恩去救妹妹，哈利拿日记2，罗恩去拿日记，哈利救金妮3，哈利一人干完所有的事情然后就愉快的解决了#include<bits/stdc++.h>using namespace std;int read(){ int num=0;bool flag=1; char c=getcha
2020-08-27 09:33:51
113
原创 2019.8.10金华暑假集训Day14讲课总结
吐槽我终于听懂期望了！！！期望这个的概念就不多说了，前面已经说过了，下面就全是题目。要求的就是E[S],下面就是推导Xi表示当前有i−1个数,E[S]=E[∑Xi]=∑E[Xi]成功匹配的概率为(n−i+1)/n,所以E[Xi]=n/(n−i+1)E[S]=∑E[Xi]=∑n/i感性理解，a要么在b前面，要么在b后面，所以是1/2...
2019-08-10 21:24:16
144
1
原创 2019.8.8金华暑假集训Day12讲课总结
吐槽时间真的不够啊！刷题的时间都没有，怎么写bolg啊！贪心在之前的bolg里，已经讲了较简单的贪心，在这里就要讲一下较难的贪心，所谓较难的贪心，就是贪心和DP，数据结构，图论，二分等的结合，还有哈夫曼树，这里就以题目为例子，来讲一下。简单的贪心对于这种每一个都是有倍数关系的题目显然是能选的就选，不能选的就往小的选，所以就500~1一步步的选，能选则选，不能选就往小的选，这...
2019-08-10 15:00:15
122
原创 2019.8.2金华暑假集训Day6讲课总结
吐槽听得有点懵....题目解释由于题目只有DP这里就只讲题目了#include<bits/stdc++.h>using namespace std;const int N=200010;struct cow{int x,y;}e[N*2];int n,a[N],head[N],top;void inse(int xxxx,int yyyy){...
2019-08-03 14:40:22
139
原创 2019.7.31金华暑假集训Day4ACM考试总结
吐槽有点崩溃，我快速的做完了1，2两道题目，但是做到后面的时候，我就开始从颓废，然后到后面就......题目说明对于题目请详见百度网盘里的链接，代码也见百度网盘A 由于这一道题目有点水，由于枚举的数的个数一定不会小于模数相乘，所以我们一开始枚举z然后每次加上1e9+7，这样的时间复杂度是不会超的B这一到题目看似很难，但是后面我们就可以发现，这个题目要求的方案数的每一...
2019-08-02 15:22:17
118
原创 2019.8.1金华暑假集训Day5讲课总结
吐槽我终于感觉不像前几天那么的难了，或许是换成了个女老师，或许是因为在衢州集训的时候是她再讲，所以风格还是比较清楚，或许是太水了网络流背景（纯属复制）图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，...
2019-08-01 20:38:31
145
原创 2019.7.30金华暑假集训Day3讲课总结
吐槽今天还是好难啊！和第一天差不多啊容斥原理举个例子，如下：假设我们要求黄色部分，那么答案就是C-A-B+A∩B=C-A∪B对于黄色部分，答案也就是D-A-B-C+A∩B+A∩C+B∩C-A∩B∩C=D-A∪B∪C那么通过这个，我们就能够发现规律了对于一个集合s[1...n],如果我们要求|∪(i=1~n)si|，那么这个式子就是∑(i=1~n)si-∑(i...
2019-07-30 19:54:22
100
原创 2019.7.29金华暑假集训Day2讲课总结
吐槽：今天讲的东西好多啊，虽然比昨天好了点，但是还是一脸懵逼......分治分治的思想将一个区间（或树）分成若干个区间（或子树），以达到优化的目的例题现在来两道例题（不是课件上的，但是比课件上的难）CDQ分治作用可以顶替比较复杂的数据结构（如二维，三维线段树），且常熟较小，但是这个东西必须要离线才能够操作二位偏序给定N个有序对(a,b...
2019-07-29 20:30:58
117
原创 2019.7.28金华暑假集训Day1讲课总结
小吐槽： 这是啥啊，我一脸懵逼对于期望的基本概念和公式： P(x)表示x事件的概率 E(x)表示x事件的期望 公式：E(X)=∑(i=1~X的种数)（P(X=i)*i）注：种数是要通过离散化变成1~n的数时 等比数列求和∑(i=0~n)x^i=(1-x^(n+1))/(1-x) 条件：0<x<1（而对于无穷的等比数列，这个答案即为1/(1-x)）...
2019-07-29 07:56:33
144
原创 2019.7.19海亮暑假集训Day14考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，这一题很水...... 首先打个表，让后找规律即可，证明过程？如下：（我不想看......） T2，首先这是一个需要dfs序（类似的）搞得莫队，我们可以用一个数组来记录当前状态的情况（sum[k]表示k在当前区间>=k的个数，即可实现O（1）转移）就这样...
2019-07-19 19:06:23
141
原创 2019.7.18海亮暑假集训Day13考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，一看就想到了枚举（贪心），可以把每一个点枚举一遍，让后+2，+3的向后扩展（还有以下边界处理问题），判断和后面的是否一样，这个看似正确的贪心，实际是不对的，为甚么呢？看下面的例子：......xyzzzz假设我们枚举到了x，那么我们就会把xy这一个东西加入合法状态，但是这样对吗？当我们把xy加入后，后面的zzzz就不能够选了，所以就不行了（...
2019-07-18 21:36:23
122
原创 2019.7.17海量暑假集训Day12考试总结
对于代码和题目详见百度网盘，这只讲思路。 首先我要吐槽一下，这为何可以用点分治做，而且还有两道！都是模板，我不会啊！！！！ T1，这是一道和换根DP的的模板非常的接近，只是加了以为，我们以图讲解： 对于这一张图，首先我们用一个f[i][j]表示i号点和其他点长度为j的个数，d[i][j]表示i号点这个子树里的到他距离为j的点的个数，显然，f[1][i]=d[1][i],而d数...
2019-07-18 12:27:10
110
原创 2019.7.16海亮暑假集训Day11考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，首先吐槽一下，这一道题数据有点水啊，我一个交到洛谷上的错解在这里却对了......这之前搞得我很慌...... 首先一看即可知道这是一道区间DP，但是转移有一点烦，我们看看， 要会贪心，显而易见的，这一道题目最好是化成一个回文串了之后再做改变，这一点是肯定的（大胆猜想不用证明）。 （可是我就是这个没想到啊！） 因此我...
2019-07-16 20:43:57
132
原创 2019.7.15海亮暑假集训Day10考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，我在做的时候竟然没想到统计方案，这真的有点......（70分啊!!!） 这一道题首先可以发现，最长上升子序列和次长上升子序列的差别就是：如果最长上升子序列有1个，那么次长上升子序列的长度则为最长上升子序列-1，否则就是最长上升子序列，那么我们就可以统计最长上升子序列和其方案数就可在O（N^2）的时间内通过了，但是还有一个问题：要O（...
2019-07-16 07:09:26
102
原创 2019.7.14海亮暑假集训Day9考试总结
对于代码和题目详见百度网盘，这只讲思路。 首先，由于这题太过毒瘤，所以我没有写T2，T3以后补吧（估计再也不会补了） 我T1是A了的，首先看到题，我先打了一个暴力，到手了，我去看T2，T3，发现T2和T3的纯暴力我都不会打，有点懵，所以我就打了几个乱搞之后去看T1，看看能不能骗点分...... 我看到没有列，只有行的时候，我知道了可以用一个线段树维护一下，直接计算即可，然后我...
2019-07-14 19:24:20
125
原创 2019.7.13海亮暑假集训Day8考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，这是一道显然易见的题，很简单（但是我没多想写了个暴力......）就是建边暴力跑dfs T2，这是一道很有意思的题，首先，我们发现这一道题有一个性质： 如果有一个集合求出来了，那么我们在下一次碰到的时候，就只需要和这里面的最大值比较一下即可，那怎么比较呢？就排序即可完成。 T3，这是一道IDA*（我考的时候还不会，就只写了...
2019-07-13 20:13:23
121
原创 2019.7.12海亮暑假集训Day7考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，这一道题我在做的时候竟然没看懂题目！！（我估计就我一个了），看了20分钟没看懂。看来我要好好学学我的语文了...... 公式的推导如下： 但是不会可以找规律啊（可以写分段函数，或者对拍一下） T2，这一道是如何枚举是一个很棘手的问题。s的长度不会超过10，若没有重复的数字，则所有可能情况为362880若有所...
2019-07-12 21:33:30
107
原创 2019.7.11海亮暑假集训Day6考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，这一题看到，感觉自己做过（实际没做过）下面讲一下我的这一道题的思路： 这一道题首先我打了一个暴力，后来我做的时候不知道脑袋怎么想的，想到把maxxSQRT一下（或许是我脑抽了）先求原来的maxx是否符合条件，在开一个根号，枚举，这样时间复杂度就从O（N^2）变成了O（Nsqrt（n）），这样这一道题还是过不了（但是我知道最后一个点0....
2019-07-11 19:14:48
134
原创 2019.7.10海亮暑假集训Day5考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1 期望的和=和的期望 考虑每对位置(a, b)对答案的贡献。 又发现每对(x,y)的期望可由每对位置(a,b)的期望和得来。 于是考虑对于第一串的 a 位置，第二串的 b 位置对答案的贡献。 若 s[a] != t[b]则贡献为 0。 若 s[a] = t[b]，考虑一共有多少种选择方法能使(a,b)对答案有贡献，由...
2019-07-10 21:22:00
138
原创 2019.7.9海亮暑假集训Day4考试总结
对于代码和题目详见百度网盘，这只讲思路。 T1，一道分块的模板，我把n写成了m，所以暴零了，很尴尬。但是这一道题我写了莫队，但是莫名50分也不知道是为什么，莫队和分块的时间复杂度不是一样的吗，为什么会T？ T2，我写了个题解，如下： T3，这是一道毒瘤题，我不会（至少现在不会），就不赘述了...
2019-07-10 11:56:16
204
原创 2019.7.8海亮暑假集训Day3考试总结
对于代码和题目详见百度网盘，这只讲思路。T1，显然是一个dfs暴力就可以过，但是我的YES小写了 沉默两秒..........T2，这一道题我要好好讲讲（下面是我写的题解）下面有四种情况看懂了吗（看懂了！！），还是挺好理解的（可是考试时候还是推不出来啊）T3，这一题我一开始想的是分块（因为下午要讲的是分块，所以我就没多想），后来正解竟然是倍增（说实话，我的倍增除了...
2019-07-09 12:04:22
161
原创 今天突然有的感想
看到一篇博客上写的，我感觉很对，意思大概是这样的：我们不要太过于专研自己，因为当我们发现自己并不是宝石时，便会放弃。只有努力的专研别的，有一天你就会发现砖瓦变成了宝石...
2019-07-07 20:58:06
177
原创 2019.7.7海亮暑假集训Day2考试总结
对于代码和题目详见百度网盘，这只讲思路。 1，这是一道LCA的模板（题目看了我好久......）仔细观察就很容易发现这道题看似是在线的，其实是离线的处理。时间复杂度：O（nlog（n）） 2，这是一道高阶差分的模板题（我都不知道什么是高阶差分）首先，我们要知道如下定理。 （1）把差分前缀和就会等于原序列 （2）C（n,k）=C（n-1,k-1）+C（n-1,k）...
2019-07-07 20:53:03
145
原创 2019.7.6海亮暑假集训Day1考试总结
对于代码和题目详见百度网盘，这只讲思路 1，这道一看，显然会以为是一个前缀和（因为这一道题和累加和差不多），但是这一道要求的是平均数，所以我们可以向把平均数转换成求和就行了（可是我就是没想到），于是看到了数据范围（1<= ai <= 5000）很容易就能想到二分这么一个东西。所以我们可以二分枚举平均数，用一个数组来记录减去平均数后的值，求一遍前缀和。 这样我们的问题就变...
2019-07-06 21:08:03
180
原创 2019.7.4考试总结
对于这次的结果就不讲了。 关于本次测试的题目和标程就放在百度网盘里 T1，这是一道很水的筛法求素数的暴力，但是由于没有换行，就暴0了，这告诉我们以后调程序一定要用文件调试。 T2，这是一道强模拟，就是把书填如二维数组，这就不赘述了 T3，这道题是一个裸的多重背包，但是要用二进制拆分，在打代码时不小心想错了，可是样例过了，我就没多想就放在一边了，可是如果是NOIP的话，我...
2019-07-04 19:20:26
123
原创 对于学了两年的总结
学了两年了（小学不算），现在根据蓝书（第三版）的做个总结章节 掌握程度 第一大章 位运算 这个已经很熟练了，学的很好 枚举，模拟，递推 这个看起来很简单，主要是递推有时会推不出来（数学不好，但是可以用写dfs来找规律来完成递推） 递归 这个对于线性的比较熟练了，但是有时会用到lca,dp等等领域，有时就不会了 二分 这个不是直接有...
2019-07-04 17:19:25
131
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人