Codeforces

Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes

原题:http://codeforces.com/contest/551/problem/C 题目大意: n堆箱子, m个学生要搬走箱子, 每个学生走过在箱子中间移动需要一秒, 移除一个箱子需要一秒, 问最少多少秒搬完. 分析: 这题有两个很tricky的地方. 一个是在搬走的时候, 不需要移动学生到别的地方. 所以如果学生在箱子上面, 在n秒内, 就能搬走n个箱子. 第二个是学生之间是同步进行搬箱子的. 解题的时候, 用的是穷举, 后来过不了TLE了. 看了答案才明白是二分搜索问题. 这里二分搜索用的是以下的原理: 如果在t秒内能完成任务, 那么肯定在大于t秒的时间内也能完成. 这就说明我们可以忽略那些大于t秒的情况.如何找到t呢. 因为题中告诉我们: at least one pile is non empty. 所以移动到这个non-empty pile需要1秒, 移动box 需要1秒, 所以我们的low bound是2. 那high bound是什么? 我们假设只有一个学生, 移动到n个地方需要n秒, 移除a1,a2…an个箱子需要a1+a2….+an秒, 所以high bound是(数组长度+box总数). 所以我们的range是在[2,Total(box+index)] 在每次搜索中,我们对m个学生依次分配任务, 从最后一个non-empty的pile开始移动尽可能多的箱子中. 因为我们已经知道时间是固定的, 所以问题转换成: 在已知时间内, 每个学生最多能拿多少箱子, 这里用贪婪的思想, 假设每个学生拿最多就可以. public void […]

Date July 29, 2015
Category Codeforces
Comments No Comments

Codeforces Round #307 (Div. 2) B. ZgukistringZ

原题: http://codeforces.com/contest/551/problem/B 题目大意: 给3个string,a,b,c. 问用a的字母通过交换,最多可以得到多少个b或者c? 分析: 本来感觉是dp的题, 后来想想不用那么复杂, 先用三个26个字符数组, 存下三个字符串的字频, 然后用三个变量,num, nums_a, nums_b存下对应a,b,c的个数. 然后暴力破解就可以, 因为题目是求最多b或者c. 我们假设从0个b开始,一步步递增. 看看最多能有多少个. 这里需要注意的是, b的取值应该是从[0,count_b[j]*i > count_a[j]](0个b, 到i个b的第j个字母超过了i个a的第j个字母). 最后输出的时候, 先输出b,再是c, 最后把a剩下的字符输出就行了 public void solve(int testNumber, InputReader in, OutputWriter out) { String a = in.readString(); String b = in.readString(); String c = in.readString(); int[] ca = new int[26]; int nums = 0; int […]

Date July 27, 2015
Category Codeforces
Comments No Comments

Codeforces Round #307 (Div. 2) A. GukiZ and Contest

原题: http://codeforces.com/contest/551/problem/A 题目大意: 给n个人, 每个人都有rank, rank最高的人是1, 同一个rank的人得分一样, 不同rank的人,得分是前边rank人数的合, 问返回的数组是什么. 分析: 我看题目是sorting, 我没sort唉. 一共rank才2000, 用个count数组记录一下, 然后从后往前(从大rank到小rank)扫数组,每次扫都取合传给下一个rank. 然后再走一般数组打印出来对应的rank就行了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[2005]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { int t = in.readInt(); count[t]++; nums[i] = […]

Date July 26, 2015
Category Codeforces
Comments No Comments

Codeforces Round #308 (Div. 2) C. Vanya and Scales

原题: http://codeforces.com/contest/552/problem/C 题目大意: 给两个数字,w和m, 再给一堆砝码, 砝码的重量是w^0,w^1,w^2….w^100, 且每种只有1个.是否能放到天平上来称出m(天平平衡). 砝码能放天平的两边. 分析: 首先观察一下题, 一看就是进制问题, 上来先把m变成w进制. 然后我们知道每个砝码只有一个, 所以我们要考虑怎么放才能平衡, 举个栗子, m是7, w是3, 我用一个叫into的数组, 把m变成w进制, 变成后就是 1,2,0, 因为 1*3^0 + 2*3^1. 然后我们观察一下这个数字, 假设我们把m放在天平的左边, 那么相当于左边已经放上了1个3^0 和2个3^1, 通过观察我们发现, 如果数组元素为1, 那么我们可以通过直接放一个相同的砝码在右边的天平, 天平就可以平衡. 如果数组元素为0, 那么我们可以不放任何砝码在右边就能使天平平衡. 如果数组元素为w, 那么我们尝试去放一个比当前砝码大1的砝码到右边的天平上, 比如, 如果w=3, 数组的第二位,3^1的值是3, 那么3*3^1 = 3^2. 不失一般性的, 假设w = w, 数组第i位 w^i的值是w, 那么w*(w^i) = w^(i+1). 如果数组元素为w-1, 那么我们放当前砝码在左边, 并且尝试放一个大1的砝码在右边. 这时,相当于天平的右边欠了左边一个差为w^(i+1), […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #308 (Div. 2) B. Vanya and Books

原题:http://codeforces.com/contest/552/problem/B 题目大意: 给个数字n, 求这n个数字的digits个数的合分析: 比如1234, digit是1的区间是[1,9], 一共9个, 2的区间是[10,99]一共90*1个digit, 3的区间是[100,999]一共900*2个digit, n的区间是[10^n,10^(n+1)-1]一共10^(n+1) – 10^(n)*(n-1)个digit. 那么1234 落在区间4, [1000,9999]中. 可以用1234-1000+1得到4个digit的数字的个数, 然后乘以4,得到digit为4的digit数, 然后与前边的区间的合相加, 就是答案第一次写: public void solve(int testNumber, InputReader in, OutputWriter out) { long n = in.readLong(); long t = n; long res = 0; int digits = 1; while (n / 10 != 0) { res += (9 […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #308 (Div. 2) A. Vanya and Table

原题:http://codeforces.com/contest/552/problem/A 题目大意: 给[1,100]个格子, n个矩阵, 问n个矩阵覆盖格子的合是多少? 分析: 乘一下就出来了 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int res = 0; for (int i = 0; i < n; i++) { int x1 = in.readInt(); int y1 = in.readInt(); int x2 = in.readInt(); int y2 = in.readInt(); res += (x2-x1+1) * (y2-y1+1); […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #310 (Div. 2) C. Case of Matryoshkas

原题: http://codeforces.com/contest/556/problem/C 题目大意: 俄罗斯套娃, 给n个套娃, 套成k组, 每组用数字表示, 大的数字套小的数字, 问怎么把它们套在一起. 分析: 这题想了好久哇. 因为开始读题不仔细, 所以开始想的时候各种WA. 我以为: 1 2 3 4 5 6 这种情况只需要一秒. 但是仔细看题才发现, 这个需要先把6拆下来, 然后把5 套在4上, 然后把6套在5上, 所以是三步. 这个地方卡了好久. 剩下的思路很明确: 首先找到最小的套娃1, 然后往后扫, 看看按照1 2 3 4 ….n这个顺序有几个. 因为把n个套娃套上需要n-1秒,所以坏情况, 就是我们拆下所有的套娃用n-1秒, 然后套上去, 用n-1秒, 这里的-1的原因是编号1的套娃不用动. 所以最坏下是n-1+n-1 = 2n-2秒. 然后我们用排除法, 这里需要把拆开和组装分开记录,一种是一个链子中为: 1 2 3 4 5 …. 这种情况下, 我用变量b记录了有多少个不用组装的套娃. 第二种是, […]

Date July 25, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 2) B. Ohana Cleans Up

原题:http://codeforces.com/contest/554/problem/B 题目大意: 给个n x n的binary矩阵, 只能翻转(0->1,1->0)列, 问如何翻转, 让全是1行的总数最大. 分析: 因为每次翻转列的时候, 每个行都要翻转, 所以只要找到最大数目的相同的行. 就可以了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); HashMap<String, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { String s = in.readString(); if (!map.containsKey(s)) map.put(s,0); map.put(s,map.get(s)+1); } int max = 0 […]

Date July 23, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 2) A. Kyoya and Photobooks

原题:http://codeforces.com/contest/554/problem/A 题目大意: 给一个string,表示一个相册页, 左右都能放photo, 问几种方法. 分析: n个相册夹, 左右都能放, n+1种地方, 26种photo, (n+1)*26, 当然会有重复, 重复是n个. 减去重复的就是答案 public void solve(int testNumber, InputReader in, OutputWriter out) { String s = in.readString(); int n = s.length(); out.print((n+1)*26 – n); }

Date July 23, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 1) A. Kyoya and Colored Balls

原题:http://codeforces.com/contest/553/problem/A 题目大意: k个颜色, n个球, 球之间没区别. 问怎么放能至少让一个i个颜色的球排在i+1的颜色的球的前边. 分析:这题目看起来是很拗口, 我看着发愣了一会儿才明白. 颜色是有顺序的.第i+1颜色的前边至少要有一个i颜色的球, 这个i不是固定的. 1<=i<=k-1, 所以题目也可以解释成,至少一组球是有序的, 这个有序不一定是连续的球. 因为i表示的颜色是个范围, 所以要用dp来做, 假设i = 1, 这时候就一种颜色, 因为球和球之间无区别, 所以答案是1. i = 2的时候, 因为要保持以上的条件, 所以我们选一个颜色为2的球,放到最后, 然后其他的无所谓. (点一下,有清楚的图) public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = IOUtils.readIntArray(in,n); int max = 1002; long[][] bio = new long[max][max]; for (int […]

Date July 23, 2015
Category Codeforces
Comments No Comments