- 博客(313)
- 收藏
- 关注
RSS订阅
原创 qb neighbor
#include<cstdio>#include<iostream>using namespace std;int n,m,maxn;int a[19999],b[19999],h[299999],h2[299999];int ans,s;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&
2017-09-20 15:57:39
421
原创 伊吹萃香
网上竟然没有能看的懂的解释，我也是醉了 搞了好几个小时才找着一份代码，硬是看懂了 思路：记一个dis[i][j]数组,i表示节点，j表示时间是奇数还是偶数，0是偶数，1是奇数 某一个点的状态是由上一秒转移来的，而这两秒一定一个是奇数一个是偶数，所以1状态由0转移，0状态由1转移，黑洞需要翻转，而奇数秒的状态一定是被反转了的，偶数是没反转的，而这个可以用异或来搞定 因为0^1=1,1^1==0
2017-08-09 10:36:16
777
原创 狐狸分奶酪（codeforces 371b）
很容易想到的一个思路是暴力，就是对多的蛋糕吃，进行bfs（）； 一旦两种蛋糕相等，就是最小步数的，很容易写。 还有更好的方法，很容易看出，最后的解一定是它们的最大公约数，然后把他们的最大公约数去掉，看看能不能吃成1，记下步骤，也可以看能不能吃成最大公约数，是一样的。#include<cstdio>#include<iostream>#include<cstring>#include<que
2017-06-18 08:46:41
1687
1
原创 最大正方形
dp 处理一个矩阵前缀和，就可以O(n)的求出矩阵的和了，而且只有和为完全平方数才是正方形，因为数据只有1吗，要是不是一的话就不容易了 这样再枚举一个起点，和一个边长就是任意一个正方形了，再优化剪枝一下，就可以0ms过了#include<cstdio>#include<iostream> using namespace std;int n,m;int maxn=1;int a[101][
2017-06-06 11:24:14
548
原创 清北 游
#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#include<queue>#include<vector>#include<climits>#include<string>#include<cstdlib>#include<ctime>#define M
2017-05-22 22:44:36
354
原创 银河英雄传说
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;int t;int q[99999];int h[99999];int f[99999];int find(int x){ if(f[x]==x)return x; int fx=fin
2017-02-24 14:35:09
379
原创 vim使用
http://www.xuebuyuan.com/1116162.html https://blog.csdn.net/luojj26/article/details/50935921 https://blog.csdn.net/lhy2932226314/article/details/69668891# set nu “nu=number set cul “行亮 cuc 列 s...
2019-06-12 21:29:41
233
原创 NTT
#include<cstdio>#include<iostream>using namespace std;const int P=998244353,M=510000;int ans=0,g[M],inv[M],n,m,w[2][M],jc[M];int abs(int x){return x>0?x:-x;}int pow(int a,int k){i...
2019-06-12 21:29:15
286
原创 FFT
#include<cstdio>#include<iostream>#include<cmath>using namespace std;const double PI=acos(-1);const int M=110000; struct complex{//虚数a+bi double a,b;complex(){}complex(doub...
2019-06-12 21:28:53
255
原创 鬼东西
fft 点分治 李超线段树 cdq分治 后缀数组 分块大发 多项式除法，求逆 ,提答构造 后缀自动机 https://blog.csdn.net/clover_hxy/article/details/68059043硬币 http://www.cnblogs.com/CQzhangyu/p/7054998.html 有趣 https://blog.sengxia...
2019-06-12 21:28:34
709
原创 莫比乌斯反演与杜教筛
莫比乌斯反演我们知道积性函数可以迪雷克卷积 我们知道F(x)=Σd|xf(d) 要求f(x) 两面卷上一个μ 得 F∗μ=f∗1∗μF∗μ=f∗1∗μF*μ=f*1*μ 得 F∗μ=f∗(1∗μ)F∗μ=f∗(1∗μ)F*μ=f*(1*μ) 得 F∗μ=f∗eF∗μ=f∗eF*μ=f*e 得F∗μ=fF∗μ=fF*μ=f 也就是f=Σd|xμ(x/d)f(d)f=Σd|xμ(x...
2019-06-12 21:27:59
132
原创 P4022 [CTSC2012]熟悉的文章
这真是个神dp 我肯定想不出来，太牛逼了题解假设我们知道了len[i]为i之前的最长匹配熟悉子串 我们可以二分答案，得到一个L 那么就可以得到 dp[i]表示匹配到i的最长熟悉长度 dp[i]=max(dp[j]+i−j)(i−len[i]<=j<=i−L)dp[i]=max(dp[j]+i−j)(i−len[i]<=j<=i−L)dp[i]=max(d...
2019-06-12 21:26:44
170
原创 杂题
HH去散步 矩阵乘法优化dp 对边dp dp[i]=西格玛dp[j]; 最后找是连接节点的边，计数// luogu-judger-enable-o2#include<cstdio>#include<cstring>using namespace std;const int M=121,p=45989; int u[M],v[M],n,m,t,S,T,st...
2019-06-12 21:26:06
122
原创 扩展欧拉定理
ab≡x(modm)求xab≡x(modm)求x a^b≡x(mod m) 求xgcd(a,m)=1，欧拉定理：ab≡a的(bmodφ(m))次方(modm)gcd(a,m)=1，欧拉定理：ab≡a的(bmodφ(m))次方(modm)gcd(a,m)=1，欧拉定理：a ^ b ≡a 的( b mod φ ( m ) )次方 (mod m)gcd(a,m)>1，且b>...
2019-06-12 21:25:50
159
原创 范德蒙矩阵
https://wenku.baidu.com/view/70fe14f8f705cc1755270933.html 范德蒙矩阵的行列式值 =所有可能差值的积 | 1 , 1 , 1 , 1 , 1 ||x1,x2,x3,x4,x5||x1^2,x2^2,x3^2,x4^2,x5^2||x1^3,x2^3,x3^3,x4^3,x5^3||x1^4,x2^...
2019-06-12 21:24:31
3803
原创 更牛逼的高斯消元(辗转相除法)
没有精度问题，但多了个log，不明白的话手动模拟一下for(int i=1;i<n;i++) { for(int j=i+1;j<n;j++) while(a[j][i]) { int t=a[i][i]/a[j][i]; for(int k=i;k<n...
2019-06-12 21:23:36
936
原创 最小顶标和与最大权值匹配
结论：不知为什么。 满足任意xi+xj>=cost[i][j] xi到xj连cost[i][j]的边 求出最大权值匹配就是最小顶标和 最大权职匹配可以用最大费用可行流
2019-06-12 21:22:17
415
原创 KD_TREE总结
用途KD_TREE可以求K维空间最短/长两点的距离 或者前T长的距离，蒟蒻大概就知道这一点。。。思想把空间切割，完成缩短时间的半目的实现(建树，插入)怎样切割？？？ 用二叉树来实现，每一层按层数%K这一维切割 记录每一个子空间的状态就可以了，例如处理出每个空间每维的上限下限 然后合并子树的状态，插入类似复杂度就可以做到随机数据logN的复杂度，但毒瘤出题...
2019-06-12 21:21:24
225
原创 P4211 [LNOI2014]LCA
又一鬼题 对于每次查询 把l-r到跟的路上+1 然后深度就是这个位置的全职 然后查分一下，查询r-l 这样就可以离线记下查询位置 只添加，不用删除 就可以利用之前的信息了// luogu-judger-enable-o2#include<cstdio>#include<iostream>#include<cstring>#inclu...
2018-04-01 09:21:45
250
原创 线性基
P3292 [SCOI2016]幸运数字 亦或和 最大值就是二维线性基了 倍增维护线性基 本想写树剖维护，想了想还是倍增简单。。。// luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<iostream>#define ll long longusing name...
2018-03-31 18:59:10
277
原创 灾难
搞出灭绝树。 一群动物的祖先就是他们的灭绝祖先 倍增搞lca// luogu-judger-enable-o2#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int M=110000;int n...
2018-03-31 18:48:06
188
原创 栗栗的书架
本以为是线段树套主席书 不过看数据做题，大数据只有一条线。。 二分一个厚度直接大数据主席书 小数据暴力dp// luogu-judger-enable-o2// luogu-judger-enable-o2// luogu-judger-enable-o2#include<cstdio>#include<iostream>#define mid (l+r...
2018-03-31 18:44:54
264
原创 费用刘
二分一个费用 限制上限，跑最大流// luogu-judger-enable-o2#include<cstdio>#define ll long long#include<cstring> #include<queue>using namespace std;const int M=10000,inf=0x7fffffff;const l...
2018-03-31 18:41:03
129
原创 杂题
P1955 [NOI2015]程序自动分析 离散化+并查集判约束 可以先弄0的再弄1 避开了一些情况 一开始写了个反集，不知为啥错了。。。// luogu-judger-enable-o2#include<cstdio>#include<iostream>#include<algorithm>#define ll long long u...
2018-03-31 18:39:52
178
原创 三分法
维护凸函数 可以用导数二分水做。 但某些不知通项的函数只能拉格朗日插值做了。。 不过我不会。。。。 但不是多项式的也无法作，还是三分吧。。。 宅男计划 猜出是一个凸函数 三分+ 神TM贪心，不懂就这么写了。。。// luogu-judger-enable-o2// luogu-judger-enable-o2#include<cstdio>#include...
2018-03-31 17:41:09
202
原创 小Z的袜子
简单莫队 对袜子分块，对操作排序 概率是 某颜色个数/总个数 然后暴力修改就行了// luogu-judger-enable-o2#include<cstdio>#include<iostream>#include<cmath>#include<algorithm> #define ll long longusing names...
2018-03-31 17:25:16
179
原创 树状数组
首先我们发现如果reverse下树状数组所操作的数组的话，它写的代码是完全正确的，但是reverse之后前缀变成了后缀，所以，它写了一个正确的单点修改求后缀和的数据结构那么我们发现，对于一个通常的询问，其实是在询问(l-1,r)这两个点相同的概率，然后一个错误的思路是用线段树维护每一个点被修改的概率，但是这样做是错的，因为对于一次操作，修改且只修改一个点，如果按照线段树来做，其实是会导致一...
2018-03-31 17:21:49
109
原创 营业额统计
裸地平衡树，维护前驱后继。// luogu-judger-enable-o2#include<cstdio>#include<iostream>using namespace std;int abs(int x){return x>0?x:-x;}int n,root=0,tot=0,ans,inf=0x7ffffff;struct Splaytree...
2018-03-31 17:14:02
622
原创 可并堆
P1456 Monkey King 这个题把做朋友的合并，维护最大值，所以就是一个可并堆。// luogu-judger-enable-o2#include<cstdio>#include<iostream>const int M = 110000;int n,m,A[M];struct node{int ls,rs,h,w,f;void init(){ls=...
2018-03-31 17:12:15
252
转载 purfer序列
转自 http://www.cnblogs.com/zhj5chengfeng/archive/2013/08/23/3278557.html 题目大意自从明明学了树的结构，就对奇怪的树产生了兴趣……给出标号为 1 到 N 的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树？Input 第一行为 N(0<N<=1000)，接下来 N...
2018-03-26 10:45:20
518
原创 最优化问题的算法
爬山算法大概是：找局部最优解的算法，很大几率忽视掉全局最优解 随机一个数，就是找最近的数，比较是不是最优的，是就接受，不是就不接受 不过我没学QWQ模拟退火算法设一个温度T根据温度降低，解的变化量越来越少 然后根据温度随机接受一定的次优解，就可以找到最优解了遗传算法，有点复杂。还没学。。。。。参考：https://xueqiu.com/9842090891...
2018-03-26 10:18:20
403
原创 杂题（大部分网络流+暴力）
[HEOI2016/TJOI2016]树 写了个树剖。。。，记一下链头 跑得比暴力还慢，这数据也是太弱了。。。。。。// luogu-judger-enable-o2#include<cstdio>#include<algorithm>#define ll long longconst int M=210000,mod=(int)1e9+7;int nex...
2018-03-20 20:50:14
141
原创 杂题（大部分网络流+暴力）
[HEOI2016/TJOI2016]树 写了个树剖。。。，记一下链头 跑得比暴力还慢，这数据也是太弱了。。。。。。// luogu-judger-enable-o2#include<cstdio>#include<algorithm>#define ll long longconst int M=210000,mod=(int)1e9+7;int nex...
2018-03-20 20:50:09
994
转载 可持续化trie树
转自http://blog.csdn.net/BerryKanry/article/details/76165196世界真的很大trie树贪心求最大异或和大概也就是那么回事了但是对于区间的查询就不是那么容易的了考虑主席树的思想，怎么得到区间的值域的这就是可持久化的trie树说来容易指针教做人哪看题先：description：给定一个非负整数序列 {a}，初始长度为 N。 ...
2018-03-11 15:50:46
512
原创 情报传递
第一问就是树上距离 第二问，两个限制T// luogu-judger-enable-o2#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int M=210000,N=1000010;int n,m,to[2*M],nex[M*2],h...
2018-03-11 15:48:57
418
原创 亦或和
考虑到分解为二进制后 疑惑后只有每一位是一得个数有奇数个才行 就统计出每位1,0的个数 查询，我也不是多明白。就这样搞吧。。。// luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<iostream> using namespace std;const int N...
2018-03-11 15:43:26
1093
原创 [SCOI2016]萌萌哒
这个题的限制可以用并查集来做 最后的答案就是，因为每一个并查集是固定的，一个数有10种选择 所以答案就是9*10^(n-1) 然后并查集用倍增优化 对一个区间打标记 大区间在一个集合，小区间也在一个集合。 修改完将完全标记下放 查询有几个集合就行了#include<cstdio>using namespace std;int f[21][121102],T,n,c...
2018-03-11 10:10:44
268
原创 [SDOI2015]排序
大爆搜 操作不分先后，所以我们就枚举每一个操作 我们从1开始枚举区间个数为i 因为只能交换1<#include<cstdio>#include<iostream> using namespace std;int jc[14],base[14],n,a[1<<13];long long ans;bool check(int x,int t)...
2018-03-10 17:05:23
310
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人