Mrhanice

UVA

codeforces(2) DP基础(3) POJ(8) 云服务器(1) 区间DP(4) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章 / UVA （共14篇）

Perfect Service UVA - 1218

树形DP 题目描述：求最少的服务器，使得其他不是服务器的计算机恰好和一台服务器计算机相邻。解题分析：定义dp[u][0] u是服务器，每个子节点可以使服务器也可以不是。 dp[u][0] = sum(min(dp[v][0],dp[v][1])). dp[u][1]...

dp 树形DP

2017-08-24

0 528

Party at Hali-Bula UVA - 1220

树形DP基础求最大独立集题目描述:老板和员工不能同时选，问最大能选择多少人，并且种种方案是否唯一。解题分析：定义两个数组 int dp[maxn][2];dp[u][1]表示以u为根节点的子树中选择u能得到的最大人数，dp[u][0]表示不选最大人数 int f[ma...

dp 树形DP

2017-08-23

0 490

习题8-14　商队抢劫者（Caravan Robbers ACMICPC NEERC 2012 UVa1616）

二分+贪心题目描述：有n个区间，选择各区间的子区间使得各个子区间不相交，而且子区间的长度相同，求最大子区间的长度。解题思路：二分枚举子区间长度，用贪心法判断该子区间是否满足题意。最后一步是将所得的浮点数化成分数。另外，本题对精度卡的特别严，1e-6都不行，1e-9可行。代码...

2017-05-16

0 491

顾客是上帝（Keep the Customer Satisfied, ACM/ICPC SWERC 2005, UVa1153）

题目描述：求最少的交换次数，使给定的数字序列能成为环。解题思路：最少交换次数的环一定是某一个数为起点的环。那便枚举1~n使之作为起点。注意环可以使顺时针增加也可以减少，所以需要再反序枚举，求出最小的交换次数。求最小的交换次数的方法是,让alien[i]=i，否则交换，此时cnt++。至于为...

2017-05-13

0 638

奇怪的股市（Hell on the Markets,ACM/ICPC NEERC 2008, UVa1614）

题目描述:简而言之就是给一系列数前面加个正负号，使得其和为0. 解题思路：先给这一系列数排序。如果sum是奇数一定不可行，sum必须是偶数才有解，sum/=2,按照从大到小的顺序使sum-trade[i];直到sum为0。为了记录trade[i]在原序列的位置，用一个map来定位，其键就是t...

2017-05-11

0 2898

猜名次（Guess, ACM/ICPC Beijing 2006, UVa1612）

贪心题目描述：有n个选手，每个选手做三个题。对了得相应得分，错了不得分，问能否最终得出给你的那个排名。排名规则是：分高的排名高（名次号码低），分数相同的话，ID小的排名高。题目分析：按照给出的排名对应的选手处理相应的数据，第一名一定是三题全对，其后的人分数不能大于上一名，或者是分...

2017-05-10

0 770

生成排列（Generating Permutations, UVa11925）

题目描述：给你一个特定序列，要求你经过一定的变换规则将升序列变为给的特定序列。变换规则为：1.第一个元素和第二个元素交换. 2、首元素到尾部。题目分析：借鉴的别人的。将一个升序列变为特定序列显然不如把这个特定序列变为一个升序列容易。那么就逆着处理，最后输出的时候倒着输出就行了。方法类似于冒...

2017-05-08

0 649

起重机（Crane ACMICPC CERC 2013 UVa1611）

贪心题目描述：给定一串数，要求把数按照给定的交换规则排成升序。交换规则：选定偶数个数把这些数的前半部分和后半部分交换，各半部分中的数不变。求交换的次数和每次交换数字序列的首端点和尾端点。题目分析：按照选择排序法的思想，将数字i放在第i的位置,前面排好的数字就不用管了。如果数字i不...

2017-05-06

0 548

Knight Moves UVA - 439

这题比较简单，对于我这种学弱学习bfs再好不过了。下面是代码： /************************************************************************* > File Name: Knight Moves UVA ...

2017-03-16

0 336

UVA - 1600 Patrol Robot

题目描述：要求一个机器人从一个m*n的矩阵的（1,1）到（m,n）的最短路。矩阵中有障碍物，机器人最多可以一次跨越k个障碍物，遇到非障碍物则障碍物数清零。解题思路：最短路问题。核心是在结点中加状态量，在队列中添加满足条件的结点时，在原结点的基础上改变一些状态量，添加进队，直到要么走到目的地...

2017-03-16

0 509