题意： 自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 = 625，76^2 = 5776，9376^2 = 87909376。请求出n(包括n)以内的自守数的个数 解法（循环加判断） 枚举从0~n所有数字，分别判断每个数字是否满足条件即可。 具体的，我们假设当前枚举到数字 我们设变量 由于数字是非负数，显然，其中bit(x)表示数字x在十进制下的位数 我们按照『数字翻转』的while循环写法来写，循环条件为，每次分别取出当前x和y的个位，即和，要满足在循环中每次取出的个位都相等，即可把答案+1 代...

题意： 输入n个整数。输出为n个整数中负数的个数，和所有正整数的平均值，结果保留一位小数。 解法（循环，判断） 记变量表示负数的数量， 变量表示正数之和， 变量表示正数的数量。 显然上述三个变量只需要扫描一遍整个数组即可求出来，最后按照题意计算输出即可。 代码： #include<bits/stdc++.h> using namespace std; int main(){     ios::sync_with_stdio(false);   &n...

题意： 输入一个字符串，在字符串中所有连续的数字子串左右各加一个*，输出处理后的字符串。 解法（while循环） #include<bits/stdc++.h> using namespace std; int main(){     ios::sync_with_stdio(false);     string s;     while(cin>>s){    &n...

题意： 输入一个数字金额，输出其中文表示法。 解法（高精度版本） 本题解中我们实现一个支持任意大小数字的转换程序 我们举个例子，比如数字： 该数字的中文表示法为： 首先，我们将该数字从右到左四个四个分块，不足的部分单独一块 可得到： 对应的，我们再将中文表示法按照对应数字进行分块： 我们可以发现，我们从右到左从第二块开始，分别给每一块加一个『单位』（万、亿、万亿、亿亿、万亿亿、亿亿亿、万亿亿亿......）后，再在『单位』前加上当前块的数字的中文表示法，就是答案。 所以，我们只需要求出最多四位数字对应的中文表示法然后再...

题意： Alice有张石头牌、张剪刀牌、张布牌， Bob有张石头牌、张剪刀牌、张布牌， 其中获胜得1分，平局不得分也不扣分，失败扣1分。 你可以随意安排出牌策略，问Alice最多可以得多少分？（可能是负数） 解法一（暴力模拟） 我们按照『能获胜就获胜，不能获胜就平局，实在不行才失败』这样一个贪心策略来，显然这样得分一定是最高的。 一. 我们首先考虑获胜的情况     1. Alice出石头，Bob出剪刀。     2. Alice出剪刀，Bob出布。     3. Alice...

题意： Alice有张石头牌、张剪刀牌、张布牌， Bob有张石头牌、张剪刀牌、张布牌， 你可以随意安排出牌策略，问你Alice最多可以胜Bob多少回？ 解法一（暴力模拟） 题目叫我们求获胜的次数，故我们只考虑获胜的情况。     1.  Alice出石头：         我们此时让Bob出剪刀     2. Alice出剪刀         我们此时让Bob出布 &...

题意： 定义，求 解法一（递推法） 我们设，显然有 我们发现，那么我们可设，显然有 同理我们可得，设，显然有 于是我们就可以做到用线性复杂度求解本题了。 代码： class Solution { public:     const int mod=1e9+7;     int f[1000000001];     int T[1000000001];  ...

题意： 给你一个大小为的网格图，其中有一块矩形区域（左上角位置为，右下角位置为）不能走，起点在处，每次你只能向右或者向下走，问最后走到终点有多少种方案？ 解法一（DFS暴力枚举，不可AC） 我们可以用深度优先搜索算法枚举所有的路线，并且统计答案。 具体的：     我们用递归函数表示当前走到点，接下来我们开始讨论：     1. 点超出网格图范围，直接返回     2. 点处在不可走的矩形区域范围，直接返回     3. 点处在终点处，答案+1并返回 &nbsp...

题意： 有个格子，每个格子都可以填写四个整数，现在问你有多少种方案，使得最后所填数字中相同的偶数出现的次数也是偶数次？ 解法一（动态规划，不可AC） 我们设：     表示前个格子有偶数个和偶数个的方案数     表示前个格子有偶数个和奇数个的方案数     表示前个格子有奇数个和偶数个的方案数     表示前个格子有奇数个和奇数个的方案数 一.  我们考虑转移   &n...

题意： 给你一个数，判断这个数是不是某个平方数对取模的结果 解法一（扩展欧几里得） 我们记这个平方数为 由 可得 显然这是一个不定方程，于是我们可以用扩展欧几里得算法求解 具体的，我们可以解出的解 于是原方程的一个解为： 我们设，则的通式为 于是我们只需要最多枚举到判断即可 代码： class Solution { public:     /**      *   &nbsp...

题意： 给你一个长度为的序列，第个数字代表了一段连续的区间， 其中这些区间满足要么完全覆盖，要么不相交， 现在每次等概率地随机选择一个点，并且将区间全部打上标记， 问期望多少次能将整个序列都打上标记（答案对998244353取模）？ 解法一（问题转化+暴力求解） 做这道题我们需要注意到这个性质：『其中这些区间满足要么完全覆盖，要么不相交』 一个区间可以被另外一个区间完全覆盖，我们可以想到『父-子』级关系，再加上两个区间完全不相交，我们可以想到两棵子树完全不相交 那么我们可以根据题目给的序列，构建出一棵树，其中第个节点若被标记，则以第个节点为根节点...

题意： 给你一个无限长的数轴，刚开始你在位置处，你每次可以向左或者向右移动个单位，现在有次询问，第次询问给你一个数字，问从起点位置到所在位置最少需要多少步？ 解法一（最短路，不可AC） 显然我们可以根据题意构建一张以数轴上的数字为点，边权为的无向图，边表示数字变化成数字的一次操作 那么对于第个询问，答案为起点到点的最短路 代码： class Solution { public:     vector<int> MinimumTimes(vector<int>&amp...

题意： 定义数列，，，求的值 解法一（暴力递推，不可AC） 一个显然的做法就是直接循环一遍递推过去求的值 代码： class Solution { public:     const int mod=1e9+7;     long long nthElement(long long n, long long b, long long c) ...

题意： 有个人，第个人办理事务需要时间，刚开始（时间点为）有个空闲窗口，现在按照第个人的顺序办理事务，当某个时刻发现有空闲窗口后，第个人会到那个空闲窗口办理事务 现在设第个人办理事务的截止时间为，求数组的逆序对个数 解法一（优先队列+暴力枚举求逆序对，不可AC） 我们设第个窗口已经花费的时间为，显然对于第个人，会到最小的那个窗口进行办理事务 由此我们可以维护一个优先队列（小根堆）     1. 初始化放个0到优先队列中     2. 对于第个弹出堆顶元素，设为，则     3. 将放入队...