欢迎辞欢迎来到“笃志以砺，决起而飞”！ 如果您是第一次来到本站，建议访问 本站导读以便更快地了解本站。 如果您喜欢本站， 欢迎订阅。 | 本解题报告非本人原创，程序为本人原创。转载请注明出处并保留本注释。 题目描述 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中的一个数减 [...] 之所以两道题放在一起，就是因为他们很相似。 本解题报告版权归 Ceeji 所有，转载请注名出处并保留本注释。 题目一：Count 大项堆是具有如下性质的二叉树： 1.它的任意一个父亲节点的权值总是比孩子的权值要大 2.它是一颗完全二叉树 先给定这个堆的节点个数N，假如每个节点的权值都为在1—N之间的整数且各不相同，求可能的大项堆的个数。当然，这个个数可能很多，这里只要求这个个数模K即可。 输入： 两个用空格隔开的整数N和Q（N<30,Q<10^9） 输出： 可能的大项堆的个数模Q 输入样例： 3 1000 输出样例： 2 题目二：树的同构 本解题报告版权归 Ceeji 所有，转载请注名出处并保留本注释。 排序二叉树是我们熟悉的一种数据结构，这里提到的排序二叉树都是指根的关键字比左 子树上的所有点都大，比右子树上的都小（假定不存在相同的关键字）的排序二叉树。如果 给定一个输入序列，按照这个序列依次将各个结点插入，我们就得到了一棵排序二叉树。比 如输入序列 4 2 1 3 5，对应如下排序二叉树： 2 4 5 1 3 而输入序列4 5 2 1 3 以及4 2 5 1 3都对应同样的树，我们说这三个序列同构。现在给定 一个长度为N的输入序列，求与之同构的序列有多少个（包括这个序列本身）。由于问题的 答案可能比较大，只要求输出答案 mod 10,007的结果。 Input 第1行：一个正整数N，即输入序列长度。 第2行：N个1—N之间的正整数，数字相互之间不重复。 Output 仅有一行，即同构序列数 [...] 本解题报告版权归 Ceeji，转载请保留出处和本注释。 问题描述 原始生物的遗传密码是一个自然数的序列K=(a1,…,an)。原始生物的特征是指在遗传密码中连续出现的数对（l,r），即存在自然数i使得l=ai且r=ai+1。在原始生物的遗传密码中不存在(p，p)形式的特征。 求解任务： 请设计一个程序： •从文件PIE.IN中读入一系列的特征。 •计算包含这些特征的最短的遗传密码。 •将结果写到文件PIE.OUT中。 输入： 在输入文件PIE.IN的第一行是一个整数n ，表示特征的总数。在接下来的n行里，每行都是一对由空格分隔的自然数l 和r ，1 <= l，r <= 1000。数对（l， r）是原始生物的特征之一。输入文件中的特征不会有重复。 输出： 输出文件PIE.OUT的唯一一行应该包含一个整数，等于包含了PIE.IN中所有特征的遗传密码的最小长度。 样例输入： 12 2 3 3 9 9 6 8 5 5 7 7 6 4 5 5 1 1 4 4 2 2 8 8 6 样例输出： 15 注： PIE.IN中的所有特征都包含在以下遗传密码中： (8, 5, 1, 4, [...] 昨天进行了模拟赛，很不爽，只有120分。想当然让我措失了80分，数学知识不能合理利用让我又失去了80分。懒惰也让我失去了一些分数。 从现在开始，我总结一下做题的情况和问题。将发布各题的解题报告。 第一题：不会，骗分 骗分也是一门艺术，不过只骗了20分。 我的骗分程序：（反正不会写，索性用 C++ 而不是 Pascal 写了一个骗分程序新鲜一下。） /* Cheat By Ceeji XD */ #include <cstdio> using namespace std; int n,q; int main() { freopen(“count.in”,”r”,stdin); freopen(“count.out”,”w”,stdout); scanf(“%d”,&n); scanf(“%d”,&q); if (n==1) { printf(“%d\r\n”,(1 % q)); } if (n==2) { printf(“%d\r\n”,(1 % q)); } if (n==3) { printf(“%d\r\n”,(2 % q)); } if (n==4) { printf(“%d\r\n”,(3 % q)); } if (n==5) { printf(“%d\r\n”,(8 % q)); } if (n==6) { printf(“%d\r\n”,(20 % q)); } if (n>6) { printf(“%d\r\n”,5); } fclose(stdin); fclose(stdout); return 0; } /* <br/> Cheat By Ceeji XD<br/>*/<br/>#include <cstdio><br/>using namespace std;<br/>int n,q;<br/>int main()<br/>{<br/> freopen(“count.in”,”r”,stdin);<br/> freopen(“count.out”,”w”,stdout);<br/><br/> scanf(“%d”,&n);<br/> scanf(“%d”,&q);<br/><br/> if (n==1) { printf(“%d\r\n”,(1 % q)); }<br/> [...] 本解题报告版权归 Ceeji，转载请注明出处并保留本注释。 题目描述 有N个字符串，只包含大写字母‘A’-‘Z’，要求从中找到若干个字符串，使得这些字符串包含的每个字母的个数和都为偶数，即，这些选出的字符串包含偶数个‘A’，偶数个‘B’，偶数个‘C’……且选出的字符串个数最多。 输入： [...] | |
近期评论