NOIP2012山东提高组成绩

CCF全国信息学奥林匹克联赛（NOIP2012）复赛提高组 day1（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU Intel Core2 Quad Q8200 2.33GHz, 内存2G，上述时限以此配置为准。

4、特别提醒：评测在NOI Linux下进行。

1．Vigenère密码(vigenere.cpp/c/pas)【问题描述】16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密码。

Vigenère密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。

在密码学中，我们称需要加密的信息为明文，用M表示；称加密后的信息为密文，用C表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为k。

在Vigenère密码中，密钥k是一个字母串，k=k1k2…k n。

当明文M=m1m2…m n时，得到的密文C=c1c2…c n，其中c i=m i®k i，运算®的规则如下表所示：®【输入】输入文件名为vigenere.in。

输入共2行。

第一行为一个字符串，表示密钥k，长度不超过100，其中仅包含大小写字母。

第二行为一个字符串，表示经加密后的密文，长度不超过1000，其中仅包含大小写字母。

【输出】输出文件名为vigenere.out。

输出共1行，一个字符串，表示输入密钥和密文所对应的明文。

对于100%的数据，输入的密钥的长度不超过100，输入的密文的长度不超过1000，且都仅包含英文字母。

2．国王游戏(game.cpp/c/pas)【问题描述】恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。

2012年第十八届全国青少年信息学奥林匹克联赛（NOIP 2012）广东赛区成绩公告2012年第十八届全国青少年信息学奥林匹克联赛（NOIP 2012）广东赛区实际参赛人数为2868人（提高组1104人，普及组1764人）, 参赛学校有235所。

本届参赛选手程序全部由全国统一测评，其中提高组一等奖按分配名额划线，结果提高组87名同学（含往年获奖30人，初三6人）获联赛一等奖（A组），提高组81名同学（含往年获奖4人，初三2人）获联赛一等奖（B组）。

获联赛一等奖的高三同学都获保送上大学资格。

今届广东获提高组联赛一等奖A、B组分数线分别高出全国最低分数线90分及20分，获奖人数是全国获奖人数最多的3个省份之一。

表明广东省信息学竞赛不仅普及面而且尖子层人数也在全国前列。

29年的实践表明，GDOI（广东省青少年信息学（计算机）奥林匹克竞赛活动）是培养我们国家、我省计算机优秀后备人才的成功之路。

今年提高组一、二等奖及普及组一、二等奖由全国划定最低分数线及获奖范围，普及组三等奖由省竞赛委员会划定分数线，最后确认：提高组一等奖A组、B组、二等奖分数线分别为315、245、200，普及组一、二、三等奖分数线分别为210、140、110。

今年全国提高组一等奖分数线按初、复参赛人数及平均分计算，各省分数线差别很大，广东各奖项均大幅度地高于全国的最低分数线。

按照广东省信息学竞赛评委会制定的量的评估方法，综合测评省内各校在开展计算机教学和科技活动中取得的成绩，从全省参加复赛的学校中评出成绩优异的前60所学校，其中校团体一等奖10所，二等奖20所，三等奖30所。

在个人奖方面，NOIP2012广东赛区复赛分数线的划定仍按多年来的规则执行，即信息学大型比赛按实际参赛人数的10%、20%、30%的比例划定一、二、三等奖，边界同分同奖的规则。

获奖统计情况如下表所列：其中，提高组获奖人数占复赛（318人）72.96%，普及组获奖人数占复赛（507人）56.02%，全省获奖人数占复赛总人数（825人）62.55%。

NOIP 2012简要题解王赢绪东北师大附中高二二班499167119@2012年11月19日分数分布：Day 1：Problem Contest Current Vigenère密码（vigenere）100 100国王游戏（game）100 100开车旅行（drive）70 100Day 2：Problem Contest Current 同余方程（mod）100 100借教室（classroom）90 100疫情控制（blockade）50 100题解：Day 1：Problem 1 Vigenère密码（vigenere）这是一道模拟题，我的做法的先把密钥都换成大写或者小写。

然后对输入的加密文章进行处理，如果当前对应的密钥位置超过了密钥的总长度，则把当前位置转回1即可，并且注意加密文章的大小写问题。

时间复杂度为O(n+m)，其中n和m分别为两个字符串的长度。

Problem 2国王游戏（game）这道题的主要考察点是高精度乘法除法以及贪心算法的应用。

这是USACO 2007年某次月赛的改编题。

我们不难观察出必存在一种最优的安排方案，是按照每个人左右手两个数的乘积由小到大排序后计算得来，对于乘积相同的我们可以不考虑他们的顺序。

Problem 3开车旅行（drive）这道题我只能想到用平衡树然后倍增维护每个点往前走2的次幂到达哪，以及需要的路程为多少。

具体实现是这样的，我们首先按照站点倒序的顺序进行处理，那么显然每个点离它最近的那个点一定是它高度值的前驱或者后继（如果存在的话），接下来我们考虑每个点的次近点，比如最近点为前驱，那么显然次近点为前驱的前驱或者后继，而如果最近点为后继，则次近点为后继的后继或者前驱。

所以我们可以花O(n log n)的时间处理完成每个点的最近点及次近点。

接下来由于我们已经有了每个点可以到达的最近点及次近点，那么我们可以处理出每个点走2的次幂以后，A走过的路程为多少，B走过的路程为多少，以及此时所在的位置。

CCF全国信息学奥林匹克联赛（NmP2012）复赛提高组day22． 1 ·同余方程〖问题描述〗求关于的同余方程三1 (mod句的最小正整数解。

输入〗输入文件为mod.ino输入只有一行，包含两个正整数用一个空格隔开输出〗输出文件为mod.outo输出只有一行，包含一个正整数№即最小正整数解。

输入数据保证一定有解。

〖输入输出样例〗对于40％的数据，2 L000：对于60％的数据，2 50，000，000：对于100％的数据，2，2，000，000，000。

2 ·借教室 (classroom. cpp/c/pas)问题描述〗在大学期间，经常需要租借教室。

大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。

教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。

共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借dj个教室。

我们假定，租借者对教室的大小、地点没有要求。

即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。

如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。

这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。

现在我们需要知道，是否会有订单无法完全满足。

如果有，需要通知哪一个申请人修改输入〗输入文件为classroom.in第一行包含两个正整数n，m,表示天数和订单的数量。

第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。

接下来有m行，每行包含三个正整数dJ,s]，t]，表示租借的数量，租借开始、结束分别在第几天。

第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

NOIP2012复赛提高组第二天试题（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。

3、全国统一评测时采用的机器配置为：CPU Intel Core2 Quad Q8200 2.33GHz，内存 2G，上述时限以此配置为准。

4、特别提醒：评测在NOI Linux下进行。

1. 同余方程(mod.cpp/c/pas)【问题描述】求关于x的同余方程ax≡ 1 (mod b)的最小正整数解。

【输入】输入文件名为 mod.in。

输入只有一行，包含一个正整数a，b,用一个空格隔开。

【输出】输出文件名为 mod.out。

输出只有一行，包含一个正整数X0，即最小正整数解。

输入数据保证一定有解。

【样例】【数据说明】对于40%的数据，2 ≤b≤1,000；对于60%的数据，2 ≤b≤50,000,000；对于100%的数据，2 ≤a, b≤2,000,000,000。

2．借教室(classroom.cpp/c/pas)【问题描述】在大学期间，经常需要租借教室。

大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。

教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息，其中第i天学校有r i个教室可供租借。

共有m份订单，每份订单用三个正整数描述，分别为d j,s j,t j，表示某租借者需要从第s j天到第t j天租借教室（包括第s j天和第t j天），每天需要租借d j个教室。

我们假定，租借者对教室的大小、地点没有要求。

即对于每份订单，我们只需要每天提供d j个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。

CCF关于CCF NOIP2012奖项评定的公告
CCF召开NOI科学委员会、竞赛委员会会议，对CCF NOIP2012各奖项分数
线进行了划定。

名额计算方法如下：
1、参考初赛人数（30%）、复赛人数（35%）、复赛成绩（35%）。

2、中国科协给定的600个具有保送资格的获奖名额仅向高三选手分配，在各省一等奖分数线之上的高一、高二选手都可获奖。

3、优秀省份（初次划线分数线300分以上）及获奖比例偏低省份适当增加名额。

4、按照CCF规定，在初赛阶段实现网上注册85%以上的省份奖励10%获奖名额。

5、高三选手(未获往届保送资格)将获得中国科协及CCF共同颁发的证书，其余高三（获往届保送资格）、高一、高二选手将获得CCF颁发的证书，初中选手将获得CCF颁发的成绩证明。

全国分数线及名额分配表参见附件。

6、各省组织单位需根据提高组二等奖、普及组一等奖获奖条件，结合本省实际情况，确定本省获奖选手名单，并于12月3日前上报CCF。

此公告。

中国计算机学会
2012年11月28日
附录1：CCF NOIP2012各奖项全国基准分数线
提高组一等奖分数线低于全国基准分数线225分的省份，可根据本省的实际情况，适当调低提高组二等奖的分数线，但需报CCF批准后执行。

附录2：CCF NOIP2012提高组一等奖各省分数线公示
名单按照提高组一等奖最低分数线由高到低次序排列；应届人数指高三且未获往届保送资格的选手人数；。

2012年山东高考各段成绩划分山东2012年高考分数线公布：一本理科582分文科573分山东2012高考分数线：军检线本科文科545分理科535分山东2012高考体育类本科专业文化分数线为：399分山东2012高考艺术类文理两科本科分数线均为300分山东2012年高考分数线公布：一本理科582分文科573分2012山东本科二批分数线公布烟台文516 理515 2012-07-24 20:45 胶东在线【大中小】·孩子考了500分报考什么学校？·上海交大留学桥直通国外"211"名校胶东在线消息，2012年山东省本科二批分数线已经公布：科类文科理科省市省属516515济南496495青岛496495市属496495注：1、东营、烟台、威海、日照、莱芜、聊城执行省属线；淄博、枣庄、潍坊、济宁、泰安、临沂、德州、滨州、菏泽执行市属线。

2、春季高考本科录取控制分数线：种植类380，机电类445，计算机类489，建筑类311，财经类499，商贸类380，餐旅服务类499，幼教类499，医学类401，护理类456，化工类494，煤炭类280。

3、高水平运动员录取控制分数线321。

省二本线公布临沂执行市属线低于省属线20分2012-07-25 10:22:20 来源：鲁南商报作者：浏览次数：58607月24日晚9点，省招考院正式发布山东省2012年普通高校本科二批分数线，其中省属线文科516分，理科515分；济南、青岛两城市执行特殊分数线，在本科二批省属线基础上分别减少20分，为文科496分，理科495分。

临沂仍然执行市属线，文科为496分、理科495分。

临沂文科线、理科线首次“追平”济南、青岛线。

今年，省属线文科比去年提高了4分，理科提高了12分，在招生计划基本与去年持平的前提下，对于分数线提高的原因，相关专家表示，今年的试题难度比去年略有降低，一本分数线文科比去年增加3分，理科增加了15分，二本线的变化在合理的范围之内。