本文最后更新于：2023年11月8日 中午
说明
假期学习计划本来是很早之前就有的，但是之前的都没有更新在博客上，后来想如果每天给所学内容做一个总结，一来督促自己学习，二来方便自己查阅，所以之后会把前面的刷题记录慢慢补上，之后每天的都在这做记录。
2022.01
思路
枚举，题目说明不管哪一面向上都可以，所以就两面加起来取各个字母的最大值，最后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;
}
|
思路
枚举，根据题目叙述可知，相邻两个手势之间具有胜负关系，所以我们只需要将三个手势分别编号为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
思路
枚举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;
}
|
思路
依旧是枚举的思路，按照每个位置依次进行枚举。每次枚举的时候，首先把有斑点的牛都遍历一遍，把所有出现过的基因都记录为一个库序列；其次再对没有斑点的奶牛进行遍历，如果出现了在有斑点的基因库序列中没有的基因，则退出循环（条件不成立），如果第二个循环正常退出，则说明符合条件，累加结果即可。
代码
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;
}
|
思路
题目给出排列后的顺序序列，要求还原出排列前的，因此我们可以按照给定的序列进行逆转即可，例如本来是奶牛从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;
}
|
思路
本题主要分析方法也还是使用枚举的方法，逐个奶牛进行解雇后对区间覆盖长度（有效工作时间区间段）进行判断。
使用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;
}
|
思路
枚举，利用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;
}
|
思路
这里依然是使用枚举的方法，我们先假定已知了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;
}
|
思路
枚举，分段找到连续的相反的一段，算作一次变换即可。
代码
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;
}
|
思路
枚举，双指针找最小范围
代码
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;
}
|
代码
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;
}
|