路径统计
题目描述
你有一棵 \(n\) 节点的树 \(T\)，回答 \(m\) 个询问，每次询问给你两个整数 \(l\),\(r\)，问存在多少个整数 \(k\) 使得从树上编号为 \(l\) 的点沿着 \(l→r\) 的简单路径走 \(k\) 步恰好到达 \(k\) 。
输入格式
第一行，两个整数 \(n,m\) 表示节点数和询问数。
之后 \(n?1\) 行，每行两个整数 \(u,v\) 表示一条边。
之后 \(m\) 行，每行两个整数 \(l,r\) 表示 一个询问，题意同题目描述。
输出格式
\(m\) 行，对于每个询问单独输出一行表示你的答案。
样例 #1
样例输入 #1
9 3
5 4
4 3
3 7
4 1
1 6
1 8
1 9
5 2
6 7
2 3
3 2
样例输出 #1
2
1
0
提示
样例解释
如图，红色表示第一次询问中 \(k=0,1,…,4\) 的情况，蓝色表示第二次询问，绿色是第三次询问。
其中，在第一次询问中：
-
走 \(0\) 步到达 \(6\)，不符题意。
-
走 \(1\) 步到达 \(1\)，满足题意。
-
走 \(2\) 步到达 \(4\)，不符题意。
-
走 \(3\) 步到达 \(3\)，满足题意。
-
走 \(4\) 步到达 \(7\)，不符题意。
数据范围
| 测试点编号 | \(n≤\) | \(m≤\) | 特殊性质 |
|---|---|---|---|
| \(1～3\) | \(10\) | \(10\) | \(AC\) |
| \(4～6\) | \(100\) | \(100\) | \(AC\) |
| \(7～10\) | \(500\) | \(500\) | \(ABC\) |
| \(11～13\) | \(10^4\) | \(10^4\) | \(AB\) |
| \(14～16\) | \(10^5\) | \(10^5\) | \(AB\) |
| \(17～20\) | \(3×10^5\) | \(3×10^5\) | 无 |
\(A\) ： 一条链
\(B\) ： 深度不超过 \(50\)
\(C\) ： 将 \(1\) 作为根时会形成一棵二叉树
字符串变换
题目描述
\(Fly\) 在批改作业的时候发现大家的提交的文件名都很不规范，这让他很头疼。作为一个强迫症患者，他决定手动规范大家的文件名。但是有些人的文件名特别长，他想要知道最少需要修改多少次才能够使得字符串 \(A\) 变成字符串 \(B\) 。当然对于修改代价超过 \(K\) 的文件名我们会选择放弃。
每次修改可在 \(A\) 中添加或删除一个字符。
输入格式
输入共包含 \(3\) 行。
第 \(i\) 行包含三个整数 \(n\) , \(m\) , \(K\) ，分别表示原始串 \(A\) 的长度 \(n\) ,目标串 \(B\) 的长度 \(m\) 和限制的最大修改次数 \(K\) 。
接下来 \(2\) 行，分别输入原始字符串 \(A\) 和目标字符串 \(B\)。
输出格式
输出共包含 \(1\) 行，如果最小修改次数小于等于 \(K\) ，则输出最少修改次数，不然输出 \(?1\) 。
样例 #1
样例输入 #1
3 4 2
bee
beef
样例输出 #1
1
提示
对于其中 \(25\%\) 的数据，\(n,m \leq 10\) 。
对于其中 \(50\%\) 的数据，\(n,m \leq 1000\) 。
对于另外 \(25\%\) 的数据，\(K \leq 10\) 。
对于 \(100\%\) 的数据，满足 \(0 \leq n,m \leq 500000,0 \leq K \leq 100\) 。字符串中只包含小写字母。
染色
题目描述
有长度为 \(n\) 的一个序列，编号为 \(1\) 到 \(n\) ，现要对这些元素进行染色标记，若编号 \(i-j\) 为素数，且 \(1\leq i < j \leq n\) ，则 \(i\) 和 \(j\) 必须染上不同的颜色。
是否存在一种方案使得颜色尽可能少呢，请输出该方案
如有多种，则输出任意一种。
输入格式
第一行一个整数 \(n\) 。
输出格式
第一行一个整数 \(k\) ，表示所用的颜色数。
第二行 \(n\) 个整数 \(col_i\)（ \(1 \leq col_i \leq k\) ），表示 \(i\) 的颜色。
样例 #1
样例输入 #1
7
样例输出 #1
4
1 2 2 3 3 4 1
提示
对于 \(30\%\) 的数据，\(n \leq 10\)；
对于 \(60\%\) 的数据，\(n \leq 20\)；
对于 \(100\%\) 的数据，\(n \leq 10^4\)。
对数计数
题目描述
对于两个数字 \(a\) 、\(b\) ，有多少 \(x\) ，能够满足 \(x^b<=a\) 。
输入格式
一行两个正整数 \(n\) , \(m\) 。
输出格式
一个整数表示正整数 \(x\) 的个数。
样例 #1
样例输入 #1
5 2
样例输出 #1
3
提示
对于 \(25\%\) 的数据满足 \(m=1\) ；
对于 \(50\%\) 的数据满足 \(n<=10^6\) ；
对于 \(100\%\) 的数据满足 \(1<=n,m<=10^9\) 。
标签：11,10,26,题意,输出,样例,整数,leq,Round From： https://www.cnblogs.com/SkyMaths/p/16947693.html