acwing周赛52(Acwing week 52)-其他
acwing周赛52(Acwing week 52)
题目链接
1.上车
算法(暴力枚举) \(O(n)\)
只需要判断出车辆空余是否大于二即可
时间复杂度
暴力一遍即可，复杂度位\(O(n)\)
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int cnt = 0;
cin >> n;
while(n--)
{
int a, b;
cin >> a >> b;
if(b - a >= 2)
cnt++;
}
cout << cnt;
return 0;
}
2.连通分量
算法(dfs + 模拟) \(O(n^3)\)
题目是找将障碍物假设位空格是的联通分量的数目
所以我们先预处理将连通块给找出来，并且将每一个连通块的数目找出来即可。
时间复杂度
预处理是n*m + 一次深搜， 枚举每一个障碍物是n*m*4,所以时间复杂度最大位\(O(n^3)\)
C++ 代码
#include<iostream>
#include <set>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10100;
int n, m, k;
char a[N][N];
int vis[N][N];
int cnt = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int dfs(int x, int y)
{
vis[x][y] = cnt; //标记是哪个连通块
int res = 0;
for(int i = 0; i < 4; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if(check(tx, ty) && !vis[tx][ty] && a[tx][ty] == '.')
{
res += dfs(tx, ty); //计算数目
}
}
return res + 1; //加上自己
}
int main()
{
int Hash[1000005];//记录每一个联通块的联通数目
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i] + 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '.' && !vis[i][j])
{
++cnt;
int c = dfs(i, j);
Hash[cnt] = c;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '*')
{
set<int> umap; //用于去重
umap.clear();
for(int k=0;k<4;k++)
{
int tx = i + dx[k], ty = j + dy[k];
if(check(tx, ty) && a[tx][ty] == '.' && umap.find(vis[tx][ty]) == umap.end())
umap.insert(vis[tx][ty]);
int res = 1;
for(auto c : umap) res += Hash[c];
a[i][j] = (res % 10) + '0';
}
}
}
}
for (int i = 1; i <= n; i++)
cout << a[i] + 1 << endl;
return 0;
}
3.信号
算法(贪心) \(O(n)\)
题目让我们找最小个数覆盖全部房子。
分析可得如果我们找到一个覆盖范围比前面一个大的，我们就可以选择后面一个最为一个最值
时间复杂度
一次遍历即可求出 \(O(n)\)
C++代码
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,r,cnt;
int qu[N];
int main()
{
cin >> n >> r;
for(int i= 1; i <= n;i++)
{
int x;
cin >> x;
if(x)
qu[cnt++]=i;
}
int last = 0, res = 0;
for(int i = 0; i < cnt; i++)
{
if(last >= n)
break;
if(qu[i] - r + 1 > last + 1)
{
res = -1;
break;
}
int j = i;
while(j + 1 < cnt && qu[j + 1] - r <= last) j++;
last = qu[j] + r - 1;
res++;
i = j;
}
if(last >= n)
cout << res;
else
cout << -1;
return 0;
}
————————
Title Link
1. Get on the bus
Algorithm (violence enumeration) \ (O (n) \)
You only need to judge whether the vehicle spare is greater than two
Time complexity
Violence once, complexity bit \ (O (n) \)
C + + code
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int cnt = 0;
cin >> n;
while(n--)
{
int a, b;
cin >> a >> b;
if(b - a >= 2)
cnt++;
}
cout << cnt;
return 0;
}
2. Connected component
Algorithm (DFS + simulation) \ (O (n ^ 3) \)
The problem is to find the number of connected components that assume that the obstacle is a space
Therefore, we first find the connected blocks by preprocessing, and find the number of each connected block.
Time complexity
The preprocessing is n * m + one deep search, and the enumeration of each obstacle is n * m * 4, so the maximum time complexity \ (O (n ^ 3) \)
C + + code
#include<iostream>
#include <set>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10100;
int n, m, k;
char a[N][N];
int vis[N][N];
int cnt = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int check(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int dfs(int x, int y)
{
vis[x][y] = cnt; //标记是哪个连通块
int res = 0;
for(int i = 0; i < 4; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if(check(tx, ty) && !vis[tx][ty] && a[tx][ty] == '.')
{
res += dfs(tx, ty); //计算数目
}
}
return res + 1; //加上自己
}
int main()
{
int Hash[1000005];//记录每一个联通块的联通数目
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i] + 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '.' && !vis[i][j])
{
++cnt;
int c = dfs(i, j);
Hash[cnt] = c;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] == '*')
{
set<int> umap; //用于去重
umap.clear();
for(int k=0;k<4;k++)
{
int tx = i + dx[k], ty = j + dy[k];
if(check(tx, ty) && a[tx][ty] == '.' && umap.find(vis[tx][ty]) == umap.end())
umap.insert(vis[tx][ty]);
int res = 1;
for(auto c : umap) res += Hash[c];
a[i][j] = (res % 10) + '0';
}
}
}
}
for (int i = 1; i <= n; i++)
cout << a[i] + 1 << endl;
return 0;
}
3. Signal
Algorithm (greedy) \ (O (n) \)
Let’s find the minimum number to cover all the houses.
The analysis shows that if we find one with a larger coverage than the previous one, we can choose the latter one as the most value
Time complexity
\ (O (n) \) can be found in one traversal
C + + code
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,r,cnt;
int qu[N];
int main()
{
cin >> n >> r;
for(int i= 1; i <= n;i++)
{
int x;
cin >> x;
if(x)
qu[cnt++]=i;
}
int last = 0, res = 0;
for(int i = 0; i < cnt; i++)
{
if(last >= n)
break;
if(qu[i] - r + 1 > last + 1)
{
res = -1;
break;
}
int j = i;
while(j + 1 < cnt && qu[j + 1] - r <= last) j++;
last = qu[j] + r - 1;
res++;
i = j;
}
if(last >= n)
cout << res;
else
cout << -1;
return 0;
}