zz_ylolita-CSDN博客

原创 hdu6601Keen On Everything But Triangle[2019hdu多校第二场，主席树]

//需要依次查询区间第1大，第2大，第3大，...，第k大，直到构成三角形或者数用完//O(n*logn*44)#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespac...

2019-07-26 12:54:30 165 1

原创 hdu2665Kth number[求区间第k大，静态不带修改]

hdu2665线段树：//线段树求区间第k大//给定你一个长度为S的无序序列，每次询问其间一段[L,R]，问在这一段中的第k大数是多少//O(q*(log n)^3)//线段树维护归并排序的过程，线段树的每一个结点是一个区间，且里面的数有序//因为占用空间太大，只能开成vector#include <iostream>#include <cstdio>#i...

2019-07-25 23:43:40 186

原创 bzoj2462[二维hash/矩阵hash]

//二维hash//相当于每个位置有两个权，行一个，列一个，然后推的方法和一维一样//bzoj2462#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespace std...

2019-07-25 22:24:57 214

原创 hdu5936 Difference[折半枚举/搜索]

x=f(y,k)-y，等式的右边每位是可以独立算的，最后也可以合并。当y较大的时候，必然会减成负数，而x>=0, 所以y有一个上限。9^99大概是3e109^910大概也是3e109^9*11是4e10不够11位所以y最多应该是10位分y的低5位和高5位分别枚举并查询就可以了。注意x=0的时候，y=0不能作为解，因为题目要求y>0注意折半枚举的条件，两个部分可以分开计算...

2019-07-08 22:53:07 181

原创 BZOJ2118 墨墨的等式[一个图论模型]

由于某些原因，题解之后再写好久没有这么开心的写代码了，但是还有2个小细节没注意到qwq，下次注意。//BZOJ2118//图论模型#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <queue>using na...

2019-07-08 15:39:27 283

原创 luogu4774 [NOI2018]屠龙勇士

题目链接可以想到第一次屠龙用的刀是确定的，可以列一个同余方程x∗atk1−a1=0(mod p1) x * atk_1 - a_1 = 0 (mod \space p_1) x∗atk1−a1=0(mod p1) ，然后每次用的刀都可以确定，因此预先确定所有的刀，对100%的数据用EXCRT求解同余方程组就可以了。怎么预先确定所有的刀呢？直接写的话可以离散然...

2019-06-01 23:48:22 196

原创 CF1114F. Please, another Queries on Array?

没有注意到所有的因子都是300以内，注意到了也想不到这样就可以用集合来表示质数是否出现，从而直接计算出欧拉函数。打标记的线段树在change的时候忘记pushdown了，调了一天orz#include &amp;lt;iostream&amp;gt;#include &amp;lt;cstdio&amp;gt;#include &amp;lt;string&amp;gt;#include &am

2019-02-12 23:43:57 324

原创 hdu2167 状态压缩DP入门题

照猫画虎写了道入门题。。讲道理这东西我不应该现在才来学TAT//状态压缩DP入门题//九宫格的相邻限制条件//N*N 3<=N<=15/*dp[i][j]表示前i行，最后一行状态为j时得到的最大分数和对于一行j的所有可能可以用DFS弄出来，在同行搜索的时候只要保证行不相邻。在判断合法状态转移的时候，判断本身、左移和右移即可。dp[i][j] = max{dp[i-1...

2019-02-03 22:05:00 207

原创 hdu5992 Finding Hotels ——KDtree

每一个点有三个属性：(x,y,c)每次查询要在log的时间内完成，查找距离(x,y)点最近的已知点，并且已知点的花费c要小于等于给定的一个数。一开始想，如果直接用二维的kdtree来做，直接在query找的时候忽略花费>c的点不就好了，但是发现这样不满足kdtree BST的性质，是没有办法往下走的。那就得考虑把c也作为一维坐标，所以应该是三维kdtree.可以手动定义如果花费大...

2018-10-31 00:58:46 261

原创 hdu1724 自适应辛普森积分求面积定积分

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>using namespace std;const double eps = 1e-6;//eps是整个辛普森应用的关键，取的大小根据题目要求的精度来...

2018-10-21 21:11:40 253

原创 zoj3688棋盘多项式，有限制的排列问题

棋盘多项式本来的式子，但是这道题直接算出来棋盘多项式很麻烦，计算r_i的时候把问题转化为在1~2n的圆周上选取i个不相邻的数即可。1的时候特判一下。#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;...

2018-09-24 14:51:57 406

原创 bzoj4659LCM

总感觉我的做法是假的莫比乌斯反演。。只用到了莫比乌斯函数的性质复杂度是O(nlogn)的，这题正好p是2^30可以用int自然溢出，不用取模，但是最后的答案还是要+p在%p，防止是负数#include <bits/stdc++.h>using namespace std;const int P = 1<<30;#define N 4000005int ...

2018-09-23 20:49:49 132

原创 luogu1829 [国家集训队]Crash的数字表格 / JZPTAB

式子好难推。。看别人的博客好了。。#include <bits/stdc++.h>using namespace std;#define N 10000005#define P 20101009bool vis[N];int prime[N],miu[N];typedef long long LL;LL x[N], ans;int cnt,n,m;void ...

2018-09-23 18:10:33 210

原创 luogu2522[HAOI2011]Problem b

用一个简单的容斥就可以求出a<=x <=b, c<=y<=d范围的答案了注意1LL呀qwq#include <bits/stdc++.h>using namespace std;#define N 50005bool vis[N];int miu[N],prime[N];typedef long long LL;LL sum[N],ans;...

2018-09-23 16:42:40 104

原创 luogu3455 [POI2007]ZAP-Queries——莫比乌斯反演

比上一题更简单。。。#include <bits/stdc++.h>using namespace std;#define N 50005bool vis[N];int miu[N],prime[N];typedef long long LL;LL sum[N],ans;int n,m,d,T,cnt;void Miu(){ miu[1] = 1; cnt ...

2018-09-23 16:27:29 191

原创 luogu2257 YY的GCD——莫比乌斯反演

注意一下处理前缀和的时候的trick#include <bits/stdc++.h>using namespace std;#define N 10000005bool vis[N];int miu[N];typedef long long LL;LL sum[N],ans,g[N];int prime[N];int cnt,T,n,m;void Miu(){...

2018-09-23 16:03:00 173

原创 uva11354 找瓶颈路径——并查集按秩合并

在做最小生成树的时候，使用并查集的按秩合并，不会破坏树的结构，复杂度O(logn)#include <bits/stdc++.h>using namespace std;#define INF 1000000009#define N 50010int n,m,q,x,y;int fa[N],Rank[N],edge[N],c[N];struct node{ int...

2018-09-23 13:44:39 218

转载 STL

优先队列：https://www.cnblogs.com/xzxl/p/7266404.html队列：https://www.cnblogs.com/xzxl/p/7266370.html栈：https://www.cnblogs.com/xzxl/p/7267275.htmlset：http://www.cnblogs.com/SarahLiu/p/5892900.htmlmap...

2018-09-01 19:59:05 119

原创 [luogu2742]凸包模板

//凸包板子#include <bits/stdc++.h>using namespace std;#define N 10010const double eps = 1e-10;int dcmp(double x){ if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;}struct poi...

2018-09-01 00:03:24 154

原创 hdu6430 Problem E. TeaTree 权值线段树合并暴力

新学到的权值线段树和它的合并，数组版的动态开点，以及如何估算线段树数组要开多大敲开心~应该还要学怎么分裂。。。关于权值线段树的讲解看这里：https://www.cnblogs.com/Mychael/p/8665589.htmlhttps://blog.csdn.net/Stupid_Turtle/article/details/80445998不过这题也可以直接bitset...

2018-08-30 00:26:39 339

原创单调栈

傻逼zzy...poj2796注意一下最后答案可能是0，所以res的初始值要赋为-1#include <iostream>#include <cstdio>using namespace std;int n,top;long long res;int ans;long long s[100005], a[100005];int L[100005]...

2018-08-24 19:52:28 158

原创 hdu4418 Time Travel 概率DP+高斯消元

可以先用BFS判断每个点是否可以到达，在BFS中使用队列和vis[]，但是vis[]只用标记一次，并且即使点出队，标记也不要清除，因为如果一个点的vis = 1，那么它要么在队列里，当前不用入队，要么已经出队了，那么这个时候它能影响到的点已经被更新了，不用再入队一次。（和DFS同理）设E[i]表示从i走到终点y的期望，那么E[y] = 0来回折返的处理：为了将走动变成只有一个方向，将数轴翻...

2018-08-10 11:21:57 390 2

原创 poj2533 LIS裸题 O(nlogn)

/*O(nlogn) LISd[i]表示使得f[i]为i的最小的a[i]!!! d[]的初始值为INFd[]单调递增证明：反证，假设d[]不单增，与定义矛盾二分查找d[]中不大于a[i]的最大元素，返回下标poj 2533*/#include <iostream>#include <cstdio>#include <cstdlib>#in...

2018-07-18 16:58:49 245

原创高斯消元法

跟着大哥混系列。。模板题：luogu3389//普通高斯消元法模板#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>using namespace std;#define eps 1e-6int n...

2018-07-12 09:04:06 261

原创 bzoj1801 AHOI2009 chess

动态规划计数问题每行每列最多两个炮以每一行划分状态bzoj上不删掉system("pause");就无限RE #include #include #include #include #include #include using namespace std;#define P 9999973long long f[105][105][105];int n,m;l

2017-08-13 16:25:00 316

原创百度之星2017 资格赛 1003 度度熊与邪恶大魔王

完全背包这题要考虑到怪兽的数目100000很多，但是生命值1000和防御力10很小，并且招数种类1000也不大，（根据抽屉原理）说明有很多生命值或者防御力重复的怪兽。因此我们没有必要一个怪兽一个是怪兽大，只要对每种生命值和防御力的怪兽进行每种招数的转移即可。dp[i][j]表示消灭生命值为i,防御力为j的怪兽最少消耗的冰晶石数dp[i][j] = min ( dp[i][j], dp[

2017-08-06 20:07:15 626

原创 hdu4607 Park Visit 树形DP版

题目大意：给一棵树，要经过K个不同的点，求走的路径最短是多少。每一条树上的边长度都是1.先用DP求出树的直径len（表示直径上的边数）。如果k如果k>len+1，答案为沿着直径走，遇到比较好的岔路口就进去再出来，因为不要求方案，所以默认她会走。。。 len + 2*（k-len-1）在dog的帮助下理解了后面为什么这样算，学文化课大概真的会把脑子学坏。。。#includ

2017-07-28 11:41:33 397

原创 hdu5806 two-pointers

头尾两个指针扫就可以了，注意ans非常大，要用long long ，输入输出要配套#include #include #include #include using namespace std;int T,n,m,k,x,s,i,j;long long ans;int a[200010];int main(){ scanf("%d", &T); while (

2016-08-10 19:47:26 640

原创 poj3264

水一发线段树，顺便复习（骗经验）...宝宝还是想好好走下去^ ^#include #include #include #include using namespace std;#define N 50010int n,q,x,y,m1,m2;int a[N];struct node{ int l,r,m1,m2,num;}tr[N*4];void updata(in

2016-07-21 15:09:33 415

原创 poj2182 Lost Cow

根据题目给出的数列的性质，每次可以求出最后一头牛的编号也就是在当前有的数列1 2 3 .... n 中找到第a[i]+1小的数可以用树状数组或者线段树，记录的是已经删除了的数的个数还有的数的个数为区间长度-区间记录的数字这个是单调的（不严格），所以可以用二分查找优化然后更新一下就可以了#include #include #include #inclu

2016-07-21 14:36:35 545

原创 [hihoCoder太阁最新面经算法竞赛8]B.Dice Possibility

描述What is possibility of rolling N dice and the sum of the numbers equals toM?输入Two integers N and M. (1 ≤ N ≤ 100, 1 ≤ M ≤ 600) 输出Output the possibility in percentage with 2 decimal pla

2016-07-19 00:25:00 571

原创 hdu1028;hdu1398——母函数入门

Tanky Woohdu1028分解整数G(x)=(1+x+x^2+…)*(1+x^2+x^4+...)*(1+x^3+x^6+...)*...*(1+x^n)所以第i个括号的增量是i，从0开始，保证方案数没有重复，从小到大排列答案为h(N)#include #include #include #include using namespace std;int n;

2016-07-16 18:21:00 571 1

原创 [hihocoder]太阁最新面经算法竞赛8]A.A Game

题目大意：小hi和小ho玩游戏，给出一个数列，两人每次从数列的头尾取数，小ho 先取，小hi每次都采取最优策略，问小ho最终能取得的数的总和最大是多少。分析：一开始想贪心，但贪心不行，不知道以前从哪本书上看到说每个人都只能去奇数位或偶数位上的数，但显然这是不对的。那么就dp吧，一个区间dp。因为两个人轮流取数，而且都执行最优策略，那么只要求某个长度下某人执先手可以取得的最大和就可以转移了。

2016-07-16 12:30:39 664

转载卡特兰数——括号匹配问题

卡特兰数的递推公式是F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}一般性公式为F(n)=C(2n,n)/(n+1)可以描述的问题有1、n个元素的二叉查找树有多少种。2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。3、2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票

2016-04-05 23:59:01 2604

原创 BC#78Div.2 1001

虽然是一道很水的题，但是要考虑不等式移项才能不爆long long//a a-b-c<d//long long 的范围是 -2^63~2^63-1//unsigned XX 没有负数，如果运算结果是负数的话会变成循环的那个正数//对于会爆炸的不等式可以考虑移项使得不等号两边的数不爆炸//能构成一个四边形的条件是：任意一边小于其他三边之和//注意如果有边==0，也不能构成四边形#in

2016-04-02 22:38:52 388

原创 bzoj1036-树链剖分模板

剖分后的树有如下性质：性质1：如果(v,u)为轻边，则siz[u] * 2 性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。总之两个dfsdfs1(int x,int f) //f是x的父亲枚举和x相邻的点的时候注意不等于f 才可以递归要维护的东西： dep[x] x节点深度 siz[x] 以x节点为根

2016-03-18 23:39:11 1245

原创 bzoj1070: [SCOI2007]修车-费用流

Description同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。Input第一行有两个m,n，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+

2016-03-16 19:12:24 1547

原创 1192: [HNOI2006]鬼谷子的钱袋

用二进制表示是最少的把m变成二进制，那么用m的二进制的位数那么多钱袋就可以了比如m=11010那么多个钱袋放1,10,100,1000.10000，最多可以达到11111所以这道题就是求m的二进制位数#include #include #include #include using namespace std;int n,m;int main(){ sca

2016-03-03 00:08:51 1396 1

原创 bzoj1208：[HNOI2004]宠物收养所-splay

这个splay维护的不是下标，维护的是数值，所以每必要记下size 还有各种标记只要能够插入一个数，删除一个数，找一个不在树中的数的前驱和后继就可以了。需要想的是这道题并不需要用两个splay或者记下多余的没用掉的宠物或者人，只要用一个splay就好了，因为题目中说了任意时刻宠物店中只有人或者只有宠物，这样轮换着用一个splay就好了orz...好奇怪，这道题在家里写了一天都是WA，在

2016-03-02 19:42:30 977

原创 poj1149 PIGS-Dinic模板

这道题的建图比较有趣，流入猪圈的和流入超级汇点的是常规的建法，然后根据题目性质，除了在猪圈和有相应钥匙的人之间连边，同时也在依次同一个猪圈买猪的人之间依次连边，因为这样可以保证上一个人打开的猪圈剩下的猪可以流向下一个人，对公共的猪圈而言，是剩下的猪流向下一个人。这样就符合题意了。加当前弧优化的Dinic&i居然是参变量可以让等于它的变量的值跟着改。#include #

2016-03-02 18:49:02 677

ioi2013 art_class的题目描述

空空如也