Loading... ## 写在最前 题解拖了挺久了，到期末事情越来越多= = 抽了个空把这个坑给补了 这次新生赛是我们ACM集训队打完ICPC银川区域赛之后回来的路上开始准备的(坐了火车2天，一方面是为了明年下个赛季的ICPC/CCPC招新做准备，另一方面可以同时检测同学C语言的基础,为期末的C语言上机和考试做准备。 这次的出题人是17级的我和韩律，验题则是由ACM集训队的所有队员进行的，没有他们这次数据可能就出锅了Orz 这次新生赛老师们也给予了很大的帮助，包括机房电脑环境的更新，活动的组织等等（花了半天装了CodeBlocks和DevC++，顺便更新了下Chrome， 想装VSCode结果不兼容Orz）。 这次比赛赛制与程序设计天梯赛类似。因为有分数，所以难度区分也非常容易。接下来的题解会按题目编号顺序编写, 样例代码则给出C版本和C++版本。新生赛的复现赛的时间已经延长，大家可以继续进行练习。 <button class="btn m-b-xs btn-info btn-addon" onclick='window.open("/usr/uploads/2021/05/2779831486.pdf","_blank")'><i><i data-feather="file"></i></i>题目册下载</button> <button class="btn m-b-xs btn-info btn-addon" onclick='window.open("/usr/uploads/2021/05/2417415796.zip","_blank")'><i><i data-feather="code"></i></i>标准程序下载</button> ## A. Hinata Loves Programming #### Pt：5 #### Accepted Ratio: 0.91% (3 / 330) 一道简单的输出题，当初出题时只是单单给出了输出而已，但是验题时被提醒说不一定能想的起转义字符，所以后来加了一句 > 除了Ctrl + C&Ctrl + V外不要忘了什么哦 结果最后也并没有几个人做出来，到期末了，转义字符这一块应该还是要复习一下的。。。 其实很简单，将输出一行一行复制，最后将 `\` 在代码中替换为 `\\` 即可. #### Code ```c #include <stdio.h> int main(){ printf(" ______ ______ ____ ____ __ ___ _ __ ___ ____ __ __ ______ __ __ ____ _ __\n"); printf(" / ____/ / ____/ / __ \\ / __ \\ / / / || | / / / | / __ \\\\ \\/ / /_ __/ / / / / / __ \\ / | / /\n"); printf(" / / / / / /_/ / / /_/ / __ / / / /| || | / / / /| | / /_/ / \\ / / / / /_/ / / / / / / |/ /\n"); printf("/ /___ / /___ / ____/ / ____/ / /_/ / / ___ || |/ / / ___ | / ____/ / / / / / __ / / /_/ / / /| /\n"); printf("\\____/ \\____/ /_/ /_/ \\____/ /_/ |_||___/ /_/ |_| /_/ /_/ /_/ /_/ /_/ \\____/ /_/ |_/\n"); } ``` ```cpp #include <bits/stdc++.h> using namespace std; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run(){ cout << " ______ ______ ____ ____ __ ___ _ __ ___ ____ __ __ ______ __ __ ____ _ __" << endl; cout << " / ____/ / ____/ / __ \\ / __ \\ / / / || | / / / | / __ \\\\ \\/ / /_ __/ / / / / / __ \\ / | / /" << endl; cout << " / / / / / /_/ / / /_/ / __ / / / /| || | / / / /| | / /_/ / \\ / / / / /_/ / / / / / / |/ /" << endl; cout << "/ /___ / /___ / ____/ / ____/ / /_/ / / ___ || |/ / / ___ | / ____/ / / / / / __ / / /_/ / / /| /" << endl; cout << "\\____/ \\____/ /_/ /_/ \\____/ /_/ |_||___/ /_/ |_| /_/ /_/ /_/ /_/ /_/ \\____/ /_/ |_/" << endl; } ``` ## B. Hinata And Rescue #### Pt：10 #### Accepted Ratio: 10.53% (12 / 114) 该题考查二重循环. 首先题目说明了这个正方形的边长为奇数，且 Miyako 位于正方形的正中心，那么我们设正方形的边长为 $n$, 可以得到 Miyako 此时的 $(x_1,y_1) = (int(n/2), int(n/2))$, 此时我们只需要找到 Hinata 此时的位置就可以得到最近的距离. 我们只需要找到一个二重循环，找到单元格为 $1$ 的那个坐标$(x_2, y_2)$. 距离 $d = |x_1-x_2| + |y_1-y_2|$ <div class="tip inlineBlock warning"> 在C语言中，请不要这样输出 ``printf("%d\n", fabs(x - n / 2) + fabs(y - n / 2));`` 原因很简单，fabs函数返回值的类型为 `float` ,而你输出的 `%d` 是 `int` 类型，这么做会导致某些编译器编译后出现乱码(更准确地说应该是一个未知数) 你应当进行类型强制转换后在输出结果，例如 ``printf("%d\n", (int)(fabs(x - n / 2) + fabs(y - n / 2)));`` 或 ``int d = fabs(x - n / 2) + fabs(y - n / 2); printf("%d\n", d);`` </div> #### Code ```c #include <math.h> #include <stdio.h> int main() { int n; scanf("%d", &n); int x, y; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int t; scanf("%d", &t); if (t == 1) { x = i, y = j; } } } int d = fabs(x - n / 2) + fabs(y - n / 2); printf("%d\n", d); } ``` ```cpp #include <bits/stdc++.h> using namespace std; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { int n; cin >> n; int x, y; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int t; cin >> t; if (t == 1) { x = i, y = j; } } } cout << fabs(x - n / 2) + fabs(y - n / 2) << endl; } ``` ## C. Miyako And Keyboard #### Pt：15 #### Accepted Ratio: 1.69% (1 / 59) 一道替换字符题. 根据输入，我们可以将字符与字符之间一一对应. 例如 `qwertyuiopasdfghjklzxcvbnm` `veamhjsgqocnrbfxdtwkylupzi` 我们可以通过ascii码值来存储被替换和替换的关系，例如 `s['q'] = 'v'` 之后对需要修改的字符进行遍历，判断大小写和字符串即可 <div class="tip inlineBlock info"> C语言有一个库，`#include <ctype.h>`，可以对字母进行判断和操作 常用的函数有以下几种 | 函数 | 作用 | | - | - | | int isalnum(int ch); | ch为字母或数字时，函数返回非0，否则返回0 | | int isalpha(int ch); | ch为英文字母时，函数返回非0，否则返回0 | | int isdigit(int ch); | ch是十进制数字时，函数返回非0，否则返回0 | | int islower(int ch); | ch是小写字母，函数返回非0值，否则返回0 | | int isupper(int ch); | ch是大写字母，函数返回非0值，否则返回0 | | int tolower(int ch); | 当ch为大写字母时，返回其对应的小写字母，否则返回ch | | int toupper(int ch); | 当ch为小写字母时，返回其对应的大写字母，否则返回ch | </div> 当然对于C++可以直接使用map容器进行存储 #### Code ```c #include <ctype.h> #include <stdio.h> int main() { char s1[150]; char s2[150]; char letter[150]; scanf("%s", s1); scanf("%s", s2); for (int i = 0; i < 26; i++) { letter[s1[i]] = s2[i]; } int n; scanf("%d", &n); char res[2000 + 10]; scanf("%s", res); for (int i = 0; i < n; i++) { if (isalpha(res[i])) { if (islower(res[i])) { res[i] = letter[res[i]]; } else { res[i] = toupper(letter[tolower(res[i])]); } } } printf("%s\n", res); } ``` ```cpp #include <bits/stdc++.h> using namespace std; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { string s1, s2; cin >> s1 >> s2; map<char, char> m; for (int i = 0; i < 26; i++) { m[s1[i]] = s2[i]; } int n; cin >> n; string t; cin >> t; for (auto c : t) { if (!isalpha(c)) { cout << c; continue; } bool f = false; if ('A' <= c && c <= 'Z') { f = true; c = c - 'A' + 'a'; } if (f) { cout << (char)(m[c] - 'a' + 'A'); } else { cout << m[c]; } } cout << endl; } ``` ## D. Hinata's Zero Array #### Pt：10 #### Accepted Ratio: 0% (0 / 51) 第一个条件： 首先对于数组，因为每次需要减去两个 $1$， 所以数组元素的总和加起来必须为偶数，否则必定会留下一个剩余. 第二个条件： 最后一次相减时，必须剩余$2$个数，否则只能减去1个$1$，我们只需要找到数组的最大值，并判断它的2倍是否大于数组所有元素总和即可 顺便一说，我不知道老师有没有教过`long long`这个数据类型。 在一般的编程竞赛中 - 数据范围$1 \leq n \leq 2^{32}$ 或 $1 \leq n \leq 10^9$统一使用 `int` - 数据范围$1 \leq n \leq 2^{64}$ 或 $1 \leq n \leq 10^{18}$统一使用 `long long` - 数据为精度数的统一使用 `double` 或者 `long double` 在实际使用中，`long` 和 `int` 在数据范围等等几乎没有区别, 具体可以查看这条[博客][2] 所以在这里，因为有$10^5$个$10^9$，所以数组元素的总和`int`是无法存储的,我们需要使用`long long`进行存储 ```c #include <stdio.h> typedef long long ll; int max(int a, int b) { return a > b ? a : b; } int main() { int n, m = 0; ll sum = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { ll a; scanf("%d", &a); sum += a; m = max(m, a); } if (sum % 2 == 1 || sum < 2 * m) { puts("NO"); return 0; } puts("YES"); return 0; } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { ll n, m = 0, sum = 0; cin >> n; for (int i = 0; i < n; i++) { ll a; cin >> a; sum += a; m = max(m, a); } if (sum % 2 == 1 || sum < 2 * m) { cout << "NO" << endl; return; } cout << "YES" << endl; return; } ``` ## E. Hinata's Birthday Cake #### Pt：20 #### Accepted Ratio: 0% (0 / 13) 思维题。 首先，一个矩形切 $k$ 刀，第一个想到的就是横着竖着均匀的切，但这样实际是错误的。 正确的方法是优先均匀的切长的那一边，如果还有剩余的切割次数则均匀切短的那一边。 这纯粹就是想不想的到的问题了，当然也有严格的数学证明，这里就不再赘述了。 ```c #include <stdio.h> typedef long long ll; int max(ll a, ll b) { return a > b ? a : b; } int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); int i; ll maxans = -1; for (i = 1; i * i <= n; i++) { int t = n / i; int f = k - i + 1; if (f < 0) f = 0; if (m > f) maxans = max(maxans, (ll)m / (f + 1) * t); } for (i = 1; i * i <= n; i++) { int t = i; int f = k - n / t + 1; if (f < 0) f = 0; if (m > f) maxans = max(maxans, (ll)m / (f + 1) * t); } printf("%lld", maxans); return 0; } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { int n, m, k; cin >> n >> m >> k; int i; ll maxans = -1; for (i = 1; i * i <= n; i++) { int t = n / i; int f = k - i + 1; if (f < 0) f = 0; if (m > f) maxans = max(maxans, (ll)m / (f + 1) * t); } for (i = 1; i * i <= n; i++) { int t = i; int f = k - n / t + 1; if (f < 0) f = 0; if (m > f) maxans = max(maxans, (ll)m / (f + 1) * t); } cout << maxans << endl; } ``` ## F. Hinata And Number Root #### Pt：25 #### Accepted Ratio: 0% (0 / 18) 这是一道找规律题。 如果直接暴力求结果肯定会超时。 先将$0 - 50$的结果打出一个表，求出每个数对应的数根，即可以发现规律: ![20190129204912296.png][3] - 是一个以9为周期的循环，每个周期的结果都是 1 ~ 9 于是很容易得到结果$res = (k- 1) * 9 + x$ ```c #include <stdio.h> typedef long long ll; int main() { int t; scanf("%d", &t); while (t--) { ll n, x; scanf("%lld%lld", &n, &x); n--; printf("%lld\n", n * 9ll + x); } return 0; } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { int t; cin >> t; while (t--) { ll n, x; cin >> n >> x; n--; cout << n * 9ll + x << endl; } } ``` ## G. Hinata And Matrix #### Pt：25 #### Accepted Ratio: 0% (0 / 6) 一道简单的线性代数模拟题，虽然没学过线性代数但是Hint给出了计算公式。 直接按照公式求肯定会得到超时的结果，我们先计算$n=2,3,4,5,...$的情况 $$ A^2 = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}= \begin{bmatrix} 1+1 & 1+0 \\ 1+0 & 1+0 \end{bmatrix}= \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} $$ $$ A^3 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 2+1 & 2+0 \\ 1 + 1 & 1+0 \end{bmatrix}= \begin{bmatrix} 3 & 2 \\ 2 & 1 \end{bmatrix} $$ $$ A^4= \begin{bmatrix} 3 & 2 \\ 2 & 1 \end{bmatrix}\times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 3+2 & 3+0 \\ 2 + 1 & 2+0 \end{bmatrix}= \begin{bmatrix} 5 & 3 \\ 3 & 2 \end{bmatrix} $$ 我们可以发现，最大值永远都是左上角$a_{0,0}$的值，且$a_{0,0}$遵循斐波那契数列的规律，我们只需要预处理前$n<10^5$个的所有值，之后查询即可立刻得出结果 顺便一提，结果需要对一个数求模，需要在预处理时，每次对结果求模.`f[i] = (f[i - 1] + f[i - 2]) % MOD;` ```c #include <stdio.h> typedef long long ll; int main() { const int MOD = 998244353; const int MAXN = 1e5 + 5; int f[MAXN]; int t; scanf("%d", &t); f[0] = 1; f[1] = 1; f[2] = 2; for (int i = 3; i <= 1e5 + 1; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD; for (int i = 0; i < t; i++) { int x; scanf("%d", &x); printf("%d\n", f[x]); } } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } const int MOD = 998244353; const int MAXN = 1e5 + 5; int f[MAXN]; void run() { int t; cin >> t; f[0] = 1; f[1] = 1; f[2] = 2; for (int i = 3; i <= 1e5 + 1; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD; for (int i = 0; i < t; i++) { int x; cin >> x; cout << f[x] << '\n'; } } ``` ## H. Hinata And Calculate #### Pt：10 #### Accepted Ratio: 0% (0 / 62) 其实很简单，每次分别将分子分母相乘即可，同时gcd求一下最大公约数化简即可。同时需要注意分子为$0$时的特殊判断分母必定为$1$ 不过依旧是数据范围问题，两个`int`相乘可能会超过`int`这个范围，你需要使用`long long`来维护结果. ```c #include <ctype.h> #include <stdio.h> #include <string.h> typedef long long ll; int gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } int main() { char s[100]; scanf("%s", s); ll res1 = 1, res2 = 1; int op = 0; for (int i = 0; i < strlen(s); i++) { if (isdigit(s[i])) { if (!op) { res1 *= s[i] - '0'; if (res1 == 0) { printf("0/1"); return 0; } } else { res2 *= s[i] - '0'; } ll x = gcd(res1, res2); res1 /= x; res2 /= x; } else { if (s[i] == '*') { op = 0; } else { op = 1; } } } printf("%lld/%lld", res1, res2); } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { string s; cin >> s; ll res1 = 1, res2 = 1; int op = 0; for (int i = 0; i < s.length(); i++) { if (isdigit(s[i])) { if (!op) { res1 *= s[i] - '0'; if (res1 == 0) { cout << "0/1" << endl; return; } } else { res2 *= s[i] - '0'; } ll x = __gcd(res1, res2); res1 /= x; res2 /= x; } else { if (s[i] == '*') { op = 0; } else { op = 1; } } } cout << res1 << "/" << res2 << endl; } ``` ## I. Hinata And Prime Numbers #### Pt：5 #### Accepted Ratio: 24.48% (35 / 143) 题目说明了输出10以内的质数，那么你只需要背出来就行了，真不需要写程序计算。。。 ```c #include <stdio.h> int main() { printf("2 3 5 7\n"); } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { cout << "2 3 5 7" << endl; } ``` ## J. Hinata And Count 1 #### Pt：10 #### Accepted Ratio: 0.89% (1 / 121) 维护一个长度为$n$的数组统计出现次数和一个长度为$n$数组统计是否出现过的，初始值都赋为0，之后遍历一遍，找出出现过且出现次数最少的那个数即可。 ```c #include <stdio.h> #include <string.h> int main() { int n; scanf("%d", &n); int a[25]; int vis[25]; memset(a, 0, sizeof(a)); memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); a[x]++; vis[x] = 1; } int minx = 9999999; int res; for (int i = 0; i < 25; i++) { if (vis[i] && a[i] <= minx) { res = i; minx = a[i]; } } printf("%d", res); } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { int n; cin >> n; int a[25]; int vis[25]; memset(a, 0, sizeof(a)); memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { int x; cin >> x; a[x]++; vis[x] = 1; } int minx = 9999999; int res; for (int i = 0; i < 25; i++) { if (vis[i] && a[i] <= minx) { res = i; minx = a[i]; } } cout << res << endl; } ``` ## K. Hinata And Count 2 #### Pt：20 #### Accepted Ratio: 0% (0 / 6) 这道题用到了下学期数据结构哈希的思想 先将字符串通过给出的哈希函数转化为数字，接下来的操作就和上一题差不多了.具体请阅读代码理解 ```c #include <stdio.h> #include <string.h> int Hash(char *url, int mod) { unsigned int n = 0; char *b = (char *)&n; for (int i = 0; url[i]; i++) b[i % 4] ^= url[i]; return n % mod; } int main() { int a[100000 + 1]; int vis[100000 + 1]; char name[100000 + 1][11]; int hashed[100000 + 1]; memset(a, 0, sizeof(a)); memset(vis, 0, sizeof(vis)); memset(hashed, 0, sizeof(hashed)); int MOD = 100003; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", name[i]); hashed[i] = Hash(name[i], MOD); a[hashed[i]]++; vis[hashed[i]] = 1; } int minx = 9999999; int res; for (int i = 0; i < 100000+1; i++) { if (vis[i] && a[i] <= minx) { res = i; minx = a[i]; } } for (int i = 0; i < 100000; i++) { if (hashed[i] == res) { printf("%s\n", name[i]); return 0; } } } ``` ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define io() \ std::ios::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); #define endl '\n' void run(); int main() { io(); run(); return 0; } void run() { map<string, int> m; int n; cin >> n; for (int i = 0; i < n; i++) { string s; cin >> s; m[s]++; } string res; int minx = 0x3f3f3f3f; for (auto c : m) { if (c.second < minx) { res = c.first; minx = c.second; } } cout << res << endl; } ``` ## L. Hinata And Triangle #### Pt：15 #### Accepted Ratio: 15.85% (13 / 69) 已知三角形三点求面积。 方法很多，这里通过向量叉积求面积 $$ S=(x_1 \cdot y_2 - x_1 \cdot y_3 + x_2 \cdot y_3-x_2 \cdot y_1 + x_3 \cdot y_1 - x_2 \cdot y_2) $$ ```c #include <stdio.h> #include <math.h> struct point { double x; double y; } a[3]; double get_area(int i, int j, int w) { double x = (a[j].x - a[i].x) * (a[w].y - a[i].y); double y = (a[w].x - a[i].x) * (a[j].y - a[i].y); return fabs(x - y); } void solve() { scanf("%lf%lf", &a[0].x, &a[0].y); scanf("%lf%lf", &a[1].x, &a[1].y); scanf("%lf%lf", &a[2].x, &a[2].y); printf("%.2lf\n", get_area(0, 1, 2) / 2.0); } int main(void) { solve(); return 0; } ``` ```cpp #include <bits/stdc++.h> using namespace std; struct point { double x; double y; } a[3]; double get_area(int i, int j, int w) { double x = (a[j].x - a[i].x) * (a[w].y - a[i].y); double y = (a[w].x - a[i].x) * (a[j].y - a[i].y); return fabs(x - y); } void solve() { scanf("%lf%lf", &a[0].x, &a[0].y); scanf("%lf%lf", &a[1].x, &a[1].y); scanf("%lf%lf", &a[2].x, &a[2].y); printf("%.2lf\n", get_area(0, 1, 2) / 2.0); } int main(void) { solve(); return 0; } ``` ## M. Hinata And Magic Line #### Pt：30 #### Accepted Ratio: 0% (0 / 1) ICPC区域赛难度的题目，题解请看这个[博客][4] [1]: /usr/uploads/2021/05/1357302695.png [2]: https://blog.csdn.net/CV_Jason/article/details/85244813 [3]: /usr/uploads/2021/05/663288548.png [4]: https://blog.csdn.net/sinat_40872274/article/details/97410026 最后修改：2021 年 08 月 19 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏
暂无评论
墙啊大佬，AFO蒟蒻顶礼膜拜orz%%%