Beauty-of-Programming 2015 Qualification Round Tutorial

A. 2月29日 (Feb. 29th)

Description

Given a starting date and an ending date. Count how many Feb. 29th are between the given dates.

Solution

The easiest way, of course, the brute force, which is quite simple with Python using the datetime lib.

However, it's not an effective way for the …

more ...

GCJ Qualification Round 2015 题解

前言

这篇日志用中文写是因为想省点时间打游戏。。。(请鄙视我吧。。。

A. Standing Ovation

题意

这是一个骗掌声的故事。

当演出结束后,观众们要站起来鼓掌。但是有些观众比较羞涩,只有在k个人站起来鼓掌后才会故障。

你的目标是在观众中安插一些卧底领掌,让所有观众都站起来鼓掌。(臭不要脸)

求最少的卧底数。

数据规模

抛开数据规模谈解题,都是TM耍流氓。 —— Wizmann

100组数据。

小数据集,观众羞涩值的范围:0 ≤ Smax ≤ 6.

大数据集,观众羞涩值的范围:0 ≤ Smax ≤ 1000.

解题

本题比较简单。有两种方法,一是暴力枚举,因为大数据集中,观众羞涩值最大只为1000,即最大安插卧底数不超过1000。(当然,二分也可以,不过对于1000的数据集,真心没啥必要。)

二是O(N)的一个遍历,在观众羞涩的不想鼓掌时,安插相应数量的卧底。

本题推荐方法一。因为个人感觉,在编程竞赛中 …

more ...

Codeforces Round #289 (Div. 2) Tutorial

A. Maximum in Table

Simulation.

n = int(raw_input())
g = [[1 for i in xrange(n)] for j in xrange(n)]

for i in xrange(1, n):
    for j in xrange(1, n):
        g[i][j] = g[i - 1][j] + g[i][j - 1]

print g[n - 1][n - 1]

B …

more ...

Codeforces Round #288 (Div. 2)

A. Pasha and Pixels

Brute force.

There are multiple ways to form a 2*2 square at one single step.

Alt text

So at every step, we have to check the neighbours of pixel that is colored black.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define …
more ...

Codeforces 447D DZY Loves Modification

题意

给你一个n * m的矩阵,让你做K次操作,使得最后得到的值最大。

操作有两种:

一是在任意一行上操作,最终的结果值加上这一行数的和,然后这一行每一个数都要减去p。

二是在任意一列上操作,最终的结果值加上这一列数的和,然后这一列每一个数都要减去p。

数据范围:1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100

退化版的题目思路

如果我们只限定一种操作,此题就是简单题了。我们维护一个大根堆,堆中保存每一行(或列)之和。

每次操作只需要取出最大值,加到最终结果上。之后将这个值减去对应的p * n(或p * m),再加入堆中。

经过K次循环,就可以得到最后的答案了。

真正的题目思路

对于行和列同时操作,我们也可以套用这种方法。但是要解决对行操作后,对列上数字的值的影响 …

more ...

Codeforces Round #242 (Div. 2) Tutorials and Solutions

A. Squats

Trun x => X or X => x to make the number of 'x' is equal to the number of 'X'.

n = int(raw_input())
hamsters = [c for c in raw_input()]

sits = hamsters.count('x')
stands = hamsters.count('X')

if sits == stands:
    print 0
    print ''.join(hamsters)
else:
    if sits > stands …
more ...


Codeforces Round #223 (Div. 2) 不完全不正确题解

由于大号已经进Div. 1了,所以接下来的几场Div. 2都是用小号做的。

等有实力切D题了,再去打一区。(弱

事情一直很多,所以题解落后了好久才发。

A. Sereja and Dima

纯模拟,Python随便搞

n = int(raw_input())
pokers = map(int, raw_input().split())

v = [0, 0]
p = 0

for i in xrange(n):
    if pokers[0] > pokers[-1]:
        v[p] += pokers[0]
        del pokers[0]
    else:
        v[p] += pokers[-1 …
more ...

Codeforces Round #221 (Div. 2)不完全不正确题解

A. Lever

水题,杠杆原理。

^把字符串分割开。然后分别计算两边的重量即可。

#Result: Dec 24, 2013 6:04:41 PM    Wizmann  A - Lever   Python 2   Accepted     312 ms  4200 KB
def calc(ss):
    res = 0
    p = 1
    for item in ss:
        if item != '=':
            t = int(item)
            res += t * p
        p += 1
    return res

s = raw_input …
more ...

Codeforces Round #218 (Div. 2)不完全不正确题解

A. K-Periodic Array

将Array切片,然后按位统计某一位上1的个数C(1)和2的个数C(2)。然后在这一位上的操作数就为M = min(C(1), C(2))。

简单题

B. Fox Dividing Cheese

傻逼才错的题,不幸中枪。

不想多说了,直接看代码吧。手贱不是病,贱起来要人命。

C. Hamburgers

模拟 + 二分。

和CJL还讨论过这题的纯模拟做法,看了半天代码没找到问题。于是刚才用Python自己实现了一个,在代码正确的情况下,没有WA,但是T在了22组上。

所以这题最好使用二分,如果用模拟的话,需要考虑各种情况。代码见下,细节上注意就好。

D. Vessels

这题得好好讲一下~比赛时做出来了好得意~

Vessels

题意是给出一组层层叠的容器,每一个容器都有自己的容量。然后我们向某些容器里灌水,如果水的体积超过了某个容器的容量,则剩余的水溢出到下一个容器中。最后一个容器溢出的水会落到地面上 …

more ...