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

传送门

闲来无事,突然想 vp 一场之前忙的来不及做的

A – Adjacent Squares

这题没想到居然还会卡了一下

给出一个图,给出当前位置,看看有多少个格子相邻

行和列分别判断就好

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

C – Adjacent Swaps

这个用桶来处理一下位置,然后每次询问的时候桶和数组同时维护

#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

这个题比较有趣

首先素数的话先用一个欧拉筛预处理一下

接着要寻找合理的情况,本来是想用 \(O(n^2)\) 强行莽一下,但是一直死活写不对,就突然想到二分,一下就过了

因为 \(k = p * q ^ 3\) 且有 \(p < q\),所以可以枚举 \(q\),然后再找有多少个符合的 \(p\)

而找 \(p\) 的数量,可以直接用二分去寻找第一个大到不符合要求的 \(p\) 的位置,然后知道有多少个 \(p\) 符合条件

这题比较友好的一点是,因为查询的是素数乘积,所以不会出现说相同一个数字有多种分解的情况,就不用查重,不然还得用一个 set 去维护

#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

这题也很有趣,大概就是问 \(a\) 数组前 \(x_i\) 个 和 \(b\) 数组前 \(y_i\) 个,这两组各自形成的集合是否相等

尺取

我用的是尺取过的,但是看了别人的题解,好像都是用哈希来预处理 \(a\) 的前缀集合 还有 \(b\) 的前缀集合,然后直接判断是否相等

我认为,如果选定了 \(a\) 数组的前 \(i\) 个,则在 \(b\) 数组中,一定有一个范围 \([l, r]\) 使得答案成立

并且对于这个范围,有 \(l_{i} \leq l_{i+1}\) 和 \(r_{i} \leq r_{i+1}\),因此可以判断他是单调的,所以直接尺取区间就行,尺取复杂度为 \(O(n)\)

因为要维护一个桶,所以用了 \(map\)

总的时间复杂度为 \(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;
}
————————

Portal

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

A – Adjacent Squares

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

C – Adjacent Swaps

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