Mrhanice

分类

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

/ 注册

全部文章（共50篇）

奇怪的股市（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 2925

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

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

2017-05-10

0 831

生成排列（Generating Permutations, UVa11925）

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

2017-05-08

0 693

起重机（Crane ACMICPC CERC 2013 UVa1611）

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

2017-05-06

0 569

Knight Moves UVA - 439

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

2017-03-16

0 350

UVA - 1600 Patrol Robot

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

2017-03-16

0 537

S-Trees UVA - 712

这个题形如二叉树，但我没有建树，用了类似于中找到对应叶子位置的方法。本题中，非终止的层数有几层，则叶子数为1<<n,后续输入的4个查询，我按照根据输入的查询来找到应该的叶子的位置，例如：输入时是x1,x2,x3, 4次查询是000 010 111 110，则对应叶子的位置是0,2,7,6...

2017-03-12

0 494

Tree Recovery UVA - 536

题目只是要求输出后序遍历，这样就省事多了。无需建树，用数组来表示每个节点的字母，递归输出后序遍历即可。 /************************************************************************* > File Name:...

2017-03-12

0 452

UVA 673 - Parentheses Balance

一个渣到爆的菜鸡，就是一个模拟栈的操作，调试了这么长时间。 /************************************************************************* > File Name: Parentheses Balance U...

2017-03-11

0 563

UVA12716 GCD XOR

本题借鉴了刘汝佳的思路和别人的博客，刚开始尝试用gcd来判断，时间特别长，没成功，最后选择了判断a^b==c的方法解题关键： 1.若a^b=c,则a^c=b;(a^a=0,b^0=b) 2.若gcd(a,b)=a^b=c,则a-b=c; ...

2017-03-05

0 536