2020 计蒜之道 线上决赛 - C. 攀登山峰

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

题意

原题

给一个长度为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 …

more ...

容斥原理以及一些题目

什么是容斥原理

容斥原理是一种计数手段。例如在下图中,我们想不重复、不遗漏的求出包含在ABC三个集合中所包含的元素的个数,应该使用怎么样的方法呢?

image

formula

这个问题对于我们来说并不陌生,当然也并不困难。直观的方法是把所有的元素计数,再把重复的元素排除出去。这种计数的方法,有“容”有“斥”,我们讲其称做“容斥原理”。

容斥原理的应用

小规模的计数问题自然难不倒我们,我们甚至可以使用visit[]数组来记录某元素是否出现。但是当问题的规模增大时,使用数组记录这种方式需要使用更多的内存,在很多情况下,这是我们不能接受的。

考虑一个问题

问题:统计在1~N中的,能被2或3整除的数。(1 <= N <= 1e9)

我们先把这个问题拆成两部分来看:

  1. N以内的,能被2整除的数
  2. N以内的,能被3整除的数

这两个问题都非常简单,我们可以直接使用除法进行求解,其结果分别为N/2N/3

与此同时 …

more ...

一种区间交问题的奇怪姿势

我们要解决什么问题

区间交问题,是我们在做题中经常遇到的问题。

例如,Insert Interval一题,就是比较直白的区间交问题:

给定一系列的整数区间,再插入一个新的区间,问合并后的整数区间是什么

类似的还有Merge Intervals

给定一系列可能有重叠的整数区间,求合并后的整数区间

另一种区间交问题的描述是时间区间相关的问题,如Time Intersection:

给定用户A和用户B的在线时间区间,问两人同时在线的时间区间

又如经典的会议室安排问题Meeting RoomsMeeting Rooms II:

给定N个会议的时间区间,问一个人能否参加所有的会议

以及

给定N个会议的时间区间,问最少需要多少个会议室

还有系统设计与API设计包装后的算法题Range Module。归根结底,都是整数区间问题的变形或者包装。

传统解法

对于这类区间问题,传统的解法是将区间使用顺序容器(如vector)保存,在查询和修改时,使用“排序+遍历”或者 …

more ...

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

思维训练 - Thinkin' in induction 2

最大导出子图(maximal induced graph)

你现在在组织一个学术会议。现在你有一份人员名单。假定名单中的每一个人都同意到达,并且有充足的时间交流意见。同时,每一个科学家都写下了他愿意与其进行交流的科学家的名字。

现在,问题来了:挖掘机技术哪家强?

如果要保证每一位科学家至少能与k位到场的科学家进行深入的交♂流♂。那么我们最多可以邀请多少人到会?

注:如果A愿意和B交流,AB一定会进行交流。反之亦然。

我们可以把问题转化成数学语言:对于一个无向图G=(V, E),试求得G的最大导出子图H,使得H中所有顶点的度大于或等于k,或者证明这样的子图是不存在的。

我们继续使用归纳的思想来解决这个问题。

易得,对于顶点数为k的图,如果存在k-导出子图,则该图必为一个完全图。

假设,对于任意顶点数小于n的图,我们总可以找到图的k-最大导出子图。

对于有n个顶点的图G来说,如果有任意顶点的度小于k,那么对于图G的任意子图,此顶点的度总小于k。

所以,对于图中任意度小于k的点,必然不属于所求的子图。于是,我们每次删除一个不属于k-导出子图的点,就可以把有n个顶点的图问题化归为n-1顶点的图问题。

一对一映射

给定一个集合A和一个映射关系f。求A的一个子集S,使得f对于S是一个一对一映射 …

more ...