QTY_-CSDN博客

原创自我介绍

hzoi即将参加NOIP2017的某oier，觉得自己的奥赛之路也就是到联赛吧。。学的不怎么地，考试老挂，每天默默膜拜周围的大佬。。。虽然一路上并不太顺利，但笑过，也哭过，有兄弟一路陪伴。。。不枉为青春路上的一段风景雁过留痕，走过就要留下些痕迹，别让记忆随风而逝。再回首，由此博客，记录最后拼搏的岁月。愿高中生活因奥赛而添彩。

2017-07-26 21:05:53 1156 5

真的要联赛滚粗了。。。DAY 0上午就从衡水出发了，往德州的大巴上和一个学弟坐一起了（成功和ljy错开了QAQ）。。。从德州坐的高铁直达秦皇岛，挺舒服的，好评。被joker弄醒之后就和std,joker玩了一路听低级但好玩的某猜拳游戏。16:30到的燕大，还能赶上试机，鼠标键盘灵敏得不习惯，简单敲了个高精拍了一下(结果还拍出错了，多写了一个输出。呵呵)在回宾馆的路上碰到了爸妈（说实在，唐山到秦皇岛比

2017-11-15 11:22:29 959 1

原创联赛前最后一次总结

也算不上总结，退役前提前说说自己的经历。最开始，只是听父母提到奥赛，觉得挺有意思，并没有一个明确的目标。后来经过一些抉择选择了信息奥赛。开始时只是觉得喜欢电脑之类的知识，当把C++语言入门学完，开始接触算法之后，才发现信息奥赛十分有趣，也渐渐热爱上的OI.做过了一道很难，或者好多个算法结合起来的题，总有一种发自内心的满足感，越发觉得有趣中间还经历了很多。。。。快联赛的，考试频率越来越高，成绩总是忽上

2017-11-10 08:40:24 518

原创 DP bzoj4321 queue2

问题 J: queue2 时间限制: 1 Sec 内存限制: 128 MB 题目描述 n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行；现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。输入只有一行且为用空格隔开的一个正整数 N，其中 100%的数据满足 1≤N ≤ 1000; 输出

2017-11-05 11:49:00 648

原创卡常神器手写堆

跟gxy大神还有yzh大神学了学手写的堆，应该比stl的优先队列快很多。其实就是维护了一个二叉堆，写进结构体里，就没啥了。。。据说达哥去年NOIP靠这个暴力多骗了分合并果子。。。。#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define N

2017-11-03 10:38:18 858 1

原创 bzoj3124 [Sdoi2013]直径树的直径

问题 I: [Sdoi2013]直径时间限制: 1 Sec 内存限制: 256 MB 题目描述小Q最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有N个节点，可以证明其有且仅有N-1 条边。路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a

2017-11-03 10:34:43 940

原创树规+二分 [Poi2011]Dynamite

Byteotian Cave的结构是一棵N个节点的树，其中某些点上面已经安置了炸药，现在需要点燃M个点上的引线引爆所有的炸药。某个点上的引线被点燃后的1单位时间内，在树上和它相邻的点的引线会被点燃。如果一个有炸药的点的引信被点燃，那么这个点上的炸药会爆炸。求引爆所有炸药的最短时间。输入：第一行是两个整数N,M。(1<=m<=n<=300000）接下来一行有N个整数Di，第I个数为1表

2017-10-31 06:23:24 348

原创概率DP Spoj4060 game with probability Problem

问题 A: Spoj4060 game with probability Problem 时间限制: 1 Sec 内存限制: 128 MB 题目描述 Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷

2017-10-30 21:14:39 391

原创树规 [Heoi2013]Sao

问题 J: [Heoi2013]Sao 时间限制: 3 Sec 内存限制: 256 MB 题目描述 WelcometoSAO(StrangeandAbnormalOnline)。这是一个VRMMORPG，含有n个关卡。但是，挑战不同关卡的顺序是一个很大的问题。有n–1个对于挑战关卡的限制，诸如第i个关卡必须在第j个关卡前挑战，或者完成了第k个关卡才能挑战第l个关卡。并且，如果不考虑限

2017-10-30 20:54:27 406

原创十月集训总结

我好颓废啊。。。以后应该不会分机房了。。那么总共分了3次。我以7/15/15的名次三次都留在了第一机房（明显的退步）。其实第二轮是非常险的，要不是那几个人被开回家了而且不算成绩，我在就滚到第二机房了。。。第三轮感觉稍有好转，但成绩起伏很大，而且没有突出的成绩，考好了10名左右，考不好20大几。。。每次总结都在说自己不稳，但从来没有改善，还是太浮躁了，不能以良好的心态正确面对成绩，考不好就

2017-10-30 17:59:55 485

原创概率DP 收集邮票

问题 H: 收集邮票时间限制: 1 Sec 内存限制: 162 MB= 题目描述有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

2017-10-28 21:47:05 366

原创 tarjan BLO

[POI2008]BLO 时间限制: 1 Sec 内存限制: 162 MB 提交: 56 解决: 30 [提交][状态][讨论版] 题目描述 Byteotia城市有n个 towns m条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 所有towns连通。输入输入n<=100000 m<=500000及m条边输出输出n个数，代表如果把第i个

2017-10-28 21:43:42 354

原创矩阵乘 [Shoi2013]超级跳马

问题 F: [Shoi2013]超级跳马时间限制: 1 Sec 内存限制: 256 MB 题目描述现有一个n行m列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。例如，当n = 3, m = 10时，下图是一种可行的跳法。试求跳法种数mod 30011。输入仅有一行，包含两个正整数n, m，表示棋盘的规模。

2017-10-26 07:25:19 538

原创几何 Crazy Rabbit

问题 H: Crazy Rabbit 时间限制: 2 Sec 内存限制: 512 MB 提交: 37 解决: 12 [提交][状态][讨论版] 题目描述兔子们决定在自己的城堡里安排一些士兵进行防守。给出 n 个点的坐标，和城堡里一个圆心在原点的圆形的障碍，兔子们希望从中选出 k 个兔子，使得它们两两所在的直线都不与圆相交。兔子们希望知道最多能选出多少兔子输入第一行两个整数

2017-10-26 06:26:04 535

原创可持久化01Trie [Heoi2013]Alo

问题 I: [Heoi2013]Alo 时间限制: 3 Sec 内存限制: 256 MB 提交: 64 解决: 24 [提交][状态][讨论版] 题目描述 Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，如名字所见，到处充满了数学的谜题。现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石

2017-10-24 21:38:08 888

原创矩阵乘+概率DP bzoj2676 Contra

问题 C: Contra 时间限制: 3 Sec 内存限制: 512 MB 提交: 133 解决: 33 [提交][状态][讨论版] 题目描述　　偶然间，chnlich发现了他小时候玩过的一个游戏“魂斗罗”，于是决定怀旧。但是这是一个奇怪的魂斗罗MOD。　　有N个关卡，初始有Q条命。　　每通过一个关卡，会得到u分和1条命，生命上限为Q。　　其中u=min(最近一次连续通过

2017-10-24 21:23:53 815

原创树链剖分树

很明显一点，T1树里每一条边都会被选取一次。把T2树的每一条边看成一个线段覆盖。每次找到一个只被覆盖了一次的线段，找到他是被那个区间覆盖的，把那个区间删去。如果最后能删完，就有解，删不完就是无解。搞个树剖维护区间被覆盖的最小次数。但是较难的地方是：如何判断某一条边是被那个区间覆盖的。其实我们可以再维护一个值，把覆盖这个点的区间的编号加起来，因为我们找线段时只是找被覆盖一次的线段，所以一定就是他的

2017-10-24 20:51:03 261

原创凸包+可持久化栈 Lost My Music

这玩意看上去好恶心。。。实际上并没有。原来的式子是(c[top]-c[i])/(dep[i]-dep[top])—-> -(c[top]-c[i])/(dep[top]-dep[i]).这样就变成了斜率的形式了。要原来的式子最小，同理就是要现在的式子最大，并且这个斜率满足单调性。如果把斜率从小到大排序，然后放在一起，发现就成了一个下凸壳。考虑维护一个栈，dfs，每到一个点就退栈直到第一个满足的位置

2017-10-24 06:50:50 565

原创线段树 God Knows

听说这是“极长上升序列”。。。我们可以把题中的图改一下，把左侧的一排视为编号，此位置的值就是此点在右侧连的点的编号。这样问题就变成一个序列了。很明显选一个点就会覆盖它之前权值比他大的点以及它之后权值比他小的点。设f[i]为最后一个选的是i，且i之前的全被覆盖时的最小花费。很容易发现，如果f[i]要从之前的f[j]转移过来，那么a[j]一定比a[i]小，否则i已经被j覆盖了。而且，a[j]一定是区间[

2017-10-23 21:46:22 411

原创二分 starway

很容易联想到二分答案。同样重点在于如何check什么时候不满足呢？有些点间距离<当前二分的答案*2，并且这些点连成了一排使至切断了0~m的整个平面。很明显可以维护一个并查集，并维护这个联通块的最上端和最下端，比较即可。优化：按x坐标排序，如果a[i].x-a[j].x>ans*2，那么前面的不可能再相交了。（否则n=6000,O(N*N*logN)会超时）#include <iostream>#i

2017-10-23 20:32:36 215

原创 aoj某比赛记录

背景：达哥lrd给我们推荐了foolmike的一场D2水平的模拟赛。过程：极其滑稽。。。T1是矩阵快速幂水题，T2有点意思，mike说正解是笛卡尔树，但我并查集+卡常貌似过了（一大拨人被卡常，yzh气得把所有差评都点了一遍）。172. 艺术统计描述提交自定义测试题目描述Marvolo正看着刚刚入手的北京市地图，路痴的他表示一脸懵逼。刚刚开完会的两人如释负重，决定在帝都游玩一

2017-10-21 09:35:58 405

原创状压DP 分裂

问题 E: 分裂时间限制: 1 Sec 内存限制: 128 MB 提交: 53 解决: 24 [提交][状态][讨论版] 题目描述 Description 背景：和久必分，分久必和。。。题目描述：中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。同时经常搞OI的他把这个变成了一个数学模型。假设中国的国土总和是不变的。每个国家都可以用他的国土面积

2017-10-20 17:58:21 791

原创欧拉函数+线段树奇数国

问题 B: 奇数国时间限制: 1 Sec 内存限制: 256 MB 提交: 82 解决: 44 [提交][状态][讨论版] 题目描述在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋，他惜财如命，因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的

2017-10-20 17:33:30 784

原创单调队列 A

题面去内网找很明显正解要二分答案，如何高效率地check呢 1.搞一发线段树。 2.单调队列。题挺水的，但是该复习一下单调队列了。#include <cstdio>#define N 100005int read(){ int sum=0,f=1;char x=getchar(); while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar

2017-10-20 14:11:38 205

原创杂题 [Ceoi2010]A huge tower

问题 A: [Ceoi2010]A huge tower 时间限制: 1 Sec 内存限制: 259 MB 题目描述有N(2<=N<=620000)快砖，要搭一个N层的塔，要求：如果砖A在砖B上面，那么A不能比B的长度+D要长。问有几种方法,输出答案 mod 1000000009的值输入第一行： N，D 第二行： N个数，表示每块砖的长度。输出方案数。输出要mod1000

2017-10-19 15:50:07 814

原创 NOIP初赛+CF某比赛回忆录

并没有怎么写过回忆录之类的东西。。。但这么重要的NOIP初赛得记录一下（还有点副线任务）简直太搞笑了。。。初赛前一天做了做NOIP2016的题，发现去年不会，今年还不会。。。然后听说录取线貌似还没有考试题的暴力分多？？放心了，再傻也有60吧然后第二天下午。。进了考场，竟有种调研考试的感觉，同场有好几个衡水二中的（按比例算他们妹子好多啊QAQ）。大猩猩趴着休息被OD抓了，莫名搞笑。开考

2017-10-18 21:36:42 725 2

原创乱搞寿司

题面去内网找。。第一思路当然是找一个位置成为断点，让所有的移动都不经过它，让一部分点到这个断点的两侧。很明显是有符合方案的，并且在所有枚举中有一种是最优解。于是我考试时打了O(N^2)的暴力。。。。枚举每一个点是要移动到左边还是右边。而实际上是可以找到一个边界之后用前缀和，找边界可以二分。O(N*logN），如果数据水可以卡过去。但是，如果移动红点，枚举每一个蓝点作为断点，边界就是最中间

2017-10-18 21:17:48 235

原创 tarjan 回家

题面去内网找。很明显要找的是割点，只要low[son]>=dfn[x]，则x为割点，因为son只能连到一个在父亲x以下的点，并不能回到x之上，故x是割点。同时考虑在无向图上的tarjan。这都是基础，这道题还要多考虑一个地方，如果这个割点没有割断1和n，那他也没有意义。只要在找割点时加一句，判断n是否在找完son时已被打上了时间戳了，切时间戳>=x的（在x以下），并在son以下。最后升序输出

2017-10-18 20:46:43 227

原创分层背包 [HNOI2007]梦幻岛宝珠

问题 I: [HNOI2007]梦幻岛宝珠时间限制: 1 Sec 内存限制: 162 MB 提交: 32 解决: 6 [提交][状态][讨论版] 题目描述给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大为，并输出最大的总价值。数据范围：N<=100;W<=2^30,并且保证每颗宝石的重量符合a*2^b（a<=10;b<=30）输入

2017-10-18 20:23:13 1082

原创容斥原理集合计数

问题 J: 集合计数时间限制: 1 Sec 内存限制: 128 MB 题目描述一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）输入一行两个整数N,K 输出一行为答案。样例输入 3 2 样例输出 6 提示【样例说明】

2017-10-18 19:52:49 1057

原创 DP [Sdoi2010]地精部落

问题 H: [Sdoi2010]地精部落时间限制: 1 Sec 内存限制: 64 MB 题目描述传说很久以前，大地上居住着一种神秘的生物：地精。地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为 N 的山脉 H可分为从左到右的 N 段，每段有一个独一无二的高度 Hi，其中Hi是1到N 之间的正整数。如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一

2017-10-18 18:28:10 611

原创树DP [ZJOI2008]骑士

问题 G: [ZJOI2008]骑士时间限制: 1 Sec 内存限制: 162 MB 提交: 104 解决: 38 [提交][状态][讨论版] 题目描述 Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能

2017-10-18 18:01:18 550

原创杂题 [Tjoi 2013]松鼠聚会

问题 F: [Tjoi 2013]松鼠聚会时间限制: 1 Sec 内存限制: 128 MB 提交: 70 解决: 35 [提交][状态][讨论版] 题目描述有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。输入第一行给出数字N，表示有多少只小松鼠。

2017-10-18 17:51:24 477

原创 DP+乱搞位运算

今天的题都这么。。。。这道题后面会用到逆推。。。。首先得判断是否有合法方案。而且方案明显会有很多种，但只需要统计算到这一位时答案有多少个1。设f[i][j]表示算完i位时，答案里有j个1. 考虑转移，转移时对答案产生影响的还有两位间1位置的交集，也就是f[i][j]&a[i+1]后1的个数，设它为k。交集中1个数就是运算符是 & : k 运算符是 |：j+a[i+1]-k

2017-10-17 21:47:13 289

原创数学数论

题面去内网找。这题目。。。。可以发现，如果数g不良，g*p^k一定也不良。所以搞个数组保留当前有哪几个数是良的。然后对这个数组进行拓展，就是枚举到下一个质数，把当前所有认为是良的数乘上当前质数的多少次方都加进这个数组里（边界就是乘到>m就停，但会炸long long，我傻写了个快乘）。这样数组就拓展完了，之所以上面我说是”认为良的”数，就是在这里拓展完之后，得把所有不满足的删掉，我用了一个权

2017-10-17 21:15:59 261

原创记忆化搜索 [SCOI2008]着色方案

问题 B: [SCOI2008]着色方案时间限制: 1 Sec 内存限制: 162 MB 提交: 80 解决: 38 [提交][状态][讨论版] 题目描述有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。所有油漆刚好足够涂满所有木块，即c1+c2+…+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木

2017-10-16 21:39:44 292

原创杂题翻硬币

问题 A: 翻硬币时间限制: 1 Sec 内存限制: 128 MB 题目描述有一个n行n列的棋盘，每个格子上都有一个硬币，且n为偶数。每个硬币要么是正面朝上，要么是反面朝上。每次操作你可以选定一个格子(x,y)，然后将第x行和第y列的所有硬币都翻面。求将所有硬币都变成同一个面最少需要的操作数。输入第一行包含一个正整数n。接下来n行，每行包含一个长度为n的01字符串，表示棋盘上

2017-10-16 10:11:44 508

原创贪心+线性基 [BeiJing2011]元素

问题 C: [BeiJing2011]元素时间限制: 2 Sec 内存限制: 128 MB 提交: 25 解决: 16 [提交][状态][讨论版] 题目描述相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法

2017-10-15 21:41:13 235

原创贪心阿狸和桃子的游戏

问题 E: 阿狸和桃子的游戏时间限制: 1 Sec 内存限制: 128 MB 题目描述　　阿狸和桃子正在玩一个游戏，游戏是在一个带权图G=(V, E)上进行的，设节点权值为w(v)，边权为c(e)。游戏规则是这样的： 1. 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。 2. 为了保证公

2017-10-15 21:25:05 543

原创区间DP 表达式

题面去内网找其实大模拟可过。题比较水，但考试时越改越没耐心。感觉怎么改都不对。。。还是我区间DP学得太死了。。。其实这题枚举到一个区间时，先处理端点（）还有’ ‘，再找中间的运算符就行了。#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<iostream>using namespace

2017-10-15 19:06:13 310

编程软件2subline

软件1devc++5.11

COGS提交的代码

空空如也