题目 在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，求覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 解题思路 第 i 张地毯的左下角点坐标为 (c[i][0], c[i][1])，右上角点坐标为 (c[i][2], c[i][3])。从第 n 张地毯遍历到第 1 张，如果地毯覆盖在所求的点 (x,y) 上，则这张地毯是最上面的地毯，记录下编号，退出循环。 C++代码 ...

题目 要买 n 件物品，其中有一些是凳子。商场正在举行促销活动，如果购物车中有至少一个凳子，那么可以半价购买这个购物车中最贵的一个物品。现有 m 辆购物车，求最少的花费。 解题思路 将非凳子的价格录入 item1，将凳子的价格录入 item2。对 item1 和 item2 进行从大到小排序。 如果还有新的购物车，将价格最贵的物品放入其中， 如果该物品是凳子，价格减半。 如果不是凳子，将价格最小的凳子放入其中，最贵的物品价格减半；如果没有凳子，物品原价。 如果没有新的购物车，将剩下的东西随便放置其中一个购物车，物品原价。 C++代码 #include<cstdio> #incl...

题目 有一张 个点的带权无向图，这张无向图是一张完全图。第 个点有一个点权 ，边 的权值为 。找一个这张图的边权之和最小的生成树。 解题思路 生成树有 n-1 条边，每个的点权至少要加一次。选取点权最小的那个点作为根节点，将其他的点都作为该节点的子节点，即是边权之和的最小生成树。注意：当只有 1 个点时，没有边，边权之和为 0。 C++代码 #include<iostream> using namespace std; int main(){ int n; cin >> n; int a; int m = 1e9+1; l...

题目 求正整数 N 的阶乘的最后面的非零位。 解题思路 两个整数 a 和 b 相乘后的的值的个位数的值，只与 a 和 b 个位数上的值有关。 C++代码 #include<iostream> using namespace std; const int M = 1e5; int main(){ int N; cin >> N; int ans = 1; for(int i=2; i<=N; ++i){ ans *= i; while(ans % 10 == 0){ ans ...

题目 给定一个多项式 ，请求出多项式展开后 项的系数。 解题思路 由二项式定理，得 。所以， 项的系数为 。 函数 power(x,n) 返回 ，并对 mod 取模。。 函数 C(x,y) 返回 ，并对 mod 取模。。 C++代码 #include<iostream> using namespace std; const int mod = 10007; long long power(int x, int n){ x %= mod; if(x==1) return 1; if(n==0) return 1; ...

题目 给定两个正整数 a 和 b，求 a 和 b 的最小公倍数。 解题思路 求出 a 和 b 的最大公约数 c，则最小公倍数为 a*b/c。 C++代码 #include<iostream> #include<algorithm> using namespace std; typedef unsigned long long ULL; int main(){ ULL a, b; cin >> a >> b; ULL c = __gcd(a, b); ULL ans = a / c * b; cout &...

题目 给出一个数 n，求 1 到 n 中，有多少个数不是 2、5、11、13 的倍数。 解题思路 根据容斥原理，先不考虑重叠的情况，把 2、5、11、13 的所有倍数的数目先计算出来，然后再把计数时重复计算的数目排斥出去。所以，1 到 n 中，这四个数的倍数的总数为cnt = n/2 + n/5 + n/11 + n/13- n/(2*5) - n/(2*11) - n/(2*13) - n/(5*11) - n/(5*13) - n/(11*13)+ n/(2*5*11) + n/(2*5*13) + n/(2*11*13) + n/(5*11*13)- n/(2*5*11*13)。最终结果...

题目 给出一个数 x，判断它是否为素数，并输出所有它的素因子。 解题思路 使用筛法求素数会内存超限。所以，使用试除法求素数：令 i 的取值范围为 [2, sqrt(x)]，若 i 能整除 x，则 x 不是质数，记录因子。 C++代码 #include<iostream> #include<cmath> #include<vector> using namespace std; int main(){ int T; cin >> T; int x; while(T--){ cin >> ...

题目 现在给出一个素数，这个素数满足两点：①只由 1-9 组成，并且每个数只出现一次，如 13，23，1289。②位数从高到低为递减或递增，如 2459，87631。请判断，这个素数的回文数是否为素数（13 的回文数是 131，127 的回文数是 12721）。 解题思路 先求出这个素数的回文数 t，再从 2 到 sqrt(t) 遍历 i，如果 i 能整除 t，则 t 不是素数。 C++代码 #include<iostream> #include<cmath> using namespace std; int main(){ long long t; ...

题目 现在有 个点构成的点集 ，每个点有点权 。想用这 个点构造 个无向图 。对于第 个无向图，牛妹指定了一个参数 。牛妹规定 当且仅当 ，其中 表示二进制按位异或运算。对于第 个无向图，求 到 的最短路径长度，。 解题思路 对于任意 3 个整数 ，若 ，则有 ，。 如果 a[x] ^ k == a[y]，表示 (x,y) 是无向图中的一个边，距离为 1。 如果上述条件不成立，判断 a[x] ^ k 是否存在，如果不存在，表示这个点是独立的，返回 -1。如果存在，判断 a[x] 与 a[y] 是否相等，如果相等，表示点 x 和 y 都与权值为 a[x]^k 的点相邻，所以距...

题目 求出一个正整数 ，满足 可以表示成 （ 是正整数），使得 的值最小。 解题思路 使用 sqrt() 函数将 y 开平方，得到一个整数 a，则有 。距离 y 最近的完全平方数在 和 其中的一个。 C++代码 #include<iostream> #include<cmath> using namespace std; int main(){ long long x; cin >> x; long long a = sqrt(x); long long y = a*a; long long y2 = (a+...

题目 现在规定，若两个数 x 和 y 具有相同的奇偶性，或者 |x-y|=1，则称它们相似。给定一个由 n 个正整数构成的数组（n 是偶数）。检查数组是否有这样的成对划分，即数组的每个元素恰好属于一对，并且每对中的数字彼此相似。 解题思路 如果 n 个数中奇数的个数为偶数，则可以根据奇偶性划分对。否则，需要查找是否有存在两个整数满足 |x-y|=1，若存在，则这两个数属于一对，其他根据奇偶性划分对。如果上面两个条件均不符合，则不能成对划分。 C++代码 #include<iostream> #include<vector> #include<algorithm&g...

题目 在一个大小为 n×n 网格的森林里，每个格子中，都放有一个宝藏，其中 n 是奇数。求把这些宝藏都集中到同一个单元格中的最小移动次数。在一次移动中，可以选择某个单元格中的一个宝藏，将其移动到相邻的 8 个格子中的一个。不能将宝藏移出森林。 解题思路 将所有宝藏都移动到网格的最中心的位置。 中心的相邻的第 1 层有 2 * 4 = 8 个格子，每个格子移动到中心的最少次数都是 1。中心的相邻的第 2 层有 4 * 4 = 16 个格子，每个格子移动到中心的最少次数都是 2。依此类推，中心的相邻的第 i 层有 (2 * i) * 4 个格子，每个格子移动到中心的最少次数都是 i，这些格子移动总...

题目 给定两个字符序列 a 和 b，求 b 在 a 中出现的次数。a 中的每个字符只能出现在零个或一个 b 字符序列中，每组字符序列 a 和 b 输入在一行中，以空格分隔。如果遇见 # 字符，则不再进行工作。 示例：输入 abcde a3 aaaaaa aa #输出 0 3解题思路 从头到尾遍历 a，一旦遇到与 b 相符的序列，就计数 cnt。 C++代码 #include<cstdio> #include<vector> using namespace std; int main(){ vector<char> a, b; char c...