P3893【概率】聪聪和可可问题描述 输入格式 数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。输入保证任何两个景点之 ...

P3805距离问题描述 对于两个正整数a、b，这样定义函数d(a,b)：每次操作可以选择一个质数p，将a变成a*p或a/p， 如果选择变成a/p就要保证p是a的约数，d(a,b)表示将a变成b所需的最少操作次数。例如d(69,42)=3。 现在给出n个正整数A1,A2,…,An，对于每个i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj ...

P3804机器人 M 号问题描述 3030 年，Macsy正在火星部署一批机器人。第 1 秒，他把机器人 1 号运到了火星，机器人 1 号可以制造其他的机器人。第 2 秒，机器人 1 号造出了第一个机器人——机器人 2 号。第 3 秒，机器人 1 号造出了另一个机器人——机器人 3 号。之后每一秒，机器人 1 号都可以造出一个新的机器人。第 m 秒 造 出的机器人 编号为 m。我们可以称它为机器 ...

P3614【CQOI2016 Day2】密钥破解 问题描述 一种非对称加密算法的密钥生成过程如下： 1.任选两个不同的质数p,q； 2.计算N=pq，r=(p-1)(q-1)； 3.选取小于r，且与r互质的整数e； 4.计算整数d，使得ed≡1 mod r； 5.二元组(N,e)称为公钥，二元组(N,d)称为私钥。 ...

P3616【CQOI2016 Day2】伪光滑数 问题描述 若一个大于1的整数M的质因数分解有k项，其最大的质因子为$a_k$，并且满足$a_k^k$≤N，$a_k$<128，我们就称整数M为N-伪光滑数。 现在给出N，求所有整数中，第K大的N-伪光滑数。 输入格式 输入文件内容只有一行，为用空格隔开的整数N和K。 输出格式 输出文件内容只有一行，为一个整数，表示答 ...

P3611【CQOI2016 Day1】不同的最小割 问题描述 学过图论的同学都知道最小割的概念：对于一个图，某个对图中节点的划分将图中所有节点分成两部分，如果节点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的权值相加所得到的定义为这个割的容量，而s,t的最小割指的是在关于s,t的个中容量最小的割。 而对冲刺NOI竞赛的选手而言，求带权图中两点的 ...

P4040小Q 的表格 问题描述 题目给出了一个有规律的表格，因此我们先随便修改一个数找一下所有被修改的数之间有没有什么规律，很容易发现好像被修改的数的行号和列号的gcd是一样的，于是我们考虑证明，实际上我们的修改过程和辗转相减的过程是一样的，因此很容易得证。接着我们来考虑gcd一样的这些格子的数有什么特点，容易发现他们的倍数关系是固定的，等于行号列号乘积之商，所以我们用 $A[d]$ 表 ...

P4042老C的方块 问题描述 此题比较明显可以想到图论，由于是经典的棋盘问题，我们观察四种讨厌的形状，发现这四种形状有一个共同特点，即都可以看成以特殊边为邻边的两个方块各自再连上一个方块，然后我们发现，特殊边的分布刚好是配合这个规律的，于是我们将棋盘染色 染色很丑陋，因为是我故意的。简单说一下，我们将格子分成4类，分别是四种颜色，我们发现，如果一个图形是讨厌的，那么一定满足这个图形是黄- ...

P4043老C的键盘 此题由于给出的字符串，很容易想到变成一颗树，于是容易想到树形DP。 注意到将1-n分配到一棵树的时候，数的具体值是没有意义的，因此每一次往下分都可以认为是将1-size的排列分到这颗子树上。 因此，为了计算方案数，我们需要确定根的取值，再确定将哪些数分到左子树上，另一些分到右子树上，然后组合数乘一下，再乘上左子树和右子树各自的DP值。 注意到题目给出的限制是关于儿子和父 ...

C. Strange Radiation n people are standing on a coordinate axis in points with positive integer coordinates strictly less than 106. For each person we know in which direction (left or right) he is f ...