东溪看水

题解

/ 注册

全部文章 / 题解（共169篇）

【每日一题】毒瘤xor

题目有个数，给出个询问，每次询问给出区间，现在请找到一个数，使得最大，表示异或操作。解题思路要使条件 2 成立，需要求出区间中，所有数值的二进制表示的 31 位，每位 1 的个数。如果某位 0 的个数大于 1 的个数，那么所求在该位上取 1，否则取 0。计算...

前缀和位运算每日一题

2020-07-04

3 668

铺地毯

题目在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，求覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四...

2020-07-03

0 573

Shopping

题目要买 n 件物品，其中有一些是凳子。商场正在举行促销活动，如果购物车中有至少一个凳子，那么可以半价购买这个购物车中最贵的一个物品。现有 m 辆购物车，求最少的花费。解题思路将非凳子的价格录入 item1，将凳子的价格录入 item2。对 item1 和 item2 进行从大到小排序。如果...

贪心

2020-07-03

0 653

最小生成树

题目有一张个点的带权无向图，这张无向图是一张完全图。第个点有一个点权，边的权值为。找一个这张图的边权之和最小的生成树。解题思路生成树有 n-1 条边，每个的点权至少要加一次。选取点权最小的那个点作为根节点，将其他的点都作为该节点的子节点，即是边权之和的最小生成树。注意：当只有 ...

树图

2020-07-03

0 654

阶乘

题目求正整数 N 的阶乘的最后面的非零位。解题思路两个整数 a 和 b 相乘后的的值的个位数的值，只与 a 和 b 个位数上的值有关。 C++代码 #include<iostream> using namespace std; const int M = 1e5; int ma...

数学

2020-06-30

1 514

计算系数

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

数学排列组合

2020-06-30

0 564

最大公约数(lcm)

题目给定两个正整数 a 和 b，求 a 和 b 的最小公倍数。解题思路求出 a 和 b 的最大公约数 c，则最小公倍数为 a*b/c。 C++代码 #include<iostream> #include<algorithm> using namespace std; ...

gcd

2020-06-30

0 542

大水题

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

容斥原理

2020-06-30

1 603

素数判断

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

数学素数

2020-06-30

1 1156

素数回文

题目现在给出一个素数，这个素数满足两点：①只由 1-9 组成，并且每个数只出现一次，如 13，23，1289。②位数从高到低为递减或递增，如 2459，87631。请判断，这个素数的回文数是否为素数（13 的回文数是 131，127 的回文数是 12721）。解题思路先求出这个素数的回文数 t...

数学素数

2020-06-30

1 1389