1.1 题目描述
九条可怜是一个热爱思考的女孩子。
九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法：gobo sort！
Gobo sort 的算法描述大致如下：
• 1. 假设我们要对一个大小为 n 的数列 a 排序。
• 2. 等概率随机生成一个大小为 n 的排列 p 。
• 3. 构造一个大小为 n 的数列 b 满足 bi = api，检查 b 是否有序，如果 b 已经有序了就结
束算法，并返回 b ，不然返回步骤 2 。
显然这个算法的期望时间复杂度是 O(n × n!) 的，但是九条可怜惊奇的发现，利用量子的
神奇性质，在量子系统中，可以把这个算法
题目描述小 Q 正在设计一种棋类游戏。 在小 Q 设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点，编号为0,1,2 … , V− 1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小 Q 在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。 小 Q 现在想知道，当棋子从格点 0 出发，移动 N 步最多能经过多少格点。格点可以重复经过多次，但不重复计数。 输入输出格式输入格式： 第一行包含2个正整数V, N，其中 V 表示格点总数，N 表示移动步数。 接下来V − 1行，每行两
题目描述曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明：自动刷题机——一种可以自动 AC 题目的神秘装置。 自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，自动刷题机的代码生成模块会有两种可能的结果： 1.写了x行代码 2.心情不好，删掉了之前写的y行代码。（如果y大于当前代码长度则相当于全部删除。） 对于一个 OJ，存在某个固定的长度n>0，一旦自动刷题机在某秒结束时积累了大于等于n行的代码，它就会自动提交并 AC 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机，得到了很多条
题目描述 输入输出格式输入格式： 第一行有一个整数N(3<N<2000)，表示登陆地带的大小是2×N。随后的两行每一行有N个整数（其绝对值不超过10^6），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。 输出格式： 只有一行输出，为整数M，即所确定的实验基地的适用度。 输入输出样例输入样例#1： 复制4
-1 2 -3 4
5 6 7 8 输出样例#1： 复制31 不知道为什么N会是2000而不是10^6。这道题
题目背景我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。 题目描述请写一个程序： 读入所有演讲的起始和终止时间； 计算最大的可能演讲总时间； 输入输出格式输入格式： 第一行包括一个正整数n，n<=10000，为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k，0<=p&l
题目背景学校艺术节上，规定合唱队要参加比赛，各个队员的衣服颜色不能很混乱：合唱队员应排成一横排，且衣服颜色必须是左右对称的。 例如：“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的，而“红蓝绿红”或“蓝绿蓝红”就不符合要求。 合唱队人数自然很多，仅现有的同学就可能会有3000个。老师希望将合唱队调整得符合要求，但想要调整尽量少，减少麻烦。以下任一动作认为是一次调整： 题目描述1、在队伍左或右边加一个人（衣服颜色依要求而定）； 2、在队伍中任两个人中间插入一个人（衣服颜色依要求而定）； 3、剔掉一个人； 4、让一个人换衣服颜色； 老师想知道就目前的队形最少的调整次数是多少，请你编一个程序来回答他。 因
题目描述很久以前，有一个传说中的“EWF”部族，他们世代生活在一个N×M的矩形大地上。虽然，生活的地区有高山、有沼泽，但通过勤劳勇敢，渐渐地，他们在自己的地盘上修筑了一条回路。 后来，“EWF”部族神秘地消失了。不过，考古学家在那片他们曾经生活过的地方找到了一份地图。地图是N×M的矩阵，左上角的坐标为(0, 0)，右下角的坐标为(N, M)。矩阵中的每个格子，表示高山、沼泽、平地、房屋或是道路其中之一。如果一个格子表示道路，那么经过这个格子的道路要么是直走，要么是拐弯。如下图，左边2幅表示直走格子的，右边4幅表示需要拐弯的格子。一个表示道路的格子只能表示下列情况之一。 可是，由于地图的年代久
题目描述参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。 同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。 他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市
题目描述这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！ 输入输出格式输入格式： 一行包含两个整数N，M，之间由一个空格隔开。 输出格式： 总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。 输入输出样例输入样例#1： 复制1 3 输出样例#1：&nbs
题目描述windy学会了一种游戏。 对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。 最开始windy把数字按顺序1，2，3，……，N写一排在纸上。 然后再在这一排下面写上它们对应的数字。 然后又在新的一排下面写上它们对应的数字。 如此反复，直到序列再次变为1，2，3，……，N。 如： 1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6 windy的操作如下 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6
Rockdu's Blog