xrwy2000-CSDN博客

原创线段树注意事项

1.所有的乘除法都用位运算，速度快，而且好像可以防wrong answer2.树的大小开maxn的四倍，即maxn3.如果范围是[0,n-1]，子节点为2*root+1和2*root+2 如果范围是[1,n]，子节点为root4.区间更新时，节点表示范围内的总和，和表示范围内的最大最小值是有不同的，表示范围内总和时，整个区间都要乘上改变的节点值。5.对于pushDown

2017-08-06 19:47:07 198

原创考研英语___百词斩word~(2)

cape名词：海角；斗篷，披肩the monkey's cape looks so cool.interim名词：中间时期，过渡时期形容词：暂时的the government provided us with interim housing until our new houses are ready.hamper动词：阻碍，妨碍，牵制名词：

2017-06-14 11:36:41 606

原创整除取整问题

向下取整：直接x/k就好向上取整：如 12/5 = 2，要向上取整，需 (12+4)/5 = 3.即，(x+k-1)/k，为向上取整或者 12*1.0/5 = 2.4，然后(int)2.4+1，把2.4转换为int后加1即，(int)x*1.0/k+1

2017-05-09 11:58:49 949

原创动态规划，背包问题变型

题目：UVALive - 4870题意：坐过山车，可以兴奋，可以头晕。对于每一段路，你可以闭眼睛，也可以睁开眼睛。如果睁开眼睛，会得到一定的兴奋值，也会产生一定的眩晕值。如果闭上眼睛，会减少一定的眩晕值，但不会得到兴奋值。求不超过一个给定眩晕值情况下，得到的最大兴奋值。另外，眩晕值初始为0，也不会低于0。InputThere will be severa

2017-05-05 21:49:41 253

原创线段树，单点更新

题目：HDU 1166代码：#include#includeusing namespace std;const int maxn = 50005;int n,dat[maxn<<2];void pushplus(int k){ dat[k] = dat[k<<1]+dat[k<<1|1];}void init(int l,int r,int k){ if(l==r){

2017-05-05 21:43:10 234

原创 HDU1494 动态规划

HDU 1494题意：跑跑卡丁车是时下一款流行的网络休闲游戏，你可以在这虚拟的世界里体验驾驶的乐趣。这款游戏的特别之处是你可以通过漂移来获得一种加速卡，用这种加速卡可以在有限的时间里提高你的速度。为了使问题简单化，我们假设一个赛道分为L段，并且给你通过每段赛道的普通耗时Ai和用加速卡的耗时Bi。加速卡的获得机制是：普通行驶的情况下，每通过1段赛道,可以获得20%的能量(N2O).能量集

2017-05-03 19:13:16 360

原创尺取法。。

尺取法：反复推进区间的开头和末尾，来求满足条件的最小区间的方法被称为尺取法。一般区间有连续或者单调等特点。例题：poj 2566求任意子序列和的绝对值与所给值相差最小的区间求出前N项的和构成新数组，从小到大排序，再用尺取法做。。。这题恶心，，，不想多说#include#include#includeusing namespace std;typedef pair

2017-05-02 15:43:59 258

原创湖南省第八届省赛，最小生成树Prim算法+利用二进制的状态枚举

题目信息：http://blog.csdn.net/acm_cxq/article/details/52192026题意：n个城市1--n，有m座桥可以城市，编号为1的城市是皇宫。修建每座桥的费用为c，每个城市的人口为pi。总费用为k。求从皇宫出发，修建桥连接尽可能多的城市，城市相互直接或者间接连接通向皇宫，使得跟皇宫相连的所有城市的人口数之和为最大值，且费用不超过k。（无向图）

2017-05-01 15:59:40 259

原创 C++模拟操作系统最近最少使用算法（LRU），acm

题目：cache的大小为K，表示有K个空间储存item，一开始是空的。当CPU在内存中需要item x时，如果x在cache里，就可以直接得到它。如果不在，先判断cache有没有装满，如果没装满，将会把x放入cache中。如果放满了，找出cache中最近最少使用的元素y，然后把y替换成x。输入有多组数据，对于每组数据。给定两个整数N和K，N代表内存需要的item

2017-05-01 13:09:00 1085

原创利用dfs和bfs的回溯，湖南省第八届省赛Collection Coins

第一次接触bfs和dfs的结合，他们是可以相互转化和互补的，还是要多做题。。。

2017-05-01 11:02:36 253

原创动态规划之，最长公共子序列，最长上升子序列，最长公共递增子序列的长度

动态规划小练习

2017-04-27 20:05:35 1248

原创 poj 3292 艾氏筛法的变型

挑战程序设计竞赛第二章练习题，素数部分，对于打表的变型题目，不能硬套模板，还是需要多加思考。

2017-04-26 20:00:23 307

poj 3421，挑战程序设计竞赛第二章，练习题，数学问题的解题窍门，素数部分~感觉除了做题，还学到比较好的模板题意：给一个整数X，求X的因子组成的链的个数（不包括X0）和 m （是所有链中的最大长度（不包括X0）），1 = X0, X1, X2, …, Xm = XX0固定是1。要求满足：X(i+1)>X(i)，且X(i+1)能够整除X(i)。举例：如X =10，那么它的因子组成的链有：1 2 101 5 10所以结果，个数为2，最大长度也为2。

2017-04-26 11:49:21 704

原创 poj 2229，简单的动态规划

#include#include#include#includeusing namespace std;#define MAX_N 1000001typedef long long ll;ll dp[MAX_N];/*** 当n为奇数时，dp[n] = dp[n-1],因为一定包含一个1，所以dp[n-1]的每一种再加1都一一对应着dp[n]; 当n为偶数时，要么至少

2017-04-11 16:34:33 170

原创贪心算法

贪心算法的一般框架1.Greedy Algorithm(parameters)2.{3.初始化;4.重复执行以下的操作:5. 选择当前可以选择的最优解6. 将所选择的当前的解加入到问题的解中去;7.直至满足问题求解的结束条件8.}活动安排问题：设待安排的11个活动的始末时间如下：i1

2016-12-12 16:17:27 252

xrwy2000的博客