SXKDZ

Blog

  • COCI 2008 Junior 试题及解析

    题目
    Instrukcije
    【题目描述】
    小马克今年成为小学生。不久后她将进行她的第一次考试，其中包括数学考试。她非常认真地复习，她认为自己已经准备好了。她的哥哥通过给她提出问题并解决的方式帮助她。
    他写下许多问题，其中一个问题是由一连串整齐的数字组成，比如1个1，2个2，3个 3 等等。现在他给马克两个整数A和B；她的任务是找出由这两数描述的数列的和（从第A个数到第B个数组成的序列）。如果A是1，B是3，答案为1+2+2=5。
    写一个问题，然后计算它们的和，小马克的哥哥能够验证答案正确与否。
    【输入格式】
    仅一行，包括正整数A和B，1≤A≤B≤1000。
    【输出格式】
    输出和仅显示一行。
    【输入样例】
    [cpp]1 3[/cpp]
    【输出样例】
    [cpp]5[/cpp]

    Lagno
    【题目描述】
    Lagno（西班牙和奥赛罗）是一种二人智力游戏。游戏设有一个黑方和一个白方。游戏桌面是正方形的，包含8行8列。
    如果黑方玩家走出这样一部棋：将一枚黑子放在任一空格上，而在这个空格的八个方向（上、下、左、右和4个对角线方向）的至少一个方向上有一排白子被夹在这枚新下的黑子和其他黑子之间，任何方向，这排被新旧黑子包夹的所有的白子都要变成黑子。为这个游戏设计一个程序，计算一步棋中黑方能转变的白子数量的最大值。
    【输入格式】
    输入有8行，每行8个元素：“.”代表一个空格，“B”代表黑子，“W”代表白子。
    【输出格式】
    输出一步中黑方能吃掉白子的最大数，如果无法吃掉就输出“0”。
    【输入样例】
    [cpp]……..
    ……..
    ……..
    …BW…
    …WB…
    ……..
    ……..
    ……..[/cpp]
    【输出样例】
    [cpp]1[/cpp]

    Pjesma
    【题目描述】
    “Guess the song”是一项在克罗地亚的年轻程序员中非常流行的游戏。它是一种集技能、智慧、耐性于一体的游戏。这个游戏给玩游戏的人放音乐，游戏者的目标是竟可能快地猜这首歌的歌名。
    Mirko可能不是一个很好的程序员，但他是一个世界级的猜歌者。Mirko总是在专辑里的某首歌播放出至少一半歌词的时候猜出歌名。所有歌名的单词是唯一的（没有一个单词会出现一次或更多次）。写一个程序，给出歌名和专辑名，看看Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
    【输入格式】
    第一行：包含一个整数N，1≤N≤50，它是一首歌里的单词数目。N下面的每一行包含歌名的一个单词。
    第二行：包含一个整数M，1≤M≤10 000，它是专辑里的单词数目。M下面的每一行包含专辑里的一个单词。
    歌名和专辑里的所有单词由1到15个小写英文字母组成。
    注：测试数据将会使得Mirko总能从专辑里猜出歌曲名。
    【输出格式】
    输出一个数：Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
    【输入样例】
    [cpp]3
    sedam
    gladnih
    patuljaka
    7
    sedam
    dana
    sedam
    noci
    sedam
    gladnih
    godina[/cpp]
    【输出样例】
    [cpp]6[/cpp]

    Nikola
    【题目描述】
    Nikola现在已经成为一个游戏里的重要人物。这个游戏是由一行N个方格，N个方格用1到N的数字表示。Nikola开始是在1号位置，然后能够跳到其他的位置，Nikola的第一跳必须跳到2号位置。随后的每一跳必须满足两个条件：
    如果是向前跳，必须比前面一跳远一个方格。
    如果是向后跳，必须和前面一跳一样远。
    比如，在第一跳之后（当在2号位置时），Nikola能够跳回1号位置，或者向前跳到4号位置。
    每次他跳入一个位置，Nikola必须付费。Nikola的目标是从一号位置尽可能便宜地跳到N号位置。
    写一个程序，看看Nikola跳到N号位置时最小的花费。
    【输入格式】
    第一行：包含一个整数N，2≤N≤1000，它是位置的编号。
    第2..N+1行：第i+1行表示第i个方格的费用，是一个正整数，绝对不超过500。
    【输出格式】
    输出Nikola跳到N号位置时最小的花费。
    【输入样例】
    [cpp]8
    111
    179
    64
    78
    219
    97
    160
    40[/cpp]
    【输出样例】
    [cpp]535[/cpp]

    解析
    第一题：Instrukcije
    算法：模拟。没什么好说的。
    第二题：Lagno
    算法：枚举。从任意一个点计算到其8个方向上第一个“W”点的距离，即这个点到8个方向上能将黑子变为白字的个数。
    第三题：Nikola
    算法：动态规划。
    状态：f[i][j] 表示当前跳到第i个点，上一步跳了j步的状态。
    初始值：f = Inf, f[1][0] = 0
    答案：Min{f[n]}
    转移方程：f[i][j] = Min{f[i][j], f[i – j][j – 1] + m[i]} = Min{f[i][j], f[i + j][j] + m[i]}
    时间复杂度：O(n^2)
    第四题：Pjesma
    题意：若N个单词在M个单词表中的前i个单词出现的个数大于N的一半，则输出i的值。
    算法：字符串处理。用一个标志数组标记是否匹配过。

    数据和标程
    数据：

    COCI2008普及组数据 (0 downloads )
    。
    标程：
    COCI2008普及组标程 (0 downloads )
    。

    版权
    题目、数据版权为COCI所有，题解、标程版权归Mr.SXKDZ所有，转载请注明出处！

  • NOIp初赛总结——选择题

    计算机基础知识复习

    CPU：包括控制器和运算器。运算器：算术、逻辑（部件：算术逻辑单元、累加器、寄存器组、路径转换器、数据总线）；控制器：复位、使能（部件：计数器、指令寄存器、指令解码器、状态寄存器、时钟发生器、微操作信号发生器）。

    主频：CPU的主频，即CPU内核工作的时钟频率（CPU Clock Speed）。通常所说的某某CPU是多少兆赫的，而这个多少兆赫就是“CPU的主频”。很多人认为CPU的主频就是其运行速度，其实不然。CPU的主频表示在CPU内数字脉冲信号震荡的速度，与CPU实际的运算能力并没有直接关系。

    字长：电脑技术中对CPU在单位时间内能一次处理的二进制数的位数叫字长。所以能处理字长为8位数据的CPU通常就叫8位的CPU。同理32位的CPU就能在单位时间内处理字长为32位的二进制数据。当前的CPU大部分是32位的CPU。

    【例1】关于CPU下面哪些说法是正确的：

    A) CPU全称为中央处理器（或中央处理单元）。

    B) CPU能直接运行机器语言。

    C) CPU最早是由Intel公司发明的。

    D) 同样主频下，32位的CPU比16位的CPU运行速度快一倍。

    【答案】AB

    【解析】C选项中第一个CPU由杰克在1958年研制出人类历史上第一块集成晶体管“微芯片”；D选项中CPU字长不能代表速度。

    【例2】主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（    ）。

    A. 寄存器          B. 高速缓存          C. 闪存          D. 外存

    【答案】B

    图灵机：是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。

    【例3】关于图灵机下面的说法哪个是正确的：

    A) 图灵机是世界上最早的电子计算机。

    B) 由于大量使用磁带操作，图灵机运行速度很慢。

    C) 图灵机只是一个理论上的计算模型。

    D) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

    【答案】C

    【解析】A、B项中图灵机只是理论模型，不是最早的电子计算机，最早的电子计算机是埃尼阿克； D项中是阿兰·图灵本人为破译德军的密码发挥了重要作用。

    冯·诺依曼：冯·诺依曼计算机的设计思想：存储程序；逻辑组成：五大部分（运算器、控制器、存储器及输入输出设备）。

    【例4】提出“存储程序”的计算机工作原理的是（    ）。

    A. 克劳德·香农   B. 戈登·摩尔    C. 查尔斯·巴比奇    D. 冯·诺依曼

    【答案】D

    广告题目：CCF官网：http://www.ccf.org.cn/；NOI官网：http://www.noi.cn/；NOIp推荐IDE：GUIDE、Dev-C++、FreePascal。

    HTML：超文本标记语言（英文：HyperText Markup Language，HTML）是为“网页创建和其它可在网页浏览器中看到的信息”设计的一种标记语言。HTML是一种规范，一种标准，它通过标记符号来标记要显示的网页中的各个部分。网页文件本身是一种文本文件，通过在文本文件中添加标记符，可以告诉浏览器如何显示其中的内容（如：文字如何处理，画面如何安排，图片如何显示等）。浏览器按顺序阅读网页文件，然后根据标记符解释和显示其标记的内容，对书写出错的标记将不指出其错误，且不停止其解释执行过程，编制者只能通过显示效果来分析出错原因和出错部位。但需要注意的是，对于不同的浏览器，对同一标记符可能会有不完全相同的解释，因而可能会有不同的显示效果。HTML之所以称为超文本标记语言，是因为文本中包含了所谓“超级链接”点。所谓超级链接，就是一种URL指针，通过激活（点击）它，可使浏览器方便地获取新的网页。这也是HTML获得广泛应用的最重要的原因之一。Html由此可见，网页的本质就是HTML，通过结合使用其他的Web技术（如：脚本语言、CGI、组件等），可以创造出功能强大的网页。因而，HTML是Web编程的基础，也就是说万维网是建立在超文本基础之上的。

    HTML 5目前仍为草案，并已被W3C接纳。

    【例5】在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（    ）。

    A. <a url=”http://www.noi.cn”>欢迎访问NOI网站</a>

    B. <a href=”http://www.noi.cn”>欢迎访问NOI网站</a>

    C. <a>http://www.noi.cn</a>

    D. <a name=”http://www.noi.cn”>欢迎访问NOI网站</a>

    【答案】B

    【解析】A项语法不正确； C项无用；D项为标签。

    网络：IP地址：所谓IP地址就是给每个连接在Internet上的主机分配的一个32bit地址。按照TCP/IP协议规定，IP地址用二进制来表示，每个IP地址长32bit，比特换算成字节，就是4个字节。例如一个采用二进制形式的IP地址是“00001010000000000000000000000001”，这么长的地址，人们处理起来也太费劲了。为了方便人们的使用，IP地址经常被写成十进制的形式，中间使用符号“.”分开不同的字节。于是，上面的IP地址可以表示为“10.0.0.1”。

    现有的互联网是在IPv4协议的基础上运行的。IPv6是下一版本的互联网协议，也可以说是下一代互联网的协议，它的提出最初是因为随着互联网的迅速发展，IPv4定义的有限地址空间将被耗尽，而地址空间的不足必将妨碍互联网的进一步发展。为了扩大地址空间，拟通过IPv6以重新定义地址空间。IPv4采用32位地址长度，只有大约43亿个地址，估计在2005～2010年间将被分配完毕，而IPv6采用128位地址长度，几乎可以不受限制地提供地址。

    分类：A、B、C3类由InternetNIC在全球范围内统一分配，D、E类为特殊地址。

    【例6】关于计算机网络，下面的说法哪些是正确的：

    A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。

    B) 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。

    C) TCP/IP是互联网的基础协议簇，包含有TCP和IP等网络与传输层的通讯协议。

    D) 互联网上每一台入网主机通常都需要使用一个唯一的IP地址，否则就必须注册一个固定的域名来标明其地址。

    【答案】C

    【例7】 TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（   ）。

    A. 链路层         B．网络层          C. 传输层       D. 应用层         E.会话层

    【答案】B

    各种编程语言： 最早编程语言：机器语言；最早面向过程的编程语言：Fortran；最早面向对象的编程语言：Smalltalk；C、C++、Pascal均属于面向过程的语言（C++、Object Pascal也是面向对象语言）、都需要编译。

    【例8】Pascal语言、C语言和C++语言都属于（    ）。

    A. 面向对象语言      B. 脚本语言      C. 解释性语言      D. 编译性语言

    【答案】D

    大事件：（今年指2011年）苹果前CEO乔布斯去世、Skype被微软收购、微软拟发布Win8同时能在平板电脑上运行……

    【例9】今年（2010年）发生的事件有（   ）。

    A.惠普实验室研究员Vinay Deolalikar自称证明了P≠NPB.英特尔公司收购计算机安全软件公司迈克菲（McAfee）

    C.苹果公司发布iPhone 4手机

    D.微软公司发布Windows 7操作系统

    【答案】C

    【例10】 在以下各项中，（  ）不是操作系统软件。

    A. Solaris      B. Linux      C. Sybase      D. WindowsVista      E. Symbian

    【答案】C

    系统软件：在计算机软件中最重要且最基本的就是操作系统（OS）。它是最底层的软件，它控制所有计算机运行的程序并管理整个计算机的资源，是计算机裸机与应用程序及用户之间的桥梁。没有它，用户也就无法使用某种软件或程序。操作系统是计算机系统的控制和管理中心，从资源角度来看，它具有处理机、存储器管理、设备管理、文件管理等4项功能。操作系统如我们常用的Windows、Linux、Dos、Unix（开源）、Mac和Ubuntu（开源）等，而Foxpro、Access、Orale、Sybase、DB2和Informix等则是数据库系统。

    【例11】Linux下可执行文件的默认扩展名为（   ）。

    A. exe           B. com           C. dll           D. 以上都不是

    【答案】D

    【解析】扩展名是Windows的概念。

    编程基础知识

    布尔表达式：是一段代码声明，它最终只有true（真）和false（假）两个取值。从最基本的层次来说，所有的布尔表达式，不论它的长短如何，其值只能是true或false。 运算符号：¬ — not；∧— and；∨ – or。

    集合：组具有某种共同性质的数学元素。

    【例12】以下逻辑表达式的值恒为真的是（    ）。

    A. P∨(¬P∧Q)∨(¬P∧¬Q)           B. Q∨(¬P∧Q)∨(P∧¬Q)

    C. P∨Q∨(P∧¬Q)∨(¬P∧Q)         D. P∨¬Q∨(P∧¬Q)∨(¬P∧¬Q)

    【答案】A

  • C语言趣味题一

    某群看到：

    趣味题：
    编写原型为int foo(int i, int n)的c函数，实现打印i,i+1,…,n-1,n,n-1,…,i+1,i的序列。要求函数内只能有一条语句，只能有一个分号，只能有一个printf，并且只能用这个printf输出。不允许使用if、else、do、for、while、goto关键字。

    鉴于本人是蒟蒻，因此没有写出来，下面综合一下众神牛的答案：
    小虾：
    [cpp]
    int foo(int i, int n) {
        return i==n ? printf(“%d “, i) : (foo(i, i), i<n ? foo(i+1, n) : 0, foo(i, i));
    }
    [/cpp]
    22：
    [cpp]
    int foo(int i,int n) {
        return (i < 2 * n ? printf(“%d “, (i < n ? i : 2 * n – i)) + foo(i + 1, n) : 0);
    }
    [/cpp]
    兔子：
    [cpp]
    void foo(int i, int n) {
    //不用返回值都可以做；
        printf(“%d “, i == n ? i : (foo(i, i), foo(i + 1, n), i));
    }
    [/cpp]
    yeah：
    [cpp]
    int foo(int i, int n) {
        return printf(“%d “, i), i<n ? foo(i+1, n), foo(i, i) : 0 ;
    }
    [/cpp]
    最后是ib的：
    [cpp]
    int foo(int i, int n) {
        return i < n && foo(i, i) && foo(i + 1, n), printf(“%d “, i);
    }
    [/cpp]

    转载了以下文章中的部分内容：
    一道C语言趣味题 Xiaoxia[PG]
    趣味题 twd2

  • [转载]Win8来了，把你Hold住了吗？

    转载自面馆（Link）。

    期待了Windows 8已经有了一段很长的时间，虽说个人现在已经不再接触Windows相关开发，但不可否认它暂时还是一个具有很大影响力的桌面操作系统。9月14号，微软终于推出了预览版，趁着这个周末的时间，略为体验了一下。

    笔者是在近几天才退出的VMWare 8上进行体验的，1G的内存，40G的硬盘。以下是一些体验点：

    1.应用程序的运行情况以及兼容性
    Windows 8兼容Windows7下能运行的所有应用程序，于是我放了几个小应用上去跑了一下，果真如此。不过这要等正式版推出并持续使用一段很长时间才能知道在软件兼容性方面的情况。

    2.很酷的任务管理器
    任务管理器是一大亮点，看起来变得更加强大了，应用程序的内存占用情况也一目了然。

    3.Windows8的重置功能（恢复出厂设置）
    这是一大强点。如果因为用户中毒或者其它异常情况，不得不重装系统，那么Windows8的这个功能会大大方便你。异常的传统安装方法通常需要一个漫长的等待过程，但Windows8的重置功能将只用短短的几分钟即可。此功能在系统还原中可以找到。

    4.内置浏览器
    IE10已经被内置在Windows8中，它允许用户在传统 Windows 模式或 Metro 式的 UI 两种模式间自由切换。

    5.安全性
    Windows8将强化安全性并内置杀毒软件。

    6.附件
    Windows8对附件进行了一轮升级，从开始菜单中开来，似乎也增加了很多很有新鲜感的东西，如Piano，数独。

    7.个人信息
    Windows8可以通过LIVE帐号把用户的个人信息保存到服务器上，方便在不同的PC上进行同步。

    8.界面
    我相信Windows8的界面是有很多人期待的。Windows8采用了名为“Metro”的界面引擎，不过看起来似乎和win7大同小异。另外，开始菜单也是一大亮点，虽然开始是有点不习惯，但不可否认它的效果很绚丽。资源管理器采用了ribbon界面，显得更加友好。不过对于我来说，Windows8的界面并不算十分吸引我，个人并不太喜欢俏丽的界面，从使用Windows7开始，我还一直在用经典皮肤界面。

    9.开发者工具
    Windows8开发者预览版内置了VS2011以及远程调试工具。

    后记：
    这次体验只持续了很短的一段时间，也有很多亮点功能还没来得及体验。不过我相信Windows8会做得很好，同时也非常期待正式版的推出。

  • 坑爹一题

    伊甸园日历游戏

    【题目描述】
    Adam和Eve玩一个游戏，他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作：
    1：把日期的天数加1，例如1900.1.1变到1900.1.2；
    2：把月份加1，例如：1900.1.1变到1900.2.1。
    其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候，如果有这样的日期：1900.1.31，则变成了1900.2.31，这样的操作是非法的，我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。
    谁先将日期变到2001.11.4谁就赢了。
    每次游戏都是Adam先操作，问他有没有必胜策略？

    【输入格式】
    本题仅一个测试点，有多组数据。
    第一行为数据组数N。
    接下来每一行有3个整数X、Y、Z，表示X年Y月Z日。

    【输出格式】
    输出“YES”or“NO”（不包括引号），表示亚当是否有必胜策略。

    【样例输入】
    3
    2001 11 3
    2001 11 2
    2001 10 3

    【样例输出】
    YES
    NO
    NO

    【注释】
    建议先把所有情况都算出来。

    【题目来源】
    Vijos

     

    题目分析

    【关键算法】
    记忆化搜索、纯模拟或者数学方法。

    【分析】
    这里说说博弈论：博弈一个重要的定义：一个状态它的孩子状态全是必胜状态，则它就一定是必败状态。如果有孩子状态有一个为必败状态，则它就是必胜状态了。
    2001.11.4是一个必败状态，所以我们可以从2001.11.4递推到1900.1.1，将所有状态的情况都给计算出来，这样读入数据直接写即可。

    最后送上某大神写的代码：
    [cpp]
    #include
    using std::cin;
    using std::cout;
    int n, y, m, d;
    int main(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) { cin >> y >> m >> d;
    if ((d == 30 && (m == 11 || m == 9)) || ((m + d) % 2 == 0)) {
    cout << "YES"; } else { cout << "NO"; } cout << endl ; } return 0; } [/cpp]

    以下是这个算法的解释（Link）

    这是这个算法的解释：伊甸园日历游戏其实是游戏论的内容，这是所谓的平等组合游戏。
    什么是“平等组合游戏”？

    •  两人游戏。
    • 有一个状态集，而且通常是有限的。
    • 规定哪些状态转移是允许的。
    • 所有规定对于两人来说是一样的。
    • 两人轮流走步。
    • 有一个终止状态，到达终止状态后游戏即告终止。
    • 游戏可以在有限步内终止。

    P状态和N状态：
    就像第一是刚才走步的人的必胜状态，我们称之为P状态；而1，2，3，5，6，7，……都是下一个走步的人的必胜状态，我们称之为N状态。我们可以从终止状态出发，推出每一个状态，指出它是P状态还是N状态。就拿第一个游戏举例：
    步骤一 将所有终止状态设为P状态。
    步骤二 将所有一步之内可以到达一个P状态的状态设为N状态。
    步骤三 如果一个状态，不管怎么走都只能走到N状态，那么就将这个状态设为P状态。
    步骤四 返回步骤二。
    如果能够走到P状态，就能获胜。因为安照上面的定义，对手不管如何选择，只可能走到N状态。接下来总存在一个P状态你可以走到。这样一直走到终止状态，你获胜。当然这里所说得都是指对于最后走步的人获胜的游戏。
    我们严格的来定义P状态和N状态

    • 所有的终止状态都是P状态；
    • 对于任何的N状态，肯定存在一种方式可以一步转到一个P状态；
    • 对于任何的P状态，不管怎么走步，都只能转到N状态。

    而对于最后走步的人失败的游戏，只要将所有终止状态改成N状态，然后开始倒推就可以了。当然，必胜状态是N状态。也就是说，如果想胜利，就希望面对N状态，转移到P状态。
    2001.11.4 n
    2001.11.3 2001.10.4 p
    2001.11.2 2001.10.3 2001.09.4 n
    2001.11.1 2001.10.2 2001.09.3 2001.08.4 p
    2001.10.31 2001.10.1 2001.09.2 2001.08.3 2001.07.4 n
    2001.10.30 2001.09.30 2001.09.1 2001.08.2 2001.07.3 2001.06.4 p
    由此看出 当month+day mod 2=0 then p状态
    若month=9 day=30 then p状态

  • 信息学竞赛在线评测系统的安全性解决方案探讨

    • 信息学竞赛在线评测系统的安全性解决方案探讨

    一个高质量的 OJ 系统， Judger 要求有很高的安全性，因为它需要运行用户提交上来的代码，而用户会提交什么样的代码是无法预知的。 Judger 首先要把用户的代码编译成可执行文件，然后运行这个可执行文件，所以 Judger 的安全性主要是限制解题程序的行为，阻止它执行危险的操作。

    根据 DCS 评级，要达到 ProCode 以上级别的 Judger 程序，需要至少达到以下的安全目标：

    1. 阻止选手程序读写文件；
    2. 阻止选手程序读写注册表；
    3. 阻止选手程序修改系统设置（例如修改系统时间等）；
    4. 阻止选手程序关闭系统（包含注销等操作）；
    5. 阻止选手程序调用 API 函数；
    6. 阻止选手程序恶意提交代码（例如通过一些语言提供的支持库重复提交自身代码）。

     
    对于第四点，程序设计者可以将运行的进程放入一个作业对象中（可以参考《Windows核心编程》第五章）。对于第五点和第六点，可以将编译器中有关 API 的头文件和库文件删除，令其不能通过编译。
    本文主要关注如何解决第一、第二和第三点，要实现这几个目标，仅仅靠判题程序是不能解决问题的，一定要对操作系统进行相应的配置。对于第一点，只需要在系统中新建一个用户，在各个驱动器中的安全设置中拒绝该用户的访问，然后以这个新用户的身份来运行解题程序即可。类似的，对于第二点，只要拒绝这个用户访问注册表的各个主键即可。第三点，由于修改系统设置需要管理员特权，因此去除这个用户的大部分特权，只保留必要的特权即可。为什么不去除所有特权呢？因为有些特权是必需的，这个会在下文讲解。总的来说，这个解决方案的主要思想就是建立一个几乎无权限的用户，然后以这个用户的身份去运行解题程序。下面主要说明一下一些需要注意的问题。
     
    一、用户特权设置
    刚刚建立的用户是没有显式赋予任何特权的，这是理想的设置，不过我们仍然要赋予它一个“允许本地登录”的特权，因为我们要获取该用户的访问令牌，这只有在用户登录后获得。
    具体步骤：运行“gpedit.msc”，定位到“计算机配置-Windows设置-安全设置-本地策略-用户权限分配”，右侧列表中显示的就是用户可以拥有的特权列表。找到“允许本地登录”项，并双击，点击“添加用户或组”，在弹出的窗口中点击“对象类型”，选中“组”，确定返回，然后在下面的文本框中输入刚刚建立的用户组的名称，依次点击“确定”即可。
     
    二、以新用户的身份启动选手程序
    这个问题是本文将要说明的重点。无论是以指定用户身份启动进程还是以特定被降权了的 Token 启动进程都有如下几个Windows API函数可以使用（本文假定程序员使用 Unicode ）：
    BOOL WINAPI CreateProcessAsUser(
    __in HANDLE hToken,
    __in LPCTSTR lpApplicationName,
    __in LPTSTR lpCommandLine,
    __in LPSECURITY_ATTRIBUTES lpProcessAttributes,
    __in LPSECURITY_ATTRIBUTES lpThreadAttributes,
    __in BOOL bInheritHandles,
    __in DWORD dwCreationFlags,
    __in LPVOID lpEnvironment,
    __in LPCTSTR lpCurrentDirectory,
    __in LPSTARTUPINFO lpStartupInfo,
    __out LPPROCESS_INFORMATION lpProcessInformation
    );
     
    BOOL WINAPI CreateProcessWithLogonW(
    __in LPCWSTR lpUsername,
    __in LPCWSTR lpDomain,
    __in LPCWSTR lpPassword,
    __in DWORD dwLogonFlags,
    __in LPCWSTR lpApplicationName,
    __in LPWSTR lpCommandLine,
    __in DWORD dwCreationFlags,
    __in LPVOID lpEnvironment,
    __in LPCWSTR lpCurrentDirectory,
    __in LPSTARTUPINFOW lpStartupInfo,
    __out LPPROCESS_INFORMATION lpProcessInfo
    );
     
    BOOL WINAPI CreateProcessWithTokenW(
    __in HANDLE hToken,
    __in DWORD dwLogonFlags,
    __in LPCWSTR lpApplicationName,
    __in LPWSTR lpCommandLine,
    __in DWORD dwCreationFlags,
    __in LPVOID lpEnvironment,
    __in LPCWSTR lpCurrentDirectory,
    __in LPSTARTUPINFOW lpStartupInfo,
    __out LPPROCESS_INFORMATION lpProcessInfo
    );
     
    以上这三个函数中第二个和第三个均没有提供 ANSI 版本。
    因为需要启动的选手程序是需要分配给一个作业对象的，而 CreateProcessWithLogonW和 CreateProcessWithTokenW 函数启动的进程默认绑定到了一个匿名的对象，所以只能使用 CreateProcessAsUser 这个函数。
    CreateProcessAsUser 函数与 CreateProcess 函数的参数几乎完全一样，唯一不同的是多了一个 hToken 参数。这个参数是某个用户的 Token ，标识了这个用户的身份，新的进程就使用这个令牌来运行。要获得用户的令牌，需要使用 LogonUser 函数（关于它的使用，请参考MSDN）。
    调用该函数之后可以获得访问令牌，将该 Token 传入 CreateProcessAsUser 函数的第一个参数，就可以以指定用户的身份启动进程了。
    三、关于 CreateProcessAsUser
    关于 CreateProcessAsUser 函数，有很多需要注意的地方。首先，调用该函数的进程令牌中需要有两个特权： SE_ASSIGNPRIMARYTOKEN_NAME （替换一个进程级令牌）和 SE_INCREASE_QUOTA_NAME （为进程调整内存配额），否则函数调用会失败。这意味着 Judger 需要以较高权限的用户身份运行。例如，一个 Judger 普遍作为一个Windows服务运行，需要以 Local System 用户的身份来运行。很明显这样做存在安全隐患，因为 Local System 的权限实在是太大了。相比之下 CreateProcessWithLogonW 和 CreateProcessWithTokenW 则不需要这两个特权，安全性更佳。这也是使用 CreateProcessAsUser 的无奈之处。于是可以再建立一个用户专门用来运行判题程序，只赋予它这两个必要的特权。
    另一个要注意的问题是，以 CreateProcessAsUser 启动的进程默认是不能交互的，换句话说，这个进程不能显示窗口界面，以及不能执行与窗口有关的操作，例如接收命令行输入，向命令行窗口输出信息等，甚至不能通过管道与该进程的标准输入输出通信——即使在调用 CreateProcessAsUser 的时候指定了 CREATE_NO_WINDOW 这个标记也是如此。所以必须使启动后的进程是可交互的。
    这里要简单讲一下可交互的条件。在Windows中有两种对象， WindowStation 和 Desktop ， WindowStation 是 Windows 中一种重要的安全对象， Desktop 是包含在 WindowStation 中的。这两种对象都可以存在多个，但是只有在某个特定的 Desktop 中启动的进程才是可交互的，这个 Desktop 名为“default”，位于名为“winsta0”的 WindowStation 中。要想在这个 Desktop 中启动进程，需要进程具有访问“winsta0”和“default”的权限。没有桌面权限连 Win32 子系统都启动不起来。
    要达到这个目的，需要允许上面建立的运行解题程序的用户访问这两个对象，这是在调用 LogonUser 函数获得令牌后进行的，而不是手动配置的。MSDN上有一篇题为《Starting an Interactive Client Process in C++》的文章对此进行了详述，文章中的代码比较多，也比较复杂，这里简单讲一下文章中代码的原理：

    1. 获取 winsta0 WindowStation 的句柄。
    2. 获取 winsta0 的安全描述符。
    3. 复制原来的安全描述符。
    4. 获取安全描述符中的 DACL 。
    5. 复制原来的 DACL 。
    6. 向复制得到的 DACL 中添加允许用户访问的 ACE 。
    7. 将新的 DACL 设置到复制得到的安全描述符中。
    8. 将新的安全描述符设置到 winsta0 中。

    对于default Desktop的操作也是一样的。
    至此，我们可以正确地启动选手程序，并可以保证它的安全性了。
     
    参考资料：
    [Windows]ACM在线判题系统的安全性解决方案
    Win7下超级管理员创建普通权限任务

  • 冲刺NOIp2011模拟题（三）

    袁绍的刁难(recruitment.c/cpp/pas, 1s, 128M)

    [题目描述]

    黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
    这时候有很多很多的将领到袁绍处报到，每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
    袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
    袁绍想知道，他可以获得的第k大的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。

    [输入格式]

    输入数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。

    [输出格式]

    输出包含n行，每行输出一个对应的结果。

    [输入样例]

    1
    7

    [输出样例]
    13

    [样例说明]

    郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7大的总武力值是13。

    [数据范围]

    对于50%的数据，有k≤5000。
    对于100%的数据，有k≤2^31-1。

    游历的路线(lines.pas/c/cpp, 1s, 128Ms)

    [题目描述]

    我们的郭嘉大大经过一段时间发现了袁绍这个人干大事而惜身，见小利而忘义，又逢曹操在招兵买马，决定逃离袁绍去投曹操，而我们的曹操在第M天招募良材，我们的郭嘉大大既不能早去，也不能晚去，于是乎，他就趁着这一段时间到其他的城市游历一番，而每两个城市之间只能坐马车来往，由于我们的郭嘉大大很贪钱，他想用最少的费用，所以需要我们帮他求出这一个最小的费用。

    [输入格式]

    第一行包含两个数n，m， 表示有n个城市，和m天后曹操招纳良材。城市一就是郭嘉所在的城市，城市n就是曹操处。接下来n * (n – 1)行描述马车乘坐表。第2到第n行就是描述的城市1到2… n的马车乘坐表，第n + 1到第2n – 1行描述的城市2到城市1，3..n的马车乘坐表……对每一行，首先有一个数T，表示城市I到城市J的马车以T为周期，接下来有T个数，表示每天的马车的价格，如果价格为0则表示没有马车可坐。（n <= 100, m <= 200, T <= 20， Price <= 50000）

    [输出格式]

    如果存在这样的路线使郭嘉第m天到达曹操处，则输出最少的费用，否则输出0！

    [输入样例]

    3 5
    2 130 150
    3 75 0 80
    2 110 100
    4 60 70 60 50
    3 0 135 140
    2 70 80

    [输出样例]

    355

    老师的询问(baffles.c/cpp/pas, 1s, 128M)

    [题目描述]

    东汉末年，颖川书院，有一日老夫子给他的学生出了一道问题，书院中有一口清澈见底的池塘（什么都看得见），老夫子要吃鱼，池塘里有很多很多鱼，而池塘是一个n*m的矩形，他希望放置最少的挡板，将池塘分成很多个矩形（包括正方形），使得每个矩形里有且只有一条鱼，而作为老夫子学生的郭嘉很想完成这个任务，所以他把这个任务交给了你，希望你能很快地解决问题。
    例如n=4，m=3时的一种情况（0表示小方格内无鱼，1表示有鱼）：
    0 1 0
    0 0 0
    1 0 1
    0 0 0
    可以这么分：
    0 1 0
    0 0 0
    – – –
    1|0 1
    0|0 0
    由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为5。

    [输入数据]

    第一行有两个整数n和m（1≤n,m≤32），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

    [输出数据]

    对于每组输入数据，输出一行：一个数字，所需挡板的最短总长度。

    [输入样例]

    4 3
    0 1 0
    0 0 0
    1 0 1
    0 0 0

    [输出样例]

    5

    游历的路线(lines.pas/c/cpp, 1s, 128Ms)

    [题目描述]

    我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（N现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细。

    [输入格式]

    输入文件的第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。

    [输出格式]

    输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

    [输入样例]

    8
    0 0 1 0 0 0 0 0
    1 0 0 1 0 0 0 0
    0 1 0 1 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 1
    0 0 0 0 0 0 1 0

    [输出样例]

    2

  • “大三学生无证飙车撞人逃逸狂言百万‘了难’”感想

    长沙话普及：了难【LiaoNan】解决问题；充当打手或说客。

    三湘都市报8月28日讯 大三学生驾驶新买的大众CC轿车，凌晨在街头斑马线上撞飞两名路人后，不但不停车，还逆行疯狂逃逸，一路频频闯红灯。最可恶的是，被警方控制后，小伙子竟口出狂言声称愿出100万摆平此事。今日，长沙市芙蓉交警大队通报了该案情。
    肇事后为何疯狂逃窜，甚至被警车逼停后仍倒车脱逃。年仅22岁的马聪表示，当时是否撞人并不知情，“我视力不好，近视偏光。另外，车灯也不好。 知道警车追我，没意识到出了什么事。”让人惊讶的是，马聪到交警队后曾公开声称，“你们交警要的就是钱，我给100万就行了。”
    马聪住在中南大学的学生公寓，3天前拿着家里给的28万元购买了新车。正在考驾照的他并未取得驾驶执照，属无证驾驶。事发路段限速60码，对于超速的原因，马聪的回答更雷人，“想检验新车提速怎么样，直接从0拉到100码……”

    这则消息日前是长沙市民街头巷尾议论的焦点，这件事情目前又有了新的进展：

    前日在面对媒体时，马延圣曾自称只是一家配送公司的普通员工，家里有两套单位分的福利房。
    然而根据种种细节和马延圣的名字，记者在网上找到了这样一家公司——甘肃省食品总公司联销配送分公司。公司联系人一栏写的正是马延圣。随后记者多次拨打网站上公布的电话想核实马延圣的身份，但电话一直无人接听。而记者在甘肃省工商行政管理局的网站上进行搜索，找到了这家公司，他的法人代表正是马延圣，注册资金为80万元。
    通过记者的继续调查，马延圣的身份信息更加明朗。在甘肃省工程建设项目招标代理机构名目中，记者同样找到了马延圣的名字。这家公司的名字叫做甘肃中化建国际招标有限责任公司，该公司现在已更名为中海建国际招标有限责任公司。
    登录甘肃省工商行政管理局的网站，记者查找到中海建国际招标有限责任公司的法人代表正是马延圣。公司注册资金为5000万元。该公司主要从事政府采购、工程建设、国内、国际设备等招标项目，以及进出口代理工作，涉及工业、农业、能源、环保及咨询服务等国民经济的众多领域。而在招标名录中，这个马延圣留下的电话号码，正是马聪父亲的手机号码。

    （在这里查看完整消息）

    好了，新闻看完了，我喝杯水开始说话。我刚刚看到新闻里说：“马聪的父亲正在慢慢学会躲避媒体，应该是有人在教马延圣如何面对媒体，他已经慢慢从公众视野中消失。”
    嗯，首先是震撼到我的马同学的观点——“我怎么知道开车要拿执照！”是的，要是马家开的公司注册资金有5个亿买的起飞机的话我估计马家大少爷没准会买一架飞机来玩玩（是不需要执照的哦亲~）

    好了，不扯淡了。我们转回正题。
    肇事者的冷漠在我看来是十分的刺眼的。或者说这些所谓富二代的学生，根本没有接受过是非观念的教育——比如药家鑫“农村人难缠”（这里还有一篇新闻）、以及引起广泛声讨的“我爸爸是李刚！”。不管怎么样，越来越多的年轻人们已经抛下了他们的富裕光环向社会展示出了他们纯真的一面，亦或者说是无知的一面。从马聪的爸爸的表现来看，马聪本人做出的这些事情或许也就不足为奇，我也能更深刻地理解“富不过三代”的意义。提起马聪，我脑海里首先浮现的是一个对生命冷漠的青年形象。
    我不想去讨论这是不是有钱人就能拥有狂妄自大的资本，这或许是一个长期的教育问题积累下来的结果。我只想说，在如今“向钱看”的社会中，拥有基本的是非观念，知道开车要执照而不是开车要有钱并非一件很难的事情。我很难过的是那些披着富二代的喊着黄金出生的孩子不缺钱，也拥有名牌大学的学历证明，但是缺少社会责任感等做人的基本因素。那种因为钱带来的高傲而又冷漠的眼神才正是他们可悲的所在。

    社会的贫富差距在渐渐地加大，在财富与道德不对等的情况越来越明显的情况下，那些有钱的和没钱的又会何去何从呢？

  • CreateProcess, CreateProcessWithLogonW & CreateProcessAsUser 一些注意事项

    前一阵子写Small Sandbox和SXKDZ Compare的时候遇到了一些问题。问题都是出在CreateProcess， CreateProcessWithLogonW和CreateProcessAsUser这三个函数上。
    于是写一个备注，以防忘记，如有错误，请留言指正。

    第一个问题：

    [cpp]
    CreateProcessW(NULL, _TEXT(“C:\\init.exe”), ……);
    [/cpp]

    这是 SXKDZ Compare里面的一段代码，可能明眼人马上就看得出来。我没写过Unicode的程序（搞OI的都是写Ansi的程序），于是以为以下的代码可以直接改成Unicode版本的

    [cpp]
    CreateProcessA(NULL, “C:\\init.exe”, ……);
    [/cpp]

    后来我发现改为Unicode版本以后会报错1812或者直接崩溃，于是检查StartupInfo和ProcessInformation结构体的初始化……但是没有发现错误。（咨询FlowerCode也无果）
    后来咨询iceboy才知道MSDN中有这么一句（Link）：

    The Unicode version of this function, CreateProcessW, can modify the contents of this string. Therefore, this parameter cannot be a pointer to read-only memory (such as aconst variable or a literal string). If this parameter is a constant string, the function may cause an access violation.

    也就是说我得给第二个参数一个缓冲区。
    这是我犯的第一个错误 😥

    第二个问题：我写Small Sandbox的时候想把被限制程序以一个0权用户运行再加上若干JobObject的限制来防止被限制程序乱搞，将程序以一个用户的权限运行有2还是可以用：CreateProcessWithLogonW、CreateProcessAsUser，咨询熊熊得知CreateProcessWithLogonW方便些（当时没有告诉他我还要加JobObject），于是有了如下代码：

    [cpp]
    CreateProcessWithLogonW(_TEXT(“Username”), _TEXT(“.”), _TEXT(“Password”), LOGON_WITH_PROFILE, NULL, _TEXT(“C:\\init.exe”), ……);
    [/cpp]

    然后成功以后加入JobObject，提示拒绝访问-5的错误，然后找到一解决方案（Link），按照解决方案添加了Breakaway form job的标记还是错了。最后在StackOverFlow里找到一提问（Link），里面有这样一句：

    Edit: It seems that svchost.exe, which actually creates the process when CreateProcessWithLogonW is used, already assigns the process to an anonymous job. The CREATE_CREAKAWAY_FROM_JOB flag is ignored by this function. So the real question is: is there a way to prevent svnhost from assigning the process to a job ?

    于是咨询ib，得出不能同时使用JobObject和CreateProcessWithLogonW这俩玩意儿，于是尝试写CreateProcessAsUser。
    开始的时候莫名其妙什么错误吧（源代码已经丢了 😡 ） ，然后改了改弹出了应用程序初始化失败，然后ib告诉我是没有某权限（我的聊天记录丢了），于是参照VijosNT Mini的代码添加了给窗口站和一个我又忘记名字的东西加上了权限，最后成功。
    代码存档：

    CreateProcessAsUser + JobObject 代码存档 (0 downloads )

    ib友情提示：这个函数很难用……

  • SXKDZ Cena 0.8.1 Release+源代码

    SXKDZ Cena是在原Cena的基础上修改而来，目前的版本号是0.8.1。
    修正了在部分Win7下崩溃的错误。
    许可协议：GPL V2。

    • 注意事项：为了节约安装包体积，默认打包进去的编译器是LZZ（Pascal编译器，中文）和NCC（C编译器，中文）。为了保证你的评测环境与NOIp的尽量相同，请安装FreePascal2.4.4和MinGW-GCC4.5.2（推荐tdm-gcc），并在选项->编译器选项中设置。

    安装包：

    SXKDZ Cena 0.8.1 Release (0 downloads )

    源代码下载：
    SXKDZ Cena 0.8.1 源代码 (0 downloads )