YuYaoHeKai-CSDN博客

原创 BZOJ2299: [HAOI2011]向量

Time Limit: 10 Sec Memory Limit: 256 MB Description给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。说明：这里的拼就是使得你选出的向量之和为(x,y)Input第一行数组组数t，(t<=5000

2017-06-22 19:21:47 513

原创 BZOJ1984 月下“毛景树”

这题在线段树中需要成段覆盖和成段加，在处理时需要当心。同时需要将边权转换成点权。题目链接#include<iostream>#include<cstdio>using namespace std;int n,tot,lable,root,f[100100],lazy1[800800],lazy2[800800],a[800800],Next[200010],head[200100]

2017-06-13 18:34:15 436

原创 BZOJ1036 [ZJOI2008]树的统计Count

树链剖分裸题。题目链接#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define N 30500using namespace std;int n,tot,lable,Next[N*2],head[N*2],tree[N*2],a[N],m,fa[N],de

2017-06-13 18:31:08 319

原创 POJ3237 Tree

这题同样需要将边权转换成点权。题目链接另一道需要将边权转换成点权的题#include<iostream>#include<cstdio>using namespace std;int n,tot,label,tree[80010],Next[20010],head[10010],tree1[20010],val[20010],num[20010],dep[10010];int top

2017-06-13 18:30:05 287

原创 HDU3966 Aragorn’s Story

题目链接这题查找为单点查找，故可以用树状数组来维护。 #include<iostream>#include<cstdio>using namespace std;int n,m,q,tot,label,a[50010],Next[100010],head[100010],tree[100010],dep[50010],son[50010],size[50010],fa[50010];in

2017-06-13 18:27:09 264

原创 SPOJ Query on a tree

此题需要把边权转换成点权，方法如下：可以从根开始dfs，然后将每条边的值赋到向下的一个节点上，最后再把根的值赋为-∞即可。例如有一条1到2的边，权值为3，则从1开始dfs，就将2这个点的点权赋为3。题目链接 Vjudge题目链接#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include

2017-06-13 18:25:51 311

原创详解树链剖分

树链剖分，顾名思义为将链剖开分成多条。当我们想要修改树上一条路的值或求值时，我们暴力只能用一个个修改，这是非常慢的。这时，我们就要想一个办法，数据结构？但是数据结构我们都需要连续修改，可是树上路径的编号是不连续的。于是我们想了一个办法。我们先定义 fa[x]为x的父亲 dep[x]为x的深度 size[x]为以x为根的子树的节点个数几个名词： 1.重边（一个节点的儿子中

2017-06-13 16:10:15 357

原创零件加工（贪心）

时间限制: 1 Sec 内存限制: 128 MB 题目描述工匠小K最近有n个零件需要加工。每个零件都需要ti天的时间来完成，每个零件每延迟一天加工都要缴纳一定的罚金si。延迟的天数为从今天算起到该工作开始的那天，第一个零件加工没有罚金。现在小K想知道怎样安排加工顺序可以使他要交的罚金最少，最少是多少。这个数可能会很大，请输出这个数对m取模后的结果。输入输入文件名为process.in。输

2017-06-13 15:37:25 1207

原创 Dijkstra+Priority_queue

模板#include<iostream>#include<cstdio>#include<queue>using namespace std;int n,m,S,tot,Next[500010],head[20000],tree[500010],val[500010];bool visit[20000];long long dis[20000];struct cmp{ boo

2017-06-06 08:27:27 547

原创 Vijos1579 宿命的PSS

题目链接背景P.S.S:“我来自哪里？” WH:“你来自一个图。” P.S.S:“我是谁？” WH:“你是最小生成树。” P.S.S:“我又要到哪里去？” WH:“你要成为一个最小完全图（边权之和最小的完全图）。” P.S.S:“为……为什么啊？” WH:“这是你的宿命！因为你无聊！！！P.S.S！” 描述最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Ki

2017-06-03 16:56:43 517 2

原创 Tyvj P1034 尼克的任务

题目描述尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去写成，假如某些任务开始时

2017-06-02 14:27:23 363

原创加分二叉树

时间限制: 1 Sec 内存限制: 128 MB 题目描述设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋

2017-06-02 14:17:32 1950

原创括号序列

时间限制: 1 Sec 内存限制: 128 MB 题目描述定义如下规则序列（字符串）： 1.空序列是规则序列； 2.如果S是规则序列，那(S)和[S]也是规则序列； 3.如果A和B都是规则序列，那么AB也是规则序列。例如，下面的字符串都是规则序列： (), [], (()), ([]), ()[], ()[()] 这几个不是规则序列： (, [, ], )(,

2017-06-02 13:58:41 731

原创 TyvjP1047乘积最大

时间限制: 1 Sec 内存限制: 128 MB 题目描述今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得

2017-06-01 20:53:40 325

原创 TyvjP1045 最大的算式

时间限制: 1 Sec 内存限制: 128 MB 题目描述题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如： N=5, K=2，5个数字分别为1、2、3、4、5，可以加成： 1*2*(3+4+5)=24 1*(2+3)(4+5)=45 (1*2

2017-06-01 20:45:15 323

原创石子合并（NOI1995）

题目描述在操场上沿一直线排列着 n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。输入输入数据共有二行，其中，第1行是石子堆数n≤100；第2行是顺序排列的各堆石子数（≤20），每两个数之间用空格

2017-06-01 20:33:08 1725

原创低价购买

时间限制: 1 Sec 内存限制: 128 MB 题目描述 “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(216范围内的正整数)，

2017-06-01 20:03:14 289

原创运动鞋

时间限制: 1 Sec 内存限制: 128 MB 题目描述经过几个月的艰苦学习，Iserlohn终于赢得了全额奖学金。作为一个运动鞋狂热爱好者，他决定用所有的钱在运动鞋商店进行消费。有一些球鞋Iserlohn要收集，如Air Jordan 和 Nike Pro。而每个品牌已发布各种产品。由于，Iserlohn绝对是一个运动鞋狂热，他意欲购买每个品牌至少有一个产品。虽然每个产品的都

2017-06-01 19:34:17 330

原创 YYHS1619(tyvj 1050)

时间限制: 1 Sec 内存限制: 128 MB 题目描述一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。输入第一行两个字符串用空格分开。输出最长子串的长度。样例输入 abccd aecd 样例输出 3 提示两个串的长度均小于2000我们令两个串为s

2017-06-01 18:43:00 382

原创 BZOJ4756: [Usaco2017 Jan]Promotion Counting

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 218 Solved: 150 DescriptionThe cows have once again tried to form a startup company, failing to remember from past experience t hat cows make terrib

2017-06-01 16:53:07 531

原创 BZOJ4518: [Sdoi2016]征途

DescriptionPine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。 Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。帮助Pine求出最小方差是多少。设方差是v，可以证明，v×m^2是一个

2017-05-26 13:55:45 299

原创 0/1背包

题目描述一个旅行者有一个最多能装m公斤物品的背包，现在有n件物品，它们的重量分别是w1，w2,…，wn，它们的价值分别为c1,c2,…，cn。若每件物品只有一件，求旅行者能获得的最大总价值。输入第一行：两个整数，m（背包容量，m<=200）和n（物品数量，n<=30）。第二~n+1行：每行两个整数wi，ci，表示每个物品的重量和价值。输出一个数据，表示最大总价值。样例输入

2017-05-25 20:25:46 511

原创导弹拦截

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹一次飞来的高度（雷达给出的高度不大于30000的正整数）。计算这套系统最多能拦截多少导弹。输入 n颗

2017-05-25 20:16:37 346

原创 BZOJ3675: [Apio2014]序列分割

Description小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤： 1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）； 2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将

2017-05-23 20:19:27 309

原创分块基础

题目有两种操作，一是将l~r的数都开方，二是求l~r的数的和。 n<=100000，中间过程保证小于long long 这题当然可以用线段树做，但我们同样可以用分块来做。我们发现每个数经过小于8次的开方后都会小于等于1，所以我们就可以在每次处理整个块时，如果这个块每个数都小于等于2，那么这个块以后就不用开方了（因为块内的1开方后还是1，0开方后还是0）。代码如下：#include<iostr

2017-05-23 14:18:43 294

原创详解斜率优化

这里讲一下斜率优化，其实也是给自己复习一下。我们从一道例题开始：BZOJ1597: [Usaco2008 Mar]土地购买Description农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快

2017-05-22 18:17:26 751

原创铺砖块

题目描述现有n*m的一块地板，需要用1*2的砖块去铺满，中间不能留有空隙。问这样方案有多少种输入输入n，m（1<=n, m<=11) 有多组输入数据，以m=n=0结束输出输出铺砖块的方案数样例输入 1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0 样例输出 1 0 1 2 3 5 144 51205此题可以用状压DP来

2017-05-20 14:45:21 1950

原创导游

题目描述宁波市的中小学生们在镇海中学参加程序设计比赛之余，热情的主办方邀请同学们参观镇海中学内的各处景点，已知镇海中学内共有n处景点。现在有n位该校的学生志愿承担导游和讲解任务。每个学生志愿者对各个景点的熟悉程度是不同的，如何将n位导游分配至n处景点，使得总的熟悉程度最大呢？要求每个景点处都有一个学生导游。输入有若干行：第一行只有一个正整数n，表示有n个景点和n个学生导游。第二行至第n+1行

2017-05-20 08:30:02 847

题目描述 XYZ公司已在沿太平洋东海岸位于不同地区的几个岛屿发现了5种稀有的矿藏。该公司认为，这将是一个获利最好的机会。然而，由于金融危机，该公司并没有足够的人手和金钱在所有岛屿上建立矿田。因此，公司委员会选择了一些有较高的矿石储量岛屿，并派出一名调查员对这些岛屿制作了岛上的矿石分布调查。调查结果显示，每个岛上有许多连接在一起的村庄。由于耗费时间，调查员并没有记录的地图中的所有路径。只是记下了一条

2017-05-19 17:52:18 591

原创炮兵阵地

题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域

2017-05-19 14:27:19 489

原创天上掉Pizza

题目描述明明喜欢Pizza，但总是缺钱。有一天，他在报纸上阅读，他最喜爱的比萨饼店��必胜客，正在对大批新Pizza运行的促销。促销的办法是：在购买一些Pizza后，可能得到一些优惠券，可以对另一些Pizza进行打折，更令人惊喜的是这些优惠券可以结合起来。但是，有一个限制，Pizza必须一个接一个买，而后得到的优惠券也不可能追溯前面已经买过的Pizza。明明想尝试若干新品Pizza，可又没有充足

2017-05-19 14:09:37 662

原创兔子跳跃之谜下(BZOJ2454 RabbitPuzzle（BZOJ中不是多组数据）)

题目描述小生和小森在玩兔子之谜游戏。有三只兔子排成一排。知道每只兔子的初始位置，以及三个兔窝的位置。游戏的规则是，重复以下步骤k次：选择两个不同的兔子A和B，分别位于a和b。A可以跳过B到达2*b-a的点：跳跃是不允许其他小兔子已经在点2*b-a的位置上：跳跃也不允许一次跳过一个以上的兔子：现在小生和小森想要知道，k次操作之后，能否让所有兔子都分别跳到一个兔窝里面。注意，第i个兔子并不一

2017-05-18 21:19:15 824

原创小明的喷漆计划

时间限制: 5 Sec 内存限制: 128 MB 题目描述小明极其喜欢涂鸦，总是在墙上涂上各种颜色的漆。现在小明得到一个任务，需要喷涂一段空白围墙，且单位长度内的颜色都是相同的。小明有一种喷涂工具，它可以给任意长度的一段墙面涂上任意颜色的漆，这样的操作计为一次操作。小明要完成这个任务，又想使得操作次数尽量少，就请你帮他解决这个问题吧。输入有多组输入数据。每组包含一个长度不超过100

2017-05-18 20:25:06 579

原创最大的算式

题目描述题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如： N=5, K=2，5个数字分别为1、2、3、4、5，可以加成： 1*2*(3+4+5)=24 1*(2+3)(4+5)=45 (1*2+3)(4+5)=45 ……输入输入文件共有二行，

2017-05-18 15:00:41 318

原创胖男孩

时间限制: 1 Sec 内存限制: 128 MB 题目描述麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要

2017-05-17 21:20:05 1250 1

原创 Tyvj P1013 找啊找啊找GF

题目描述 ” 找啊找啊找GF,找到一个好GF,吃顿饭啊拉拉手,你是我的好GF.再见.” ” 诶,别再见啊…” 七夕…七夕…七夕这个日子,对于sqybi这种单身的菜鸟来说是多么的痛苦…虽然他听着这首叫做” 找啊找啊找GF” 的歌,他还是很痛苦.为了避免这种痛苦,sqybi决定要给自己找点事情干.他去找到了七夕模拟赛的负责人zmc MM,让她给自己一个出题的任务.经过几天的死缠烂打,zmc MM终

2017-05-16 08:57:35 688

原创友好城市

问题 B: 友好城市时间限制: 1 Sec 内存限制: 128 MB 提交: 32 解决: 26 [提交][状态][讨论版] 题目描述 Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置不同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避

2017-05-16 08:36:24 629

原创 BZOJ4034: [HAOI2015]树上操作

题目链接树链剖分，单点修改，查询最大值和总和。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define N 30500using namespace std;int n,tot,lable,Next[N*2],head[N*2],tree[N*2],a[N

2017-04-27 07:45:04 417

原创 BZOJ2243: [SDOI2011]染色

题目链接树链剖分，这题两个区间合并时和Query求值时都需要注意！！！#include<iostream>#include<cstdio>using namespace std;int n,m,tot,lable,color[410000],Next[410000],head[410000],tree[410000],fa[410000],dep[410000],size[410000];

2017-04-26 18:37:35 394

空空如也

空空如也