【藍橋杯每日一題】3.16

Alt ?

🏝?專欄：?【藍橋杯備篇】
🌅主頁：?f狐o貍x

3.9 高精度算法

一、高精度加法

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

二、高精度減法

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

三、高精度乘法

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

四、高精度除法

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

3.10 枚舉

一、鋪地毯

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

二、回文日期

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

三、掃雷

? ? ? ? 題目鏈接：

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 解題代碼：

????????刷題就像打游戲，藍橋杯是終極大BOSS，每天的真題都是小怪——雖然爆率低，但裝備（知識）掉不停！

3.9 高精度算法

? ? ? ? 今天來點有意思的，模擬小學的加減乘除

一、高精度加法

? ? ? ? 題目鏈接：

????????P1601 A+B Problem（高精）

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 這題我們可以看到a，b這兩個數的值是非常大的（已經超過了long long）因此我們需要自己寫一個加法的代碼，我們可以用一個數組把數字的每一位存起來，在想小學數學那樣一位一位的計算就可以了

? ? ? ? 解題代碼：

#include <iostream>using namespace std;const int N = 1010;int a[N], b[N], c[N];
int la, lb, lc;void add(int c[], int a[], int b[])
{for (int i = 0; i < lc; i++){c[i] += a[i] + b[i];c[i + 1] = c[i] / 10;c[i] %= 10;}if (c[lc]) lc++;
}int main()
{string x, y; cin >> x >> y;// 將數據存入數組la = x.size();lb = y.size();lc = max(la, lb);for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';add(c, a, b);// c = a + bfor (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

二、高精度減法

? ? ? ? 題目鏈接：

????????P2142 高精度減法

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 這題和上面的高精度加法類似，都是不能簡單的用一個long long 的變量就能搞定的，因此還是需要我們模擬一下小學時候學的減法，列豎式來一個一個算

? ? ? ? 解題代碼：


#include <iostream>using namespace std;const int N = 1e5 + 10;int a[N], b[N], c[N];
int la, lb, lc;bool bigger(string x, string y)
{if (x.size() != y.size()){return y.size() > x.size();}return y > x;
}void sub(int c[], int a[], int b[])
{for (int i = 0; i < lc; i++){c[i] += a[i] - b[i];if (c[i] < 0){c[i + 1]--;c[i] += 10;}}while (1 != lc && c[lc - 1] == 0) lc--;
}int main()
{string x, y; cin >> x >> y;if (bigger(x, y)){swap(x, y);cout << '-';}la = x.size(); lb = y.size(); lc = max(la, lb);for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';sub(c, a, b); // c = a - b;for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

三、高精度乘法

? ? ? ? 題目鏈接：

????????P1303 A*B Problem

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 同上，模擬小學列豎式乘法即可

? ? ? ? 才怪，我騙你的，這里為了代碼更加簡潔，我們可以先處理進位，最后在處理，如下圖：

? ? ? ? 解題代碼：

#include <iostream>using namespace std;const int N = 2010;int a[N], b[N], c[N];
int la, lb, lc;void mul(int c[], int a[], int b[])
{for (int i = 0; i < la; i++){for (int j = 0; j < lb; j++){c[i + j] += a[i] * b[j]; // 無進位乘法}}// 處理進位for (int i = 0; i < lc; i++){c[i + 1] += c[i] / 10;c[i] %= 10;}while (lc != 1 && c[lc - 1] == 0) lc--;
}int main()
{string x, y; cin >> x >> y;la = x.size(); lb = y.size(); lc = la + lb;for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';for (int i = lb - 1; i >= 0; i--) b[lb - 1 - i] = y[i] - '0';mul(c, a, b);// c = a * b;for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

四、高精度除法

? ? ? ? 題目鏈接：

????????P1480 A/B Problem

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 模擬小學除法即可

? ? ? ? 解題代碼：

#include <iostream>using namespace std;typedef long long LL;const int N = 5010;int a[N], c[N];
LL b;
int la, lc;void div(int c[], int a[], LL b)
{LL t = 0;for (int i = lc - 1; i >= 0; i--){t = t * 10 + a[i];c[i] = t / b;t = t % b;}while (lc != 1 && c[lc - 1] == 0) lc--;
}int main()
{string x; cin >> x >> b;la = x.size(); lc = la;for (int i = la - 1; i >= 0; i--) a[la - 1 - i] = x[i] - '0';div(c, a, b); // c = a / bfor (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

3.10 枚舉

? ? ? ? 枚舉，顧名思義就是意義列舉，來吧來吧直接上題目

一、鋪地毯

? ? ? ? 題目鏈接：

????????P1003 [NOIP 2011 提高組] 鋪地毯

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 因為題目給的數量不大，因此我們可以暴力枚舉，把所有情況全部意義羅列出來，在判斷是否符合題目要求，符合直接返回即可（因為這個題是我們需要我們找到最后一個符合要求的地毯，因此我們可以之后從后往前遍歷來優化代碼）

? ? ? ? 解題代碼：


#include <iostream>using namespace std;const int N = 1e4 + 10;int a[N], b[N], g[N], k[N];int main()
{int n; cin >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> b[i] >> g[i] >> k[i];}int x, y; cin >> x >> y;int flag = 0;for (int i = n; i >= 0; i--){if (a[i] <= x && b[i] <= y &&a[i] + g[i] >= x && b[i] + k[i] >= y){cout << i << endl;flag++;break;}}if (!flag) cout << -1 << endl;return 0;
}

二、回文日期

? ? ? ? 題目鏈接：

????????P2010 [NOIP 2016 普及組] 回文日期

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 這里可以我們可以直接暴力枚舉從date1 一直枚舉到 date2，然后再一一判斷該日期是否是回文日期，再用一個cnt變量計數就行了。

? ? ? ? 但是這樣的算法會不會太過于浪費呢？這里有另外一個方法：將data1里的year1 枚舉到year2，再判斷日期是否合法即可。

? ? ? ? 但是這樣依然不是最優解，方法二還需要枚舉9999次，這里我們還有法三：將所有日期枚舉出來，在判斷回文的年份是否在題目要求的年份里面

? ? ? ? 解題代碼：

? ? ? ? 這里煮波偷個懶，只寫第第三種方法，前兩種方法大家可以自己去試試

#include <iostream>using namespace std;typedef long long LL;int days[13] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };int main()
{int date1, date2; cin >> date1 >> date2;int cnt = 0;for (int m = 1; m < 13; m++){for (int d = 1; d <= days[m]; d++){if (date1 <= (((d % 10) * 1000 + (d / 10) * 100 + (m % 10)*10 + m / 10) * 10000 + m * 100 + d) &&date2 >= (((d % 10) * 1000 + (d / 10) * 100 + (m % 10) * 10 + m / 10) * 10000 + m * 100 + d)){cnt++;}}}cout << cnt << endl;return 0;
}

三、掃雷

? ? ? ? 題目鏈接：

????????P2327 [SCOI2005] 掃雷

? ? ? ? 題目描述：

????????解題思路：

? ? ? ? 這個題也是可以枚舉的，我們可以根據第一排是否1有雷推出下一排有沒有雷（是否有雷用0 1表示）那么下一排有沒有雷就=上一排的地雷+當前排的地雷 - 當前排的數字

? ? ? ? 解題代碼：

#include <iostream>using namespace std;const int N = 1e4 + 10;int n;int a[N], b[N];int cheak1()
{a[1] = 0;for (int i = 2; i <= n + 1; i++){a[i] = b[i - 1] - a[i - 1] - a[i - 2];if (a[i] > 1 || a[i] < 0)return 0;}if (a[n + 1])return 0;return 1;
}int cheak2()
{a[1] = 1;for (int i = 2; i <= n + 1; i++){a[i] = b[i - 1] - a[i - 1] - a[i - 2];if (a[i] > 1 || a[i] < 0)return 0;}if (a[n + 1])return 0;return 1;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> b[i];}int ret = 0;ret += cheak1();ret += cheak2();cout << ret << endl;return 0;
}

ok，本期就到這里吧，過兩天在更新下一期拜拜~

每日三省吾身：