- 博客(64)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 【bzoj 1922】大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的 克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭 的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。 幻想历 8012年 1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同 时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。 幻想历 8012年 3月2日，位于杰森...
2018-04-30 21:53:52
278
原创 省选回忆录 ----划水进省队
day0早上坐火车，同校四位大佬都坐在我隔壁座，我只能面对tf和yzh独自而坐。。。 坐地铁试机，hsdfz的dalao正在准备让Duan2baka女装（其实蛮期待的。。。可惜没能成功见到day1早上起床吃个早餐，和同校5人一起去考场，半路遇见hhc，互相奶了几发，然后奔入考场。 接收到题，先看了看第一题（一脸蒙逼？？？what？到底怎么最优啊，对方互相知不知道对方知道自己知道对方...
2018-04-17 21:41:41
585
原创 bzoj1242: Zju1015 Fishing Net弦图判定
Description在一个高度信息化的渔村，鱼网的制作和修补都是由电脑完成。众所周知，鱼网是由网组成的(废话)，网组成的东西叫网眼。如果网眼够小，就能捕到很多鱼；如果网眼太大，鱼就会全部漏走。每次捕鱼回来，鱼网都会烂得很厉害，小网眼会变成网眼，那鱼网就需要修补。他们希望有一个程序能够为他们判断鱼网是否需要修补。程序会把鱼网看作一个联通的图(不用进一步解释了吧)。他们的判断方法是：任何一个长度...
2018-03-04 15:17:22
314
原创 【MCS】bzoj1006: [HNOI2008]神奇的国度
Description K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA 相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2 …An之间仅存在N对认识关系:(A1A2)(A2A3)…(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C D...
2018-03-04 15:04:29
226
原创 完美消除序列，MCS算法
首先，我们有一些定义对于普通图的两个性质：最大团数 ≤ 最小染色数 最大独立集 ≤ 最小团覆盖而在弦图就变成了：最大团数=最小色数 最大独立集=最小团覆盖 完美消除序列：对与序列中的点vi，排在vi后面并且和vi相连的点是一个团 一个图存在完美消除序列是它是弦图的充要条件那么完美消除序列有什么用呢？用处可大啦 求弦图的最大团数/最小色数的时候，只要在...
2018-03-04 14:56:19
1736
原创 图中的一些定义
实例：无向图G=(V, E)，V为图的所有顶点集合（非空），E为图的所有边的集合。 【子图（subgraph）和生成子图（spanning subgraph）】 G’=(V’, E’)，V’被包含于V，E’被包含于E，G’为G的子图。 另外对于子图有一个生成子图的概念，而者的区别在于：在子图中，E'<=E且V'<=V；在生成子图中，E'<=E,且V'=V...
2018-03-04 14:48:09
682
原创 省选模拟 T2 医院
题面 题目大意有两种护士，分别为A类和B类, A类休假需要有人代替，而B类不需要，每位A类护士有一个可以代替她的护士列表。 现在要找出不可以休假的护士， 以及不可以同时休假的护士(x,y)（(x,y)是无序数对，其中x和y都必须可以单独休假，但不能同时休假）。思路这题首先你先把它转化成图论 若a可以替代b休假，就连一条a->b的有向边 而题中第一个问题，谁不能
2018-01-27 14:59:37
291
2
原创 bzoj1034: [ZJOI2008]泡泡堂BNB
Description 第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表 队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份 参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号 选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场
2018-01-18 22:12:06
218
2
原创 【bzoj 1066】蜥蜴（最大流）
Description 在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃 到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石 柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不 变），如果该石柱原来高度为1，则蜥蜴离开后消失。以
2018-01-17 16:41:13
266
2
原创 noip模拟 平均数【二分+归并排序】
Description有一天，小A得到了一个长度为n的序列。 他把这个序列的所有连续子序列都列了出来， 并对每一个子序列 都求了其平均值， 然后他把这些平均值写在纸上， 并对它们进行排序， 最后他报出了第k小的平均值。 你要做的就是模仿他的过程 思路题解一：实数二分+树状数组+排序。先分析一下题目，如果是暴利枚举的话肯定会TLE。所以我们只能考虑二分答案，我们二分
2018-01-17 16:38:27
353
1
原创 bzoj1071: [SCOI2007]组队
Description NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里 速度最慢的球员速度为minV，身高最矮的球员高度为minH，那么这支球队的所有队员都应该满足: A * ( height – minH ) + B * ( speed – minV ) 球员速度和身高差距太大，会造成配合的不协调。 请问作为球队管理层的你，在N名
2018-01-16 16:41:06
344
2
原创 bzoj3408: [Usaco2009 Oct]Heat Wave 热浪
传送门DescriptionInput第1行：4个由空格隔开的整数T，C，Ts，Te. 第2到第C+1行：第i+l行描述第i条道路．有3个由空格隔开的整数Rs，Re，Ci.Output一个单独的整数表示Ts到Te的最小费用．数据保证至少存在一条道路．Sample Input7 11 5 4 2 4 2 1 4 3 7 2 2 3 4 3
2018-01-16 08:40:18
238
原创 bzoj4059: [Cerc2012]Non-boring sequences
Description我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。Input第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 Output对于每组数据输出一行，输出”
2018-01-15 15:20:35
265
原创 bzoj4195: [Noi2015]程序自动分析
传送门Description在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定 n 个形如xi=xj 或 xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3
2018-01-15 13:56:04
177
原创 虚树模板
虚树所谓虚树，就是我们在做题中把用到的点建到一颗新树上。 比如如果我们当前询问一条链的两端，如果我们直接dfs（暴力）的话时间复杂度就是O(n) 但是如果我们用虚树，那么这棵树上就只会有这两个节点 两个节点之间的那条边记录了原本链的信息 于是复杂度从O(n)为了O(2)一般题中除了给出的询问点，我们还会用到询问点的lca，但是lca数也是o(n^2)的，于是我们想到把关键点按dfs序排序，
2017-12-21 20:08:39
303
2
原创 【lct模板】bzoj2631: tree
Description 一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一： + u v c：将u到v的路径上的点的权值都加上自然数c； - u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树； * u v c：将u到v的路径上的点的权值都乘上自然数c； / u v：询问u到v的路径上的点的权值
2017-12-21 16:30:43
279
原创 splay模板
#include<bits/stdc++.h>using namespace std;struct Node{ Node *ch[2],*fa; int key,siz; bool flip; Node(int); int dir(int val){ if(val==ch[0]->siz+1) return -1; re
2017-12-08 15:16:32
1462
原创 【线段树合并】【bzoj4399】: 魔法少女LJJ
Description在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了 LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果；鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境” SHY觉得LJJ还是太naive，一天，S
2017-12-06 14:37:15
1366
2
原创 【模板主席树】洛谷p3834
主席树主席树的主体是线段树，准确的说，是很多棵线段树，存的是一段数字区间出现次数（所以要先离散化可能出现的数字）。举个例子，假设我每次都要求整个序列内的第 k 小，那么对整个序列构造一个线段树，然后在线段树上不断找第 k 小在当前数字区间的左半部分还是右半部分。这个操作和平衡树的 Rank 操作一样，只是这里将离散的数字搞成了连续的数字。先假设没有修改操作：对于每个前缀 S1…i，保存这样一个线段树
2017-11-04 20:50:26
460
原创 【搜索】bzoj1086: [SCOI2005]王室联邦
Description “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成 员来管理。他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条 直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个 城市。每个省必须有一个省会，这个省会可以位于省内，也可以在该省
2017-10-30 10:05:45
943
原创 【动态规划】字符串编辑距离（Levenshtein距离）算法
基本介绍Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量（string metric）。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如修改、插入、删除）所需要的最少次数。俄罗斯科学家Vladimir Levenshtein于1965年提出了这一概念。简单例子从字符串“kitten”修改为字符串“sitting”只需3次单字符编
2017-10-27 20:51:47
2433
原创 【动态规划】【记忆化搜索】关键子工程
Description 思路这题其实是一道比较经典的Dp题，可以用记忆化搜索来解决这道题 首先子工程之间由于优先性，构成一个图，而Dp却只能解决有向无环图，所以我们先进行拓扑排序，用拓扑序进行递推，检验图是否有环 接着我们只需记忆化搜索进行Dp即可求出最大时间 然后我们第二次动规是反向来写的，Dp出每个子工程最晚完成的时间，与上一次Dp求得的时间进行判断，若相等则证明他是关键子工程代码#in
2017-10-27 20:12:14
293
原创 【搜索+枚举+数学思维】洛谷P1286 两数之和
题目描述我们知道从n个非负整数中任取两个相加共有n*(n-1)/2个和，现在已知这n*(n-1)/2个和值，要求n个非负整数。输入格式：输入文件有若干行，每行一组数据，包含n*(n-1)/2+1个空格隔开的非负整数，其中第一个数表示n(2输出格式：输出文件若干行，对应每一个输入，该行按从小到大的次序依次输出一组满足要求的n个非负整数，相邻两个整数之间用一个空格隔开；若问题无解则输出“Impossib
2017-10-23 20:02:06
673
原创 【树链剖分】bzoj4034: [HAOI2015]树上操作
~biu~Descriptionsubmit 有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个 操作，分为三种： 操作 1 ：把某个节点 x 的点权增加 a 。 操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。Input第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，
2017-10-13 20:07:40
289
原创 【动态规划】BZOJ2423: [HAOI2010]最长公共子序列
Description字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列Input第1行为第1个字符序列，都是大写字母组成，以”.”结束。长度小于5000。 第2行为第2个字符序列，都是大写字母组成，以”.”结束
2017-10-13 09:03:29
219
原创 【线段树】bzoj2957：楼房重建
~传送门~Description 小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。 为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与
2017-10-12 21:28:12
253
原创 莫比乌斯函数详解
在讲这个函数之前。最好先了解欧拉函数。我们用 \ 记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。欧拉函数用来表示。 那么根据法里级数的展开(这个感觉和ACM关系不大就先不介绍了。大概讲的就是构造所有最简分数的一种树。而法里级数n定义分母<=n的最简分数。)比如对于分母为12. 化简后: 分别为:1/12 1/6 1/4 1/3 5/
2017-10-12 20:47:12
3319
原创 【二维树状数组】【模板】poj1195Mobile phones
biu~DescriptionSuppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and
2017-10-12 20:18:56
190
原创 【树链剖分】【bzoj2157】: 旅游
DescriptionRay 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座
2017-10-11 21:25:58
203
原创 【数论】【poj1845】Sumdiv
DescriptionConsider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).InputThe only line contains the two nat
2017-10-11 15:36:44
269
原创 【bzoj1036】【树链剖分】 [ZJOI2008]树的统计Count
Description 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成 一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身Input 输
2017-10-09 21:24:48
294
原创 【DBSDFZOJ4473】幻想
Description ~~只有图片思路其实这题看的第一眼首先想到的就是最短路 但是他有k次机会可以使路径变为原来的一半（向下取整） 当k==0时，我们只需跑一个最短路即可 在其他情况下，我们可以用Dp思想，从用了i次机会推到用了i+1次机会 每次都可以用最短路来求（我这里写的是分层Spfa） 时间复杂度应该是k*O（P *m）（p为Spfa常数）PS：这里要用long long，否则会
2017-10-05 14:35:45
219
原创 【欧拉函数+线性筛】bzoj2818: Gcd
biu~题目在这里Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.Input一个整数NOutput如题Sample Input4Sample Output4HINT对于样例(2,2),(2,4),(3,3),(4,2) 1<=N<=10^7思路枚举n内每个质数，然后每个质数p对答案的贡献就是（1~n/p）中有序互质数对的个数 而求1~n
2017-10-05 10:35:42
283
原创 【huffman】bzoj4198:【UOJ#130】 [Noi2015]荷马史诗
题目在这里~~Description Time Limit: 10 Sec Memory Limit: 512 MB追逐影子的人，自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些
2017-10-04 13:07:09
196
原创 【GarsiaWachs算法】bzoj3229: [Sdoi2008]石子合并
biu~DescriptionTime Limit: 3 Sec Memory Limit: 128 MB submit在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将N堆石子合并成一堆的最小得分。 Input 第一行是一个数N。 以下N行每行一
2017-10-04 10:51:31
513
原创 【Dijkstra堆优化】【BZOJ 3040】 最短路(road)
传送门~Descriptionsubmit Time Limit: 60 Sec Memory Limit: 200 MBN个点，M条边的有向图，求点1到点N的最短路（保证存在）。 1<=N<=1000000，1<=M<=10000000Input第一行两个整数N、M，表示点数和边数。 第二行六个整数T、rxa、rxc、rya、ryc、rp。前T条边采用如下方式生成： 1.初始化x=y=z
2017-10-04 08:29:43
700
原创 bzoj1411: [ZJOI2009]硬币游戏
DescriptionOrez很喜欢玩游戏，他最近发明了一款硬币游戏。他在桌子的边缘上划分出2*n个位置并按顺时针把它们标号为1，2，……，2n，然后把n个硬币放在标号为奇数的位置上。接下来每次按如下操作：在任意两个硬币之间放上一个硬币，然后将原来的硬币拿走；所放硬币的正反面由它两边的两个硬币决定，若两个硬币均为正面朝上或反面朝上，则所放硬币为正面朝上，否则为反面朝上。 那么操作T次之后桌子边缘上硬
2017-10-03 20:30:16
456
原创 【二分+数学】bzoj1257: [CQOI2007]余数之和sum
biu~Description给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7Input输入仅一行，包含两个整数n, k。Output输出仅一行，即
2017-10-03 20:16:19
386
原创 C++中 bitset的用法及解释
~这里我们来介绍一下bitset的用法~bitset首先我们了解一下什么是bitset： ①：C++语言的一个类库，用来方便地管理一系列的bit位而不用程序员自己来写代码。bitset除了可以访问指定下标的bit位以外，还可以把它们作为一个整数来进行某些统计。 ②：大小可动态改变, 取值为true或false的位集合。用于表示一组bool标志。 它隶属于头文件<bitset><bitset>通
2017-09-29 21:35:39
2033
二分三分哈希
2017-09-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人