下载文档原格式
第 23 届全国青少年信息学奥林匹克联赛初赛普及组 C++ 语言试题竞赛时间： 2017 年 10 月 14 日 14:30~16:30页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸选手注意：1 、试题纸共有 8 上的一律无效。
2 、不得使用任何电子设备 如计算器、手机、电子词典等)或查阅任何书籍资料。
一、单项选择题(共 20 1. 在 8 位二进制补码中， A. 43 B. -85 C. -43 解析：补码就是符号位不变， 结论： -85 答案 B题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项)10101011 表示的数是十进制下的 ( ) 。
D. -84其他各位逐位求反再加一2. 计算机存储数据的基本单位是 (A. bitB. ByteC. GBD. KB)。
3. 下列协议中与电子邮件无关的是( )。
A. POP3B. SMTPC. WTOD. IMAP 4. 分辨率为 800x600 、16 位色的位图，存储图像信息所需的空间为 ( )。
A.937.5KBB. 4218.75KBC.4320KBD. 2880KB 解析：800*600*16/8=A5. 计算机应用的最早领域是 ( )。
A. 数值计算B. 人工智能C. 机器人D. 过程控制6. 下列不属于面向对象程序设计语言的是 A.C B. C++ C. Java D. C# 解析：新出的语言都是面向对象的， OOP 的， 旧的不是，答案 A7.NOI 的中文意思是 ( ) 。
A. 中国信息学联赛B. 全国青少年信息学奥林匹克竞赛C. 中国青少年信息学奥林匹克竞赛D. 中国计算机协会 解析：全国青少年信息学奥林匹克竞赛 答案：B8. 2017 年 10 月 1 日是星期日， 1999A. 星期三B. 星期日年 10 月 1 日是 ( ) 。
C. 星期五D. 星期二 解析：什么年是闰年？你首先想到的可能是能被 4 整除的年就是闰年。
NOIP2017解题报告一、成绩（score）这是一道送分题。
题目明确规定A、B、C都是10的正数倍。
所以我们可以将读入进来的a、b、c都先整除10，再分别将a*2，b*3，c*5，然后相加，就是最后的答案。
且结果可以保存在longint类型中。
代码如下：vara,b,c,sum:longint;beginassign(input,'score.in');reset(input);assign(output,'score.out');rewrite(output);readln(a,b,c);sum:=a div10*2+b div10*3+c div10*5;writeln(sum);close(input);close(output);end.但倘若题目没有说明A、B、C都是10的正数倍，那么我们就将a*0.2，b*0.3，c*0.5，然后相加。
但这一次结果需存在实型中。
二、图书管理员（librarian）这是一道简单题。
其实吧，本套试卷我们要认真阅读数据规模，总能发现一些微妙的细节。
例如本题，所有的图书编码和需求码均不超过10,000,000完全可以用longint存的（那不就很棒棒了~~）对于读入的每一个需求码，我们都去循环一遍，先判断当前的这本书符不符合需求，但怎么判断呢？数据会告诉我们需求码的长度k，也就是说我们要判断当前书码的后k位是否等于需求码。
哈哈哈，没错，只要用书码mod（10的k次方）即可。
如果相等，那么进行判断取小（因为题目君说要最小的啦~~）。
所以这里如果使用了快排从小到大，那么当你找到第一个满足要求的书码就是答案。
当然不用也可以，时间复杂度为O（nq），1000,000不会炸。
话不多说，代码如下：varn,m,i,j,x,y,sum,min:longint;a:array[0..1000]of longint;procedure f(l,r:longint);varx,y,mid,t:longint;beginx:=l;y:=r;mid:=a[(l+r)div2];repeatwhile a[x]<mid do inc(x);while a[y]>mid do dec(y);if x<=y thenbegint:=a[x];a[x]:=a[y];a[y]:=t;inc(x);dec(y);end;until x>y;if l<y then f(l,y);if x<r then f(x,r);end;beginassign(input,'librarian.in');reset(input);assign(output,'librarian.out');rewrite(output);readln(n,m);for i:=1to n do readln(a[i]);f(1,n);for i:=1to m dobeginreadln(x,y);sum:=1;for j:=1to x do sum:=sum*10;min:=maxlongint;for j:=1to n doif a[j]mod sum=y then begin min:=a[j];break;end;if min=maxlongint then writeln(-1)else writeln(min);end;close(input);close(output);end.但倘若我们的需求码和编码是一些很大很大的数（longint无法承受）时，最最高大上的字符串就闪亮登场了（蹬蹬蹬，天空一声巨响，字符串闪亮登场）。
noip2017普及组初赛试题+答案第 23 届全国青少年信息学奥林匹克联赛初赛普及组 C++ 语言试题竞赛时间： 2017 年 10 月 14 日 14:30~16:30页，答题纸共有 2 页，满分 100 分。
请在答题纸上作答，写在试题纸选手注意：1 、试题纸共有 8 上的一律无效。
2 、不得使用任何电子设备如计算器、手机、电子词典等)或查阅任何书籍资料。
一、单项选择题(共 20 1. 在 8 位二进制补码中， A. 43 B. -85 C. -43 解析：补码就是符号位不变，结论： -85 答案 B题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项)10101011 表示的数是十进制下的 ( ) 。
D. -84其他各位逐位求反再加一2. 计算机存储数据的基本单位是 (A. bitB. ByteC. GBD. KB)。
3. 下列协议中与电子邮件无关的是( )。
A. POP3B. SMTPC. WTOD. IMAP 4. 分辨率为 800x600 、16 位色的位图，存储图像信息所需的空间为 ( )。
A.937.5KBB. 4218.75KBC.4320KBD. 2880KB 解析：800*600*16/8=A5. 计算机应用的最早领域是 ( )。
A. 数值计算B. 人工智能C. 机器人D. 过程控制6. 下列不属于面向对象程序设计语言的是 A.C B. C++ C. Java D. C# 解析：新出的语言都是面向对象的， OOP 的，旧的不是，答案 A7.NOI 的中文意思是 ( ) 。
A. 中国信息学联赛B. 全国青少年信息学奥林匹克竞赛C. 中国青少年信息学奥林匹克竞赛D. 中国计算机协会解析：全国青少年信息学奥林匹克竞赛答案：B8. 2017 年 10 月 1 日是星期日， 1999A. 星期三B. 星期日年 10 月 1 日是 ( ) 。
C. 星期五D. 星期二解析：什么年是闰年？你首先想到的可能是能被 4 整除的年就是闰年。
第23届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2017年10 月14 日14:30~16:30选手注意：1、试题纸共有8 页，答题纸共有2 页，满分100 分。
请在答题纸上作答，写在试题纸上的一律无效。
2、不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。
A. 43B. -85C. -43D. -84解析：补码就是符号位不变，其他各位逐位求反再加一结论：-85 答案B2.计算机存储数据的基本单位是( )。
A. bitB. ByteC. GBD. KB3.下列协议中与电子邮件无关的是( )。
A. POP3B. SMTPC. WTOD. IMAP4.分辨率为 800x600、16 位色的位图，存储图像信息所需的空间为( )。
A.937.5KBB. 4218.75KBC.4320KBD. 2880KB解析：800*600*16/8=A5.计算机应用的最早领域是( )。
A. 数值计算B. 人工智能C. 机器人D. 过程控制6.下列不属于面向对象程序设计语言的是( )。
A. CB. C++C. JavaD. C#解析：新出的语言都是面向对象的，OOP的，旧的不是，答案A7.NOI 的中文意思是( )。
A. 中国信息学联赛B. 全国青少年信息学奥林匹克竞赛C. 中国青少年信息学奥林匹克竞赛D. 中国计算机协会解析：全国青少年信息学奥林匹克竞赛答案：B8. 2017年10月1日是星期日，1999年10月1日是( )。
A. 星期三B. 星期日C. 星期五D. 星期二解析：什么年是闰年？你首先想到的可能是能被4整除的年就是闰年。
实际上这是不正确的，公历里闰年的定义是这种：能被400整除的，或者不能被100整除而能被4整除的年就是闰年，换一句话说，非世纪年份中能被4整除的，和世纪年份中能被400整除的是闰年。
NOIP2017普及组复赛-解题报告衢州市兴华中学By 冯明浩给出三个整十数A,B,C ，求A*20%+B*30%+C*50%的值模拟直接粗暴地输出A*0.2+B*0.3+C*0.5时间复杂度：O(1) 期望得分：100由于分数均为整十数，先将分数各除以10，再直接输A*2+B*3+C*5。
这样就避免了精度问题时间复杂度：O(1) 期望得分：100给出N 个数Ai ，再进行Q 次询问，找后缀为给定数Bi 的最小的Ai模拟将Ai 及Bi 都转化成字符串。
每次询问都对N 个数进行后缀比较，挑出个最小的时间复杂度：O(N*Q*len) 期望得分：80 对算法一的比较进行优化——构造出n 10，对于Ai ，直接Ai Mod 10len ，判断是否相等。
这样每次比较的时间复杂度优至O(1)同时先将Ai 排序，再每次从小到大查询，一旦找到就停时间复杂度：小于O(N*Q)（一般情况） 期望得分：100读入Ai 时进行处理，构造ans[x]数组，记录询问X 的最小值。
对于每个Ai ，依次取出其后1、2、3……len 位，修正其的最小值。
这样每次查询，就可以O （1）出结果了时间复杂度：O(N*len) 空间复杂度：O(max(Bi)) 期望得分：100给出一个N*N 的矩阵，其中部分格有颜色每次可以从一个格向上下左右四个方向移动一格（不能越出矩阵且满足条件），根据两个格子的颜色有不同的代价求从左上角走至右下角的最小代价最短路（动态规划）直接暴力地按照题意进行DFS时间复杂度：O(n n *2) 期望得分：30以左上角为起点，右下角为终点，刷四个方向的SPFA（也可预先对相邻格建好边，刷最短路SPFA 或DIJ 或进行记忆化DFS ）时间复杂度：O(k*n*n) 期望得分：100给出N 个格子的位置Xi 与价值Pi ，从起点0往右跳跃，初始跳跃的距离只能为d同时可以花费金币来调整其跳跃距离，花了t 个金币时可跳跃的距离为max(1,d-t)~(d+k)每遍历一个格子就会获得其代价Pi ，求要获得总价值为K 所需最少的金币数二分、动态规划、单调序列（堆）从小到大枚举所需金币数，用O(N*N)的DP 进行check ，一旦发现可行就为答案时间复杂度：O(max(Ai)*N*N) 期望得分：20分析发现，枚举的金币数越多，跳跃范围越大，总价值一定越多——满足二分答案的单调性，于是将算法一的枚举答案变为二分枚举时间复杂度：O()max(2log Xi *N*N) 期望得分：50 分析一下DP 的转移方程：F[i]=max(F[j])+P[i](max(1,d-t)≤a[i]-a[j]≤d+k)就会发现DP 的j 这次循环是为了找F[1~i-1]中的最大值，自然而然就想到了用堆优化——堆中存放F[1~i-1]，若堆顶距当前X[i]大于d+k ，就丢掉该元素（再也没用）否则若堆顶距当前X[i]小于max(1,d-t)，就暂存在临时数组中，最后在当前解更新好后记得塞回去则F[i]=F[heap[1]]+P[i]时间复杂度：O()max(2log Xi *N*k*N 2log ) 期望得分：80 继续优化算法三的DP ：那些离当前X[i]太近的实际上完全没有必要塞入堆中，那么再另开一个变量j 记录当前往堆中塞入的最后一个元素。
NOIP2017普及组初赛解析
纯原创+手打，求轻喷，如果觉得对你有帮助，点个赞吧，如果能打赏一下，你问我兹不兹瓷，我肯定是兹瓷的！
初步评价，整体来说，难度比2016增大了，倒并不是说题目思维难度加大很多，而是直接了当的题目少了一些，有10%左右分值的题目是有坑的，一不小心就错了。
基本结论：得分难度加大了，但是不能算是思维“非常难”级别。
如果心态平和，做完选择题之后，后面的题目都回归常规了，还是能够比较顺畅地解题，理论上应该得到比较理想的分数的。
今年无论是提高组还是普及组，数学味道都非常浓，计算机科学的基础学科是数学，所以我们要重视数学学科的学习，尤其是与计算机科学相关的组合数学、概率论、离散数学、数列等知识的学习，在OI中，这些知识与数奥的方向并不完全一致，所以对于普及组打基础的小朋友来说，没学过数奥的也不要方！。
第1篇一、引言随着计算机科学和人工智能技术的不断发展，棋盘算法在各个领域得到了广泛应用。
棋盘算法是指解决棋类游戏问题的算法，包括但不限于国际象棋、围棋、五子棋等。
本文将对棋盘算法的发展历程、主要类型及其在现实中的应用进行总结和分析。
二、棋盘算法的发展历程1. 早期阶段：20世纪50年代，随着计算机的出现，人们开始尝试用计算机程序模拟棋类游戏。
这一阶段的棋盘算法主要以穷举搜索为主，算法效率较低。
2. 中期阶段：20世纪60年代至70年代，随着算法理论的不断发展，人们提出了许多高效的棋盘算法，如Alpha-Beta剪枝、Minimax搜索等。
这些算法在提高棋类游戏程序水平方面取得了显著成果。
3. 现阶段：20世纪80年代至今，随着人工智能技术的飞速发展，棋盘算法逐渐融入深度学习、强化学习等先进技术，使得棋类游戏程序水平达到了前所未有的高度。
三、棋盘算法的主要类型1. 穷举搜索算法：穷举搜索算法通过对棋盘上的所有可能走法进行穷举，找出最优解。
该算法在棋类游戏中应用广泛，但计算量巨大，效率较低。
2. Alpha-Beta剪枝算法：Alpha-Beta剪枝算法是一种高效的穷举搜索算法，通过剪枝减少搜索空间，提高搜索效率。
该算法在棋类游戏中得到广泛应用。
3. Minimax搜索算法：Minimax搜索算法是一种基于启发式的搜索算法，通过评估函数对棋局进行评估，选择最优走法。
该算法在棋类游戏中具有较好的实用性。
4. 深度学习算法：深度学习算法在棋类游戏中取得了显著成果，如AlphaGo、Leela Zero等。
这些算法通过学习大量的棋局数据，实现对棋局的理解和预测。
5. 强化学习算法：强化学习算法在棋类游戏中也取得了显著成果，如DeepMind的AlphaZero。
该算法通过与环境交互，不断优化策略，提高棋类游戏水平。
四、棋盘算法在现实中的应用1. 国际象棋：国际象棋是棋盘算法的经典应用，许多优秀的国际象棋程序都采用了棋盘算法，如Stockfish、AlphaZero等。
个人自我介绍简单大方
很抱歉，但我无法为您提供____字的自我介绍。
以下是一个简洁而大方的自我介绍示例，供您参考：
大家好，我叫[姓名]。
很高兴有机会向大家介绍一下自己。
我出生并长大在[所在地]，是一个勤奋、积极向上的人。
在学业方面，我于[毕业时间]从[学校名称]获得了[学位/专业]学位。
在大学期间，我通过自我努力和课外学习，取得了良好的学术成绩，并参与了一些学生组织和社团活动。
这些经历不仅培养了我的团队合作和领导能力，也加强了我的沟通和组织能力。
在工作方面，我有[工作年限]年的相关工作经验。
我曾在[公司/组织名称]担任[职位]，负责[工作职责]。
在这期间，我不断努力提升自己的专业知识和技能，以适应快速发展的工作环境。
我善于分析问题并找出解决方案，能够有效地与团队合作并承担责任，这些都为我赢得了同事和上级的认可。
除了工作，我也积极参与志愿者活动，希望能为社区和弱势群体做一点贡献。
我相信，通过奉献和关心他人，我们可以建立一个更加和谐和温暖的社会。
在个人生活中，我喜欢阅读、旅行和运动。
阅读扩展了我的视野，旅行让我能够体验不同的文化和风景，而运动则让我保持健康和积极的精神状态。
此外，我也很喜欢与家人和朋友相处，分享彼此的喜怒哀乐。
总的来说，我是一个热情、乐观、有责任心的人。
我相信勤奋和坚持可以取得成功，而真诚和善良可以赢得他人的信任和支持。
我希望能够在您的团队中发挥我的才能，并与大家一同成长和进步。
这就是我简单的自我介绍，谢谢大家！。
棋盘解题报告（noip2017普及组第三题）棋盘解题报告（noip2017普及组第三题）上次写了Linux⽤vim进⾏C++编程的配置和操作⼊门后，今天再给棋盘写个解题报告试试。
题⽬描述有⼀个m ×m的棋盘，棋盘上每⼀个格⼦可能是红⾊、黄⾊或没有任何颜⾊的。
你现在要从棋盘的最左上⾓⾛到棋盘的最右下⾓。
任何⼀个时刻，你所站在的位置必须是有颜⾊的（不能是⽆⾊的），你只能向上、下、左、右四个⽅向前进。
当你从⼀个格⼦⾛向另⼀个格⼦时，如果两个格⼦的颜⾊相同，那你不需要花费⾦币；如果不同，则你需要花费1 个⾦币。
另外，你可以花费2 个⾦币施展魔法让下⼀个⽆⾊格⼦暂时变为你指定的颜⾊。
但这个魔法不能连续使⽤，⽽且这个魔法的持续时间很短，也就是说，如果你使⽤了这个魔法，⾛到了这个暂时有颜⾊的格⼦上，你就不能继续使⽤魔法；只有当你离开这个位置，⾛到⼀个本来就有颜⾊的格⼦上的时候，你才能继续使⽤这个魔法，⽽当你离开了这个位置（施展魔法使得变为有颜⾊的格⼦）时，这个格⼦恢复为⽆⾊。
现在你要从棋盘的最左上⾓，⾛到棋盘的最右下⾓，求花费的最少⾦币是多少？输⼊输出格式输⼊格式：数据的第⼀⾏包含两个正整数m，n，以⼀个空格分开，分别代表棋盘的⼤⼩，棋盘上有颜⾊的格⼦的数量。
接下来的n ⾏，每⾏三个正整数x，y，c，分别表⽰坐标为（x，y）的格⼦有颜⾊c。
其中c=1 代表黄⾊，c=0 代表红⾊。
相邻两个数之间⽤⼀个空格隔开。
棋盘左上⾓的坐标为（1, 1），右下⾓的坐标为（m, m）。
棋盘上其余的格⼦都是⽆⾊。
保证棋盘的左上⾓，也就是（1，1）⼀定是有颜⾊的。
输出格式：输出⼀⾏，⼀个整数，表⽰花费的⾦币的最⼩值，如果⽆法到达，输出-1。
输⼊输出样例输⼊样例#1：5 71 1 01 2 02 2 13 3 13 4 04 4 15 5 0输出样例#1：8输⼊样例#2：5 51 1 01 2 02 2 13 3 15 5 0输出样例#2：-1说明输⼊输出样例1 说明从（1，1）开始，⾛到（1，2）不花费⾦币从（1，2）向下⾛到（2，2）花费1 枚⾦币从（2，2）施展魔法，将（2，3）变为黄⾊，花费2 枚⾦币从（2，2）⾛到（2，3）不花费⾦币从（2，3）⾛到（3，3）不花费⾦币从（3，3）⾛到（3，4）花费1 枚⾦币从（3，4）⾛到（4，4）花费1 枚⾦币从（4，4）施展魔法，将（4，5）变为黄⾊，花费2 枚⾦币，从（4，4）⾛到（4，5）不花费⾦币从（4，5）⾛到（5，5）花费1 枚⾦币共花费8 枚⾦币。
棋盘问题总结我们在研究问题时经常能碰到这⼀类为题：在某个棋盘上有⼀种棋⼦，问最多放下⼏个棋⼦。
或者有⼀堆棋⼦，问你移去最少的棋⼦数⽬，使得剩下来的棋⼦两两不攻击。
先看下⾯这道题问题 E: P1035时间限制: 1 Sec 内存限制: 128 MB提交: 82 解决: 35[][][]题⽬描述给出⼀张n*n(n< =100)的国际象棋棋盘，其中被删除了⼀些点，问可以使⽤多少1*2的多⽶诺⾻牌进⾏掩盖。
输⼊第⼀⾏为n，m（表⽰有m个删除的格⼦）第⼆⾏到m+1⾏为x,y，分别表⽰删除格⼦所在的位置 x为第x⾏ y为第y列输出⼀个数，即最⼤覆盖格数样例输⼊8 0样例输出32这道题先想的是状压DP（爆搜）后来不会做啦。
其实⼀个棋⼦只能和它上下左右4块中的⼀块拼成⼀⼤块，所以我们把每个棋⼦与其上下左右四个棋⼦连⼀条边。
连完所有的边后，我们发现要求的就是最多有多少的边（顶点不能重复）想到了什么？⼆分图匹配。
但它不⼀定是个⼆分图啊。
我们需要证明这⼀点。
⼀种⼝糊的⽅法就是显然⼀个点仅⾛奇数次肯定不能回到原点，所以原图中不存在奇数边的环路，就是⼆分图啦。
还有⼀种⽐较巧妙和通⽤的⽅法就是将棋盘⿊⽩染⾊，所有⿊的只能与⽩点发⽣关系，就是显然的⼆分图了（⿊⽩两个点集）。
对于棋⼦的问题，我们只要在相互冲突的棋⼦连上⼀条边，然后简单的证明⼀下是不是⼆分图，最后求最⼤⼦独⽴集或最⼤匹配即可。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define grey 2#define black 1#define white 0int sum,n,m,Map[105][105],color[105][105],num_white,num_black,White[105],Black[10005],used[10005],match[10005];bool dfs(int u){int t,i;for (int v=1;v<=num_white;v++){i=White[v];if (used[i]==0 && Map[u][i]){used[i]=1;t=match[i];match[i]=u;if (t==0 || dfs(t)) return1;match[i]=t;}}return0;}void make_way(int u,int v){Map[u][v]=1;}int make_num(int a,int b){return ((n)*(a-1)+b);}void make_edge(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(color[i][j]!=grey){if(color[i][j]==white){White[++num_white]=make_num(i,j);}else Black[++num_black]=make_num(i,j);if(i>1&&color[i-1][j]!=grey) make_way(make_num(i,j),make_num(i-1,j));if(j>1&&color[i][j-1]!=grey) make_way(make_num(i,j),make_num(i,j-1));if(i<n&&color[i+1][j]!=grey) make_way(make_num(i,j),make_num(i+1,j));if(j<n&&color[i][j+1]!=grey) make_way(make_num(i,j),make_num(i,j+1));}}void draw(int n){for(int i=1;i<=n;i++){if(i%2) color[i][1]=black;else color[i][1]=white;for(int j=2;j<=n;j++){color[i][j]=1^color[i][j-1];}}}void print(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<color[i][j];cout<<endl;}}int main(){scanf("%d %d",&n,&m);draw(n);int a,b;for(int i=1;i<=m;i++)scanf("%d %d",&a,&b),color[a][b]=grey;make_edge();//print();for(int i=1;i<=num_black;i++){memset(used,0,sizeof(used));if(dfs(Black[i]))sum++;//cout<<Black[i]<<endl;}cout<<sum<<endl;}#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;#define grey 2#define black 1#define white 0int sum,n,m,Map[105][105],color[105][105],num_white,num_black,White[105],Black[10005],used[10005],match[10005]; bool dfs(int u){int t,i;for (int v=1;v<=num_white;v++){i=White[v];if (used[i]==0 && Map[u][i]){used[i]=1;t=match[i];match[i]=u;if (t==0 || dfs(t)) return1;match[i]=t;}}return0;}void make_way(int u,int v){Map[u][v]=1;}int make_num(int a,int b){return ((n)*(a-1)+b);}void make_edge(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(color[i][j]!=grey){if(color[i][j]==white){White[++num_white]=make_num(i,j);}else Black[++num_black]=make_num(i,j);if(i>1&&color[i-1][j]!=grey) make_way(make_num(i,j),make_num(i-1,j));if(j>1&&color[i][j-1]!=grey) make_way(make_num(i,j),make_num(i,j-1));if(i<n&&color[i+1][j]!=grey) make_way(make_num(i,j),make_num(i+1,j));if(j<m&&color[i][j+1]!=grey) make_way(make_num(i,j),make_num(i,j+1)); }}void draw(int n){for(int i=1;i<=n;i++){if(i%2) color[i][1]=black;else color[i][1]=white;for(int j=2;j<=n;j++){color[i][j]=1^color[i][j-1];}}}void print(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<color[i][j];cout<<endl;}}int main(){scanf("%d %d",&n,&m);draw(n);int a,b;for(int i=1;i<=m;i++)scanf("%d %d",&a,&b),color[a][b]=grey;make_edge();//print();for(int i=1;i<=num_black;i++){memset(used,0,sizeof(used));if(dfs(Black[i]))sum++;//cout<<Black[i]<<endl;}cout<<sum<<endl;}。
残缺棋盘问题问题：残缺棋盘是一个有2^k * 2^k （k>=1）个方格的棋盘，其中恰有1个方格残缺，图中给出k=1时各种可能的残缺棋盘，其中残缺棋盘的方格用阴影表示1 号 2号3 4号这样的棋盘称作“三隔板”，残缺棋盘问题就是用这4种三格扳覆盖更大的残缺棋盘，在此覆盖种要求： 1》 两个三格扳不能覆盖2》 三格扳不能覆盖残缺方格，但必须覆盖其中所有的方格在这种限制条件下，所需要的三格扳总数为（2^k * 2^k —1）/3；算法设计思想：如果对于k>=2的棋盘，直接考虑覆盖是比较复杂，那么应该用分治法解决残缺棋盘问题二分法问题是分而治之方法中的一种，用其分解得到的都是两个独立的子问题，而此题用二分法分解该问题得到的并不都是与原问题相似且独立的子问题问题分解的过程如下：以k=2为例，用二分法分解，得到的棋盘如图所示，用双线划分的4个k=1的棋盘。
但要注意这4个棋盘，并不都是与原问题相似且独立的子问题，原因当下图左面中的残缺方格在左上部时，第一个子问题与原问题相似，而其它三个子棋盘并不是与原问题相似的子问题，那么既然不能独立求解了当使用一个1号三格扳覆盖2,3,4号3个子棋盘的各一个后，如图右图所示，把覆盖后的方格，也看做是残缺棋盘（称为伪残缺棋盘），那么这时其它三个子棋盘也就是与原问题相似且独立的子问题了。
当残缺棋盘在第一个子棋盘时，用1号三格扳覆盖其余三个子棋盘的交界方格，可以使用另外三个子棋盘转化为可独立的求解的子问题；同样的，当残缺棋盘在第二个子棋盘时，则首先用2号三格扳进行覆盖，当残缺棋盘在第三个棋盘时，则首先用3号棋盘进行覆盖，当残缺棋盘在第四个子棋盘时，则首先用4号棋盘进行覆盖，这样就可以将另外三个子棋盘转化为可独立求解的子问题。
同样的k=1,2,3,4，···都是如此的，k=1为停止条件棋盘的识别问题：首先，子棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的方格在原棋盘中的行，列号就可以标识这个子棋盘了；而子棋盘中残缺方格或“伪”残缺方格直接用它们在原棋盘中的行列号标识；tr 用于标识子棋盘所在的左上角方格的所在行tc 用于标识子棋盘所在的左上角方格的所在列dr 残缺方格所在行dc 残缺方格所在列size 棋盘的行数或列数数据结构设计：用二维数组board[ ][ ]，模拟棋盘。
棋盘解题报告（noip2017普及组第三题）上次写了Linux用vim进行C++编程的配置和操作入门后，今天再给棋盘写个解题报告试试。
题目描述
有一个m ×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。
你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。
当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费1 个金币。
另外，你可以花费2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。
但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入输出格式
输入格式：
数据的第一行包含两个正整数m，n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的n 行，每行三个正整数x，y，c，分别表示坐标为（x，y）的格子有颜色c。
其中c=1 代表黄色，c=0 代表红色。
相邻两个数之间用一个空格隔开。
棋盘左上角的坐标为（1, 1），右下角的坐标为（m, m）。
棋盘上其余的格子都是无色。
保证棋盘的左上角，也就是（1，1）一定是有颜色的。
输出格式：
输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。
输入输出样例
输入样例#1：
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
输出样例#1：
8
输入样例#2：
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
输出样例#2：
-1
说明
输入输出样例1 说明
从（1，1）开始，走到（1，2）不花费金币
从（1，2）向下走到（2，2）花费1 枚金币
从（2，2）施展魔法，将（2，3）变为黄色，花费2 枚金币从（2，2）走到（2，3）不花费金币
从（2，3）走到（3，3）不花费金币
从（3，3）走到（3，4）花费1 枚金币
从（3，4）走到（4，4）花费1 枚金币
从（4，4）施展魔法，将（4，5）变为黄色，花费2 枚金币，
从（4，4）走到（4，5）不花费金币
从（4，5）走到（5，5）花费1 枚金币
共花费8 枚金币。
输入输出样例2 说明
从（1，1）走到（1，2），不花费金币
从（1，2）走到（2，2），花费1 金币
施展魔法将（2，3）变为黄色，并从（2，2）走到（2，3）花费2 金币从（2，3）走到（3，3）不花费金币
从（3，3）只能施展魔法到达（3，2），（2，3），（3，4），（4，3）
而从以上四点均无法到达（5，5），故无法到达终点，输出－1
数据规模与约定
对于30%的数据，1 ≤m ≤5，1 ≤n ≤10。
对于60%的数据，1 ≤m ≤20，1 ≤n ≤200。
对于100%的数据，1 ≤m ≤100，1 ≤n ≤1,000。
解题报告
这道题目是2017年普及组第三题，实质上是求矩阵中一个点到另一个点的最短路径，对于这类型的题目，通常可以用搜索的方法来完成，深度优先和广度优先都行，广度优先需要使用队列，稍微复杂一点，我这里就用深搜来完成。
1、输入数据，构造棋盘，总共三种颜色，0表示红色，1表示黄色，-1表示无色；
2、从（1,1）点开始，往上下左右四个方向去搜索，这里和普通的只能往右和左搜索的题目有点不同，在普通的搜索里面，到达了一个点就设一个标志变量，然后下次就不再搜索这个节点，但是这里不能这么简单的处理，因为每个节点可以往上下左右四个方向搜索，如果不设标志则会形成死循环，出不来，设个标志则有可能从不同的路径走到这个点的花费可能不相同，第一次的花费不一定是最低的。
那么我们就把进到这个节点的花费记录下来，下次进入这个节点时候，比较一下花费，如果相同或者大于上次花费，就不用搜索这个节点，否则就继续搜索他，我们把这种方法叫做记忆化搜索。
3、对于魔法问题，我们采用一点贪心策略，碰到一个无色格子，就让他变得和当前格子颜色一样，再到深搜递归函数里面加上一个参数，来表示魔法状态，如果上次已经使用了魔法，而当前格子是无色，也需要使用魔法，因为不能两次使用魔法，就直接返回。
4、当走到了右下角（m,m）点，说明已经找到了一条路径，把花费最小那条路径记录下来就OK了。
这道题目还是比较简单的，具体看代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[102][102],v[102][102],n,m,ans=999999;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};//按右下左上搜索
//搜索单元格（x,y），从（1,1）到上一单元已花费val
//上个单元颜色为c，上单元是否使用魔法mo
void dfs(int x, int y, int val, int c, bool mo)
{
if(a[x][y] == -1 && mo)//不能两次魔法
return;
if(x==m&&y==m)
{
if(a[m][m] != c)
{
temp++;
if(a[m][m]==-1)//变魔法，在原来基础上再加1 temp++;
}
if(temp<ans)
ans=temp;
return;
}
if(a[x][y]==-1)
{
val += 2;
mo=1;
}
else
{
mo=0;
if(a[x][y] != c)
{
val += 1;
}
}
if(val>=v[x][y] || val>=ans)
{
return;
}
else
{
v[x][y] = val;
int xx,yy;
for(int i=0; i<4; i++)
{
xx=x+dx[i];
yy=y+dy[i];
if(xx>=1&&xx<=m&&yy>=1&&yy<=m)
dfs(xx,yy,val,c,mo);
}
}
}
int main()
{
int i, x, y, k;
cin>>m>>n;
memset(a, -1, sizeof(a));//把a数组全部设为-1表示没有颜色memset(v, 127, sizeof(v));//把v数组设为一个巨大的数字
for(i=0; i<n; i++)
{
scanf("%d%d%d", &x,&y,&k);
a[x][y] = k;
}
dfs(1,1,0,a[1][1],0);
if(ans==999999)
cout<<-1;
else
cout<<ans;
}。
