首先把去年的官方題解擺在這里大家可以看看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，希望本博客能對你有幫助，如有疑問或發現錯誤，歡迎下方評論，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278797.html
標籤：AI
上一篇：Python小白入門系列教程：注釋、變數、輸出、運算子，看過的都收藏了
下一篇：工訓賽：從參賽到“棄賽”