Articles tagged as

  1. OI最后的谢幕·18岁新的开始

    OI

    NOIP结束的那天一回到家,我就先把QQ上“巨菜逆铭”的头像和“我巨菜”的个人说明去掉,然后把blog里“OI之路”的文章分类改成了“OI往事”。是啊,退役了,不再是一个OIer了,无论是菜是牛都已成往事。这个谢幕也许并不完美,但是我无愧于心。

    从去年NOIP06前夕到现在,一年多一点,就是我全部的OI之旅了。虽然非常羡慕那些强省的OIer可以很早就了解到OI之美,然而从NOIP06启航,到在WC里瞻仰群牛大开眼界,然后在省选时置于死地后又峰回路转,接着是NOI由于水平不足加之准备策略失误导致的惨败,最后是NOIP07并不完美的结局,我经历了一个OI巨菜所能期望经历的一切。有过泪水,有过欢笑,有过初涉OI时的无知无畏,也有过面对大牛时的相形见绌。这短暂却充实的一年因为经历丰富而显得格外漫长,而曾经的那一幕幕却仍如在昨日。我甚至还清楚地记得今年过年那天,我一个人呆在房子里,不顾隔壁的喧嚣,计算USACO里那道The Clocks的搜索树节点个数。那时候还是我刚刚入门、OI热情最高涨的时候啊,每次深夜关掉电脑从思考中回过神来都恍若隔世。

    的确,每个OIer对于自己的OI之路都会有很深刻的记忆。我会一直记得USACO那些诡异的奶牛们和“Your Program Works The First Time”时的惊喜,记得Vijos刷出五六页Waiting时的万分焦急,记得20分钟啪啪啪拍出一套完整SBT后小小的得意,记得几个小时都过不了一道搜索时的郁闷,记得深夜里面对显示器又涩又痒的眼睛,记得大赛之前自己砰砰乱跳的心。短短一年的OI之路,曾经阳光明媚,也曾经曲折泥泞,不管怎么说,我跌跌撞撞地一直走了下来,我不曾后悔。

    OI在每个OIer心中都已不仅仅是一项学科竞赛。即使不像Ghost说的达到“信仰”的高度,也是一种信念、一种精神。还有哪科竞赛会使我们收获全国范围内的真挚友谊?还有哪科竞赛会让我们在大年三十仍在群里一边开玩笑一边讨论算法?还有哪科竞赛会让我们在网上自发组织这么多自己出题(M67牛说这些题比NOIP07题的水平高多了)的模拟赛,甚至用举办模拟赛的方法庆祝七夕、庆祝光棍节、过生日甚至见证爱情?OIer是所有搞竞赛的学生中最另类的一些,OI也是唯一与高考科目无关的竞赛。我们因此也面对了更多的困难,经受着更大的考验,然而OI承载着OIer们的梦想,OIer们也为此付出了太多太多。

    我曾经很多次感叹,我学到的越多就越清楚地意识到自己的无知。这确实是实话。OI和演讲比赛不同,我不需要刻意掩藏自己的胆怯,强做出一副自信满满、天不怕地不怕的样子。看到很多初中的小朋友就比自己强出很多,很羡慕他们的环境,而那种挫败感也是很难避免的。况且每天上网和那些不把北大清华当回事的大牛们待在一起,不生出些自卑情绪都难。但和他们在一起我也学会了很多东西,自己水平也有不少长进,生活也充实不少。我想起前一段时间自己在Vijos的签名:“我是巨菜,但我在尽我所能快速成长。”这话看着真提气。

    那些读不完的OI书

    每个OIer无论是牛是菜,在成长过程中都会得到很多无私的帮助,因而在退役的时候也会有一大堆要感谢的人。下面我也要列出一个名单,向帮助过我的人表达我的谢意。谢谢你们,如果没有你们,也许我根本不会走完这条并没有多长的OI之路。

    首先要感谢我师傅大漠。师傅在OI方面也许没有我后来遇到的很多冲金夺银的大牛那么牛,但是在我OI之路开始于NOIP06迷茫无助之时,是师傅给我提供了最真诚热情的帮助,教给了我很多东西。正所谓 “师傅领进门”,对此我至今仍心存感激。

    然后不能不提的就是我们甘肃大水牛Ghost~~他几乎是对我乃至这两届很多GSOIer的OI生涯影响最大的人了。无论是OI还是数学还是保送问题,我都缠着问他,还有很多重要的决定,都曾向他征求意见。Ghost人非常好,非常乐意帮助我们这些菜,也算是少数几个我不叫“大牛”的大牛了,即使叫也要叫“大水牛”-_-|||……很难想象一个其实有些不善言谈的人在OI方面能这么牛,而且在QQ上能如此口若悬河,尽妖孽之所极……GSOIer的诡异外号几乎都是他起的,还有“21727”、“interrosting”等等笑料。。。能通过OI认识这个鬼牛,也真是一大幸事~

    很幸运遇到了我们的信息老师老赵 ...

  2. [NOIP05] 篝火晚会

    描述

    佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官”。在军训结束的那天晚上,佳佳被命令组织同学们进行篝火晚会。一共有n个同学,编号从1到n。一开始,同学们按照1,2,……,n的顺序坐成一圈,而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序,形成新的一个圈,使之符合同学们的意愿,成为摆在佳佳面前的一大难题。

    佳佳可向同学们下达命令,每一个命令的形式如下:

    (b1, b2,… bm -1, bm)

    这里m的值是由佳佳决定的,每次命令m的值都可以不同。这个命令的作用是移动编号是b1,b2,…… bm –1,bm的这m个同学的位置。要求b1换到b2的位置上,b2换到b3的位置上,……,要求bm换到b1的位置上。

    执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置,那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗?

    输入格式

    输入文件fire.in的第一行是一个整数n(3 <= n <= 50000),表示一共有n个同学。其后n行每行包括两个不同的正整数,以一个空格隔开,分别表示编号是1的同学最希望相邻的两个同学的编号,编号是2的同学最希望相邻的两个同学的编号,……,编号是n的同学最希望相邻的两个同学的编号。

    输出格式

    输出文件fire.out包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望,则输出-1。

    数据规模

    对于30%的数据,n <= 1000;

    对于全部的数据,n <= 50000。

    题解

    至此我就算做完了NOIP05提高组的全部四道题,发现除了第一题外其它题都不水,对于我这样的水平来说很值得一做。过河的状态压缩我想了好久;本题优化方法较过河简单,但也需要动动脑子;至于那个等价表达式则是典型的ws题:思想简单(特值法+用栈求表达式的值),但实现起来却比较繁琐,细节硕多,稍不留神就会出错,我前后一共提交了5次才AC(得到的分数分别是20、30、40、90、100)。还好这些题都是自己独立搞出来的。顺带一提,等价表达式取特值时并不像很多人说的要多个,一个足矣,当然不要取太特殊的,比如取a=1,-2,-3,0这样的就很容易被强数据阴掉,但要是取个a=-5.65742它不就没治了;同时B4数据中括号不匹配的情况。

    当然这都是题外话,下面言归正传。

    首先需要看到的是,虽然佳佳下达的命令形式很ws,但是在求总代价的时候却完全不需要管它。显然,在佳佳下达完一系列诡异的命令后,最后有几个人离开了原来的位置,这种情况下最小代价就是几(为什么?)。看清了这一点,问题就转化为:要使得所有人满意,最少需要让几个人离开原来的位置?

    我们先考虑无解的情况。把每个人看成无向图中的节点,两人相邻则连一条边。当n个人以某种次序围坐成一个圈的时候,每个节点的度一定都是2。而这种状态一定是初始状态通过若干次次序调整能达到的,即一定有解。那么无解的情况就一定是,根据同学们的希望构图后有同学的度不为2。这样,我们只需要构图,然后看是否所有节点的度都为2就可以判断是否有解了。

    如果有解,下面就需要计算最小代价了。对于我们构得的图,DFS(1)后一定得到唯一的一个序列。例如1,5,3,2,4。我们现在就需要比较它和初始状态1,2,3,4,5,看有几个人离开了原来的位置。但这个序列实际代表的是一个环,而且方向正反有两种(即1,3,5,2,4和4,2,5,3,1应该是等价的),我们就需要把初始序列正反分别“转”N次(即1,2,3,4,5; 5,1,2,3,4; 4,5,1,2,3; 3,4,5,1,2; 2,3,4,5,1 以及 5,4,3,2,1; 1,5,4,3,2; 2 ...

  3. [NOIP05] 过河

    描述

    在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

    题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

    输入格式

    输入文件river.in的第一行有一个正整数L(1 <= L <=10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。

    输出格式

    输出文件river.out只包括一个整数,表示青蛙过河最少需要踩到的石子数。

    数据规模

    对于30%的数据,L <= 10000;

    对于全部的数据,L <= 10^9。

    题解

    一看题,这无后效性和最优子结构也太明显了,随手就可以列出转移方程。令dp[i]表示处于i位置时,最少还要踩到几个石子(包括当前点)才能到达对岸。bridge[i]为点i处的石子个数(0或1)。则

    当0≤i<L时:dp[i] = min{dp[i+j]} + bridge[i] (S≤j≤T)

    当i≥L时:dp[i]=0

    问题的解即为dp[0]。

    但是这样写完交上去最多只能得30分。直接硬搞,复杂度是O(L*(T-S))的,T-S最大为9,无关紧要,但是L的最大值则是令人发指的10^9(青蛙跳这么长距离不累死么 – -),不TLE……恐怕需要10年以后的CPU了。那怎么办呢?(思考过程也许比较繁琐,要结论请直接看倒数第5段)

    数据范围往往是算法选择的最重要的提示。我们看到虽然L这么巨大,但是石子的总数却不超过100个。这说明什么?说明桥上必然有大段大段的无石子区间,而无石子区间的最大长度在极限情况下将接近10^9。即在跳跃中,青蛙经常会很郁闷地在巨长的无石子区间上跳啊跳啊,想踩个石子都踩不到。上面那个普通dp肯定会导致空白区间上大量的无必要决策而无谓耗费大量时间。要减少这种时间浪费,我们可以试图把大段的无石子区间等效转化为较短的无石子区间,从而使时间开销降至可承受范围。

    首先考虑最简单的情况:S=T。这种情况下,这个诡异的青蛙只能跳固定的长度。而跳的起点是0位置,那么青蛙经过的就只有S(或者说T,一回事)的整数倍点。如果石子的位置为S的整数倍,那么青蛙就一定会踩到,否则一定踩不到。比如S=T=3,L=100,那么青蛙经过的点就为且仅为0,3,6,…,96,99。在21、27、33、66等处的石子就一定能踩到,而20、40、80、92等处的石子就踩不到。于是,当S=T时,我们只需要数位置为S整数倍的石子有几个就得到了答案,不需要进行上面说到的“等效转化”。

    那如果S≠T呢?我们也从一个最简单的例子看起。假如S=5,T=6,青蛙从0位置开始跳,那么它可能到达的点是:

    5,6,

    10,11,12,

    15,16,17,18,

    20,21,22,23,24,

    25,26,27,28,29,30,31,32 ...

  4. [NOIP06] 2^k进制数

    描述

    设r是个2^k 进制数,并满足以下条件:

    (1)r至少是个2位的2^k进制数。

    (2)作为2^k进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。

    (3)将r转换为2进制数q后,则q的总位数不超过w。

    在这里,正整数k(1<=k<=9)和w(k<w<=30000)是事先给定的。

    问:满足上述条件的不同的r共有多少个?

    我们再从另一角度作些解释:设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成),S对应于上述条件(3)中的q。将S从右起划分为若干个长度为k 的段,每段对应一位2k进制的数,如果S至少可分成2段,则S所对应的二进制数又可以转换为上述的2k 进制数r。

    例:设k=3,w=7。则r是个八进制数(23=8)。由于w=7,长度为7的01字符串按3位一段分,可分为3段(即1,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:

    2位数:高位为1:6个(即12,13,14,15,16,17),高位为2:5个,…,高位为6:1个(即67)。共6+5+…+1=21个。

    3位数:高位只能是1,第2位为2:5个(即123,124,125,126,127),第2位为3:4个,…,第2位为6:1个(即167)。共5+4+…+1=15个。

    所以,满足要求的r共有36个。

    输入格式

    输入只有1行,为两个正整数,用一个空格隔开:k W

    输出格式

    输出为1行,是一个正整数,为所求的计算结果,即满足条件的不同的r的个数(用十进制数表示),要求最高位不得为0,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。

    (提示:作为结果的正整数可能很大,但不会超过200位)

    题解

    想起去年NOIP做到这题时,我还是巨巨巨巨巨巨巨菜,看了这题的标题就直接放弃了……现在看来这题也不是那么难的。

    题目中“从另一角度作些解释”是很重要的,这几乎直接给我们提供了算法(往下看之前请仔细阅读题目中的相关部分)。令N为2^k进制数的最大允许位数,(a_0) 为最高位允许的最大值,则有:

    \begin{equation*} N= \left\lceil \frac{W}{K} \right\rceil \end{equation*}
    \begin{equation*} a_0=2^{W \mod K}-1 \end{equation*}

    那么问题其实就等同于:取N个数(对应于\(2^k\)进制数中的N位),第1个数num[1](对应于最高位)取值范围为[1,a0],其余第2~N个数num[i]取值范围都为[1,2^K)。现从其中第i(1<=i<N-1)个数num[i]开始取数,一直取到最后一个数 num[N],要求对于任意的 j>i 满足 num[j-1]<num[j]。问取数方案的总数。这就是很基础的组合数学问题了。

    先不考虑第1个数,因为限制一个最大值会稍微麻烦一点 ...

  5. [VIJOS 1037] 搭建双塔

    描述

    2001年9月11日,一场突发的灾难将纽约世界贸易中心大厦夷为平地,Mr. F曾亲眼目睹了这次灾难。为了纪念“9?11”事件,Mr. F决定自己用水晶来搭建一座双塔。

    Mr. F有N块水晶,每块水晶有一个高度,他想用这N块水晶搭建两座有同样高度的塔,使他们成为一座双塔,Mr. F可以从这N块水晶中任取M(1≤M≤N)块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座双塔,这座双塔的最大高度是多少。所以他来请你帮忙。

    给定水晶的数量N(1≤N≤100)和每块水晶的高度Hi(N块水晶高度的总和不超过2000),你的任务是判断Mr. F能否用这些水晶搭建成一座双塔(两座塔有同样的高度),如果能,则输出所能搭建的双塔的最大高度,否则输出“Impossible”。

    输入格式

    输入的第一行为一个数N,表示水晶的数量。第二行为N个数,第i个数表示第i个水晶的高度。

    输出格式

    输出仅包含一行,如果能搭成一座双塔,则输出双塔的最大高度,否则输出一个字符串“Impossible”。

    题解

    应该说是很简单的dp,但是我没有独立完成……说明我果然是巨菜啊……

    状态表示是我没见过的-_-。。。看了下别人的状态表示,然后就很容易地写出了方程。

    dp(i,j)表示用前i块水晶堆2个塔,两塔间高度差为j时,较低塔的最大高度。

    \begin{equation*} dp(i,j)=\max\{dp(i-1,j+h[i]), dp(i-1,j-h[i])+h[i], dp(i-1,h[i]-j)+j, dp(i-1,j)\} \end{equation*}

    注意处理边界……我还因为边界问题WA了一次,sigh……

    #include <fstream>
    #include <iostream>
    #include <climits>
    #include <cassert>
    using namespace std;
    int N,H[101],dp[101][2001];
    bool flag[101][2001];
    int memo(int i,int j){
        if(j<0) return INT_MIN;
        if(i==0&&j==0)  return 0;
        if(i==0)    return INT_MIN;
        assert(i<=N&&j<=2000);
        if(flag[i][j])  return dp[i][j];
        int ans=INT_MIN;
        if(ans<memo(i-1,j)) ans=memo(i-1,j);//do not put
        if(ans<memo(i-1,j+H[i]))    ans=memo(i-1,j+H[i]);//put on the higher
        if(ans<memo(i-1,j-H[i])+H[i ...

Page 1 / 5