WuTao's Blog

while(!(succeed = try()));

0%

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 3.3k 阅读时长 ≈ 3 分钟

题目链接：MAXMATCH - Maximum Self-Matching

Description

You’re given a string s consisting of letters ‘a’, ‘b’ and ‘c’.

The matching function $m_s( i )$ is defined as the number of matching characters of s and its i-shift. In other words, $m_s( i )$ is the number of characters that are matched when you align the 0-th character of s with the i-th character of its copy.

You are asked to compute the maximum of $m_s( i )$ for all i ( 1 <= i <= |s| ). To make it a bit harder, you should also output all the optimal i’s in increasing order.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

Codeforces Round #488 by NEAR (Div. 1)

题目链接：

Nikita and Order Statistics

CF993E Nikita and Order Statistics

Nikita likes tasks on order statistics, for example, he can easily find the $k$-th number in increasing order on a segment of an array. But now Nikita wonders how many segments of an array there are such that a given number $x$ is the $k$-th number in increasing order on this segment. In other words, you should find the number of segments of a given array such that there are exactly $k$ numbers of this segment which are less than $x$.

Nikita wants to get answer for this question for each $k$ from $0$ to $n$, where $n$ is the size of the array.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目链接：HDU 1879

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

题目链接：POJ 3090

Description

A lattice point $(x, y)$ in the first quadrant ($x$ and $y$ are integers greater than or equal to $0$), other than the origin, is visible from the origin if the line from $(0, 0)$ to $(x, y)$ does not pass through any other lattice point. For example, the point $(4, 2)$ is not visible since the line from the origin passes through $(2, 1)$. The figure below shows the points $(x, y)$ with $0 \le x, y \le 5$ with lines from the origin to the visible points.

Write a program which, given a value for the size, $N$, computes the number of visible points $(x, y)$ with $0 \le x, y \le N$.

阅读全文 »