本文使用了一种概率算法，不是正解，只求骗分。

题意

原题

给一个长度为n的数组A[1...n]。

现在有q个查询请求（q <= 1e5），每个请求给定一个长度为m的子数组A[i...j]和一个整数t。问在子数组中出现次数超过m/t的数字中（t <= 20），最大的数是多少。

题意中的坑

阈值m / t是一个实数。（题意不明先死个🐴好吗？）

解法

首先我们将每种数字出现的位置简历一个索引，此时对于任意一个数，我们可以用二分法在O(logn)的时间内求出其在某个区间内出现的次数。

因为t最大是20，也就意味着如果我们随机取数，那么取到一个符合出现次数限制的（超过m/t次）数字的概率是1/t。如果我们进行多次尝试，并使用上面的方法对其进行验证，几乎可以保证我们一定可以取到正确的那一个。

那么“多次尝试”是多少次呢？我们枚举所有的t，然后计算其在q=1e5的情况下的成功率。因为这是一个随机算法，我们先使用下面的代码分别计算一下成功率为10%和50 …

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 …

前言

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

A. Standing Ovation

题意

这是一个骗掌声的故事。

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

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

求最少的卧底数。

数据规模

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

100组数据。

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

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

解题

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

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

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

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 …

A. Pasha and Pixels

Brute force.

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

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 …

Introduction

There are a lot of interview problem based on the 1D-array, which is the one of the easiest "data structure".

But the problem about that simple data structure might not be that simple. Here is the summary of the problem about 1D-array.

Of course, most of them come from …

题意

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

操作有两种：

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

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

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

退化版的题目思路

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

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

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

真正的题目思路

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

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 …

Overview

It has been months that I didn't participate in the contest on CF, now I'm back. :)

This round of contest makes me confused that the problem B and C is a little bit too twisted, if you can't catch the vital point, you will get a lot of WAs …

由于大号已经进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 …