Doubly-sorted Grid

GCJ09 Final Problem C

【简要描述】

       给出一个N*M的方格纸，在方格内可以任意填写字母a到z，但是必须保证，任意一行从左到右字母的字典序必须保证不降，同时任意一列也必须保证字典序不降。

       现在一些格子已经填上了一些字母，现在要求将剩余没有填写的空格子填满，同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。

       Small dataset

              N,M≤4

       Large dataset

              N,M≤10

【分析与算法设计】

       看到这个问题当然最简单的想法就是搜索了。

       不过，注意到每一个格子可以填26种不同的字母，所以简单考虑就可以发现，对于即使单独1*M的方格纸，可能填写的数目也将达到O(26^M)的规模——所以简单的搜索是绝不可行的。

       但是，同时我们也可以注意到，其实我们在进行搜索的时候进行了很多的重复搜索，所以我们需要尝试确立一些搜索的状态来进行记忆化搜索，或者进行递推。

算法1：

       注意到在Small中，虽然总的方案数很多，但是注意到行数和列数都不是很大，因此我们可以尝试进行状态压缩的动态规划。

       沿用状态压缩动态规划的一般方法，我们记录扫描线上的状态进行转移。

       如有图所示，其实我们需要记录的状态仅仅是紫色格子中的字母填写情况，蓝色格子中的已经填写过的字母情况我们其实就不用知道了——通过紫色格子已经可以反映出蓝色格子的字母状况了。

       然后我们只要枚举橘红色格子填写什么字母然后进行状态的转移即可。

       那么考虑紫色扫描线上的点只有O(M)，相应的，状态数即为O(26^M)，这在Small中，是完全可以接受的。

       至于一些格子已经填写了一些字母，我们只需要在转移到具体的格子然后再进行判断即可，算法并没有什么关键的转变。

时间复杂度：O(NM26^M)

空间复杂度：O(NM+26^M)

期望得分：Small通过

       观察到在Large中，虽然N和M仍然不大，仅仅10而已，但是，考虑到26个字母的可能填写方案，显然的，仍和关于字母具体信息的扫描线记录方式都是完全行不通的。

       我们知道，记录一个位置到底是什么字母，就需要花费26的记录代价，这是导致我们无法记录信息的关键问题。

       那么，我们能不能分离这一问题，并不去记录某一个位置是什么字母，而去记录每一种字母到底占了哪些位置呢？

       显然的！

算法2：

       这里我们就需要利用到双调有序这一重要性质了。

如果在格子(x₁,y₁)内的字母比(x₂,y₂)内的字母字典序小，那么则必然有这样的限制条件：x₁≤x₂，y₁≤y₂。

所以，对于字母c₁，以及恰好比其大一个字典序位置的字母c₂，其分界线一定是一个从左下角到右上角的连续折线，并且任意一点只会向上，或者向右：

如右图所示，我们这里标出了字母a，b，c下方的分界线，注意这里字母c所在的格子并不是连通的，所以，字母c的分界线是存在一部分与b的分界线是重合的。

而其实字母d的分界线是完全和字母c重合的。

字母e的分界线就是整个方格的下拐折线。

并且任意字典序大于e的字母的分界线都是与字母e重合的。

我们不妨称这样的一条从左下角到右上角的折线为一条路径。

对于两条路径P₁和P₂，如果满足两条路径不严格相交，并且路径P₁存在一部分严格的处在在P₂的上方，则我们称P₁<P₂，同样的，我们也可以定义P₁≤P₂所需要满足的情况。

比如在上面这个例子中，a的分界线，也就是路径P_a满足P_a<P_b，而P_c=P_d。

容易发现，在一种合法的填写方式中，我们设第k小的字母的分界线为路径P_k，则一定有P_k≤P_k+1——我们惊奇大发现，我们又挖掘出了一种数据之间的有序性，而这也正是由于字母填写的双调有序性导致的！

我们可以发现，这样的从左下角到右上角的分界线一共有种，在Large中，这个数字也不过是184756而已——完全是我们可以接受的状态数量。

于是我们可以基于上述的路径描述的方法，设立动态规划的状态。

我们设f[P][k]表示字母当前填写到路径P上方的所有格子，并且当前路径P是第k小的字母的分界线。

于是我们可以有如下转移：

由于路径总数是O(2^N+M)级别的，每次我们需要枚举上一条分界线在哪里，因此，这样我们就得到了一个复杂度为O(C4^N+M)的动态规划算法。

但是，路径数达到了10⁵级别，如果我们这样暴力枚举分界线，显然是无法通过测试的。那么，我们改如何优化转移呢？

首先，对于状态f[P][k]，如果路径P上方任意格子都不包含第k小的字母，显然这种情况下，可行方案的总数就是f[P][k-1]。

于是现在我们即可以假设在路径P上方一定存在第k小的字母，由于路径P是第k小字母的分界线，也就是说，所有P上方的格子都是用字典序前k 小的字母填充的，而又由于存在第k小的字母，因此其一定有一些位置紧邻路径P。

那么是哪些位置呢？

观察右图中黄色的路径。不妨设其为我们之前讨论的路径P，如果路径上方仅适用前k小的字母并且至少使用了一个第k小的字母，则我们用橘红色颜色标出的这些下凸的格子中，至少存在一个格子其中填写的字母是第k小的字母。

那么到底是哪一个呢？填写了几个格子呢？我们并不知道。不过我们可以通过枚举来确定：情况1，格子A中填写了；情况2，格子A和格子B中填写了……等等，对于格子A中填写的情况中，已经包含了格子A和格子B都填写了第k小字母的情况，可见，我们的枚举使得总的方案数的计数出现了重复！

如何提出重复呢？容斥原理！

因此，转移的时候，对于状态f[P][k]，我们首先找图上图中橘红色的可行拐点，然后对于这些拐点可能的情况进行枚举，并利用容斥原理进行计算。

容易发现，由于任意一条路径上拐角数量是不超过O(M)的，因此，容斥的计算复杂度为O(2^M)——并且其实是远远达不到这个数量的。

至于已经填写的一些格子，仍然是只需要在转移的时候进行特判即可。

至此，Large也被我们解决。

时间复杂度：O(C2^N+M+M)

空间复杂度：O(2^N+M)

期望得分： Large通过

       其实，算法2还可以进行一些优化得到更好的时间复杂度。

算法3：

       可以发现，容斥原理将我们的转移变得很慢，而实际上，我们也的确做了一些重复的容斥——很多时候反复的容斥原理都是可以加速的，这里也是一样的。

       我们将状态稍作修改：

       f[P][c][k]表示当前利用前c个字母填写了路径P以上的所有格子，并且第c小的字母全部位于前k列中。

       这样，我们在转移的时候，只需要枚举第k列是否存在第c小的字母就可以了——我们将容斥的复杂度转移到了状态上，并且将其大大降低。

       这样一来，虽然我们使得状态数增加到了O(CM2^N+M)，但是却使得决策复杂度降低到了O(1)——其实从本质上来说，这就是进行了一个容斥原理的加速。

时间复杂度：O(CM2^N+M)

空间复杂度：O(M2^N+M)

期望得分：Large通过

【实现与细节】

       我们首先来说一下关于路径的表示问题。

       对于一条从左下角出发的路径，我们可以认为其存在N+M个拐点，每一个拐点其要么向上，要么向右，并且其中恰好向上N次。

       这其实和2进制形成了一个一一对应：向上对应2进制中的0，向右对应2进制中的1，那么，我们之前在容斥中所描述的下凸点，其实就对应二进制位中的10。

       这样的2进制表示其实和路径的组合意义也是对应的——因为有N+M个2进制位，要保证恰好M个1，其方案总数就是。

       而且，我们可以利用2进制将所有路径和一个整数对应起来，不妨设路径P所对应的2进制整数表示为ID(P)，则容易发现，如果P₁<P₂，则一定有ID(P₁)<ID(P₂)（这里在2进制中我们也从左往右依次表示从左下角到右上角的各个拐点的前进方向），这样的好处在于，我们将路径的序与整数的序相联系起来（注意，这种对应是不可逆的），所以我们在进行动态规划的转移过程中，只要按照整数的序来进行即可——同样对于路径的记录和转移时路径的修改也可以利用数组和位运算来大大简化我们程序的书写并加快程序运行速度。

      

       详细请参加C.cpp。

【小结】

       这道题我们从一个完全不同的角度对动态规划的状态设立与序的应用进行了分析，并且得出了一种全新的思考问题的角度。同时也对容斥原理进行了应用和优化，非常具有启发意义。

 

第二篇：NOIP20xx解题报告

全国青少年信息学奥林匹克竞赛条例

由 III\huangweizu 于 2008-7-11 20:29 创建

上次修改时间: 2008-7-11 20:29 ，修改者: III\huangweizu

第一章 总则

1. 全国青少年信息学奥林匹克竞赛(National Olympiad in

Informatics, （20xx年4月14日印发）NOI)是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。

竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。

2.NOI及其系列活动由中国科学技术协会主管，中国计算机学会主办。

3.NOI系列活动包括：

1) 全国青少年信息学奥林匹克竞赛（简称信息学奥赛）。以省（包括自治区、直辖市，下同）为单位组织参加的全国性比赛，比赛集中在同一地点在同一时间内举行。

2) 全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces, 简称NOIP或联赛)。联赛分普及组和提高组两个组别，分别设初赛和复赛两个阶段。初赛以通用和实用的计算机知识为考试内容，重在考察基础与实用的知识，以笔试为主。复赛为程序设计。参加初赛者须达到规定的分数线后才有资格参加复赛。参加NOI的各省都应参加联赛，参加联赛是参加NOI的必要条件。

3) 全国青少年信息学奥林匹克竞赛冬令营(NOI冬令营，简称冬令营)。在每年的冬季假期开展的为期一周的培训活动。

4) 国际信息学奥林匹克竞赛(International Olympiad in Informatics, 简称IOI)中国队选拔赛(IOI选拔赛，简称选拔赛)。为参加当年举行的IOI而进行的选拔赛。

5) 参加国际信息学奥林匹克竞赛。由中国计算机学会组织代表队代表中国参加每年一次的国际竞赛IOI。

6) 各省组织的培训和竞赛活动以及主办单位组织的培训活动。

第二章 竞赛的组织

1、NOI及其系列活动由主办单位委托各省与有关单位共同承办，主办单位也可直接组织竞赛。

2.办单位负责经费的筹措、竞赛用设备的准备以及与活动相关的组织工作。任何参赛的省都有义务和权利承办NOI和冬令营。

3.加竞赛的各组队单位负责组织当地的联赛、组队参加NOI、参加冬令营和选拔赛，负责当地青少年的普及和培训。

4.竞赛组织机构及人员：

1)竞赛委员会(Competition Committee，简称CC)：代表主办单位负责竞赛组织工作的机构。竞赛委员会设主席1人，副主席1人，常务委员和委员若干。关于竞赛委员会的构成和职责见《NOI竞赛委员会条例》。

2)科学委员会(Scientific Committee，简称SC)：中国计算机学会下设的负责竞赛技术工作的机构，负责竞赛的命题、评测、选拔、培训、带领选手出国参赛等技术工作。科学委员会是NOI的最高学术和技术机构。科学委员会由来自高校的资深的计算机专家组成，专家由中国计算机学会聘任，以自愿者的身份参加工作。各省的计算机专家如条件合适，可以自己提出申请，

经审批通过后可被聘为通信委员。大学生或研究生可被聘为学生委员。NOI承办单位当年派2人任科学委员会委员，协助科学委员会完成部分技术工作。科学委员会的构成和工作程序见《NOI科学委员会工作条例》。

3)技术委员会(Technical Committee，简称TC)：NOI竞赛期间负责竞赛的技术工作，包括竞赛设备、网络、支持环境等。技术委员会由承办单位派员组成。

4)领队(Delegation Leader)：参赛队的负责人，每队一人。领队除负责本队选手的竞赛事宜外，还担任竞赛期间参赛队员的监护人。

5)选手(Contestant)：参加竞赛的队员，分规定选手和奖励选手。规定选手是指按照法定名额参加竞赛的选手；奖励选手是指根据奖励规则追加的参赛选手。

6)观察员(Observer)：随队参赛的人员，包括教师、学生、特派员、省级奥赛组织者以及对竞赛有兴趣者。

7)观摩队(Observation Delegation)：由第二年或第三年将承办竞赛的单位派出的观摩人员。

8)特派员：由省组织单位推荐、主办单位聘任的负责省竞赛组织工作的人员。特派员职责见《NOI特派员条例》

9)省级奥赛组织委员会：省一级为组织奥林匹克竞赛而设立的组织机构，该机构通常由省级科协、省计算机学会和（或）省级教育行政机构联合组成。该机构必须向主办单位备案。

第三章 全国青少年信息学奥林匹克竞赛(NOI)

1. NOI是全国青少年信息学奥林匹克最高水平的比赛，每年举行一次，以省为单位派队参加。这一竞赛记个人成绩，同时记团体总分。

2. NOI安排在每年暑期进行。竞赛日期经主办单位确认后，提前一年公

布。

3. NOI各参赛队领队和选手报名表寄送的截止日期为竞赛前40天（以邮戳为准）。领队和选手报名表须有省组队单位盖章和特派员签字方为有效。

4. 每队由1名领队和不超过5名规定选手组成，其中，男选手不超过4名。如有得到奖励名额，则有奖励选手1名。

5. NOI承办单位所在省在竞赛当年可另得到5个奖励名额。如NOI承办单位(或举办地)是中学，除其参加省队选拔外，可获得上述5个奖励名额中的3个。

6. 选手必须为当年在校学生（不含当年暑假高三毕业生，港澳可参照当地学制自定），年龄上限为19岁（以6月30日为截止日期计算）。注册时领队必须向竞赛委员会交付选手身份证或户口簿复印件，并在上面签名。竞赛委员会负责资格的确认。不符合竞赛条件的选手将被取消竞赛资格。

7. 参赛选手必须是省内按照选拔程序选拔产生的（承办学校奖励名额除外）。不经选拔而由组队单位指定的选手没有参赛资格。各省选拔程序须报主办单位备案。

8. 团体总分前三名、联赛参赛人数最多的前五名的代表队奖励1名参赛选手，参加下届NOI。当团体前三名与联赛参赛人数前五名重选时，不重复计名，即每队至多有一名奖励选手。奖励选手只计个人成绩，其成绩不计入团体总分。

9. 竞赛的题目由NOI科学委员会确定。

10. 奖项的设定：

1）一等奖的人数为20名，二等奖占参赛总人数的20%，三等奖为30%，其余为优秀奖。

2）竞赛设最佳女选手奖1名。

3）根据各队规定选手的总分评定出团体总分前8名。

11. 竞赛实行七天赛制，即：到达日、开幕日、第一次竞赛日、交流参观日、第二次竞赛日、闭幕日、返回日。

12. 竞赛时间为竞赛日的8:00-13:00；评测时间为13:30-15:00；自我复评和投诉时间从15:30开始。

13. 每个竞赛日有3个赛题，每题100分，笔试题为100分，竞赛个人总分为700分。

14. 交流和参观是NOI的重要组成部分，每一位NOI参加者必须参加由承办单位安排的交流项目。交流项目可安排在交流参观日、开幕日和闭幕日。未经主办单位批准不参加活动的选手，将每次扣分100分。

15. 第二个竞赛日结束后，由科学委员会安排竞赛题目的讲评。

16. 观察员和观摩队可参加NOI。观摩队的人数为2-3人。观察员人数由承办单位根据其接待能力确定。

17. 网上同步赛（NOI by the Internet）。

1）NOI竞赛的同时，组织网上同步比赛，旨在给那些不能到现场参加竞赛的选手提供机会。任何符合参赛条件的青少年都可以报名参加同步赛。同步赛为非正式的比赛。

2）网上同步赛的承办单位为NOI的承办单位或主办单位委托的其他单位。

3）网上同步赛在NOI比赛开始半小时后开始，比赛用时与正式比赛相同。

4）参加同步赛的选手必须交纳一定的费用。

5）同步赛的评分标准同NOI。同步赛的获奖选手由主办单位颁发证书。

第四章 全国青少年信息学奥林匹克联赛(NOIP)

1. 全国青少年信息学奥林匹克联赛是在同一时间段内、在不同地点以省为单位组织的全国性的比赛。NOIP是NOI的基础。初高中或其他中等专业学校

的学生可报名参加联赛。

2. 每年10月份的第三个星期六下午举行初赛， 11月的第三个星期六举行复赛。该年的联赛称之为NOIn联赛，以NOIPn表示，其中n为年份。

3. 参赛者均须交纳一定的费用，费用的数额由主办单位根据竞赛组织成本核定。

4. 联赛的出题范围、竞赛形式及评分标准等由科学委员会制定的联赛大纲确定。

5. 联赛分初赛和复赛。联赛以省为赛区。每个赛区可设若干考场。

6. 联赛的初赛为书面答题，复赛为上机编程，试卷由主办单位统一印制。

7. 关于NOIP的具体规定，见《全国青少年信息学奥林匹克联赛组织指南》。

第五章 NOI冬令营

1. 每年的1月初举办NOI冬令营。冬令营共8天，第一天为到达日，6天为培训和交流，最后一天为返回日。

2. 获得NOI一等奖的20名选手可参加函授培训并作为正式营员参加冬令营，其指导教师1名有资格作为正式营员参加冬令营，承办单位可另外派6名教师或学生作为正式营员。

3. 冬令营培训内容包括授课、讲座、讨论、测试等。参加IOI中国队选拔赛队员的成绩将作为选拔赛成绩的一部分记入档案（见第六章）。

4. 在保证教学质量和条件许可的前提下，可适度增加非正式营员。每个代表队可派教练1人作为非正式营员（如已有教练作为正式营员，则不再有该名额）；其他非正式营员的资格和数量由主办单位确定。非正式营员参加冬令营属自愿。

5. 参加冬令营的正式营员和非正式营员都必须交纳费用，费用包括注

册费、听课费、资料费、食宿费等。交通费自理。非正式营员的收费比正式营员高，收费数额根据每年不同情况在报名前确定。

6. 欠发达省份可为其非正式营员教练1名申请优惠付费，经主办单位批准后可按正式营员标准交费。

7. 冬令营的技术工作由NOI科学委员会负责，报名和联络工作由主办单位负责，后勤和组织工作由承办单位负责。

关于冬令营的具体规定，见《冬令营组织指南》。

第六章 IOI中国队选拔赛和参加IOI

1. 选拔参加当年IOI的中国选手。获上届NOI一等奖的20名选手入选国家集训队，获得参加次年国际信息学奥林匹克竞赛(IOI)中国队选拔赛的资格，其中4名优胜者将代表中国参加IOI。

2. 已获得IOI金牌的选手次年不再入选国家队。集训队员如有缺额，依次替补。

3. IOI中国队队员的选拔赛在NOI科学委员会的主持下于每年5月初进行。

4. 参加选拔的选手及其指导教师的食、宿、行由参赛单位或选手承担，并交纳参赛费。

5. 选拔分两试，均为程序设计。竞赛时间为竞赛日的8:00-13:00

6. 选手总分为：1）冬令营成绩(满分100分)、2）平时成绩(满分100分)、3）论文成绩(满分100分)和4）选拔赛成绩(满分100分)加权之和(见下式)：

总分=冬令营成绩×25% + 平时成绩×5% + 论文成绩×10% + 选拔赛成绩×60%

上述四项成绩计算方法如下：选手得分和本次竞赛最高分之比乘以100

（本次竞赛得分/本次竞赛最高分×100）。

上述公式中的前三项成绩由科学委员会在选拔赛前公布。

1. 获总分前6名者参加面试，面试满分为10分。其中：表达能力3分，反应速度4分，仪态1分，其他2分。一个选手面试的得分为所有参加评分的科学委员会委员评分的平均值。科学委员会根据选手的总分和面试得分之和选出出国参赛选手。

2. 获选的4名选手将在出国参赛前进行一周的集中训练。训练期间所需费用由主办单位承担，往返旅费由选手所在单位承担。

3. 获选的选手代表中国参加当年的IOI，如其中的选手因突发事件不能参赛时，由科学委员会决定是否补缺。

4. 中国代表队一般由领队1人、副领队1人和4名选手组成。必要时可派遣观察员。

5. 出国参赛的经费由中国科协专项经费支持。

6. 中国代表队回国后，领队和参赛选手必须写出参赛总结，回国后10天内交派队单位，代表队总结还要按规定上报中国科协。

第七章 命题、保密与约束条款

1. NOI及 其系列活动的命题工作实行开放性原则，任何人都可向科学委员会提供未曾使用过的题目。题目一经科学委员会录用并纳入题库，主办单位将为出题人颁发录用证明并支付命题酬金，而出题人则不具有对题目的所有权，两年之内不得以任何形式继续使用该题，并有义务保密。录用后的题目的所有权属于主办单位，主办单位对录用的题目可以全权处置。

2. NOI命题工作由科学委员会负责，竞赛前五个月启动该工作。

3. 竞赛前一个月，完成所有工作，并开始全面审定题目。

4. 科学委员会应在竞赛前一周完成下述工作，并在比赛结束后，将下

面所列内容发给每一位注册参加者。

1）题目描述。对题目的完整描述，并附有输入输出样例。

2）测试数据。对选手编制程序进行正确性检测的数据。每个题目的测试数据不应少于10组。

3）标准答案。对应于测试数据的正确答案。

4）题目背景介绍和算法提示。不属于命题基本部分，但有助于选手理解题目背景和相应算法。

5）参考程序。由科学委员会做出，或选定某些选手的程序作为示例。

5. 委员会成员有义务和责任在赛前对题目进行保密。

6. 联赛初赛的题目应以推动信息学在青少年中的普及为出发点。复赛题目的类型与NOI题目类型一致。

7. 题目大纲由科学委员会制定，题目由科学委员会负责征集并负责最终审定。

8. 赛题目的接受、包管、分发等过程的保密规定，按

照《全国青少年信息学奥林匹克联赛组织指南》和中国科协《全国五项学科竞赛条例》的有关规定执行。

9. 冬令营和选拔赛的题目由科学委员会负责。

10. 所有以中国计算机学会名义组织的与信息学奥林匹克竞赛（包括NOI、NOIP、冬令营、IOI选拔赛、培训等活动）有关的题目、说明、题解、测试数据、经当事人授权的答案（包括解题过程和源程序）以及相关资料的所有权属于中国计算机学会，授权SC管理和使用。题目解密后可用于教学等非商业性活动。未经CCF同意和授权，任何组织和个人不得以任何形式自行出版和传播，或以任何形式谋取商业利益。如结集出版，应纳入信息学奥林匹克丛书出版系列并以中国计算机学会的名义出版，或和出版机构合作出版，主编或编者可以署个人姓名。

第八章 成绩评定和认定

1. NOI评测只检查按照要求输出的结果，不涉及过程和算法。

2. NOI获奖人数的比例由NOI一章给出。

3. NOI评测由科学委员会负责，由该委员会主席签发最终成绩。

4. NOIP各省赛区提高组复赛一等奖获奖人数由如下的公式得出：

（1）所有获奖选手必须满足最低分数线。最低分数线由科学委员会和竞赛委员会于竞赛结束后给出。

（2）省参加初赛人数在2000人内（含），该省获奖（基本）名额b为参加NOIP初赛选手人数p的1%（四舍五入）；省参加初赛人数p在2000人以上时，根据全国未分配的得奖名额与（p-2000）各省之和之比得出单位选手应得获奖名额k，则该 省获奖名额为b+（p-2000）×k（四舍五入）。

（3）一个省的获奖人数最多不超过50人。一个省参赛人数不足500人时，可获得5个名额。

（4）高中阶段已获得NOI一、二、三等奖及已获得NOIP一等奖的选手，不占本届联赛所在省赛区一等奖名额。

5. 普及组复赛一等奖只设最低分数线，不限制得奖名额。奖项的评定由省赛区负责，结果报送主办单位备案。

6. NOI一、二、三等奖以及NOIP提高组复赛一等奖获得者名单将由中国计算机学会报送中国科协，由中国科协审核后送教育部备案。

7. NOIP提高组复赛一等奖由中国计算机学会确定，其他单位和个人确定NOIP一等奖获得者无效。

8. NOIP各赛区上报一等奖候选名单由赛区组织单位盖章，并由该赛区特派员签字。

9. 获NOIP二等奖人数的比例不超过参加复赛人数的20%，且满足科学

委员会给定的最低分数线。根据上述两项条件，由省赛区认定，并报主办单位备案。

10. NOI的获奖证书由主管单位中国科协青少年部和中国计算机学会共同颁发，NOIP一等奖由中国计算机学会颁发，NOIP提高组复赛二等奖及其他奖项由省级组织单位颁发。NOI和NOIP证书由中国科协统一制作，NOIP二等奖证书由中国计算机学会统一印制。

11. 主办单位在NOI网站（）公布获奖名单和成绩，接受相关教育、科研机构及社会各界对上述成绩的查询。

第九章 监督与惩罚

1. 中国计算机学会的工作由中国科协监督。

2. NOIP特派员的工作由中国计算机学会监督。

3. 特派员对联赛的事务负责并全权监督所负责赛区的各分赛区。

4. 发现某个人或组织单位有违规行为，任何与竞赛有关的个人与单位都有权向违规人或该单位的上一级机关投诉。

5. 竞赛中选手的舞弊行为、实施监考的工作人员和特

派员的失职行为，要视情形给以惩罚。

6. 选手舞弊行为是指，在选手独立解题竞赛时：

1）将不允许夹带的物品带入考场并经指出后不予改正；

2）在考场从其他人那里获得与竞赛有关的信息或为其他选手提供与竞赛有关的信息；

3）用各种途径和介质将答案带入考场；

4）提前得到竞赛的题目；

5)不遵守赛场规定并可能影响公平竞赛的其他行为。

7. 赛场工作人员的失职行为是指，在选手独立解题竞赛时：

1）发现选手有舞弊行为而不予制止；

2）非法为选手提供与竞赛有关的信息；

3）将竞赛题目提前泄漏给选手；

4）更改选手的竞赛结果。

8. 特派员的失职行为是指，在选手独立解题竞赛时：

1）发现选手有舞弊行为而不按规定惩罚；

2）发现赛场工作人员有不规范行为而继续聘用；

3）提前将竞赛题目泄漏给选手；

4）没有按规定上报竞赛结果；

5）更改选手的竞赛结果。

9. 在联赛初赛中发现选手有舞弊行为，取消该选手当年成绩，并禁赛两年。

10. 在联赛复赛中发现选手有舞弊行为，立刻取消该选手参加联赛及NOI的资格，并禁赛两年。

11. 在联赛初赛和复赛中监考教师纵容舞弊行为或发现舞弊行为不予制止，视为失职。从当年算起三年内不得从事与NOI相关的工作。

12.在联赛初赛和复赛中特派员已发现舞弊行为但不予处罚，视为失职，主办单位将撤消其特派员资格。

13. 在NOI中发现选手有舞弊行为，取消该选手从当年算起参加NOI任何竞赛的资格，并禁赛两年。

14. 科学委员会委员如有泄密，取消其委员资格。

15. 上述舞弊行为均由主办单位记录在案。

16. 受理投诉的单位必须为投诉人保密。

17. 被处罚方可向主办单位或其上一级单位申诉。主管单位为最终裁决单位。

18. 对主办单位及当事人的处罚由主管单位制定。

第十章 经费和赞助

1. 主办单位的部分资金来自中国科协和国家自然科学基金委，这些经费主要用于竞赛的组织和联络、培训、宣传、出国选拔、出国参赛、资助经济条件差的组队单位和参赛选手等。

2. 主办单位的其他经费主要通过赞助单位赞助以及选手的参赛费获得。

3. NOI承办单位的经费来源有：承办单位的投入、赞助费、参赛代表及观察员的注册费等。

4. 联赛的经费来源于赞助费、参赛选手的参赛费等。

5. NOI冬令营的经费来源于营员的培训费和可能的赞助费。

6. 参赛选手须交纳参赛费用，这些费用用于组织机构竞赛的组织、赛场、竞赛设备、试卷、证书等。组织机构向选手收费应不以营利为目的。收费的数额不应与当地行政部门的有关收费规定相抵触，并且须经过主办单位批准。

7. 参加NOI的规定选手、奖励选手、领队和观摩队（不超过3名）人员参赛的注册费为每人800元，观察员的费用由承办单位根据成本核定。选手的注册费由其所在学校承担或由组队单位解决，也可根据情况由选手自行解决。领队的注册费由组队单位解决。

8. 交费有困难的选手和参赛队可以按照程序向主办单位以书面形式（填写申请表）提出减免注册费的申请，主办单位根据申请者所在地生活标准和家庭人均收入核定是否可以减免。减免费用由主办单位承担。

9. NOI、冬令营、联赛及中国队选拔赛均可以某赞助机构名称冠名。如前二项冠名由承办单位征得，则赞助经费三分之二归承办单位，三分之一归

主办单位，否则主办方承办方各得二分之一。以省为单位组织的有关活动的赞助经费完全由该组织单位支配。

10. NOI经费由主办单位负责管理和使用。

第十一章 竞赛的申办

1. 任何一个参赛队所在的省都有义务和资格申请承办NOI。

2. 申请承办须在举办年的两年前不晚于5月31日向主办单位以书面方式提出。

3.承办报告包括申请报告、承办条件和承办方案。

4.承办单位的选定考虑组织能力和财政支持，此外还要考虑承办地的分布。在同等条件下，没有承办过NOI的省比承办过NOI的省有更大的优先权。

5.主办单位在收到正式的申请报告后，将组织考察团对申办单位进行考察，然后根据承办条件和其他方面的因素选定承办单位。承办单位选定后，在NOI闭幕式上宣布。

6. 获得承办权的单位在签署承诺书的同时要交付主办单位保证金，如能如期举行，该保证金如数退还；如承办单位违约，则保证金不退。此外，主办单位保留对其进行惩罚的权利。

7. 获得NOI某年的承办权即自动获得该年NOI冬令营的承办权。如承办单位放弃冬令营承办权，其他单位可提出承办申请，由主办单位选定。

第十二章 附则

1. 本条例由主办单位主持制定，并根据情况的变化进行适时的修改。

2. 本条例的制定或修改应征求各省赛区组织及相关单位的意见。

3. 本条例须经中国科学技术协会青少年部批准后生效。

4. 本条例修改后并获批准后的下次活动即付实施。

5. 各省可根据本条例自行制定实施细则，但不得与中国科协的规定和本条例规定相冲突。

6. 本条例由中国计算机学会负责解释。

注：

20xx年11月7日起草

20xx年11月28日由科学委员会审定

20xx年12月1日－20xx年1月31日征求各省赛区及相关单位意见

20xx年5月23日中国科学技术协会青少年部批准实施

20xx年6月25日科学委员会修订

20xx年6月27-7月26日征求各省赛区及相关单位意见

20xx年7月15日科学委员会修订

20xx年6月23日竞赛委员会修订，NOI2005期间特派员会议征求意见

025239.aspx