问题 1841: [蓝桥杯][2017年第八届真题]发现环 时间限制: 1Sec 内存限制: 128MB 提交: 653 解决: 237 题目描述 小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。 为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？ 输入 第一行包含一个整数N。 以下N行每行两个整数a...

问题 1435: [蓝桥杯][历届试题]国王的烦恼 时间限制: 1Sec 内存限制: 128MB 提交: 810 解决: 217 题目描述 C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。 如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。 现在C国的国王已经知道了每座桥能使用的天...

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。 可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！ 燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S ，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S 。 所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。 可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。 输入格式 输入包含 k 组数据。 对于每组数据，输入包含一个号码牌 S 。 输出格式 对于每组数据，输出有两行。 第一行包含一个整数 m ，表示有 m 个等的人。 第二...

输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。 输入格式 输入包含多组数据，每组数据占一行，包含一个正整数表示 X 。 输出格式 对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。 每个结果占一行。 数据范围 1≤X≤220 输入样例： 2 3 4 10 100 输出样例： 1 1 1 1 2 1 2 2 4 6 #include<bits/stdc++.h> using namespace std; const int N=(1<<20) +10...

大圣在佛祖的手掌中。 我们假设佛祖的手掌是一个圆圈，圆圈的长为 n ，逆时针记为：0,1,2,…,n−1，而大圣每次飞的距离为 d 。 现在大圣所在的位置记为 x ，而大圣想去的地方在 y 。 要你告诉大圣至少要飞多少次才能到达目的地。 注意：孙悟空的筋斗云只沿着逆时针方向翻。 输入格式 有多组测试数据。 第一行是一个正整数 T ，表示测试数据的组数； 每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n ，筋斗所能飞的距离 d，大圣的初始位置 x 和大圣想去的地方 y 。 输出格式 对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。 ...

X星球的某个大奖赛设了 M 级奖励。 每个级别的奖金是一个正整数。 并且，相邻的两个级别间的比例是个固定值。 也就是说：所有级别的奖金数构成了一个等比数列。 比如：16,24,36,54 ，其等比值为：3/2 。 现在，我们随机调查了一些获奖者的奖金数。 请你据此推算可能的最大的等比值。 输入格式 第一行为数字 N ，表示接下的一行包含 N 个正整数。 第二行 N 个正整数 Xi ，用空格分开，每个整数表示调查到的某人的奖金数额。 输出格式 一个形如 A/B 的分数，要求 A、B 互质，表示可能的最大比例系数。 数据范围 0<N<100 0<X...

X星球的一批考古机器人正在一片废墟上考古。 该区域的地面坚硬如石、平整如镜。 管理人员为方便，建立了标准的直角坐标系。 每个机器人都各有特长、身怀绝技。 它们感兴趣的内容也不相同。 经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。 矩形的表示格式为 (x1,y1,x2,y2) ，代表矩形的两个对角点坐标。 为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。 小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。 其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。 注意，各个矩形间可能重叠。 输入格式 第一行，一个整数 ...

糖果店的老板一共有 M 种口味的糖果出售。 为了方便描述，我们将 M 种口味编号 1∼M 。 小明希望能品尝到所有口味的糖果。 遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。 幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。 给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。 输入格式 第一行包含三个整数 N,M,K 。 接下来 N 行每行 K 这整数 T1,T2,⋅⋅⋅,TK ，代表一包糖果的口味。 输出格式 一个整数表示答案。 如果小明无法品尝所有口味，输出 −1 。 数据范围 1≤N...

考虑一种简单的正则表达式： 只由 x ( ) | 组成的正则表达式。 小明想求出这个正则表达式能接受的最长字符串的长度。 例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。 输入格式 一个由x()|组成的正则表达式。 输出格式 输出所给正则表达式能接受的最长字符串的长度。 数据范围 输入长度不超过100，保证合法。 输入样例： ((xx|xxx)x|(x|xx))xx 输出样例： 6 之前看题不太理解，结果就是|运算，比如xx|xxx就是3个x，取最大的，括号只是改变运算的先后。 #include<iostream&gt...

1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####—#####—#---#####—# 2 # # | # # # # # #—#####—#####—#####—# 3 # | | # # # # # #—#########—#####—#---# 4 # # | | | | # # ############################# (图 1) = Wall | = No wall = No wall 方向：上北下南左西右东。 图1是一个城堡的地形图。...

01背包 二维可以用一维滚动数组优化，只能选一个每个物品只有选和不选两种情况。 #include<iostream> using namespace std; const int N=1010; int f[N]; int w[N]; int v[N]; int main() { int n,v1; cin>>n>>v1; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++) for(int j...

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数N。 第二行包含N个整数，表示完整序列。 输出格式 输出一个整数，表示最大长度。 数据范围 1≤N≤100000 ， −109≤数列中的数≤109 输入样例： 7 3 1 2 1 8 5 6 输出样例： 4 #include<bits/stdc++.h> using namespace std; int n; const int N=100010; int q[N],a[N]; int main() { cin>>n; for(in...

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数N和M。 第二行包含一个长度为N的字符串，表示字符串A。 第三行包含一个长度为M的字符串，表示字符串B。 字符串均由小写字母构成。 输出格式 输出一个整数，表示最大长度。 数据范围 1≤N≤1000 , 输入样例： 4 5 acbd abedc 输出样例： 3 #include<bits/stdc++.h> using namespace std; const int N=1010; char a[N],b[N]; int f[N][...

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有： 删除–将字符串A中的某个字符删除。 插入–在字符串A的某个位置插入某个字符。 替换–将字符串A中的某个字符替换为另一个字符。 现在请你求出，将A变为B至少需要进行多少次操作。 输入格式 第一行包含整数n，表示字符串A的长度。 第二行包含一个长度为n的字符串A。 第三行包含整数m，表示字符串B的长度。 第四行包含一个长度为m的字符串B。 字符串中均只包含大写字母。 输出格式 输出一个整数，表示最少操作次数。 数据范围 1≤n,m≤1000 输入样例： 10 AGTCTGACGC 11 AGTAAGTAG...