Mrhanice

分类

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

/ 注册

全部文章（共50篇）

Airport Announcements URAL - 1889

题目描述：这哥们在机场听公告，假设机场说的公告每种语言含有的短语数是相同的，他有的词能听出什么语言，有的词听不出就是“unknown”，问一共有多少种语言，多种满足情况按照从大到下的顺序输出。解题分析：简单模拟就好，没什么难度。代码如下： #include <cstdio&...

2017-05-23

0 464

C Looooops POJ - 2115

扩展欧几里得算法题目描述：算循环的次数，初始值为A，跳出循环的条件是A！=B，A每次+C，设所有的运算都是二进制k位数，运用补码的原理，当x=2^k,则x+1溢出后=1. 解题思路：扩展欧几里得算法。推一下方程，令所求的次数为x (A+Cx)%2^k=B -> A+C...

2017-05-23

0 620

Cable master POJ - 1064

二分题目描述：仓库中有N条光缆，要求把它们截成总共K段等长的光缆，求截取的每段光缆的最大长度。解题思路：比较水的二分，就是精度坑人+读题费劲。注意这个题精度要求特别高，另外输出的时候因考虑到实际因素，保留两位小数的时候是把两位之后的数据截掉，并不是默认的四舍五入，所以用到了flo...

2017-05-23

0 488

AB HDU 1576

扩展欧几里得题目描述：因为A值太大没有给出，给出了A%9973的值为n，另外还给出了B，求（A/B）%9973的值。题目分析：推一下方程，用扩展欧几里得算法。另（A/B）%9973的值为x, 方程推导过程：（A/B）%9973=x ->...

扩展欧几里得

2017-05-22

0 597

青蛙的约会 POJ - 1061

扩展欧几里得题目描述：两只青蛙都沿着一个圆轨道往西跳，第一个青蛙一步调m,第二个青蛙一步跳n,初始时第一个在位置x,第二个在位置y，轨道长度是L,求跳多少次他俩相遇。解题思路：扩展欧几里得。在此处我令第一个青蛙位置为大写的X，第二个为大写的Y，所求的次数为小写的x.方程 (X+m...

2017-05-22

0 394

C - Asteroids POJ - 3041

匈牙利算法本文采自： http://blog.csdn.net/lyy289065406/article/details/6646007 题目描述：你的飞船有个强大的武器可以打小行星，一次可以攻击一行或者一列，求最少的攻击次数。题目分析：问题可以转化为，选取最少的点，使...

匈牙利算法

2017-05-21

0 488

Educational Codeforces Round 21B. Average Sleep Time

题目链接： http://codeforces.com/contest/808/problem/B 题目描述:给n个睡眠数据，认为连续k个数据作为一周的天数，所以需要考虑n-k+1周，求所有周的平均睡眠时间。解题思路：简单模拟即可。我的处理方法是先计算前k个数据的和。以后滑块的时...

2017-05-16

0 554

Educational Codeforces Round 21 C. Tea Party

贪心题目链接 http://codeforces.com/contest/808/problem/C 题目描述: Polycarp招待朋友，给朋友们倒茶，朋友们的茶杯容量不一样，Polycarp的茶壶容量是w，w小于朋友茶杯满容量的总和。倒茶时需要满足几个条件。 1.每...

贪心

2017-05-16

0 577

习题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