# AtCoder Beginner Contest 250 A – E 题解(250 coder – coder a)-其他

## AtCoder Beginner Contest 250 A – E 题解(250 coder – coder a)

#include <iostream>
using namespace std;

int main()
{
int n, m;
cin >> n >> m;
int x, y;
cin >> x >> y;
int cnt = 0;
if(n == 1) cnt += 2;
else if(x == 1 || x == n) cnt++;
if(m == 1) cnt += 2;
else if(y == 1 || y == m) cnt++;
cout << 4 - cnt << endl;
return 0;
}


### B – Enlarged Checker Board

#include <iostream>
using namespace std;
const int maxn = 110;
char s[maxn][maxn];

int main()
{
int n, a, b;
cin >> n >> a >> b;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
char now = (i + j) % 2 == 0 ? '.' : '#';
for(int x=i*a; x<i*a+a; x++)
{
for(int y=j*b; y<j*b+b; y++)
{
s[x][y] = now;
}
}
}
}
for(int i=0; i<a*n; i++)
{
for(int j=0; j<b*n; j++)
cout << s[i][j];
cout << endl;
}
return 0;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int num[maxn], alp[maxn];

int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) num[i] = alp[i] = i;
while(m--)
{
int x;
scanf("%d", &x);
if(alp[x] == n) x = num[n-1];
int way = alp[x];
int a = num[way];
int b = num[way + 1];
swap(num[way], num[way+1]);
swap(alp[a], alp[b]);
}
for(int i=1; i<=n; i++)
{
if(i != 1) printf(" ");
printf("%d", num[i]);
}
printf("\n");
return 0;
}


### D – 250-like Number

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
int prime[maxn], tp = 0;
long long p[maxn];

void init()
{
int n = 1e6 + 1;
for(int i=2; i<n; i++) prime[i] = 1;
for(int i=2; i<n; i++)
{
if(prime[i])
{
p[tp++] = i;
for(int j=i+i; j<n; j+=i)
prime[j] = 0;
}
}
}

int main()
{
int t = 0;
init();
long long n;
cin >> n;
for(int i=0; i<tp; i++)
{
long long now = p[i] * p[i] * p[i];
long long x = n / now;
t += upper_bound(p, p + i, x) - p;
}
cout << t << endl;
return 0;
}



### E – Prefix Equality

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
pii num[maxn];

int main()
{
int n;
scanf("%d", &n);
map<int, int> r_vis, l_vis;
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=n; i++) scanf("%d", &b[i]);
b[++n] = a[1];
int l = 1, r = 1, cnt = 0;
for(int i=1; i<=n; i++)
{
if(r_vis[a[i]] == 0) r_vis[a[i]] = 1;
if(l_vis[a[i]] == 0) {cnt++; l_vis[a[i]] = 1;}
while(l <= n && cnt > 0)
{
if(l_vis[b[l]] == 1) cnt--;
l_vis[b[l]] = 2;
l++;
}
while(r <= n && r_vis[b[r]]) r++;
num[i] = make_pair(l - 1, r - 1);
}
int m;
scanf("%d", &m);
for(int i=0; i<m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(y >= num[x].first && y <= num[x].second) printf("Yes\n");
else printf("No\n");
}
return 0;
}

————————

Portal

I have nothing to do. I suddenly think VP of something I was too busy to do before

I didn’t expect to get stuck in this question

Give a diagram, give the current position, and see how many grids are adjacent

Just judge the row and column separately

#include <iostream>
using namespace std;

int main()
{
int n, m;
cin >> n >> m;
int x, y;
cin >> x >> y;
int cnt = 0;
if(n == 1) cnt += 2;
else if(x == 1 || x == n) cnt++;
if(m == 1) cnt += 2;
else if(y == 1 || y == m) cnt++;
cout << 4 - cnt << endl;
return 0;
}


### B – Enlarged Checker Board

A simulation, after calculation, will not explode the space, so write it directly and then print it

#include <iostream>
using namespace std;
const int maxn = 110;
char s[maxn][maxn];

int main()
{
int n, a, b;
cin >> n >> a >> b;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
char now = (i + j) % 2 == 0 ? '.' : '#';
for(int x=i*a; x<i*a+a; x++)
{
for(int y=j*b; y<j*b+b; y++)
{
s[x][y] = now;
}
}
}
}
for(int i=0; i<a*n; i++)
{
for(int j=0; j<b*n; j++)
cout << s[i][j];
cout << endl;
}
return 0;
}


The bucket is used to handle the position, and then the bucket and array are maintained at the same time every time

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int num[maxn], alp[maxn];

int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) num[i] = alp[i] = i;
while(m--)
{
int x;
scanf("%d", &x);
if(alp[x] == n) x = num[n-1];
int way = alp[x];
int a = num[way];
int b = num[way + 1];
swap(num[way], num[way+1]);
swap(alp[a], alp[b]);
}
for(int i=1; i<=n; i++)
{
if(i != 1) printf(" ");
printf("%d", num[i]);
}
printf("\n");
return 0;
}


### D – 250-like Number

This question is more interesting

First of all, prime numbers are pretreated with an Euler sieve

Then we need to find a reasonable situation. We originally wanted to use \ (O (n ^ 2) \) to force recklessness, but we kept writing it wrong, so we suddenly thought of two points and passed it at once

Because \ (k = P * q ^ 3 \) and \ (P & lt; Q \), you can enumerate \ (Q \) and then find how many matching \ (P \)

To find the number of \ (P \), you can directly use two points to find the position of the first \ (P \) that is too large to meet the requirements, and then know how many \ (P \) meet the conditions

The more friendly point of this question is that because the query is the product of prime numbers, there will be no case that the same number has multiple decomposition, so there is no need to check the duplicate, otherwise you have to use a set to maintain it

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int maxn = 1e6 + 10;
int prime[maxn], tp = 0;
long long p[maxn];

void init()
{
int n = 1e6 + 1;
for(int i=2; i<n; i++) prime[i] = 1;
for(int i=2; i<n; i++)
{
if(prime[i])
{
p[tp++] = i;
for(int j=i+i; j<n; j+=i)
prime[j] = 0;
}
}
}

int main()
{
int t = 0;
init();
long long n;
cin >> n;
for(int i=0; i<tp; i++)
{
long long now = p[i] * p[i] * p[i];
long long x = n / now;
t += upper_bound(p, p + i, x) - p;
}
cout << t << endl;
return 0;
}



### E – Prefix Equality

This question is also very interesting. It is probably to ask whether the two groups of \ (x_i \) before the \ (a \) array and \ (y_i \) before the \ (B \) array are equal

Ruler take

I took it with a ruler, but after looking at other people’s solutions, it seems that hashing is used to preprocess the prefix set of \ (a \) and the prefix set of \ (B \), and then directly judge whether it is equal

I think that if the first \ (I \) of the \ (a \) array is selected, there must be a range \ ([l, R] \) in the \ (B \) array to make the answer true

And for this range, there are \ (L {I} \ Leq L {I + 1} \) and \ (R {I} \ Leq R {I + 1} \), so it can be judged that it is monotonous, so it is OK to directly scale the interval, and the scale complexity is \ (O (n) \)

Because a bucket needs to be maintained, a \ (map \) is used

The total time complexity is \ (O (nlogn) \)

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
pii num[maxn];

int main()
{
int n;
scanf("%d", &n);
map<int, int> r_vis, l_vis;
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=n; i++) scanf("%d", &b[i]);
b[++n] = a[1];
int l = 1, r = 1, cnt = 0;
for(int i=1; i<=n; i++)
{
if(r_vis[a[i]] == 0) r_vis[a[i]] = 1;
if(l_vis[a[i]] == 0) {cnt++; l_vis[a[i]] = 1;}
while(l <= n && cnt > 0)
{
if(l_vis[b[l]] == 1) cnt--;
l_vis[b[l]] = 2;
l++;
}
while(r <= n && r_vis[b[r]]) r++;
num[i] = make_pair(l - 1, r - 1);
}
int m;
scanf("%d", &m);
for(int i=0; i<m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(y >= num[x].first && y <= num[x].second) printf("Yes\n");
else printf("No\n");
}
return 0;
}