LIN452-CSDN博客

原创 BZOJ1539/POI2005 Double-row

由于数据保证有一组方案达到目标,那么相同高度的士兵个数不超过2. 每列交换的次数最多是1,多次交换是无意义的. 那么假如身高相同的两个士兵在同一行中,它们所在的列数a,b中一定有一列要进行交换,且只有一列. 那么假如身高相同的两个士兵在不同行中,它们所在的列数a,b中要么都进行交换,或者都不进行交换. 有了列与列之间的关系就可以建对以上两类情况分别建边,进行01染色,将

2016-10-27 07:20:39 584

原创 BZOJ1537/POI2005 The Bus

假设dp[i][j]表示在(i,j)位置能够接到的最多乘客数量,我们会发现很多的状态是无效的,因此只要记录到达站点的状态.由于只能向北或向东走,只可能通过西南的站点到达(i,j),也就是所有满足a<=i&&b<=j的站点(a,b).这样就有两维状态,可以通过排序+区间求值的方法降维. 我们可以按照横坐标从小到大排序,维护纵坐标的区间最值,由于每次求的是前缀最值并且不断增大,可以用树状数组求解.#i

2016-10-27 07:18:18 468

原创 BZOJ1534/POI2005 Fibonacci sums

首先把两个序列相加得到初始序列.之后就对初始序列进行调整: 对于f[i]>=2的情况可以根据2*f[i]=f[i]+f[i-1]+f[i-2]=f[i+1]+f[i-2]转化为f[i-2]++,f[i+1]++. 对于f[i]=1&&f[i+1]=1,根据f[i+2]=f[i]+f[i-1]转化为给f[i+2]赋值.#include<cstdio>#include<cstring>#incl

2016-10-27 07:16:21 572

原创 BZOJ153/POI2005 A Journey to Mars

确定了起点和方向之后,旅行的过程就确定了,到达i点的花费<=到i点之间的油料数量就是题目的限制条件. 由于是绕圈问题,我们可以把序列复制相接,转化成序列上的问题. 设sum[j]sum[j] 表示到jj之前所得油料数量dis[j]dis[j]表示1到jj的距离,对于起点i,保证每个j<=i+nj<=i+n都有: sum[j]−sum[i]>=dis[j]−dis[i]s

2016-10-27 07:14:55 583

原创 BZOJ1532/POI2005 Dicing

直接求似乎不简单,由于题目求”最大值最小问题”,可以转化为二分答案来验证一个解是否成立.假设枚举的答案是x,那么所有人赢得的场次都<=x.而每场比赛最多只有一个人获胜,我们可以根据此信息,构图: 设置源点与每个人建边,每个人与它所参加的每场比赛建边,每场比赛与超级汇点建边并且流量设置为1.根据此图跑一遍最大流,判断是否为m即可. #include<cstdio>#include<cstring>

2016-10-27 07:13:09 398

原创 BZOJ1531/POI2005 Bank notes

裸的多重背包,利用二进制进行优化: 假设有12枚面额为3的硬币,可以把它转化为面值为3,6,12,15的硬币分别1枚.这样就把物品总数减少到log件.#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int M=205;const int S=15;const

2016-10-27 07:10:45 647

原创 BZOJ1529/POI2005 Piggy banks

根据图中的信息,可以构造出一棵基环外向树.每个节点指向存放自己钥匙的节点.对于每一个连通块,其中必定会出现一个环,只要将环上任意一个存钱罐打破,那么这整个联通块中的所有存钱罐都能打开了. 因此答案就是构图后联通块的个数.#include<cstdio>#include<cstring>#include<iostream>#include<vector>using namespace std

2016-10-27 07:07:43 392

原创 BOZJ1528/POI 2005Toy Cars

假设地板上能放足够多的玩具,那么肯定一次性将所有玩具都拿下来.可是题目中有了k这个限制.为了完成题目的要求,不得不将某些玩具拿回去,使得新玩具有地方放置.那么问题就是将什么玩具拿回去.如果某个玩具x之后不再出现,那么一定将它拿走,既不会对答案产生影响,又有利于以后的玩具放置.万一没有不再用的玩具了,只能将某个暂时不玩但以后还要玩的玩具y,要选择的是下一次出现的时间最晚的玩具y. 对于每个y,拿回架

2016-10-27 07:06:29 567

原创 BZOJ1527/POI 2005 Point

相似点集有一个性质,重心在点集中的位置是相同的,可以通过点集的重心判断现点集是否能还原成原点集. 如果两个点集的点数不同,肯定是不相似的.移动:直接根据重心的位置,确定现点集的移动方式,使得两个点集的重心重合.缩放:根据两个点集内的点到重心的最短距离确定缩放比例,注意如果最短距离是0要特判.旋转:根据每个点到重心的极角给两个点集内的点排序. 每个点记录两个参数:①到重心的距离,②排

2016-10-27 07:04:27 333

原创 BZOJ1526/POI 2005 Bankomat

所有可能的输入方案一共有10000种,我们可以对每一个进行检验.对每个录像求出对应的f[i][k]表示第i个字符以后第一个字符k的位置,预处理出f数组之后就可以对每个数字进行O(1)检验了. 由于无法同时求出每个串的f数组,因此可以对每个串检验10000种可能,已经不可能的数字之后就不必检验了.#include<cstdio>#include<cstring>using namespa

2016-10-27 07:00:37 551

原创 BZOJ2801/POI2012 Minimalist Security

Task 给出一个N个顶点、M条边的无向图，边(u,v)有权值w(u,v)，顶点i也有权值p(i)，并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。现在要将顶点i的权值减去z(i)，其中0<=z(i)<=p(i)。修改后设顶点i的权值p’(i)=p(i)-z(i)，对于每条边(u,v)都满足p’(u)+p’(v)=w(u,v)。求sum{z(i)}的最小值

2016-10-18 07:32:12 521

原创 BZOJ2802/POI 2012 Warehouse Store

Task 有一家专卖一种商品的店，考虑连续的n天。第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。 n<=250,000，0<=Ai<=10^9，0<=Bi<=10^9.Solution 贪心. 在第i天库存足够时,就满

2016-10-17 17:50:15 344

原创 BZOJ2800/POI2012 Leveling Ground

Task 给出n个整数X_1,X_2,…X_n，再给出两个正整数a、b，可以进行下面四种操作： 1. 选择正整数l,r (1<=l<=r<=n)，将X_l,X_{l+1},…,X_r都加上a。 2. 选择正整数l,r (1<=l<=r<=n)，将X_l,X_{l+1},…,X_r都减去a。 3. 选择正整数l,r (1<=l<=r<=n)，将X_l,X_{l+1},…,X_r都加上b。 4

2016-10-09 22:24:42 802

原创 BZOJ2799/POI2012 Salaries

Task 给出一棵n个结点的有根树，结点用正整数1~n编号。每个结点有一个1~n的正整数权值，不同结点的权值不相同，并且一个结点的权值一定比它父结点的权值大（根结点的权值最大，一定是n）。现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。问还有哪些结点的权值能够唯一确定。 n<=1,000,000, 1<=pi<=n, 0<=zi<=n.Sol

2016-10-09 21:29:30 591

原创 BZOJ2798/POI 2012 Bidding

Task A和B两个人在玩一个游戏，这个游戏是他们轮流操作一对整数(x,y)。初始时(x,y)=(1,0)，可以进行三种操作： 1. 将(x,y)变成(1,x+y)。 2. 将(x,y)变成(2x,y)。 3. 将(x,y)变成(3x,y)。给定正整数n (n<=30,000)，如果x+y>=n时就不能进行后两种操作。如果某个人操作后y>=n，他就输掉了。假如A为先手

2016-10-09 21:05:45 864

原创 BZOJ2798/POI2012 Squarks

Task 设有n个互不相同的正整数{X1,X2,…Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。现在所有取法共n*(n-1)/2个和，要你求出X1,X2,…Xn。 3<=n<=300, 每个正整数不超过10^8Solution 假设原序列是单调递增的,f(i,j)=xi+xjf(i,j)=x_i+x_j. 对于所有a＜ia＜i并且b＜jb＜j,都有f(i,j

2016-10-09 20:51:54 480

原创 BZOJ2796/POI2012 Fibonacci Representation

Task Fib数列0,1,1,2,3,5,8,13,21。给出一个数字，用FIB数列各项加加减减来得到。例如 10=5+5 19=21-2 求出通过加减得到K的最少项数. 1<=K<=10^17.Solution 有一个贪心的思路,每次找到离K最近的两项f(i),f(i+1),再把问题转化为求K-f(i),f(i+1)-K即可.用计划搜索优化.我是将10^7以内的数

2016-10-09 20:22:17 440

原创 BZOJ2795/POI2012 A horrible poem

Task 给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。 n<=500,000, q<=2,000,000.Solution 假如最短循环节为lenlen,设t=n/lent=n/len,现在的问题就是找到最大的t. t肯定是n的因子,那就可以直接枚举n的所有素因子k,若当前的

2016-10-09 19:44:35 556

原创 HDU5808(Bestcoder Round86)Price List Strike Back

题目戳这假如我们已知第i天可以购买的所有商品,那么剩下就是01背包的问题了.能够购买的所有商品由两个条件决定:编号下标和距离.我们可以减少一个维度使问题更简单.假如把询问和点一起按照距离d排序,那么就能保证询问到i时,所有考虑到的点x一定满足dis[x]<=didis[x]<=di这一条件.现在问题就转化成了:询问:在[Li,Ri][Li,Ri]区间中能否找到一些点满足其价值之和=sumisumi.

2016-10-09 18:49:22 761

原创 BZOJ2794/POI2012 Cloakroom

Task 有n件物品，每件物品有三个属性a[i], b[i], c[i] .(a[i]＜b[i]) 再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得： 1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。 2. 所有选出物品的c[i]的和正好是k。 n<=1,000, q<=1,000,000. c[i]<=1,000, 1<=a[i]＜b[i

2016-10-08 22:41:47 539

原创 BZOJ2793/POI2012 Vouchers

Task考虑正整数集合，现在有n组人依次来取数，假设第i组来了x人，他们每个取的数一定是x的倍数，并且是还剩下的最小的x个。正整数中有m个数被标成了幸运数，问有哪些人取到了幸运数。m<=1,000,000, n<=1,000,000, x<=1,000,000.Solution对于每个来的人数x(无论人数为x有几组),最多要计算mxx\frac{mx}{x}次,mxmx为最大的幸运数,那么对于所

2016-10-08 22:02:27 359

原创 BZOJ3060/POI 2012 Tour de Byteotia

Task 　　给定一个n个点m条边的无向图，问最少删掉多少条边能使得编号小于等于k的点都不在环上。　　1 ≤ n ≤ 1,000,000，1 ≤ m ≤ 2,000,000，1 ≤ k ≤ n。 Solution　　对于删边不容易解决的情况,可以”正难则反”,考虑是否能求出最多能加的边.对于两个节点都在[k+1,n]范围内的边(设为1类边),直接加到图中(过程1).全部加完之后,把一个联通块

2016-10-08 19:53:24 429

原创 BZOJ2792/POI2012 Well

Task 给出n个正整数X1,X2,…Xn，可以进行不超过m次操作，每次操作选择一个非零的Xi，并将它减一。最终要求存在某个k满足Xk=0，并且z=max{|Xi - Xi+1|}最小。输出最小的z和此时最小的k。 1<=n<=1,000,000, 1<=m<=10^18, Xi<=10^9.Solution 求最小的k,我们可以通过二分把问题转化为验证一个解是否可行. 验证解k

2016-10-08 18:43:42 486

原创 BZOJ2791/POI2012 Rendezvous

Task 给定一个n个顶点的有向图，每个顶点有且仅有一条出边。对于顶点i，记它的出边为(i, a[i])。再给出q组询问，每组询问由两个顶点a、b组成，要求输出满足下面条件的x、y： 1. 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。 2. 在满足条件1的情况下max(x,y)最小。 3. 在满足条件1和2的情况下min(x,y)最小。 4. 在满足条件1、

2016-10-08 16:26:11 625

原创 BZOj2790/POI2012 Distance

Task 对于两个正整数a、b，这样定义函数d(a,b)：每次操作可以选择一个质数p，将a变成a*p或a/p，如果选择变成a/p就要保证p是a的约数，d(a,b)表示将a变成b所需的最少操作次数。例如d(69,42)=3。现在给出n个正整数A1,A2,…,An，对于每个i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。 2<=n<=100,00

2016-10-08 15:59:12 945

原创 BZOJ2788/POI2012 Festival

Task 有n个正整数X1,X2,…,Xn，再给出m1+m2个限制条件，限制分为两类： 1. 给出a,b (1<=a,b<=n)，要求满足Xa + 1 = Xb 2. 给出c,d (1<=c,d<=n)，要求满足Xc <= Xd 在满足所有限制的条件下，求集合{Xi}大小的最大值。 2<=n<=600, 1<=m1+m2<=100,000.Solution 1.差分约束: 把X

2016-10-08 15:12:07 627

原创 IOI2011 race

Task: 给定一棵带权树,求出边数最小的一条路径使得路径长度为K. 1 ≤ N ≤ 200000 ,1 ≤ K ≤ 1000000Solution: 枚举路径的lca为节点x,只考虑一定经过x的路径. 再枚举其中的一个端点y,设y到x的距离为d1,确定了y,我们就知道了路径另一个端点到x的距离了,现在问题就是求出到x点距离为K-d1的路径的最少边数,那么只要在遍历x子树过程

2016-10-08 14:13:13 481

原创 IOI2011 ricehub

Task: n块稻田,每块稻田一个位置pi,稻田位置可能重叠.现在可以设置一个米仓,一块稻田运送粮食的代价就是运送的距离,现在给出花费t,求出在t内最多能运送多少粮食. n≤1e5,pi≤1e9,t≤2e15.Solution: 假如米仓的位置确定,可以确定最后选中的答案一定是最接近米仓的一段区间.而且左右端点到米仓的距离会尽可能接近. =>假如最后的区间确定

2016-10-08 14:06:17 1023

原创 USACO2011Open Gold Balanced Cow Subsets

N的范围很小,可以联想到枚举子集和状压.但是如果直接枚举两个子集,显然是不够的.那么我们可以联想到折半枚举!Meet inthe Middle! 把n个数分成两部分A,B集合,答案子集的来源有以下几种:1. A集合的子集.2. B集合的子集.3. 一部分是A的子集,一部分是B的子集.对于1,2两种情况都可以直接预处理出:枚举A的子集x,再枚举x的子集y,

2016-06-28 17:52:41 1006

原创 USACO2011Open Gold Bookshelf 题解

可以把题目理解为在n本书中”切几刀”. 当n2)可以解决: dp[i]表示在前i本书,第i本书为当前书架的最后一本书的最小高度.dp[i]=min{dp[j]+mx[j+1,i]}且sum[j+1,i] 当n通过dp[i]=min{dp[j]+mx[j+1,i]},当mx[j+1,i]为h[i]时,j越小越优.假设在i前面,第一本比i高的书下标为x,如

2016-06-28 17:48:19 814

原创 USACO2011Open Silver Unlocking Blocks 题解

搜索搜索搜索! 每次把一块积木移动一步,而且每块积木内部的相对位置是不变的,那么每次只要记录积木任意一点的位置表示状态即可.为了方便,我们可以设为每个积木包围块的左上角的点. 如何实现?一种想法是暴搜!可惜T了…暴搜优化一下来个迭代加深,每次设定一个步数,可惜还是T了.由于问题为”最小步数” ,我开始想广搜.可是如何判重?积木位置可以随意移动,状态最多为(30*

2016-06-28 17:16:59 771

原创 USACO2011Open Silver Running Laps题解

//请忽略我把牛看作羊....由题意,我们可以得到 t*vi-t*vj=kC.那么i,j相遇的次数就是最大的k(整数).为了得到最大的k就要使t最大,而tmax=L*C/vmax.那么把式子整理得到: k=L*(vi-vj)/vmax.(向下取整) 对于第i只,它和速度比它小的每一只羊相遇的次数都能确定,常见的思路就是运用前缀和把式子累加,但由于k是每两只羊之

2016-06-28 17:07:58 704

原创 USACO2011Open Bronze 3lines 题解

[思路]符合 FJ的要求有两种情况:三条直线平行或者两条直线平行并与一条直线垂直.至于横竖的问题,可以通过反转奶牛的坐标转化成相同的方式.三条平行直线:把所有点的横坐标记录下来,如果不同的横坐标个数小于等于3,那么符合条件.两条平行与一条直线垂直:把所有的纵坐标和它们个数记下,也记下所有出现的纵坐标个数,再按照横坐标排序,再枚举一个横坐标a,表示这条

2016-06-28 17:01:22 1077

原创 CodeForces 160D Edges in MST 题解

[题意] 给出一个n个点m条边的无向连通图,判断图中每条边是否一定在最小生成树上. n,m[思路]由于最小生成树的性质,我们造出任意一棵最小生成树,并记录下与最小生成树权值相等的所有边.暴力版:沿着非树边x的两个端点走到它们的lca,在环上去找与x权值相同的边,如果找到,说明被替换的边和x都不一定在最小生成树上.暴力做法优化版:这里又有一个结论

2016-06-28 07:13:04 599

原创 CodeForces 444C DZY Loves Colors题解

[题意] 有n个气球,每个气球有一个颜色x,改变为y后,美丽值增加|x-y|. 对一个序列有两种操作:1. 把区间在[L,R]的颜色染成x.2. 询问区间[L,R]的气球的美丽值总和.n[思路] 区间更新,区间询问可以联想到线段树. 只是更新的时候有点复杂: 因为一个区间内的颜色不一定相同,无法一次性全部更新,那

2016-06-27 22:40:45 772

原创 CodeForces 444B DZY Loves FFT 题解

[题意] 给出一个的1~n的排列A,和一个长度为n,只有0,1的序列B,求序列C:Ci=max(aj,bi-j)(i 数据保证是随机构造的.[思路]这题坑啊.不怕难题,就怕水题ToT 因为数据是随机的,所以可以乱搞(什么鬼啊). //信息量还这么少!范围怎么大!不瞎搞怎么过!(@#*&….) 从大到小枚举50(或者更少)个

2016-06-27 22:33:07 848

转载 dfs序的常见用法整理

dfs序就是一棵树在dfs遍历时组成的节点序列.它有这样一个特点:一棵子树的dfs序是一个区间.下面是dfs序的基本代码:void dfs(int x,int pre,int d){//L,R表示一个子树的范围 L[x]=++tot; dep[x]=d; for(int i=0;i<e[x].size();i++){ int y=e[x][i];

2016-06-27 21:32:06 4741

原创毯子题解(COCI 2008-2009Final C)

[题意]N 块矩形毯子铺在地上。0秒时（0,0）处有一桶油倒了，然后开始流呀流，每秒往八个方向扩散一个单位。注意，这里的坐标描述一个单元格，不表示点。M个询问，每次问一个时间点被油染到的毯子面积（若有毯子重叠，面积也要累加，如一个单位格被三个毯子覆盖，那么被油染到之后就算3个单位面积）。[思路]50分:暴力!n*m枚举每个询问时每块毯子被染到的范围.直接把顶点算出.100分:

2016-06-26 15:53:13 851

原创维修道路题解

[题意]一棵n个节点的树,求两条路径s1,s2最大的长度积,满足s1,s2都是两点之间的最短路径,而且两条路径不含任何公共点.n[思路] O(n^2): 枚举树上的每条边,把此边从树上移除,那么原来的树就变成了两棵子树:所求的两条路径分别在两棵子树中.那么为了满足题意中的最大长度积,分别求出两棵子树的直径即可. O(n):

2016-06-26 15:45:20 553

空空如也

空空如也