第八屆“圖靈杯”NEUQ-ACM程序設計競賽個人賽（同步賽）

題目總結

A題 切蛋糕

題目信息

解題思路

如果我們將 1/k展開到二進制的形式，那么就可以計算出 需要 多少塊1/(2^i) 蛋糕，因此就可以創(chuàng)建出分割的方案，最后進行打包。
本題還有一個有趣的地方是，知道需要多少塊的蛋糕后，還需要計算出需要切割多少次，
假如說需要 1個四等分的， 1個八等分的，3個十六等分的，4個三十二等分的
那么 十六等分的需要切割次數(shù) $?$$\frac{4}{2}$$?$=2，可以得到四個三十二等分
八等分需要的切割次數(shù) $?$$\frac{十六等分切割次數(shù)+十六等分原需要數(shù)額}{2}$$?$
也就是說，計算切割次數(shù)，需要受到前面切割次數(shù)信息的影響。

二進制小數(shù)點可以直接使用double進行計算，精度是足夠的

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const double esp = 1e-10; const int N = 20; LL a[N]; LL k; bool b[N], flag; int opt[N]; int cut_opt[N];bool Check(int n) {static LL l = a[10] - k, r = a[10] + k;double sum = 0;for (int i = 0; i < n; i ++ ){if (!b[i]) continue;if (i <= 10)sum += (a[10 - i]) * k;elsesum += k * 1.0 / a[i - 10];}if (n <= 10) // (a[10 - i]) * k{static int i; i = n;if (sum + (a[10 - i]) * k >= l && sum + (a[10 - i]) * k <= r){flag = true;return true;}else if (sum + (a[10 - i]) * k < l)return true;return false;}else // 1.0 / a[i - 10];{static int i; i = n;if (sum + k * 1.0 / a[i - 10] >= l && sum + k * 1.0 / a[i - 10] <= r){flag = true;return true;}else if (sum + k * 1.0 / a[i - 10] < l)return true;return false;} }int main() {a[0] = 1;for (int i = 1; i < N; i ++ )a[i] = (a[i - 1] << 1);memset(b, false, sizeof b);cin >> k;if (k == 1) // 注意{printf("1\n");printf("2 1 0\n");return 0;}flag = false;double tmp = 1.0 / k;for (int i = 1; i <= 15; i ++ ){if (abs(tmp - 1.0 / a[i]) <= esp){b[i] = true;break;}else if (tmp >= 1.0 / a[i]){tmp -= 1.0 / a[i];b[i] = true;}else{b[i] = false;}}/*for (int i = 0; i < 15; i ++ ){printf("i=%d, b[%d]=%d\n", i, i, b[i]);} */for (int i = 15; i >= 1; i -- ){opt[i] = b[i] * k;}int outcnt = k;memset(cut_opt, 0, sizeof cut_opt);for (int i = 14; i >= 1; i -- ){cut_opt[i - 1] = (opt[i] + 1) / 2;opt[i - 1] += ((opt[i] + 1) / 2);outcnt += cut_opt[i - 1];}cout << outcnt << endl;// 需要切割的for (int i = 0; i < 15; i ++ ){if (cut_opt[i] != 0){for (int j = 1; j <= cut_opt[i]; j ++ )printf("1 %d\n", i);}}int cnt = 0;vector<int> pick;// b[i] 打包的for (int i = 0; i < 15; i ++)if (b[i]){cnt += b[i];pick.push_back(i);}for (int i = 1; i <= k; i ++ ){printf("2 %d", cnt);for (int j = 0; j < pick.size(); j ++ )printf(" %d", pick[j]);putchar('\n');}return 0; }

小寶的幸運數(shù)組

題目信息

解題思路

需要注意子序列（如最長上升子序列LIS）和子串的區(qū)別
這里子數(shù)組的定義和子串類似
這里關鍵是對 原數(shù)組的前綴和 對k進行求余，得到的余數(shù)k，記錄下來他的位置，然后對余數(shù)進行分析
余數(shù) = 0，可以直接將下邊作為一種解，進行更新答案
余數(shù) = 1, res = min(res, max - min); 也就是說最長的，min + 1 ~ max這一段子序列是可行的，而且是余數(shù)等于1情況下最長的。
…
余數(shù) = k-1
經(jīng)過分析，發(fā)現(xiàn)子需要記錄下來 余數(shù)中最先遇到的 min下標，與最后遇到的 max下標即可。

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 100010; const int INF = 0x3f3f3f3f; int a[N], b[N]; int n, k; LL q[N], sum[N];int main() {int T; cin >> T;while (T -- ){cin >> n >> k;sum[0] = 0;memset(a, -1, sizeof a);memset(b, -1, sizeof b);int res = -1;for (int i = 1; i <= n; i ++ ){scanf("%lld", &q[i]);sum[i] = (sum[i - 1] + q[i]) % k;if (a[sum[i]] == -1){a[sum[i]] = i;}b[sum[i]] = i;if (sum[i] == 0){res = max(res, i);}else{res = max(res, b[sum[i]] - a[sum[i]]);}}/// cout << "###########\n";if (res == 0) puts("-1");else cout << res << endl;}return 0; }

C題上進的凡凡

題目信息

解題思路

關鍵的思路就是使用dp的思想
以 a[i] 為開始的上進數(shù)組個數(shù) f[i]
當 a[i]<=a[i+1]
f[i] = 1 + f[i + 1]
否則
f[i] =1
最后累加求和即可

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL;const int N = 100010, INF = 0x3f3f3f3f; int a[N], f[N]; int n;int main() {cin >> n;for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]);LL res = 0;a[n + 1] = -INF;for (int i = n; i >= 1; i -- ){f[i] = 1;if (a[i] <= a[i + 1])f[i] += f[i + 1];res += f[i];}cout << res << endl;return 0; }

D題Seek the Joker I

原題信息

解題思路

本題是博弈論方向的題目，對于此類問題，我們需要從 必定失敗的局面出發(fā)，推導出可以讓對手達到必定失敗的局面-》必勝
以及無法讓對手達到必定失敗的局面->必敗，最后找到規(guī)律，有時間可以證明，寫出結果即可

AC代碼

#include <bits/stdc++.h> using namespace std;bool Check(int n, int k) {if (n % (k + 1) == 0) return false;return true; } int main() {int t; cin >> t;while (t -- ){static int n, k;scanf("%d%d", &n, &k);if (Check(n - 1, k)){/// cout << "win" << endl;puts("yo xi no forever!");}else{/// cout << "lose" << endl;puts("ma la se mi no.1!");}}return 0; }

E Seek the Joker II

原題信息

解題思路

方法與上題目相同，但是推導比較易錯，** 最終的規(guī)律可以使用dp的形式表達出來 **

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 3000010; bool st[N + 1000000]; LL a[N + 1000000];bool Check(int x, int y) {if (a[x] == -1) return true; // winelse if (a[x] == y) return false; // losereturn true; // win }int main() {memset(a, -1, sizeof a);memset(st, false, sizeof st);a[0] = 0;int cur = 1;for (int i = 1; i < N; i ++ ){if (st[i]){/// if (i <= 20) printf("I=%d, st\n\ta[i]=", i);a[i] = -1;}else{/// if (i <= 20) printf("I=%d, No_St\n\ta[i]=", i);a[i] = i + cur;if (i + cur <= N)st[i + cur] = true; // 注意這個cur ++;}/// if (i <= 20) cout << a[i] << endl;} /*cout << a[0] << endl;for (int i = 0; i <= 9; i ++ ){printf("i=%d, a[i]=%lld\n", i, a[i]);} */int t; cin >> t;int x, n, mina, maxb;while (t -- ){scanf("%d%d", &n, &x);mina = x - 1, maxb = n - x;if (mina > maxb) swap(mina, maxb);/// printf("a=%d, b=%d\n", mina, maxb);if (Check(mina, maxb))/// cout << "\t##win\n",cout << "yo xi no forever!" << endl;else/// cout << "\t##lose\n",cout << "ma la se mi no.1!" << endl;}return 0; }

成績查詢ing

原題信息

解題思路

思路很清晰的模擬題，就是排序，查找，不會stl頂多就是再加一個二分
但是 時間很卡 應該使用快讀 來解決時間的問題，考試的時候沒有板子，就T了

AC代碼

#include <bits/stdc++.h> using namespace std; const int BASE1 = 10, BASE2 = 10000; map<string, int> t1; set<string> t2[101];int n, m, opt;inline int IntRead()//內(nèi)聯(lián)函數(shù)稍微快一點點 {char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0',ch = getchar();}return s * w; }inline string StringRead() {string str;char s = getchar();//處理多余回車或空格while (s == ' ' || s == '\n' || s == '\r'){s = getchar();}//不斷讀入直到遇到回車或空格while (s != ' ' && s != '\n' && s != '\r'){str += s;s = getchar();}return str; }inline void StringWrite(std::string str) {int i = 0;while (str[i] != '\0'){putchar(str[i]), i++;} }inline void IntWrite(int s) {int k = 0, len = 0;if (s == 0)putchar('0');while (s){k = k * 10 + s % 10;s /= 10, len++;}for (int i = 0;i < len;i++){putchar(k % 10 + '0');k /= 10;} }int main() {cin >> n;string _name; int _id, _sex, _grade;for (int i = 1; i <= n; i ++ ){_name = StringRead();_grade = IntRead(), _sex = IntRead(), _id = IntRead();t2[_grade].insert(_name);t1[_name] = _sex + BASE1 * _grade + BASE2 * _id;}cin >> m;while (m -- ){opt = IntRead();if (opt == 1){_name = StringRead();static int num;num = t1[_name];printf("%d %d %d\n", num % BASE2 / BASE1, num / BASE2, num % BASE1);}else{_grade = IntRead();static set<string>::iterator it;for (it = t2[_grade].begin(); it != t2[_grade].end(); it ++ ){StringWrite(*it);putchar('\n');}}}return 0; } /* 5 N 28 2 7475 UN 83 2 27550 EXF 28 2 17298 OVYNH 51 2 14827 XNV 53 1 7591 2 1 XNV 2 28 */

G 貪吃的派蒙

原題信息

解題思路

關鍵就是改變其他人領取的數(shù)量，來使得派蒙的前一個人剛剛好領完，這是一個 數(shù)學 區(qū)間 + 不等式的問題

最后注意上下取整就好

H數(shù)羊

原題信息

解題思路

直接打表找規(guī)律，我是證明半天沒出來，最后快沒時間了，才打的表，血虧

AC代碼

#include <bits/stdc++.h> using namespace std;const int MOD = 998244353; typedef long long LL;int fun(int x, int y) {if (x == 1 && y == 0) return 2;else if (x == 0 && y >= 0) return 1;else if (x >= 2 && y == 0) return x + 2;else return fun(fun(x - 1, y), y - 1); }int qmi(LL a, int k, int MOD) {LL res = 1;while (k){if (k & 1){res = (res * a) % MOD;}a = a * a % MOD;k >>= 1;}return res; }int cal(int x, int y) {if(x == 1) return 2;if (y == 0){return (x + 2) % MOD;}else if (y == 1){return (x * 2) % MOD;}else{return qmi(2, x, MOD);} }int main() {/*for (int i = 1; i <= 18; i ++ ){printf("i=%d, ", i);for (int j = 0; j <= 2; j ++ ){printf("%d, ", fun(i, j));}cout << endl;}*/int t; cin >> t;while (t -- ){static int x, y;scanf("%d%d", &x, &y);printf("%d\n", cal(x, y));}}

I 買花

原題信息

解題思路

直接就是 $2^i$ 的前綴和，但是要注意 不可以是一天的

AC代碼

#include <bits/stdc++.h> using namespace std;int a[200];bool Check(int x) {for (int i = 2; i <= 15; i ++ ){if (x % a[i] == 0)return true;}return false; }int main() {a[1] = 1;for (int i = 2; i <= 15; i ++ ){a[i] = (a[i - 1] << 1);}for (int i = 1; i <= 15; i ++ )a[i] = a[i - 1] + a[i];int t; cin >> t;while (t -- ){static int n;scanf("%d", &n);if (Check(n)){puts("YE5");}else{puts("N0");}}return 0; }

J 這是一題簡單的模擬

原題信息

解題思路

直接就是模擬就行了，關鍵是題目描述的不太清楚，多讀幾遍 就好了
對于一個可行的道路，必須要經(jīng)過所有的城市，是N個，不是n個

AC代碼

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std;const int N = 310, INF = 0x3f3f3f3f; int n, m; int e[N][N]; bool st[N]; int k; int path[N * 1000]; int res = INF;int main() {cin >> n >> m;memset(e, 0x3f, sizeof e);for (int i = 1; i <= m; i ++ ){static int x, y, w;scanf("%d%d%d", &x, &y, &w);e[x][y] = e[y][x] = w;}cin >> k;res = INF;int tmpres;while (k -- ){tmpres = 0;static int n2; scanf("%d", &n2);for (int i = 1; i <= n2; i ++ )scanf("%d", &path[i]);if (n2 != n)continue;n2 ++; path[n2] = 0;path[0] = 0;memset(st, false, sizeof st);for (int i = 1, pre, cur; i <= n2; i ++ ){pre = path[i - 1], cur = path[i];if (st[cur] == true){tmpres = INF;break;}st[cur] = true;if (e[pre][cur] == INF){tmpres = INF;break;}tmpres += e[pre][cur];}res = min(res, tmpres);}if (res == INF) res = -1;cout << res << endl;return 0; }

K黑洞密碼

原題信息

解題思路

就是一個簡單的字符串問題，和模擬相關，注意 字母誰在誰的后面，特判就好

AC代碼

#include <bits/stdc++.h> using namespace std;const int N = 100; int num[N]; char str[N]; char s[N]; int nidx, cidx;char Change(char ch, int num) {if (ch >= 'A' && ch <= 'Z'){if (ch + num <= 'Z') return ch + num;else return ch + num - 'Z' - 1 + 'b';}else{if (ch + num <= 'z') return ch + num;else return ch + num - 'z' - 1 + 'B';} }int main() {nidx = cidx = 0;cin >> str;for (int i = 0; i < 32; i ++ ){if (str[i] >= '0' && str[i] <= '9'){num[nidx ++] = str[i] - '0';}else{s[cidx ++] = str[i];}}for (int i = 0; i < 16; i ++ ){s[i] = Change(s[i], num[i]);}for (int i = 0; i < 4; i ++ ){for (int j = 3 + i * 4; j >= i * 4; j -- ){cout << s[j];}}cout << endl;return 0; }

L建立火車站

原題信息

解題思路

求最大值最小，典型的 二分

AC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 100010;LL a[N]; LL n, k;bool Check(LL l, LL k) {if (l == 0){for (int i = 2; i <= n; i ++){if (a[i] != a[i - 1]) return false;}return true;}LL dist;for (int i = 2; i <= n; i ++ ){dist = a[i] - a[i - 1];k = k - (dist - 1) / l;if (k < 0) return false;}return true; }int main() {cin >> n >> k;for (int i = 1; i <= n; i ++ )scanf("%lld", &a[i]);sort(a + 1, a + n + 1);LL l, r, mid;l = 0, r = 1e12+10;while (l < r){mid = l + r >> 1;if (Check(mid, k)){r = mid;}else{l = mid + 1;}}cout << l << endl;return 0; }

心得體會

題目信息要讀懂，讀清楚，不要漏掉信息，結合樣例

空間開的足夠，LL信息需要注意

輸出的字符串YES，NO不要自己打，直接復制粘貼

快讀卡時間，記得打板子

double精度很高的，不必轉(zhuǎn)換為整數(shù)求二進制信息

一些數(shù)學題目，先打表找規(guī)律，別直接推導

總結

以上是生活随笔為你收集整理的第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。