来源：“歌尔创客杯”第二届哈尔滨理工大学（荣成）程序设计竞赛 题目 小L和小M在下棋。这张棋盘是 n×m 的。每一个格子要么是黑色的，要么是白色的。两个人轮流进行操作。小L先手。每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，构成一个矩阵，将这个矩阵的所有黑色变成白色，所有白色格子变成黑色。如果找不到一个黑色的格子，那么那个人就输了。请问谁能赢呢。 解题思路 推测：每一次操作无论先选中哪个黑色格子，都不影响最终结果。那么，每一次操作都选择接近棋盘右下角的那个黑色格子。这样，这个格子变成白色后不再会变成黑色。如果每次操作，都对 board 进行颜色转换，那么时间复杂度会是 ...

解题思路 有 n 个神奇的恶魔果实，每个恶魔果实有一个改变数字的能力，可以把数字 a 变成数字 b。给定一个正整数 x，吃完这些恶魔果实后，可以把数字 x 变成多少种的数。注：每一个恶魔果实的能力可以重复使用多次，当然也可以不用，存在相同能力的恶魔果实。 使用 vis 记录数字 a 可以变成的数字，并计算数字的种类 cnt。计算整数 x 中每个数字能变成的数字个数（包括这个数字本身）。假设 x 中有 k 个数字，第 1 个数字能变成的数字个数为 ，第 2 个为 ，...，第 k 个为 。根据组合数学的乘法规则，最终结果即为 。 C++代码 #include<cstdio> #inc...

解题思路 有一个 n * m 大小的01迷宫，0表示这个位置可以走，1表示有障碍物不能走。现在需要从起点 (1,1) 走到终点 (n,m)。如果可以走到终点，求出走的最少步数，并记录如何走到终点的。如果有多条路径步数一样，选择走字典序最小的那条。数据保证起点和终点都是 0。 使用 BFS 算法，并将方向按照字典序排序，这样保证路径的字典序最小。令使用 pre 记录到达点 (a,b) 的前一个点 (x,y)，这样可以从终点到起点还原路线。 C++代码 #include<iostream> #include<vector> #include<queue> #in...

解题思路 有一个长度为 n 的字符串（仅包含小写字母），把这个字符串每隔 k 个就分出来一个子串，比如 [1,k] 为第一个子串，[k+1,2k] 为第二个、[2k+1,3k] 为第三个.....（保证n%k=0）求：把这些子串都变成一样的最少操作次数。 对所有子串的第 1 个字符，求出哪个字符最多，然后把其他不同的字符转换为该字符。这要使这些子串的第 1 个字符相等，这样操作次数最少。同理，对所有子串的第 2 个至第 k 个字符，使用同样的操作。然后把这些操作次数相加起来就是最终答案。 C++代码 #include<iostream> using namespace std; ...

解题思路 题目中的阴影面积为 。 C++代码 #include<iostream> #include<iomanip> using namespace std; const long double pi = 3.1415926535; int main(){ int n; while(cin >> n){ long long square = 1LL * n * n; long double ans = (pi - 2) * square / 2.0; cout << fixed...

解题思路 现有 、、 三个正整数，是否存在一个正整数 ，使得 成立。 上面的等式化为 ，所以 。 C++代码 #include<iostream> using namespace std; int main(){ int T, a, b, c; cin >> T; while(T--){ cin >> a >> b >> c; long long bc = 1LL * b * c; if(bc % a == 0){ long long ...

题目：救救AR来源：西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛 解题思路 输出一个长度不超过 n 的字符串，这个字符串存在 n 个子序列是 "AR"。子序列的定义：从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列，这样的新序列称为最初序列的子序列。 最初的序列可以表示为 AR...RA...AR...R，即 1 个 A，k 个 R，i-1 个 A，j 个 R。这样，有 i * j + k 个子序列是 "AR"。此时序列的长度为 i + j + k。 C++代码 #include<iostream> using namespace std; ...

题目：签到题来源：西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛 解题思路 在 1 ~ n 之间随机生成长度为 n 的整数序列，请问正好含有 n-1 个不同的整数的方案数，答案 mod 1e9+7。 排列组合：首先从 n 个数中选出 n-1 个数，C(n, n-1) = n。再从 n-1 个数中选出 1 个数，这个数是重复值，C(n-1, 1) = n-1。从 n 个位置中选出两个位置放置 2 个重复值，C(n, 2) = n(n-1)/2。对剩下的 n-2 个数进行排列，A(n-2, n-2) = (n-2)!。将上述的值相乘，取模，即为所求。 C++代码 #include<io...

解题思路 先辈家里有 n 个大小为 1 的面包和 m 个大小为 2 的面包，先辈要求后辈把所有面包吃完。后辈每吃一块面包，就会积累等同面包大小的饱腹值，当后辈的饱腹值 > k 时，就会因为吃太撑没力气昏倒。后辈可以选择喝一次红茶消除当前所有的饱腹值，求后辈想在不昏倒的情况下，喝红茶的最少次数。 如果 k 为偶数，喝红茶次数为 cnt = (n + 2 * m) / k。如果余数为 0，表示喝茶 cnt - 1 次后，清空饱腹值，还吃了 k 大小的面包，此时饱腹值为 k，没有昏倒，也不需要吃了，所以也不需要喝最后一次茶，所以 cnt -= 1。 如果 k 为奇数，可以吃大小为 2 的面包至...

解题思路 给出 n 个组，第 i 组有 m 个数。一组数的权值表示为该组数所有数的乘积，找出权值最大的组，输出权值对 mod 取模后的值。对于每组数据中的每个数 val，保证 val 是 k 的非负整数次幂。 。求出每组数的幂次之和 sum，最大的 sum 记为 ma。则最大权值为 。函数 myPow(k, n, mod) 是计算 k 的 n 次方的值，并对 mod 取模。 C++代码 #include<cstdio> #include<algorithm> using namespace std; long long myPow(int k, int n, long...

解题思路 给一个长度为 n 的序列 a，一开始有一个数 A = 0，每次可以从序列中选一个数 b，令 A = A + b 或者 A = A * b，每个数都要使用一次，加的次数要和乘的次数相同，要求最大化 A，输出 A 对 998244353 取模的值。 对序列 a 进行排序，将前 n/2 个数相加，再依次乘以后面 n/2 个数。 C++代码 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int mod = 998244353; int ...

解题思路 搭建一座宽度为 n 的大厦，大厦可以看成由 n 块宽度为1的积木组成，第 i 块积木的最终高度需要是 h[i] 。在搭建开始之前，没有任何积木（可以看成 n 块高度为 0 的积木）。接下来每次操作，可以选择一段连续区间 [L, R] ，然后将第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加 1 。求建造大厦的最少的操作次数。 递归：每次都选择最大限度的连续区间 [left, right]，其最小的高度为 mi，其所在的下标记录在 vmin。这时，操作 mi 次，计入 cnt，vmin 中的下标位置已经达到所需高度。将区间从 [left, right] 以 ...

解题思路 rqy和clccle一起刷题。因为clccle太弱了，所以说她会跳过难度较高（h >= a）的题目，同时，如果clccle的时间不足以切掉当前这道简单题（ct < T[i]），那么她同时也会跳过这道简单题目。相对的，rqy要花掉两倍的时间去切掉一道难度较高（h >= b）的题目，但如果时间不够用（rt < 2*T[i]），她会跳过这道题目。有一个特殊规定，她们只会按给定的顺序刷，现在两人的刷题列表是一样的，请求出在给定时间里clccle和rqy各最多能刷多少道题目。 C++代码 #include<cstdio> #include<vector...

题目：EndAs GPA来源：吉林大学ACM集训队选拔赛（重现赛） 解题思路 期末成绩 GPA 计算 。如果结果为 4.0，则输出 Yes，否则 No。绝对误差小于 。 C++代码 #include<cstdio> #include<vector> #include<cmath> using namespace std; int main(){ int n; scanf("%d", &n); vector<int> a(n), p(n); for(int i=0; i<n; ++i) ...