首先把去年的官方题解摆在这里大家可以看看19软卓选拔官方题解
在我的题解里，我会把所有题目的代码进行力所能及的逐句分析
（4.21晚有修改，更新了c题题解）
软卓选拔A 涛哥补足精神
软卓选拔A
这题没有考什么算法，就是一道考基础的模拟题，但是题意的确有些绕。写出这题还是需要比较扎实的c++基本功的
#include<iostream>
#define ll long long
using namespace std;
int main()
{
ll t = 0;//根据题意，有10%的数据在longlong类，因此答案需要用longlong
cin >> t;//t次询问
while (t--)
{
ll a, b, c, d,ans=0;
cin >> a >> b >> c >> d;//定义与输入
if (a <= b)//如果需要的睡眠小于第一次闹钟的响铃时间便在第一次闹钟响起后醒过来
{
cout << b << endl;//输出答案
continue;//进入下一次循环
}
else
{
if (c <= d)//如果再一次入睡时间要大于响铃时间则再也起不了床
{
cout << "-1" << endl;//按照题意输出-1
continue;
}
else//这是能起床的情况
{
ans = b;//先把答案初始化为第一次闹铃响起的时间
a -= b;//更新还需要睡眠的时间
ll k = c - d;//k代表入睡时间，即闹铃间距减去入睡所需时间
if (a % k == 0)//算算闹铃要响几次才能起床
{
ans += c * (a / k);//答案加几次时间
}
else//这里要注意，即使睡眠时间够了，但是闹铃不响是不会起来的，所以需要（a+k+1）
{
ans += c * ((a / k) + 1);//答案更新
}
cout << ans << endl;//输出答案
}
}
}
return 0;
}
软卓选拔B 后缀零计数
软卓选拔B
这是一道数学题目，可能有很多同学会把这个数算出来后再看看有几个后缀零，但是有一点需要注意的是，longlong数据类型的极限是10的18次方，如果把这个数完整的算出来肯定是会超过这个值的，所以我们需要用另外的方法来解决这个问题，当然，直接算是可以拿一部分分数的。真正的比赛可以这样拿一部分分数
思路：首先，出现0就肯定是相乘出现了10，只有相乘出现了10的倍数才可能有0，比如45等于20，实际上就是225=210等于20，那么我们再看看10，只有25才等于10，而103=20可以看做253，那么问题就转化成了看你的数据能被分解成多少个2和多少个5，比如10，2，8，5，一共5个2，2个5，能凑出2个2*5，那答案就是2
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll x, y;//用来记录一共出现了多少个2和5
ll a[100000];//用来记录数据
void fun(ll t)//一个求解t最多能除以几次2的函数，递归实现
{
if (t % 2 == 0)
{
x++;
fun(t / 2);
}
else
return;
}
void fun2(ll t)//一个求解t最多能除以几次2的函数，递归实现
{
if (t % 5 == 0)
{
y++;
fun2(t / 5);
}
else
return;
}
int main()
{
ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] % 2 == 0)
{
fun(a[i]);//用来算有几个2，因为x是全局变量，所以不会因为循环而每次归零
}
if (a[i] % 5 == 0)
{
fun2(a[i]);//用来算有几个5
}
}
cout << min(x, y);//输出x，y中较小的那一个数就是正确答案
return 0;
}
软卓选拔C 塔子哥算概率
软卓选拔C
算法题，数学题：哈希算法，离散数学
去年最难的一道题，并且是去年没有学长写出来的一道题…笔者到现在总算写了出来…由于笔者能力有限以及这题的确存在难度，因此如果有同学实在想知道这道题请私聊笔者QQ（1536775802）笔者将亲自进行讲解。
塔子哥说：
这是一道原题改编自离散数学P250 课后习题12.1
不难发现：这是一个古典概型，分母是确定的，主要计算分子,也就是符合要求的方案数.
拿20分的解法：三重循环，暴力统计所有合法方案.复杂度O(n^3)
拿40分的解法：优化:三重循环，最内层循环根据外面两重循环的值来确定，跨步为m，复杂度为
O(\frac{n^3}{m} )
拿70分的解法：同余类的应用.
先把书上那题的解法彻底搞懂：
https://www.zybang.com/question/47028159d760daa405307dd3158dd42e.html
这样以来，我们的三重循环的上界就不再是n，而是m。根据简单的计数原理，每次统计三个同余类中数字的个数，求组合数。
内层我使用了map存储i , j , k，但是由于每次只存储三个元素，所以这部分复杂度是个常系数，可以忽略不计.
内层组合数的计算,不难发现，计算次数恒等于3，也是一个常系数，忽略不计.
所以总复杂度:O(m^3 )
拿100分的解法：
根据同余关系恒等式 . (i,j,k分别为三层循环的循环变量)
最内层循环的k可以根据外层确定的i,j O(1)的计算出来,优化掉最内层循环.
复杂度降为O(m^2) 可以完全通过此题。
官方代码
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int maxn = 1e5 + 5;
#define ll long long
ll C(ll a , ll b)
{
if (a < b) return 0;
if (b == 0 || b == a) return 1;
if (b > a - b) b = a - b;
ll up = 1 , down = 1;
for (int i = 0 ; i < b ; i++){
up = up * (a - i);
down = down * (b - i);
}
return up / down;
}
ll R[maxn];
map <ll,ll> book;
int main()
{
ll n , m ; cin >> n >> m;
for (int i = 1 ; i <= n ; i++)
R[i%m]++;
ll cnt = 0 , res = 1;
for (int i = 0 ; i < m ; i++){
for (int j = i ; j < m ; j++){
ll k = (m - i - j + 3 * m)%m;
if (k < j) continue;
if ((i + j + k)%m == 0){
book.clear();
book[i]++ , book[j]++ , book[k]++;
res = 1;
for (auto g : book) {
res *= C(R[g.first] , g.second);
}
cnt += res;
}
}
}
ll g = __gcd(cnt , C(n , 3));
cout << cnt / g << "/" << C(n , 3) / g << endl;
return 0;
}
笔者的代码
#include<iostream>
#define ll long long
using namespace std;
ll gcd(ll a, ll b)//辗转相除法求最大公因数
{
return b == 0 ? a : gcd(b,a%b);
}
ll hx[2050];//余数哈希表
ll n, k;
ll ans;
ll res(ll x, ll y, ll z)//（x+y+z）%k==0时的情况
{
if (x == y && y == z)
{
return hx[x] * (hx[y] - 1) * (hx[z] - 2)/6; //排列组合知识
}
else if (x == y)
{
return hx[x] * (hx[y] - 1) * hx[z] / 2;//排列组合知识
}
else if (z == y)
{
return hx[x] * (hx[y] - 1) * hx[z] / 2;//排列组合知识
}
else
return (hx[x] * hx[y] * hx[z]);
}
int main()
{
cin >> n >> k;
for (ll i = 1; i <= n; i++)
{
hx[i % k]++;//只存下该数据的余数
}
for (ll i = 0; i < k; i++)//二重循环
{
for (ll j = i; j < k; j++)
{
ll p = (k * 2 - i - j) % k;//(x+y+z)%k必须等于0
if(p>=j)//i,j,p必须严格递增才能保证不重复
{
ans += res(i,j,p);
}
}
}
ll ans2 = (n) * (n - 1) * (n - 2) / 6;//排列组合C（n 3）
ll j = gcd(ans, ans2);
ans = ans/j;
ans2 = ans2/j ;
cout << ans << '/' << ans2 << endl;
return 0;
}
软卓选拔D 小y学数学
软卓选拔D
依然是思维题，想到了就不难，但就是难想到。想到了也还考验你的基本功
#include<iostream>
#define ll long long
using namespace std;
int main()
{
ll n;
cin >> n;
if (n<10)//如果这个数小于10的情况，特判一下，输出这个数加10就可以了
{
cout << 10+n;
return 0;
}
else
{
/*依次把这个数分解因子，必须要从9往1去求，因为我们8=2*2*2，结果里写三个2当然不如写一个8*/
int x9 = 0;
while (n % 9 == 0) { x9++; n /= 9; }
int x8 = 0;
while (n % 8 == 0) { x8++; n /= 8; }
int x7 = 0;
while (n % 7 == 0) { x7++; n /= 7; }
int x6 = 0;
while (n % 6 == 0) { x6++; n /= 6; }
int x5 = 0;
while (n % 5 == 0) { x5++; n /= 5; }
int x4 = 0;
while (n % 4 == 0) { x4++; n /= 4; }
int x3 = 0;
while (n % 3 == 0) { x3++; n /= 3; }
int x2 = 0;
while (n % 2 == 0) { x2++; n /= 2; }
if (n != 1)//如果这个数是大于10的质数，那么上面x1到x9全为0，否则被分解到这一步n一定等于1
{
cout << -1;//输出-1，无答案
return 0;
}
/*之后只要按照从小到大把这些因数输出就行了，这样子输出的数各个位数相乘一定是等于原数的*/
for (int i = 0; i < x2; i++)
{
cout << 2;
}
for (int i = 0; i < x3; i++)
{
cout << 3;
}
for (int i = 0; i < x4; i++)
{
cout << 4;
}
for (int i = 0; i < x5; i++)
{
cout << 5;
}
for (int i = 0; i < x6; i++)
{
cout << 6;
}
for (int i = 0; i < x7; i++)
{
cout << 7;
}
for (int i = 0; i < x8; i++)
{
cout << 8;
}
for (int i = 0; i < x9; i++)
{
cout << 9;
}
}
return 0;
}
软卓选拔E 小y上楼梯
软卓选拔E
本题为算法题，考的是动态规划，如果是没有学过动态规划算法的同学是不太可能写出这道题的，除非你能推导出这道题的规律，变成一道找规律的题目。然而，对动态规划比较熟练的同学来说这道题其实就很简单了。由于篇幅有限，在这里就不介绍什么是动态规划算法了。感兴趣可以在csdn上搜索学习
#include<iostream>
#define ll long long
using namespace std;
ll q = 1e9 + 7;
int main()
{
int n, k;
ll dp[101];
dp[0] = 1;//上第0层楼梯的方案为1
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
dp[i] = 0;
for (int j = 1; j <= k && i - j >= 0; j++)
{
dp[i] = ((dp[i] % q) + (dp[i - j] % q)) % q;
/*转移方程，上到每i层楼梯的方案数为第i-1到第i-k层的方案数之和*/
}
}
cout << dp[n];//输出到第n层的方案数
return 0;
}
软卓选拔F 杰瑞的2020
软卓选拔F
非算法题，基础题，考察的是对字符串的处理和使用。考察的是代码基本功。
#include<iostream>
#include<string>
#define ll long long
using namespace std;
int main()
{
string a;
string b="";//定义一个空字符串
int ans = 0;//答案
cin >> a;//字符串输入
for (int i = 0; i < a.size(); i++)//遍历a字符串，删除非‘2’和‘0’的字符，存入b
{
if (a[i] == '2' || a[i] == '0')
{
b += a[i];
}
}
int t = 0;//这里的t代表寻找的是’2020‘的第几个
for (int i = 0; i < b.size(); i++)
{
if (b[i] == '2' && t == 0)
{
b[i] = 'a';//变成a就不会再次被选了，但好像也没啥用？
t++;
}
if (b[i] == '0' && t == 1)
{
b[i] = 'a';
t++;
}
if (b[i] == '2' && t == 2)
{
b[i] = 'a';
t++;
}
if (b[i] == '0' && t == 3)
{
b[i] = 'a';
t = 0;
ans++;
}
}
cout << ans;//最后输出答案
return 0;
}
作者：Avalon·Demerzel，希望本博客能对你有帮助，如有疑问或发现错误，欢迎下方评论。