ascii991-CSDN博客

原创 poj 2938 Economic Phone Calls

此题的核心就是选择，按时间顺序进行选择的话，可以发现每次选择只和当前选择的集合中时间最晚的电话有关。所以可以dp。令f[i][j]为处理了前i个电话，当前选择的电话中最晚的电话为j时，选择的最少电话数。对于i而言，如果选择i，则有f[i][i]=min{f[i-1][j]},其中1同时，如果i是今年的电话，则除了上面的转移，还有f[i][i]=min(f[i][i],f[i-1][

2012-08-18 16:25:22 635

原创 poj 2817 wordstack

数据规模很小，不免让人想到搜索。但10！=3628800还是不够优秀。考虑到每次选择只与前一次选择有关，且N注意理解题意，允许两个单词中位置相同的字母不同，只是要求位置相同的字母相同的数目最大即可。可以在dp前做一些预处理。【代码】#include #include #include #include #include using namespace std;

2012-08-18 16:12:22 689

原创双调TSP问题总结---poj 2677和usaco5.4 canada tour

双调TSP指的就是从最左边的城市出发，从左往右遍历一些城市，到达最右端，再从最右端从右往左返回出发城市，然后最优化某些东西。poj 2677 就是要遍历所有的城市，最小化行走的距离（欧几里德距离）usaco canada tour 就是每个城市最多遍历一次（出发点两次），最大化遍历的城市数量。【解答】显然从左往右，从右往左都是一样的，都可以变成从左往右。我们称前者为上行路线，后者为

2012-08-16 15:24:06 2778

原创 poj 2486 apple tree

显然是一道树上的分配问题。自然而然想到树上的背包。但要注意，这道题有两种情况。1、往下遍历，并最后返回根节点。2、往下遍历，并停留在某处结束，不返回根节点。令第一种为f[x]，第二种为g[x]。求g[x]时，要枚举究竟是哪个儿子是往下遍历，最后停留在某处结束，不返回根节点的。所以复杂度为O(N*N*K*K)【教训】在叶子这里的边缘状态设置：f[x][0]=f[x

2012-08-14 14:22:12 940

原创 POJ 2057 The lost house

这道题求的是期望。首先，一看到期望，就会想到可以将问题分成若干个子问题，再分开算期望，所以这道题可以使用动态规划。注意到每个叶子有房子的概率是均等的。所以答案就是遍历每个叶子最少的步数/叶子的总数。所以问题划归为求遍历所有叶子的最少步数。我们令fail[x]为以x为根的子树找不到房子的最少步数。su[x]为以x为根的子树中找到房子最少步数。le[x]为以x为根的子树中叶子的

2012-08-14 14:04:51 1206

原创 poj 1925 spiderman

首先，这道题有两种做法。第一种是先枚举位置，再枚举楼进行dp。第二种是先枚举楼，再枚举位置。然而蜘蛛侠的行进路线有对称性的。相当于将一号楼沿着某一座楼对称过来，就像镜子一样。根据对称性，蜘蛛侠在放出绳子时的高度永远是h[1]。因此，第二种方法中枚举位置时，可以根据蜘蛛侠所在的高度和楼的高度两个条件，缩小第二层枚举的范围。因此，第二中方法更加优秀。【代码】#include #inc

2012-08-14 13:38:22 1170 1

原创 APIO2007 数据备份贪心+堆实现

【算法分析】n，k都有10^5，所以考虑贪心算法最基本的贪心就是任意一对数必须是相邻的，这是显然的。考虑到一重要结论：假设现在有三条相邻的线段a1,a2,a3；a1>a2,a3>a2，如果a2小于等于最优解集中的最大元素，并且最优解集中不存在a2，则必同时存在a1,a3。证明：如果最优解中只有a1或只有a3，那我可以把它换成a2，这组解仍然满足要求，但总距离更小。如

2012-08-04 13:59:13 1284

原创 poj 1038 状态压缩dp 四进制压缩

黑书上的牛逼题状态压缩，每个格子有0，1，2三种状态。0表示这个格子为空，1表示这个格子到下一行为空。2表示这个格子到下下一行为空。如果以(x,y)这个格子为左上角放2*3的矩形，则(x,y)=(x,y+1)=(x+1,y)=(x+1,y+1)=(x+2,y)=(x+2,y+1)=2。如果以(x,y)这个格子为左上角放3*2的矩形，则(x,y)=(x,y+1)=(x,y+2)=(x+1

2012-08-02 17:07:13 1111

原创并查集练习---poj 2912

集合的合并与维护和食物链那道题一样。不过多了个裁判。注意到N如果有矛盾，则这个人不是裁判。唯一有点难度的是输出第几行判断出的裁判。原先以为是最后出现裁判的那一行。后来发现应当时枚举其他人时候首次出现矛盾的最大值。（仔细想想)这样这道题就解决了。【代码】#include #include #include #include #include using

2012-07-28 14:37:09 526

原创并查集练习---poj 1417 并查集+DP

这到题倒是和team them up 有些类似。很容易得到：回答yes ，则x和y是相同集合的，反之，则是不同集合的。首先用friend-enemy 并查集，注意：不要将朋友和敌人分开维护，这样容易出错。得到了若干集合，每个集合有两个数，a和b。现在要求n个集合中各挑出一个数(a或者b)，使得他们之和等于p1(说真话的人数)。而这个用dp可以很好的解决，用f[i][j]表示

2012-07-28 14:28:57 1401

原创并查集练习---poj 1984

usaco的月赛题。记录两个点之间x方向和y方向的相对距离，用并查集维护。若与poj 1182食物链进行比较，便会发现路径压缩部分，集合合并部分的相似点。所以并查集不难，是有一定套路可循的。大家一定要好好总结。【代码】#include #include #include #include #include using namespace std;const i

2012-07-28 14:20:21 1580

原创并查集练习---poj 1182 食物链

经典的并查集题目。主要是节点之间的关系的维护。首先看路径压缩部分：int find(int x){ if (fa[x]==x) return x; int t=fa[x]; fa[x]=find(fa[x]); r[x]=(r[x]+r[t])%3; return fa[x];}这里要注意保存原来的父节点。再看如何合并：fx=find

2012-07-28 14:15:52 537

原创线段树典型例题--poj2777

这到题我认为网上有些人的算法是不对的。void solve(int l,int r,int root) //询问{ if(tree[root].col>=0) //如果父节点有单一的颜色，就直接更新，不需要找到子节点更新 { flag[tree[root].col]=1;//统计哪些颜色出现过 return; } if(t

2012-07-23 17:37:27 783

原创线段树典型例题--poj3667 hotel

题目很像内存分配。线段树维护这样几个量：col：节点的颜色（0--没有覆盖，1--全覆盖，-1--有多种颜色）dl：从左边开始的最长连续段dr：从右边开始的最长连续段dm：节点中的最长连续段dp：节点中最长连续段的开始位置具体见代码：#include #include #include #include #include using namespace s

2012-07-23 17:22:37 597

原创线段树典型例题--poj3277

将x轴上的点离散化。y轴建立线段树。使用延迟标记。注意：延迟标记不是单纯覆盖，而是需要比较的。pp[i]为标记则应当是pp[i*2]=max(pp[i*2],pp[i]);pp[i*2+1]=max(pp[i*2+1],pp[i]);而不是pp[i*2]=pp[i*2+1]=pp[i];【代码】#include #include #include #incl

2012-07-23 17:16:35 534

原创线段树典型例题--poj2828

逆序处理。注意到如果逆序插入，则每次插入的位置都是第x个空位。所以可以用线段树来寻找第x个合法位置【代码】#include #include #include #include #include using namespace std;const int N=200005;int sum[N*3],pos[N],val[N],p[N];int n;void

2012-07-23 17:11:57 439

原创线段树典型例题--poj2528

此题的关键在于离散化。对于线段(a,b)，要将a-1,a,b三个量都考虑进去。否则我们看这样一个例子：31 101 36 10 答案是3如果不考虑a-1，则答案会变成2。【代码】#include #include #include #include #include using namespace std;const int N=1000

2012-07-23 17:09:06 467

原创线段树典型例题--poj2482

【题意】Assume the sky is a flat plane. All the stars lie on it with a location (x, y). for each star, there is a grade ranging from 1 to 100, representing its brightness, where 100 is the brightest and

2012-07-23 17:04:10 637

原创 poj 贪心小结（一）

本次贪心题的练习题有:2325,3258,3122,2393,1065,1323,1328,17001700:经典的过河问题。两种贪心策略，一种是最快的+最慢的，最快的回来，再最快的+次慢的，最快的回来，第二种是最快的+次快的，次快的回来，再最慢+次慢过河，在最快的回来。两中策略的结果都是最慢的和次慢的过了河。然后就可以dp，注意n=1,2,3特判。2325：贪心+高精度3258：二分

2012-07-14 10:30:42 2789

原创 ural 1165 subnumber ------猥琐的超级大繁题

1165. SubnumberTime Limit: 1.0 secondMemory Limit: 16 MBGeorge likes arithmetics very much. Especially he likes the integers series. His most favourite thing is the infinite sequence of digi

2012-07-11 14:50:52 888

原创 poj模拟题总结（一）

模拟是acm算法中基础但深奥的算法，不容轻视。本次模拟题练习题为1835，2623，2271，2996，2706，1676，1472，1027，3371。1835 宇航员：可以以左手，脸，头三个参量的方向来确定自己的方向。自己比划比划即可。2996：棋盘问题，比较水。2706：线段相交+DFS，注意线段相交的判断。1676：DFS即可。1472：典型的递归题，构建栈。

2012-07-11 14:02:26 1373

原创 poj1379 模拟退火

【题意】地图中有N个陷阱，给出他们的坐标，求一个点，使得这个点到所有陷阱的最小距离最大。【题解】乍一看是二分，但没有好方法。看到题目要求的精度为0.1，则自然想到了模拟退火。模拟退火的流程大致如下1、随即生成若干解2、定下步长d，和降温速度3、开始模拟退火过程【代码】#include #include #include #include #inclu

2012-06-06 10:39:20 3220

原创 poj 1830 异或方程组

【题意】有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）【题解】

2012-06-06 10:25:52 1297

原创【百度之星资格赛】F:百科蝌蚪团

F:百科蝌蚪团时间限制: 1000ms 内存限制: 65536kB描述百度百科有一支神奇的队伍，他们叫自己“百科蝌蚪团”。为了更好的让蝌蚪团的成员们安排工作，百度百科的运营团队定出了一个24小时制的时间表。例如：1. 每个蝌蚪团成员工作时长相同；2. 必须安排蝌蚪团成员在他们方便的时间段工作；3. 蝌蚪团成员安排时间最小安排时间节点（开始工作或停止工作）为半小时，比

2012-06-06 10:16:38 13208

原创【2012百度之星 / 资格赛】I:地图的省钱计划

时间限制: 1000ms 内存限制: 65536kB描述百度地图有自己的一套坐标系（你可以把它看作一个笛卡尔坐标系），在这套坐标系里，一个标准单位为1km。而在这坐标系上针对地理信息进行标注的数据，大多数时候是通过购买的方式完成的。为了节约数据更新的成本，数据组里的鑫哥想出了一个好主意——自己测数据。鑫哥按照他的预想开始实验；在每组试验中，鑫哥选取了三个已经被准确标

2012-06-06 10:10:57 459

原创 topcoder SRM495 div1 level3

Problem Statement When cat Taro went to an internship, he found a strange elevator in the office's skyscraper. The skyscraper contains 58 floors. The elevator is composed of 2 boxes and thes

2012-05-28 14:05:50 713

原创 topcoder SRM495 div1 level2

Problem Statement There are N boxes numbered 0 through N-1. Every box except for one contains carrots, but Rabbit Hanako does not know which box is the empty one. Each box has the same proba

2012-05-28 13:54:07 610

原创 jupiter软件--解决ubuntu在笔记本上耗电大的问题

Jupiter 是一个专用于笔记本及上网本的小工具，功能是节省用电量。用户可以用它来在“全速/高性能/省电“三种模式之间自由切换，并可以进行分辨率设置等操作。在某种工作模式下，它会自动启用/禁用蓝牙、触摸板、WIFI 等设备，以便达到省电效果，同时它还支持 Asus EeePC 的 Super Hybrid Engine (SHE) 功能。近日 Jupiter 发布了最新 0.0.50 版，在

2012-05-25 17:53:20 5855

原创 topcoder SRM 492 div2 level3

A traveling salesman wants to survey N cities for business opportunities. The cities are numbered 0 throughN-1, and he wishes to visit each of them at least once. He starts at city 0 and can end at an

2012-05-25 17:47:12 544

原创 SRM 492 div1 level 2

There is a kingdom with N cities numbered 0 throughN-1. Gogo wants to survey several cities in the kingdom. These cities are described in int[]cities containing M elements. He wishes to survey cit

2012-05-25 17:44:04 548

原创 SRM 492 div1level1

There are N trees arranged in a straight horizontal line. They are numbered 0 through N-1 from left to right. The distance between tree i and tree (i+1) is distance[i], and the initial vertical height

2012-05-25 17:39:37 406

转载使用MbrFix软件卸载Linux系统

不用Windows系统安装盘，不用安装矮人DOS工具箱也可以很简单地实现卸载Linux。双系统卸载Linux的主要问题是当在windows中将linux 分区直接格式化之后，Grub系统引导程序也会被同时删除，所以导致重启后无法进入Windows 或Linux任何一个系统。因此卸载linux之前，先修复MBR，然后再删除Linux分区就可以了。而MbrFix.exe 就是这样一个W

2012-05-24 14:47:26 986

原创 Linux下软件的安装与卸载

在Windows下安装软件时，只需运行软件的安装程序（setup、install等）或者用zip等解压缩软件解开即可安装，运行反安装程序（uninstall、unware、“卸载”等）就能将软件清除干净，完全图形化的操作界面，简单到只要用鼠标一直点击“下一步”就可以了。而 Linux好象就不一样了，很多的初学者都抱怨在Linux下安装和卸载软件非常地困难，没有像使用Windows时那么直观。其实

2012-05-24 14:44:38 453

原创 topcoder SRM 501 div1 level1

Problem Statement Fox Ciel was very bored, so she invented a single player game. The rules of the game are:You start with 0 points. You make exactly nA+nB moves. You have two ty

2012-05-19 10:44:00 587

原创 topcoder SRM 500 div2 level3

Problem Statement NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.You are given two geometric progressions S1 = (b1*q1i,

2012-05-19 10:41:14 476

原创 topcoder SRM div 2 level 1

Problem Statement Dmitry likes TopCoder Single Round Matches. Once, he registered for an SRM and was waiting for the coding phase to begin. To entertain himself while waiting, he decided to

2012-05-19 10:38:38 704

原创 topcoder SRM500 div1 Level3

Problem Statement NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.A positive integer is called nice if the sum of its di

2012-05-19 10:36:40 960

原创 topcoder SRM500 DIV1 LEVEL1 250分题

Problem Statement N friends (numbered from 0 to N-1) play a game called Mafia. The exact rules of the game are not important for this problem. What's important is that at some point in the

2012-05-14 17:08:46 697

原创 topcoder SRM500 DIV1 level2 500分

Problem Statement Nick likes to draw fractals. For the special occasion of Single Round Match 500, he decided to draw the 500th generation of his favorite fractal.Each generation of the

2012-05-14 16:47:23 679

原创 poj 1180 dp 斜率优化

【题意】N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。（1

2012-05-08 10:50:10 1963 2

空空如也

空空如也