acwing周赛52(Acwing week 52)-其他

acwing周赛52(Acwing week 52)

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;
}
``````

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;
}
``````

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;
}
``````
————————

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;
}
``````

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;
}
``````

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;
}
``````