【寒假学习计划】 - 算法刷题记录

本文最后更新于:2023年11月8日 中午

说明

假期学习计划本来是很早之前就有的,但是之前的都没有更新在博客上,后来想如果每天给所学内容做一个总结,一来督促自己学习,二来方便自己查阅,所以之后会把前面的刷题记录慢慢补上,之后每天的都在这做记录。

2022.01

AcWing 1813. 方块游戏

思路

枚举,题目说明不管哪一面向上都可以,所以就两面加起来取各个字母的最大值,最后N对字母的最大值相加就是答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>

using namespace std;

int main()
{
int n;
vector<int> ans(26);
cin>>n;
string s1,s2;
for(int i=0;i<n;i++)
{
cin>>s1>>s2;
vector<int> c1(26), c2(26);
for(char c: s1) c1[c-'a']++;
for(char c: s2) c2[c-'a']++;
for(int j=0;j<26;j++)
ans[j] += max(c1[j], c2[j]);
}
for(int i=0;i<26;i++)
cout<<ans[i]<<endl;
return 0;
}

AcWing 1801. 蹄子剪刀布

思路

枚举,根据题目叙述可知,相邻两个手势之间具有胜负关系,所以我们只需要将三个手势分别编号为0,1,2(原输入编号为1-3,需要进行处理),所以可以通过(x+1)%3获得x的下一个相邻手势,然后用两个ans分别记录两种情况下的胜负关系,然后输出较大值即可

代码

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;

int main()
{
int n;
cin>>n;
int ans1=0, ans2=0;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
x--;
y--;
if((x+1)%3==y) ans1++;
if(x==(y+1)%3) ans2++;
}
cout<<max(ans1, ans2)<<endl;
return 0;
}

2022.02

AcWing 1789. 牛为什么过马路II

思路

枚举26个字母,计算字母之间只出现一次的字母,这里借鉴大佬的思路,可以使用位运算,出现一次就是1,其余即为0,最后使用bitset.count()函数返回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
27
28
29
#include<bits/stdc++.h>

using namespace std;

int main()
{
string s;
cin>>s;
int ans=0;
for(int i=0;i<26;i++)
{
bitset<32> bits;
for(char c:s)
{
bits[c-'A']=bits[c-'A']^1;
if(c-'A'==i && bits[i]==1)
{
bits=0;
bits[i]=1;
}
if(c-'A'==i && bits[i]==0)
{
ans+=bits.count();
}
}
}
cout<<ans/2<<endl;
return 0;
}

AcWing 1776. 牛的基因组学

思路

依旧是枚举的思路,按照每个位置依次进行枚举。每次枚举的时候,首先把有斑点的牛都遍历一遍,把所有出现过的基因都记录为一个库序列;其次再对没有斑点的奶牛进行遍历,如果出现了在有斑点的基因库序列中没有的基因,则退出循环(条件不成立),如果第二个循环正常退出,则说明符合条件,累加结果即可。

代码

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

using namespace std;

int n,m,ans;
const int MAXN = 110;


string s1[MAXN],s2[MAXN];

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s1[i];
for(int i=1;i<=n;i++) cin>>s2[i];
for(int i=0;i<m;i++)
{
int flag[30], x=0;
memset(flag, 0, sizeof(flag));
for(int j=1;j<=n;j++) flag[s1[j][i] - 'A'] = 1;
for(int j=1;j<=n;j++)
if(flag[s2[j][i] - 'A'] == 1)
{
x=1;
break;
}
if(x==0) ans++;
}
cout<<ans<<endl;
return 0;
}

AcWing 1762. 牛的洗牌

思路

题目给出排列后的顺序序列,要求还原出排列前的,因此我们可以按照给定的序列进行逆转即可,例如本来是奶牛从i位置去到j位置,现在逆向以后便成为了j位置的奶牛去i位置,假设用数组a保存序列,b序列记录最终位置,c序列记录三次逆序以后的位置。
由此可得,原来位于i位置的奶牛经过一次洗牌舞后会到a[i]位置,推理可得三次逆序后会到的位置序号为a[a[a[i]]],因此编写程序对已知序列按照上述逻辑逆序即可。

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

using namespace std;

typedef long long ll;

int main()
{
int n;
cin>>n;
vector<int> a(n+1), b(n+1), c(n+1);
for(int i=1;i<=n;i++)
{
int j;
cin>>j;
a[j]=i;
}
for(int i=1;i<=n;i++)
cin>>b[i];
for(int i=1;i<=n;i++)
c[a[a[a[i]]]]=b[i];
for(int i=1;i<=n;i++)
cout<<c[i]<<endl;
return 0;
}

AcWing 1750. 救生员

思路

本题主要分析方法也还是使用枚举的方法,逐个奶牛进行解雇后对区间覆盖长度(有效工作时间区间段)进行判断。

使用last变量记录上一个奶牛工作结束时间,如果当前奶牛开始的时间大于last,则其有效工作时间即为[start, end];若结束时间大于last,则[last, end]为其有效工作时间。最后根据枚举结果输出最长覆盖长度即可。

代码

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

using namespace std;

typedef long long ll;

int main()
{
int n;
cin>>n;
vector<pair<int, int>> time(n);
for(int i=0;i<n;i++)
cin>>time[i].first>>time[i].second;
sort(time.begin(), time.end());
int res=0;
for(int i=0;i<n;i++)
{
int last=-1, sum=0;
for(int j=0;j<n;j++)
{
if(j==i) continue;
int start = time[j].first, end=time[j].second;
if(start > last)
{
sum+=end-start;
last=end;
}
else if(last<end)
{
sum+=end-last;
last=end;
}
}
res=max(res, sum);
}
cout<<res<<endl;
return 0;
}

AcWing 1460. 我在哪?

思路

枚举,利用unordered_set从短到长依次遍历尝试不同长度的串,如果能找到相同存在的则说明不可以唯一判定,即跳出循环,否则就可以认为当前长度可以唯一判断,直接输出即可。

代码

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

using namespace std;

int main()
{
int n;
int i, j;
string s;
cin>>n>>s;
for(i=1;i<=n;i++)
{
unordered_set<string> S;
for(j=0;j<=n-i;j++)
{
string tmp = s.substr(j, i);
if(S.count(tmp))
{
break;
}
S.insert(tmp);
}
if(j==n-i+1)
{
cout<<i<<endl;
break;
}
}
return 0;
}

AcWing 1443. 拍照

思路

这里依然是使用枚举的方法,我们先假定已知了a[1](由于要求字典序从小到大,这里通过从小到大枚举实现),然后便可以依照b与a的关系推出后续的各个数据。

代码

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

using namespace std;

const int MAXN = 1010;

int a[MAXN], b[MAXN];
int flag[MAXN];

int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
cin>>b[i];
for(int i=1;i<b[1];i++)
{
memset(flag, 0 ,sizeof(flag));
bool res = true;
a[1]=i;
flag[i]=1;
for(int j=2;j<=n;j++)
{
int t=b[j-1]-a[j-1];
if(!flag[t] && t>=1 && t<=n)
{
a[j]=t;
flag[t]=1;
}
else
{
res=false;
break;
}
}
if(res)
{
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
break;
}
}
return 0;
}

AcWing 1672. 疯狂的科学

思路

枚举,分段找到连续的相反的一段,算作一次变换即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

string a,b;
int n, res;

int main()
{
cin>>n>>a>>b;
for(int i=0;i<n;i++)
{
if(a[i] == b[i]) continue;
int j=i;
while(a[j]!=b[j]) j++;
res++;
i=j-1;
}
cout<<res<<endl;
return 0;
}

AcWing 1660. 社交距离II

思路

枚举,双指针找最小范围

代码

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

using namespace std;

vector<pair<int, int>> a;

int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int x,s;
cin>>x>>s;
a.push_back({x, s});
}
sort(a.begin(), a.end());
int r=1e6;
int s=a[0].second;//牛的生病状态
for(int i=1;i<n;i++)
{
if(s!=a[i].second)
{
r=min(r, a[i].first-a[i-1].first);
}
s=a[i].second;
}
r--;

int cnt=0;
int x=-1;
for(int i=0;i<n;i++)
{
if(x==-1 && a[i].second)
{
x=a[i].first;
cnt++;
}
else if(x!=-1)
{
if(a[i].first-x<=r)
{
x=a[i].first;
continue;
}
if(a[i].second)
{
cnt++;
x=a[i].first;
}
}
}
cout<<cnt<<endl;
return 0;
}

AcWing 3347. 菊花链

代码

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;

const int N = 110;

int n;
int p[N];

int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i];
int res=0;
for(int i=0;i<n;i++)
{
unordered_set<int> H;
for(int j=i, s=0;j<n;j++)
{
s+=p[j];
H.insert(p[j]);
int cnt = j-i+1;
if(s%cnt == 0 && H.count(s/cnt)) res++;
}
}
cout<<res<<endl;
return 0;
}

【寒假学习计划】 - 算法刷题记录
https://www.0error.net/2022/01/20a3212b.html
作者
Jiajun Chen
发布于
2022年1月29日
许可协议