2022牛客寒假算法基础集训营2

2022牛客寒假算法基础集训营2补题

Posted by zhangmh on 2022-01-29
Estimated Reading Time 10 Minutes
Words 2.2k In Total
Viewed Times

这场打的稀碎啊。。。

按照出题人给的题目难度顺序排序,感觉之前顺序排列意义不大。

C - 小沙的杀球

img

思路:贪心思想,如果可以杀球那就先杀球,因为若是可以杀球时选择恢复体力,后期可能没有机会杀球了。

AC代码:

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
ll x,a,b;
string s;
int cnt;

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>x>>a>>b;
cin>>s;
int len=s.length();
for(int i=0;i<len;i++)
{
if(x>=a&&s[i]=='1') cnt++,x-=a;
else x+=b;
}
cout<<cnt<<'\n';
return 0;
}

K - 小沙的步伐

img

img

思路:注意读题,只要是非5的数字,就给这个数字和5经过次数各加1,若是5则不进行处理。

AC代码:

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
const int N=13;
string s;
int cnt[N];

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>s;
int len=s.length();
for(int i=0;i<len;i++)
{
if(s[i]!='5')
{
cnt[s[i]-'0']++;
cnt[5]++;
}
}
for(int i=1;i<=9;i++)
cout<<cnt[i]<<" \n"[i==9];
return 0;
}

os:读题看了挺长时间的,在看ps是什么意思,,,结果是只对5来考虑的。因为小细节WA了一发,太不应该了。。。

H - 小沙的数数

img

思路:我们知道a+b=2*a&b+a^b,所以当a^b最大时,a&b=0,满足该条件的a和b满足同位上不全为1。所以对m进行二进制拆分,例如21二进制为10101,拆为二进制下的10000+100+1,n个元素,每个元素对于拆分的这三个数选择时的概率相同,那么方案数为n^3,所以对于每个m,我们先计算二进制形式有x个1,答案就是n^x。

AC代码:

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
ll n,m,ans;

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n>>m;
ans=1;
n%=mod;
while(m)
{
if(m&1) res=res*n%mod;
m>>=1;
}
cout<<ans<<'\n';
return 0;
}

os:一开始按照组合数做的,结果还算错了,,,这样想就很简单,数学需要加强哇

E - 小沙的长路

img

思路: 最长路的最小值,构造时尽量使图中没有环,此时每个点经过一次,路径把所有点穿成一条线,最小值即n-1;对于最大值,我们可以构造一个完全图进行删边,使其形成欧拉回路,可以理解成“一笔画”问题,一个无向图存在欧拉回路,当且仅当该图所有顶点度数都为偶数,且该图是连通图,所以根据n的奇偶性分类讨论,奇数时,直接构造完全图,可以经过每条边;n为偶数时,就需要删去某些边,使其满足欧拉回路的条件。

AC代码:

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;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
ll n;

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n;
if(n&1) cout<<n-1<<' '<<n*(n-1)/2<<'\n';
else cout<<n-1<<' '<<n*(n-1)/2-n/2+1<<'\n';
return 0;
}

os:欧拉回路第一次听说欸

F - 小沙的算术

img

思路: 由于运算有优先级,所以我们可以把乘法用并查集维护,每次修改就不用遍历数组,直接把所有相连乘积除以原数,乘上新数即可,对于加法,可以直接相加。并查集的维护:加法运算的数字fa[i]=i,而对于乘法运算,则把连乘的开端作为子连至连乘的末端的父节点,同时在父节点存连乘的积。

AC代码:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
const int N=1e6+5;
int n,q,fa[N];
string s;
ll sum[N],a[N],ans,x,y;

ll pmod(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}

ll inv(ll x)
{
return pmod(x,mod-2);
}

void init()
{
for(int i=1;i<=n;i++) fa[i]=i;
}

int getfa(int x)
{
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n>>q;
cin>>s; s=' '+s;
init();
for(int i=1;i<=n;i++) cin>>a[i],sum[i]=a[i];
for(int i=1;i<n;i++)
{
if(s[i]=='*')
{
int f1=getfa(i),f2=getfa(i+1);
fa[f1]=f2;
sum[f2]=sum[f2]*sum[f1]%mod;
}
}
for(int i=1;i<=n;i++)
{
if(getfa(i)==i)
ans=(ans+sum[i])%mod;
}
while(q--)
{
cin>>x>>y;
ll f1=getfa(x);
ans=(ans-sum[f1]+mod)%mod;
sum[f1]=sum[f1]*inv(a[x])%mod;
a[x]=y;
sum[f1]=sum[f1]*y%mod;
ans=(ans+sum[f1])%mod;
cout<<ans<<'\n';
}
return 0;
}

os:一开始看这个题的时候看到数据范围人傻了,肯定不能暴力做,没想到可以用并查集维护

A - 小沙的炉石

img

img

思路:注意理解题意,法术伤害对于每一张攻击牌的影响随时间增长,所以对于一定数量的恢复牌和攻击牌,伤害是一个既定范围,最小值为先把所有的攻击牌用完,再用恢复牌;最大值为先把所有的恢复牌用完,再把攻击牌用完,所有攻击牌伤害的和可以看做一个等差数列求和,注意特判。

AC代码:

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
ll n,m,q,u,x,ans;

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n>>m>>q;
u=min(m+1,n),x=u+m;//u为最多攻击多少次
ans=(m+1+x)*u/2;
while(q--)
{
ll a;
cin>>a;
if(m==1&&n>1&&(a==3||a>5))
{
cout<<"NO"<<'\n';
continue;
}
if(m==2&&a==8)
{
cout<<"NO"<<'\n';
continue;
}
if(a<=ans)
cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}

I - 小沙的构造

img

思路: 考察代码能力,字符串构造,注意特判

AC代码:

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll!!!
//判断是否需要初始化!!!
const int mod=1e9+7;
const int N=1e4+5;
char s1[]="\"!\'*+-.08:=^_WTYUIOAHXVM|";
string s2[5]={"<>","\\/","[]","{}","()"};
int n,m,a1,a2;
char s[N];

int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n>>m;
if(m>=36||n<m)
{
cout<<"-1"<<'\n';
return 0;
}
if(m<=11)
{
if(m%2==0) a1=(m-2)/2,a2=2;
else a1=m/2,a2=m%2;
}
else a1=5,a2=m-10;
if(n-m+1<a2)
{
cout<<"-1"<<'\n';
return 0;
}
for(int i=1;i<=a1;i++)
{
s[i]=s2[i-1][0];
s[n-i+1]=s2[i-1][1];
}
int l=a1+1,r=n-a1,cnt=0;
while(l<=r)
{
cnt++;
s[l]=s1[cnt-1];
s[r]=s1[cnt-1];
l++;
r--;
if(cnt>=a2)
{
while(l<=r)
{
s[l]=s1[cnt-1];
s[r]=s1[cnt-1];
l++;
r--;
}
}
}
s[n+1]='\0';
printf("%s",s+1);
return 0;
}

os:学习网友的代码,很简洁很好懂,,,之前构造字符串一直不太ok

这场好难啊QAQ

若有错误请赐教orz


If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !