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 #290 (Div. 2) Tutorial

A. Fox And Snake

Implementation

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

res = []

for i in xrange(n):
    if i % 2 == 0:
        res.append('#' * m)
    elif (i / 2) % 2 == 0:
        res.append('.' * (m - 1) + '#')
    else:
        res.append('#' + '.' * (m - 1))

for line in res:
    print line

B. Fox And Two Dots

DFS …

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 ...

Snake Problem

题目

在一个平面上,有n+m条蛇,其中n条蛇沿水平方向(y轴方向)移动,m条蛇沿竖直方向(x轴方向)移动。

现给出这些蛇头和尾所在的坐标点,求出这n+m条蛇在此时共有多少个交点。在同一个方向移动的蛇不会有交点。

如图所示,n = 5, m = 4,这些蛇一共有5个交点。

Alt text

分析

对于此题,最简单直接的方法就是枚举蛇两两之间的关系,这种算法的时间复杂度为O(n^2)。

当然,我们不能满足于这种暴力的解法。那么,有没有更优美的方法呢?

Alt text

对于这一条在y轴方向上的(红)蛇来说,它与x轴方向上的(黑)蛇共有三个交点。那么,也就意味着,问题的关键在于,我们如何快速确定某一条红蛇(或黑蛇)与其它蛇一共有多少个交点。

我们可以做出如下假设,我们知道当x = k时,所有在平面上的蛇的位置。根据这个假设,我们可以使用区间求和的算法来确定竖直位置上的蛇会有多少个焦点。

假设我们从x = 0到x …

more ...