wmj_-CSDN博客

原创 bzoj 2653: middle(陈立杰)

首先膜拜clj。。。这道题初看没头绪，看了诸多题解后，发现时先二分，在把大于等于它的为1，小于它的为-1，一段区间最大连续和非负就行然后想了N久都没想通，终于，在昨天在外拜年时想通了，就是以每个数建可持久化线段树，然后维护sum,lsum,rsum这样初始化就nlogn，每次询问log2n，总复杂度O(Qlog2n+nlongn)；代码写得还是蛮短的，就是怎么搞都只是rank 6。。。

2014-02-04 21:44:02 1568

原创 bzoj 1901

题目大意：带修改的区间第k大就是树状数组套可持久线段树 #include#includeusing namespace std;const int maxt=10000011,maxn=1e9,maxm=10011,maxch=maxt;char buf[maxch],*wbuf=buf;inline void read(int &x){ x=0;while (*wbuf

2014-01-29 22:06:08 561

原创最短路

题目：经过努力，LCJ终于获得了一个带薪假期。他准备要在N个城市中挑选若干个进行旅游，其中有K个城市他是一定要去的。然而他英(qi)明(guai)的上司KID向他提出了一个要求，因为经费的问题，他的旅行路线必须是某两个城市之间的一条最短路。现在LCJ就要在这N个城市之间的道路找到这样一条路线：它是一条某两个城市之间的最短路，经过了K个特殊的城市，在满足条件的路线中，找到最短的一条。输

2013-11-06 10:36:15 993

原创 Poetize4 玉蟾宫

题目大意：给你一个N行M列的地，每块地上有R或F，求这个图中最大的由F构成的矩形面积 n,m这道题，如果给定你矩形的下底所在的行，那么我们就用一个单调栈维护，即可，然后枚举矩形的下底所在的行 O(n^2)#include#includeconst int maxn=1010; using namespace std;inline int max(int a,int b

2013-11-06 10:25:01 1252

原创 [HAOI2008] 糖果传递

这题就是一个强化版均分纸牌，如果知道题没有环形，那么很水。我们现在设A为平均数，设f[i]表示第i个要给i-1个多少个糖果，f[1]代表第1个要给第n个多少个，有f[i+1]=f[i]+A-a[i] ,有f[i+1]-f[i]=A-a[i]我们设w[i]=A-a[i-1] 有f[i+1]-f[i]=w[i+1] 可得有:f[n]-f[n-1]=w[n]; .........(n-1)

2013-11-02 12:47:45 678

原创 [CTSC2007]挂缀pendant

题目大意：给你n个钩码，每个钩码有一个承受能力和重量，问最多可以挂多少个钩码，再上一问的条件下，钩码总重最小是多少 n这题明显是贪心于是我们要找一个贪心策略，我们先假设没有按任何方式排序，存在c[i]+w[i]>c[i+1]+w[i+1]我们如果把i挂在i+1上的话，那么底下还可以承受的重量:min(c[i],c[i+1]-w[i]) 反过来就是：min(c[i+1],

2013-10-31 13:46:54 1240 1

原创 Pku2376 Cleaning Shifts

题目大意：给你一些线段的起止点，问你最少用多少条线段可以把一段区间覆盖线段数1、spfa+离散化+SLF即可，直接上代码#include#include#include#includeconst int maxn=1000010,maxm=2000010;using namespace std;int st,ed,tot=0;int f[maxn],no

2013-10-30 20:17:03 675

原创 Pku2054 Color a Tree

原题 http://poj.org/problem?id=2054题目大意：给你一棵树及每个点的权值和根，你需要把这颗树染色，每个时间只能染一个点，所需的花费是当前染色时间*这个点的权值，求最少花费（根必须第一个染），n这题初看时以为是tree dp ，但没有想出来，还是看了题解，但是讲的都不明觉厉，只好拿着代码自己想了。。。。这个题的大体思路就是最大一个要最先选，但是

2013-10-30 16:52:00 878

原创 BZOJ 1909 Berth Allocation

题目大意：给你n个港口，每个港口都有个容量，然后有m条船要在s是进入sec，e时出去，问最多可以满足几条船的要求 n因为不同的港口互不影响，所以把不同的港口分开做对于相同的港口，只要按出来的时间贪心就行了#include#include#include#includeconst int maxn=15,maxm=100010,maxt=maxm*4;usi

2013-10-30 11:32:11 968

原创 [Shoi2005]带限制的最长公共子序列

这题就是求最长有条件的上升子序列，n很小只有500，可以承受O(n^3)于是我们设f[i][j][k]代表第一串匹配到i，第二串匹配到j，已满足前k个条件转移方程很好想，就不多述了空间问题也就用滚动数组就OK了#include#include#include#define updata(a,b) a=max(a,b)#define f(i,j,k) f[(i)&

2013-10-29 21:28:14 1052

原创 Noi2001 食物链

Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1 X Y”，表示X和Y是同类。第二种说法是“2 X Y”，表示X吃Y。此人对N个动物，用

2013-10-29 11:36:16 915

原创 [jsoi2008]星球大战

Description很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始

2013-10-29 11:30:36 726

原创 [Usaco 2011 Dec]Umbrellas for Cows

题目大意：FJ的N （ 1 输入数据第1行：两个用空格隔开的整数： N和M 这题就是一道裸dp，先按坐标排序然后记f[i]表示覆盖前i个牛需要多少钱 f[i]=min{f[j-1]+cost[a[i]-a[j]+1]) 1附代码#include#include#include#includeconst int maxn=5010,maxm

2013-10-29 11:22:56 865

原创树 (罗雨屏)

试题来源　　IOI2012中国国家队训练问题描述　　给定一棵大小为 n 的有根点权树,支持以下操作:　　• 换根　　• 修改点权　　• 查询子树最小值输入格式　　第一行两个整数 n, Q ,分别表示树的大小和操作数。　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f 　　接下

2013-10-29 11:12:24 1461

wmj的专栏