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

思维训练 - Thinkin' in induction

热身题 - 24Game

原题请戳我

题意

给你一个包含整数1...n的集合S。接下来进行n-1次操作,每次操作从集合S中选取两个数,在加、减、乘三种运算中选取一种,将结果放回再集合S。在n-1次操作完成后,集合S中只剩下一个数。求问一种取数和运算策略,使最后的结果为24。

举例:

S = [1, 2, 3, 4, 5]

我们选取(2, 5),并进行加法运算,获得结果7。再将7放回集合S中。

此时,S = [1, 3, 4, 7]。

数据范围

1 <= n <= 100000

解答

建议:请思考10分钟后再来看答案

我们日常写代码,往往是为了实现一个功能或者实现一套逻辑。这时候,我们做的事一般是从零开始,然后逐步迭代,最终实现目标。

这是正常的一种思维方式,也是不错的思维 …

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 #253 Tutorial


443A - Anton and Letters

Simple and easy, solved by two lines of python code.

ls = filter(lambda y: y, map(lambda x: x.strip(), raw_input()[1:-1].split(",")))
print len(set(ls))

443B - Kolya and Tandem Repeat

Brute force. Just enumerate the beginning and the end of the substring, and …

more ...