Home > OI > NOIP2010提高组初赛问题求解第三题解答

NOIP2010提高组初赛问题求解第三题解答


题目:记T为一队列,初始时为空,现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是___________。

答案:18

证明:设这些数依次为a1, a2, a3, …, an,且记Si为前i项和,规定S0=0。很明显Si单调递增,且对任意i有0<=Si<=32。

我们可以以Si为顶点构造一张图,两点Si,Sj间连边当且仅当|Si-Sj|=9(图中数字为Si的编号,即i):

0–9–18–27
1–10–19–28
2–11–20–29
3–12–21–30
4–13–22–31
5–14–23–32
6–15–24
7–16–25
8–17–26

我们从这个图中选择一些顶点,将它们的编号排序作为一个可能的序列,比如选择0, 1, 10, 2, 13, 16,

排序后得0, 1, 2, 10, 13, 16,作差得ai依次为

1,1,8,3,3

显然有a2+a3=9 即满足条件

可以发现,若我们选择了图中的两个顶点,且它们之间连边,那么就存在一个和为9的子序列

那么,倘若对于某个n,我们能从图中选择n个顶点,使得任意两点间没有边,那么这个n就是不满足条件的

事实上,我们最多可以选择18个顶点,使得它们之间没有边相连:

第0行~第5行每行可以选第一、三个顶点或第二、四个顶点 最多共选10个

第6行~第8行每行可以选第一、三个顶点 最多选8个

注意到S0=0是必须选的,那么也就是说不满足条件的n的最大值是17

由鸽巢原理,若我们选择18个顶点,必有2个顶点之间有边连接,即必存在一个子序列的和为9

所以答案就是18。

Categories: OI Tags: , , ,
  1. SpadeQueen
    December 7, 2010 at 1:05 pm

    很好的文章啊…但是为什么阁下的博文要翻墙才能看见?

    • December 24, 2010 at 11:54 am

      问GFW吧 WordPress被墙了

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: