- 博客(40)
- 收藏
- 关注
RSS订阅原创 bzoj 3745: [Coci2015]Norma
考虑分治，对于区间[l,r]，计算左端点在[l,mid]，右端点在[mid,r]的区间对答案的影响然后自己推公式。#include #include #include #include #define rep(j,k,l) for (LL j=k;j<=l;++j)#define red(j,k,l) for (LL j=k;j>=l;--j)#define max(a,b)
2017-08-11 08:56:36
264
原创 2017Astar资格赛1002 度度熊的王国战略
啊啊全局最小割？看了一天没看懂考虑一个最小割，把原图分成两半（废话左边取一个点为S，右边去一个点为T，跑出来的最小割一定是答案（废话于是取1为S,随机T，1000组，保证不重复，随机数据随便过但是有卡点，3000个点被分成了2999+1或2998+2这两种情况都是可以预处理的当2997+3时有三个点随机到一个就行，1000次，A掉的概率有,大概每个点70%想想卡点不
2017-08-07 10:13:57
260
原创 Astar2017资格赛1005 寻找母串
S是一个偏串，长度为n的串也是偏串。那么从n中把S挖去，还是一个偏串即问你长度（n-s）的偏串数量*（n-s+1）{s在串中可插入的位置数}长度为k的偏串===就是第k/2个卡特兰数于是mmp n大就算了膜数也大分段打出阶乘表，隔200000个打一个表，然后暴力#include #include #include #include #define mod
2017-08-07 09:58:05
571
原创 loj #6164. 「美团 CodeM 初赛 Round A」数列互质
莫队==每次维护每个数出现的次数，再上链表维护出现次数的次数。发现不同的出现次数最多根号n个，因为要出现次数有不同的x个，至少要有x*(x-1)/2个数。然后考虑每次询问暴力枚举。先把k分解成质因数，不超过logk个，分解时要判定大质数，不然GG对于每个出现次数暴力验证，复杂度#include #include #include #include #include
2017-07-31 15:49:25
501
转载 loj#6169. 相似序列
讲题前先讲故事miaom：你快来做这道题啊啊==我已经A掉了我教你 啊YYMHL：吼啊10 min latermiaom：你听懂了嘛？YYMHL：不对啊10 min laterYYMHL：我把你hack掉了啊miaom：！！！那 你帮我改一下就当你自己做的好了以下内容转自http://blog.csdn.net/Miao_zc/article/deta
2017-07-31 11:03:46
349
原创 ZJOI一试酱油记
DAY -3晚上到了宾馆（说好红太阳的）然后打sgs看电视到凌晨，然后睡觉DAY -2早上讲搜索，看起来很和谐（之后便发现这是唯一听得懂的下午讲完STL讲杂题，撑不住了睡觉（增么玩嘛晚上打sgs泼隔膜（但奇迹的很早（11点半）睡觉了DAY -1讲了一天的杂题，泼了一天的隔膜晚上看完电视就睡了（一天比一天早DAY 1T1 smg啊，10分暴力调了3小时QAQ
2017-03-23 20:53:50
423
1
原创 [SDOI2006]保安站岗
对每个节点存三个状态：未保护（但子树完全保证符合）；被保护；自己站一个警察。然后就好了n才1500让我开始想到别的地方去了QAQ（TMD）INF比-1好用到不知道哪里去了#include #include #include #include #define rep(j,k,l) for (long long j=k;j<=l;++j)#define red(j,k,l)
2017-03-07 19:46:28
408
原创 [SDOI2009]HH去散步
第一道矩乘也就不口胡了吧代码还是很simple的~#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k,l) for (int j=k;j>=l;--j)#define N 121#define mod 45989using namespac
2017-03-03 20:35:28
228
原创 [LNOI 2014] LCA
方案一：[a,b] 的lca和可以变成[1,a] 与 [1,b] 的答案和。于是离线。copied from wlc1121方案二：询问的是区间，于是想到莫队树剖+线段树同上维护。我自己没写过一个根号*两个log==QAQ留给底层优化大师去实现吧...---------分割线---------（隔壁q234rty说可以用欧拉序列去掉一个log）（
2017-03-02 21:04:30
273
原创 [SDOI2010]大陆争霸
听说只能用Dijkstra做我已经不能分辨DJ和SPFA了存下每个点的最小到达时间f[i]，最晚开放时间g[i]，之后用max(f[i],g[i])去增广。#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k,l) for (int j=k;j>
2017-02-27 20:12:50
241
原创 [HNOI2013]切糕
不管高低差限制，把每一竖串连起来做最小割。有高度差限制用inf限制。图文伺候：http://blog.csdn.net/thy_asdf/article/details/50428973#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k
2017-02-24 18:49:35
250
原创 [HEOI2016]排序
二分答案还是比较容易想到的对于每一个二分出来的东西，扫一遍初始数组，小于该数赋0，大于等于赋1于是区间排序变成了区间数0 和 区间赋值。#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k,l) for (int j=k;j>=l;--j)#d
2017-02-22 20:49:32
181
原创 [SDOI2009]Elaxia的路线
先以x1 x2 y1 y2为起点跑4遍SPFA然后判定各条边在不在最短路上=如果两条最短路上都有则加入新图（有向边）对新图跑拓扑求最长链萌萌哒cd：可以无向边啊（TMD还A了我天老爷）#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k,l)
2017-02-22 20:45:51
270
原创 CodeForces - 487E Tourists
题意：询问两点任意路径上点权的最小值，可修改点权先把所有点双处理一下=造一个新点向所有分量内的点连边，取其中一个点作为父亲，权值是除父亲外点权的最小值（修改时同时修改父亲）=于是可见，任意点双内都是可以乱走的，所以走过新建店相当于对该分量内所有点取min，同时lca为新建点是还要把它爸算进去取min什么的好像有什么multiset=（十分害怕#include #inc
2016-12-14 13:23:24
344
原创 CodeForces - 486E LIS of Sequence
对于每个点求出开头到该点的最长上升子序列长度==以及该点到结尾的最长上升子序列长度（该点都强制使用）记为dp1和dp2于是如果dp1[i]+dp2[i]-1与LIS的长度相等 则该点为2或3否则为1对于不是1的点如果有别的点与它dp1相同则为2（即可以选该点也可以选别的相同的点）否则为3#include #include #include #include #def
2016-12-11 20:03:09
291
原创 ZOJ - 3820 Building Fire Stations
题意：给你一棵树求两个点使得树上所有点到这两个点路径长度的最小值最小取直径的中点拆掉拆成两棵树，分别求两边的直径中点就是答案==QAQ细节真多==还会爆栈不开心#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;j++)#define N 400005using na
2016-12-11 15:40:59
266
原创 HDU3686 Traffic Real Time Query System
找出所有的割点然后把两个割点之间的所有边缩成一个点于是变成了求路径上割点数目然而炸了3天=生命不息=Tle不止和wzf2000对拍跑的还比他快QAQ#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define red(j,k,l) for (int
2016-12-08 15:17:49
446
原创 UVA - 11604 General Sultan
对每两个字符串进行匹配然后连边=看程序应该能看懂开始st没清零不停地爆oj#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;++j)#define M 25#define N 110#define P 250010using namespace std;int n,T
2016-12-06 18:17:17
243
原创 CQOI2012 交换棋子
现在艹道水题都要半小时+=感觉整个人都不好了把点拆掉就可以了=因为次数限制在格子上又因为走进走出要2次直接÷2=想想头和尾只踩了一次所以除以2前先+1就好了#include #define rep(j,k,l) for (int j=k;j<=l;++j)#define K 22#define N 805#define M 50005using namespace std;
2016-12-01 14:50:04
340
原创 NOIP2016 DAY2
T1：可以预处理啊开始以为20倍常数要gg结果ccf的机子没想象中那么233#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;j++)#define N 2005using namespace std;int cl[N][25],sm[N][N],T,k;int gt(i
2016-11-29 18:45:03
287
原创 NOIP2016 DAY1
T1：听说很简单然后我biubiu了#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;j++)#define N 100005using namespace std;char s[N][15];int a[N],n,T;int main(){ scanf("%d%d",&
2016-11-27 20:42:11
295
原创 NOIP2016 酱油记
写这种东西难道是城里人的习惯嘛。=不能理解day1=T1 biubiu了这感情QAQT2T3一本正经的思考然后暴力也biubiuday2=为毛连暴力分都不给=我只说这一句话转身就走最近心理也有点**=所有rp都拿去2333了=对不住党和领导对我的培育和教导大家再见=泥萌千万不要再见啊QAQ
2016-11-24 15:13:59
322
原创 线性规划与网络流24题 ---19 负载平衡问题
从原点到每一个仓库连线，流为仓库的值，费用0从每一个仓库到汇点连线，流为平均值，费用0相邻的仓库连线，流无限，费用1跑出费用输出就好了#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;j++)#define N 105using namespace std;
2016-08-10 09:45:25
386
原创 BZOJ 2588==Spoj 10628. Count on a tree
题目传送门：233333在树上建一棵主席树然后乱搞就好了L~R的路相当于[RT,L]+[RT,R]-[RT,LCA(L,R)]-[RT,FA[LCA(L,R)]]，多调一会就好了bzoj上最后一行没有回车MDZZ不然会PE#include #include #include #include #define rep(j,k,l) for (int j=k;j
2016-08-09 15:24:42
218
原创 luogu P2184 贪婪大陆
题目传送门：233333本题由萌萌哒的我的同桌推荐（woc为毛bzoj自爆了）询问区间[L,R]，就是求出L点此时的地雷数+[L+1,R]中新加的地雷数L点地雷数=[1,L]的左端点数减去[1,L-1]的右端点数[L+1,R]中新加的地雷数=[L+1,R]的左端点数所以询问[L,R]就是[1,R]的左端点数-[1,L-1]的右端点数非要打线段树也不是不可以（就像我萌
2016-08-08 09:21:33
350
原创 HDU - 2222 Keywords Search
题目传送门：23333AC自动机的裸题（虽然我看了好长时间写了2H才2333的A掉QAQ）开始没看到多组数据=幸好有cl大的提醒参考：AC自动机详解#include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;j++)#define N 10005#define M 10
2016-08-04 10:13:36
210
原创 BZOJ 3685 普通van Emde Boas树
题目链接：233333一棵裸裸的线段树rank为一个点在现在里面的排名第一个和第二个操作脑补成单点修改第三个和第四个操作脑补成看rank求点第五个和第六个操作脑补成求一个点的rank数然后+1或-1转为看rank求点第七个操作===你不会我也没办法程序中的rank可以理解为sum，自己手贱没办法#include #include #inc
2016-07-20 21:08:00
226
原创 BZOJ 2243 [SDOI2011]染色==树链剖分
题目传送门：233333学会了树剖之后这道题就主要看线段树的本事了先树剖，开线段树维护区间的颜色段数量以及最左端和最右端的颜色。合并是考虑相邻的两种颜色，如果颜色相同则ans--。在处理树剖时要看好哪一端颜色和哪一端相连，才可以正确的合并。---------------------------乌龟天空游-----------------------------最好在
2016-07-20 15:45:13
287
原创 BZOJ 4196 [Noi2015]软件包管理器
题目传送门：2333333还是裸的树剖题。每个点0=没下载，1=已下载下载就是查找这个点到零的路径上有几个0，再把整条路修改成1。卸载就是查找这个点子树中有几个1，再把整棵子树改为0。再发现一颗子树在dfs序里面是连续的一串（自己脑补），所以就变成了线段树区间赋值+求和，随便就过了。#include #include #include #inclu
2016-07-19 20:55:19
219
原创 BZOJ 3631 [JLOI2014]松鼠的新家==树剖
题目传送门：23333十分考验树剖的本事在网上看到几个大神写树剖T掉了233333主要是树剖，剖完后把一条路上的点不停地打永久标记，不用向下推，查询时直接把flag加起来就好了。另外除了第一个点外其余点都要减一，中间的点进入会拿一颗糖，出时也会计算一个，所以要减去。最后一个房间的糖题目说了不用，所以也要减。（虽说被这个坑了好久QAQ）#inclu
2016-07-19 19:26:36
361
原创 BZOJ 1103: [POI2007]大都市meg==树剖
题目传送门：23333我是用树剖写的，剖边不剖点，就是正常的树剖。只不过把第一个节点不计入线段树里。只是数据有点大开数组要节省（其实一般都不会炸，但不知为何我经常MLE）。但听说还有别的做法来节省代码量，就像我神奇的同桌的隔走廊同桌所说的那样。似乎叫做链上求和，详情百度。#include #include #include #include #def
2016-07-19 17:41:07
226
原创 BZOJ 3212【Pku 3468】A Simple Problem with Integers==线段树裸题
题目传送：23333直接建树，区间修改可以打永久标记，查询直接查就可以了。记得要开long long==我不知道不开会不会WA反正我开了#include #include #include #include #define rep(j,k,l) for (long long j=k;j<=l;j++)using namespace std;long
2016-07-19 16:31:05
229
原创 BZOJ 1012 [JSOI2008]最大数maxnumber=听说是线段树
题目传送门：23333听说是线段树标算，但我不知道为毛写了一个黑科技。--------------------------黑科技维护一个递减栈，每次增加元素时，如果栈顶元素小于新增则弹出来保持递减性。并且同时存下栈中元素的号码。查询时从栈顶往下找，找到一个在L以内最大的输出即可。--------------------------以下论线
2016-07-19 16:19:02
477
原创 BZOJ 1036 [ZJOI2008]树的统计Count==树剖裸题
题目传送门：233333直接把那棵树剖开来，剖成一条条的链，然后直接用两棵线段树维护就好了啊不会树链剖分的出门左拐。然后你会撞到墙上2333.树剖思路：设size为以该节点为根的子树的结点个数，对于每一个不是叶子节点的节点，在儿子中选出一个size最大的作为重儿子，那条边叫做重链。之后再一次dfs，优先搜索重儿子，整理出搜索顺序之后就会发现，连在一起的重
2016-07-19 15:50:34
227
原创 BZOJ 1015 [JSOI2008]星球大战starwar
问题传送门：2333其实比较23333333333333---------------------（看到 []山边[] 自然而然的就会倒着来减边对吧）于是窝萌就想出了一个倒着来的方法加边在带并查集就好了#include #include #include #include #include #define rep(j,k,l) for (int j=k;j<=l;
2016-07-14 14:29:06
235
原创 BZOJ 1007 [HNOI2008]水平可见直线===数学相关
题目链接：点我传送（第一道不看题解过的题目==2333333=====思考过程先是想到最左边肯定是斜率最小的，最右边肯定是最大的（因为x趋近于-∞时斜率小的算出来大，因为x趋近于+∞时斜率大的算出来大。于是就想到了把直线按照k从小到大排序。后来又想到，k相等时，只有b最大的直线会出镜，别的不用管，所以排序时顺便去掉这些无用线。于是就想到，三条直线Y1,Y2,Y3,满
2016-07-05 20:04:21
406
原创 BZOJ 1006 [HNOI2008]神奇的国度==最大势算法
题目链接：点我传送算法初步：点我传送算法证明：我不会且找不到=====回归正题=====首先大家一眼就看出来这道问题的实质：给你一个无向图，用最少的颜色染色，使得相连接的两个点颜色不同。（不要告诉我有板子。这种题目就要用到一种恒牛掰的算法=======最大势算法！！！（第一反应==这什么鬼（第二反应==百度百度的童鞋萌，泥萌走出了正确的一步！！！算法的主要思
2016-07-04 20:07:22
3082
原创 BZOJ 1001 狼抓兔子 [最小割转最短路=平面图转对偶图]
原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1001参考资料：最大最小定理(平面图最小割 对偶图)周冬对偶图的应用【思考】这题就是一道裸的最小割[什么你看不出来]，求最小割去多少边，使得起点与终点不连通。于是你就试着写流（滑稽。=======================
2016-06-24 19:24:13
1601
2
原创 POJ 1639 Picnic Planning 【最小度限制生成树】
原题链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11062http://poj.org/problem?id=1639参考资料：http://blog.csdn.net/ji414341055/article/details/5781800http://www.cnblogs.com/
2016-06-22 20:48:36
314
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人