现在距离第一届机房病毒杯的举行（2008年11月9日）已经过去了将近一年的时间。我也顺利获得了当年的NOIP一等奖，现在我以文化课作为主要努力方向。
为了更好的造福广大OIer，我决定逐渐公开和整理一些OI资料，于是就从《第一届机房病毒杯NOIP提高组模拟赛》开始吧。因为这是第一届（或许是最后一届？）我自己主办的NOIP比赛，所以具有一定的纪念意义。值得说明的是，当初这届比赛就是为了模拟NOIP，所以难度很低。
[...]
| ||||||
本解题报告版权归 Ceeji 所有，转载请注明出处并保留本注释。 题目描述 老师坐在机房的教师机旁写程序，现在他想到出去接杯水。但是同学们在下面做题，他不想打扰同学们。 可 以把机房理解为一个N*M的方阵，老师或者一个同学占一个方格，当然有的方格是空着的，没有人。机房的出口也占一个方格，每一步都可以从一个方格走到和它 的边或者顶点连接的8个方格（边界处除外），为了不打扰同学们，他希望自己的路线上经过的格子离其他人的最近距离最远。 [...] 本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 问题描述 一棵二叉树可以按照如下规则表示成一个由0、1、2组成的字符序列，我们称之为“二叉树序列S”： 例如，下图所表示的二叉树可以用二叉树序列S=21200110来表示。 你的任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或蓝色。并且，一个节点与其子节点的颜色必须不同，如果该节点有两个子节点，那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列，请求出这棵树中最多和最少有多少个点能够被染成绿色。 输入文件 输入文件名：TRO.IN 输入文件仅有一行，不超过10000个字符，表示一个二叉树序列。 输出文件 输出文件名：TRO.OUT 输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。 样例输入 1122002010 样例输出 5 2 思路分析 本解题报告的版权归 Ceeji 所有，转载请注明并保留本注释。 简单的树形动态规划。这三种颜色是平级的。所谓多少个点能够被染成绿色，其实染成什么色都一样。对于一颗树，分为两种情况考虑：1、父亲染成绿色，则数 量为两个子树不染成绿色的数量之和＋1。2、父亲不染成绿色，则数量为两个子树一个染成绿色，另一个不染成绿色的数量之和的最大值或最小值。 这个题目的建树过程也需要注意。 完整代码 //By Ceeji //Date: 2009-3-12 //HAOI test 2 - Problem 2 //Type: Tree DP //State: Accepted Program tro; Type node=record l,r:longint; end; Var str:ansistring; ch:char; i,j,k,len,n,key,nn:longint; a:array[1..30000]of node; // tree dp:array[1..30000,1..4]of longint; //1: has green 2:not has green b:array[1..30000]of boolean; Function max(i,j:longint):longint; begin if i>j then exit(i) else exit(j); end; Function min(i,j:longint):longint; begin if i<j then exit(i) else exit(j); end; Procedure maketree(j:longint); var c:char; begin c:=str[n]; if c=’0′ then [...] 本解题报告的版权归 Ceeji 所有，转载请注明出处并保留本注释。 题目描述 我们定义连续串为一串整数，它的第一个元素为0，并且任两个相邻元素之差的绝对值为1。更精确的说，如果[a1, a2, …, an]为一个连续串，那么有： 对于任意的1<=ka1=0 任务： 写一个程序： 在文件SUM.IN中读入连续串的长度和连续串中所有元素的和； 找出一个给定长度的连续串，使其所有元素的和与给定的和相等，或者指出这样的连续串不存在。 将结果输出到文件SUM.OUT中。 输入格式： 在文本文件SUM.IN的第一行有一个整数n，满足1n10000，表示连续串中元素的个数。第二行为一个整数S，满足|S|<=50000000，表示连续串中所有元素之和。 输出格式： 如果能够找到满足条件的连续串，你应当在文本文件SUM.OUT的前n行输出n个整数（每行一个），表示连续串中的各个元素（第k个元素输出在第k行）。否则，文件应该只包含一个单词NIE（为波兰语的“否”）。 样例： 输入（SUM.IN）： 8 4 输出（SUM.OUT）： 0 1 2 1 0 -1 0 1 思路分析 本解题报告的版权归 Ceeji 所有，转载请注明出处并保留本注释。 本题采用构造法。时间复杂度O(n)，空间复杂度O(n)。先建立一个从0到n-1的数列，并求出要求的和与数列的和的差值。如果差值为奇数则无解，如 差值为偶数，则逐渐减小差值。比如将最后一位改为降序，则差值减小2，倒数第二位改为降序则差值减小4，以此类推。可以先从前面减，减到很小的时候（不能 再减）再从右面减。所谓减就是把这一位改为上一位减一，而保持后面的升序。 完整代码 //By Ceeji //Date: 2009-4-10 //Type: Gouzao //HAOI test 1 - Problem 1 : sum (POI) //State : Accepted Program sum; Const inf=’sum.in’; ouf=’sum.out’; maxn=10000; Var n,s,i,j,l:longint; x:longint; q:qword; b:array[1..maxn]of boolean; [...] 本解题报告非本人原创，程序为本人原创。转载请注明出处并保留本注释。 题目描述 Polygons 两个做游戏的人在玩一种多边形游戏。一个有n个顶点的凸多边形需要由 n－3条对角线划分成n－2个三角形。这些对角线只会相交在顶点。划分后的三角形中有一个是黑色的，其余的都是白色。两个选手轮流取，每一个选手每一次要从多边形中切下一个三角形。每个选手只允许沿着一条对角线切下一个三角形。切下黑色三角形的选手获得比赛的胜利。 注意：我们称一个多边形是凸多边形当且仅当任意两个顶点的连线都被包含在多边形的内部。 任务：编写程序， 1、从文本文件gra.in中读入关于凸多边形的描述。 2、判断是否先取的选手有一种必胜的策略。 3、将结果写入文件gra.out。 输入： 输入文件gra.in的第一行包含一个整数n，4 <= n <= 50000，表示多边形的顶点数。顶点按顺时针编号为0至n－1。 以下的n－2行描述该多变形划分成的三角形。第i＋1行（1≤i≤n－2）包含三个非负整数，表示第i个三角形的三个顶点的编号。第一个描述的三角形是黑色的。 输出： 输出文件gra.out包含一个单词： ‘TAK’(在波兰文中表示“是”)，如果先走的选手有必胜策略。 ‘NIE’(在波兰文中表示“否”)，如果先走的选手没有必胜策略。 样例输入： 6 0 1 2 2 4 3 4 2 0 0 5 4 样例输出： TAK 《Polygons》解题报告 一、分析。 为了描述方便，我们用三角形的三个顶点的编号来表示三角形，如下图中的黑色三角形为（1，3，6）。 在 下图中，要切下黑色三角形（1，3，6），就必须切下三角形集合{(0,1,6)},{(1,2,3)},{(3,5,6),(3,4,5)}中的两个。 同样，对于任何一个凸多边形，要切下黑色三角形都必须切下三个三角形集合中的两个。切下一个三角形集合所需的步数是一定的，而与切的顺序无关，所以对于任 何一个三角形集合中我们只需考虑集合中三角形的个数而不必考虑分别是哪几个三角形。 设三个三角形集合的元素个数分别为a，b，c。下面的问题就是如何从状态(a,b,c)判断是否有必胜状态。 先分析必胜状态，首先（0,0,1）一定是必胜状态。若初始状态不是（0，0，n）则状态（0,0,c），c>1，实际是不可能出现的。 证明：(1)、状态（0，0，n）不存在。 (2)、若（0，0，c）n>＝c>＝2不存在，由于（0，0，c－1）只能从（0，0，c）和（0，1，c－1）中得到。 状态（0，0，c）不存在，而从（0，1，c－1）出发可以得到比（0，0，c－1）更优的（0，1，c－2），所以不可能选择（0，0，c－1）。 因此，若状态（0，0，（0，0，c－1）也不存在。 所以（0，0，c）,c>1不存在，则（0，0，c－1）也是不存在的。 ∴ 若初始状态不是（0，0，n），则不可能出现（0，0，c），c>1。因此必胜状态只有一个（0，0，1）。 接 着，分析状态（a，b，c），a≠0,令s＝a+b+c，称s为奇数的状态为奇状态，s为偶数的状态为偶状态。由于每一步只能将a，b，c中的一个数减 [...] | ||||||
Copyright © 2012 笃志以砺，决起而飞 - All Rights Reserved. LOVE YOU FOREVER. Powered by WordPress & Atahualpa 36 queries. 0.283 seconds. |
||||||
近期评论