比赛链接：牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
点开看着 C 题有意思，所以打算今天来补补题。
然后突然发现笔记还有好多周赛的题没补，很恐怖了。👹👹
A 小红的大小判断
题意： 判断 和 谁大。
思路：
这个题很考验数学，嗯……
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
int x;
cin>>x;
if(x!=1)cout<<"right";
else cout<<"equal";
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
B 小红的大小再判断
题意：
判断该字符串反转后的字典序和原串哪个更大。
思路：
用 reverse 反转再拿 compare 比较。不记得 compare 就用 for 循环比较。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
string s;
cin>>s;
string re=s;
reverse(re.begin(),re.end());
if(s.compare(re)==0)cout<<"equal";
else if(s.compare(re)<0)cout<<"right";
else cout<<"left";
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
C 小红的肥鹅健身房
题意：
给一个 n 行 m 列的矩阵，某些格子上有一个数字。我们使用 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格中的数字。
小红每次操作可以选择两个相等的数字合成出一个比原数字大 1 的数字（原来两个数字消失，新数字在矩阵上任意一个空位置生成），例如选择两个 13，可以合成一个 14。如果生成的数字不小于 k，小红还可以获得一枚金币。初始棋盘上的数字不计入金币获得。
现在问小红最多可以合成多少次，以及最多可以获得多少枚金币。
思路：
这个题其实就是统计每个数字出现的次数然后去从小到大循环一次，但是不建议开个数组去存，那样不好控制。
使用 map 键值对存储。遍历map中的每个数字，大于 2 的合成。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
map<int,int>a;
void solve()
{
int n,m,k;
cin>>n>>m>>k;
int cnt=0,ans=0;
for(int i=0;i<n*m;i++)
{
int x;
cin>>x;
if(x!=0)a[x]++;
}
for(auto [u,v]:a)
{
if(v>=2){
int t=v/2;
a[u+1]+=t;
cnt+=t;
if(u+1>=k)ans+=t;
}
}
cout<<cnt<<" "<<ans<<endl;
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
D 小红的神秘密码解锁
题意：
密码 s 由 0 和 1 组成，下标从 1 开始。连续相同字符构成一个“颜色块”。可以选择一个连续子串 [l,r]，把其中的 0 变 1，1 变 0。
有多少种不同的翻转区间[l,r]，使得翻转后颜色块的数量 不变。
思路：
翻转的结果只和左右边界有关。如果 a[l] 和 a[l-1] 不同的话，在翻转后颜色块减一，如果相等的话，颜色块加一。右边界也一样。内部的翻转不会影响相邻关系，颜色块数量不变。
如果要使翻转后颜色块数量不变的话就需要左边相等右边不等或者左边不等右边相等。
所以只需要统计一下相邻两个密码相等/不相等的个数，进行组合就可以得到结果。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
string s;
cin>>s;
int n1=0,n2=0;
for(int i=1;i<s.size();i++)
{
if(s[i]!=s[i-1])n1++;
else n2++;
}
cout<<n1*n2+1;
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
E 小红的多维空间冒险
题意：
思路：
只有 0 或 1 两种数，所以当 时 ；当 时 。
最后其实就是 。
也就是坐标位上不同的数量为 。
有 个节点，所以就有 个坐标位。从中任意选出 k 个。也就是 。节点无序所以再除以 2 即为
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int MOD=1e9+7;
int qmi(int a,int b)
{
int res=1;
while(b){
if(b&1)res=res*a%MOD;
a=a*a%MOD;
b>>=1;
}
return res%MOD;
}
void solve()
{
int n;
cin>>n;
int m=qmi(2,n-1);
int t=n;
for(int i=1;i<=n;i++)
{
if(i==1)t=n;
else{
t=t*(n-i+1)%MOD;
t=t*qmi(i,MOD-2)%MOD;
}
cout<<t*m%MOD<<" ";
}
}
signed main(){
IOS
int t=1;
while(t--)
{
solve();
}
}
|
F 先放放😫😫
