[数据结构与算法]AtCoder Beginner Contest 250

A - Good morning

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 110, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    int n, m, r, c;
    cin >> n >> m >> r >> c;
    int ans = 4;
    if (r == 1) ans -- ;
    if (r == n) ans -- ;
    if (c == 1) ans -- ;
    if (c == m) ans -- ;
    cout << ans << endl;
    return 0;
}

B - Enlarged Checker Board

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 110, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    
    string s;
    bool flag = true;
    for (int k = 1; k <= n; k ++ )
    {
        for (int u = 1; u <= n; u ++ )
        {
            for (int j = 1; j <= b; j ++ )
            {
                if (flag)
                    s += '.';
                else
                    s += '#';
            }
            flag = !flag;
        }
        
        for (int i = 1; i <= a; i ++ )
        {
            printf("%s\n", s.c_str());
        }
        if (s[0] != s[sz(s) - 1])
            flag = !flag;
        s = "";
    }
    return 0;
}

C - Adjacent Swaps

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 200010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int a[N];
unordered_map<int, int> mp;

int main()
{
    cin >> n >> m;
    rep(i, 1, n + 1) mp[i] = i, a[i] = i;
    
    while (m -- )
    {
        int x;
        scanf("%d", &x);
        
        int p = mp[x];
        if (p < n)
        {
            int l = a[p], r = a[p + 1];
            int t = mp[l];
            mp[l] = mp[r];
            mp[r] = t;
            swap(a[p], a[p + 1]);
        }
        else
        {
            int l = a[p], r = a[p - 1];
            int t = mp[l];
            mp[l] = mp[r];
            mp[r] = t;
            swap(a[p], a[p - 1]);
        }
    }
    rep(i, 1, n + 1)
        printf("%d ", a[i]);
    puts("");
    return 0;
}

D - 250-like Number

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 1000010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

ll m;
int primes[N], cnt;
bool st[N];

void get_primes(int n)  // 线性筛质数
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> m;
    get_primes(N);
    
    ll res = 0;
    
    rep (i, 0, cnt - 1)
    {
        int l = i + 1, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r  + 1 >> 1;
            if (pow(primes[mid], 3) <= m / primes[i]) l = mid;
            else r = mid - 1;
        }
        if (pow(primes[l], 3) > m / primes[i]) break;
        res += (l - i);
    }
    cout << res << endl;
    return 0;
}

E - Prefix Equality

这道题告诉我们边界很重要。
主要是初始化的时候按照题目要求来叭，保证初始化答案跟正确的答案不能有交集。
做法就是两个集合比较大小是否相等就可以了，提前预处理好对应a每一个数在b中的区间范围。

// shiran
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 200010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int a[N], b[N];
set<int> sa, sb;
PII q[N];

void init()
{
    int k = 1;
    rep(i, 1, n + 1)
    {
        if (!sa.count(a[i]))
        {
            sa.insert(a[i]);
            if (!sa.count(b[k])) continue;
            int l = -1;
            while (k <= n && sa.count(b[k])) 
            {   
                sb.insert(b[k]);
                if (l == -1 && sb.size() == sa.size()) l = k;
                k ++ ;
            }
            if (l != -1)
                q[i] = {l, k - 1};
        }
        else
        {
            q[i] = q[i - 1];
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, 1, n + 1) cin>>a[i];
    rep(i, 1, n + 1) cin>>b[i];
    cin >> m;
    init();
    while (m -- )
    {
        int x, y;
        cin>>x>>y;
        if (y >= q[x].fi && y <= q[x].se)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

因为接下来后面都不是蓝桥杯B组的考点，所以就不做了哈哈哈哈，1个小时下班

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖