2024牛客寒假算法基础集训营4
A 柠檬可乐
题意
根据给定的 \(a\) 和 \(b\)，判断是否 \(a \ge k \times b\)
思路
题意非常直接
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 柠檬可乐
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67744/A
| When: 2024-02-19 13:08:06
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a,b,k;
cin >> a >> b >> k;
if(a >= k*b)cout << "good" << "\n";
else cout << "bad" << "\n";
return 0;
}
B 左右互博
题意
讨厌鬼在和小甜妹在玩石头游戏。 游戏一开始有 \(n\) 堆石子，第 \(i\) 堆石子，有 \(a_i\) 个石子。两人轮流进行游戏。 轮到某个人时，这个人先选数量为 \(x(x>1)\) 的一堆石子，然后选择一个整数 \(y(2 \leq y \leq x)\)，将选择的 \(x\) 个石子分为两堆石子，数量分别为 \(\lfloor \frac{x}{y} \rfloor\) 和 \(x-\lfloor \frac{x}{y} \rfloor\)。 当有某个人不能操作时，则失败，另一个人胜利。 两人都绝顶聪明，必定使用最佳策略。讨厌鬼先手，他想知道他能不能获得胜利？
思路
假设某堆石子共有 \(x\) 个，因为必须选 \(x \gt 1\)的一堆，否则就输了，最后游戏结束的局面肯定是每一堆石子都只有 \(1\) 个。
所以对这堆石子操作的最优策略肯定是将其分为 \(x-1\)个石子 和 \(1\) 个石子 的两堆。
所以只要判断 个数不为 \(1\) 的 石子堆的个数和他们石子总数的奇偶性即可
奇数就是 sweet 赢，偶数就是 gui 赢
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 左右互博
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67744/B
| When: 2024-02-19 13:09:33
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
ll sum = 0;
int cnt = 0;
std::vector<int> a(n);
for(int i = 0;i < n;i++){
cin >> a[i];
if(a[i] != 1){
cnt++;
sum+=a[i];
}
}
if((sum - cnt) % 2 == 0)cout << "sweet";
else cout << "gui";
return 0;
}
C 冬眠
题意
阿宁生活在一个 \(n\) 行 \(m\) 列的字符矩阵中，阿宁打算在第 \(x\) 行 \(y\) 列冬眠。
在每一天，都会有 \(q\) 次行循环移动或列循环移动。
如果是第 \(z\) 行循环移动，那么第 \(z\) 行所有字符往后移动一个，最后一个字符移动到第 \(z\) 行开头。
如果是第 \(z\) 列循环移动，那么第 \(z\) 列所有字符往后移动一个，最后一个字符移动到第 \(z\) 列开头。
阿宁将要冬眠 \(p\) 天，冬眠结束后阿宁想知道第 \(x\) 行 \(y\) 列是什么字符？
思路
数据范围允许暴力模拟，直接模拟即可
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 冬眠
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67744/C
| When: 2024-02-19 13:20:34
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char zf[110][110];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,x,y;
cin >> n >> m >> x >> y;
for(int y = 0;y < n;y++){
for(int x = 0; x < m;x++){
cin >> zf[y][x];
}
}
int p,q;
cin >> p >> q;
vector<pair<int,int>>cz(q);
for(auto &[op,z]:cz){
cin >> op >> z;
}
while(p--){
for(auto &[op,z]:cz){
if(op == 1){
char tp = zf[z-1][m-1];
for(int i = m-2;i >= 0;i--){
zf[z-1][i+1] = zf[z-1][i];
}
zf[z-1][0] = tp;
}else{
char tp = zf[n-1][z-1];
for(int i = n-2;i >= 0;i--){
zf[i+1][z-1] = zf[i][z-1];
}
zf[0][z-1] = tp;
}
}
// for(int y = 0;y < n;y++){
// for(int x = 0;x < m;x++){
// cout << zf[y][x] << " \n"[x == m-1];
// }
// }
}
cout << zf[x-1][y-1];
return 0;
}
D 守恒
题意
有一个长度为 \(n\) 正整数数组 \(a\)。
可以进行任意次操作，每次操作选择数组 \(a\) 的两个元素，其中一个加 \(1\)，另一个减 \(1\)，要求每次操作后 \(a\) 的各元素仍然是正整数。
想知道操作结束后，数组的最大公约数可能有多少种不同的值？
数组的最大公约数指，该数组的所有数共有约数中最大的那个数。
思路
设数组的最大公约数为 \(x\) ，则数组中的每个数都是 \(x\) 的倍数
如果数组共有 \(n\) 个元素，数组元素总和最小的情况就是 \(n\) 个 \(x\)，也就是这个数组能求出来的最大的最大公约数。
令 \(sum(a)\) 为数组 \(a\) 所有元素的总和。
当 \(n = 1\) 时，最大公约数就是 \(1\)，
当 \(n \ge 2\) 时，必须满足 \(sum \ge n * x\) 并且 \(sum \mod x = 0\)
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 守恒
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67744/D
| When: 2024-02-19 17:39:11
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll sum = 0;
ll n;
cin >> n;
for(int i = 1;i <= n;i++){
ll x;
cin >> x;
sum += x;
}
ll cnt = 0;
for(ll i = 1;i <= sum / n;i++){
if(sum % i == 0)cnt++;
}
cout << (n == 1 ? 1 : cnt);
return 0;
}
G 数三角形（easy）
认为一个大小为 \(x\) 的等腰三角形底边长度是 \(2\times x+1\)，高是 \(x+1\)。
大小为 \(2\) 和大小为 \(3\) 的三角形，都有两个大小为 \(1\) 的三角形。
现在给出一个 \(n\) 行 \(m\) 列的仅包含 '*' 和 '.' 的矩阵， 阿宁想要数一下有多少个满足要求的等腰三角形？
思路
等腰三角形的斜边，必须满足如下
*
.
*
.
这样的规律间隔的
如果暴力，会达到 \(O(n^5)\) ，必然超时
考虑用标记数组，预处理每个点作为等腰三角形的两底角顶点能支持构建起的最长的斜边长度和底边长度。
例如当前遍历到的点为 \((x,y)\)，要判断的是否能以此点构建起大小为 \(s\) 的三角形
要满足条件如下：
\((x-s,y+s)\) 能构建起的斜边长度最长长度大于 \(s\) ，并且\((x+s,y+s)\) 能够构建起的斜边长度最长长度大于 \(s\) ，能构建起的最长底边长度为 \(\frac{s-1}{2}\)
代码
/*******************************
| Author: AlwaysBeShine
| Problem: 数三角形（easy）
| Contest: NowCoder
| URL: https://ac.nowcoder.com/acm/contest/67744/G
| When: 2024-02-19 14:17:05
|
| Memory: 524288 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt;
int n,m;
char jz[505][505];
int qzh[505][505];
int qzh1[505][505];
int qzh2[505][505];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int y = 1;y <= n;y++){
for(int x = 1;x <= m;x++){
cin >> jz[x][y];
if(jz[x][y] == '.'){
qzh[x][y] = 0;
qzh1[x][y] = 0;
qzh2[x][y] = 0;
}else{
qzh[x][y] = qzh1[x][y] = qzh2[x][y] = 1;
qzh[x][y] += qzh[x-1][y];
qzh1[x][y] += qzh1[x+1][y-1];
qzh2[x][y] += qzh2[x-1][y-1];
}
}
}
if(n < 2 || m < 3){
cout << 0;
}else{
for(int x = 2;x <= m-1;x++){ //遍历每一个点
for(int y = 1;y <= n-1;y++){
if(jz[x][y] == '*'){
for(int size = 1; n - y + 1 >= size + 1 && x - size >= 1 && x + size <= m;size++){ //遍历每个有可能作为顶点的位置
if(qzh1[x-size][y+size] - 1 >= size && qzh2[x+size][y+size] -1 >= size && qzh[x+size][y+size] -1 >> 1 >= size)cnt++;
}
}
}
}
cout << cnt;
}
return 0;
}