算法学习刷题记录-210717

本文最后更新于:2021年7月17日 下午

3768. 字符串删减 - AcWing题库

思路

双指针的练习

C++代码

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 <cstring>
#include <algorithm>

using namespace std;

int main()
{
int n;
string s;
cin>>n>>s;
int res=0;
for(int i=0;i<n;i++)
{
if(s[i]!='x') continue;
int j=i+1;
while(j<n && s[j]=='x') j++;
res+=max(0, j-i-2);
i=j-1;
}
cout<<res<<endl;
return 0;
}

3769. 移动石子 - AcWing题库

思路

经典的贪心移动石子问题

C++代码

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
int T;
cin>>T;
while(T--)
{
int n,d;
cin>>n>>d;
int res=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
if(!i) res+=x;
else
{
int t=min(x, d/i);
res+=t;
d-=t*i;
}
}
cout<<res<<endl;
}
return 0;
}

3761. 唯一最小数 - AcWing题库

思路

哈希表

代码

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 <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

const int N = 200010;

int n;
int w[N], cnt[N];

int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
memset(cnt, 0, (n+1) * 4);
for(int i=0;i<n;i++)
{
cin>>w[i];
cnt[w[i]]++;
}
int res=-1;
for(int i=0;i<n;i++)
{
if(cnt[w[i]]==1)
{
if(res==-1 || w[res] > w[i])
res=i;
}
}
if(res!=-1) res++;
cout<<res<<endl;
}
return 0;
}

3762. 二进制矩阵 - AcWing题库

思路

找规律,每操作三次就可以改变一个方格内的值而不影响其他方格的值,题目未要求最优解,所以以此为据直接进行枚举即可

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
char g[N][N];

void pL(int i, int j, int k)
{
if (!k) printf("%d %d %d %d %d %d\n", i, j, i + 1, j, i, j + 1);
else if (k == 1) printf("%d %d %d %d %d %d\n", i, j - 1, i, j, i + 1, j);
else if (k == 2) printf("%d %d %d %d %d %d\n", i - 1, j, i, j, i, j - 1);
else printf("%d %d %d %d %d %d\n", i - 1, j, i, j, i, j + 1);
}

int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> m;
int res = 0;
for (int i = 1; i <= n; i ++ )
{
cin >> g[i] + 1;
for (int j = 1; j <= m; j ++ )
if (g[i][j] == '1')
res += 3;
}
cout << res << endl;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (g[i][j] == '1')
{
if (i < n && j < m)
pL(i, j, 0), pL(i, j + 1, 1), pL(i + 1, j, 3);
else if (i == n && j == m)
pL(i, j, 2), pL(i - 1, j, 1), pL(i, j - 1, 3);
else if (i == n)
pL(i, j, 3), pL(i - 1, j, 0), pL(i, j + 1, 2);
else
pL(i, j, 1), pL(i, j - 1, 0), pL(i + 1, j, 2);
}
}
return 0;
}

3767. 最小的值 - AcWing题库

思路

贪心

代码

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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int a[N], b[N];

int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
int x=0, y=0;
for(int i=0;i<n;i++)
if(a[i]<b[i]) x++;
else if(a[i] > b[i]) y++;
if(!y) puts("-1");
else cout<<(x+y)/y<<endl;

return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!