AtCoder Beginner Contest 250 部分题解

本篇题解只是记录我的做题过程代码，不提供最优解
（另外这里所有的时间复杂度都只分析单个样例，不算 t t t的时间复杂度）

点击此处查看对应的题目.
本题设计算法：模拟
直接枚举所有点，判断是否与指定点的曼哈顿距离为 1。

时间复杂度 O ( r ∗ c ) O(r * c) O(r∗c)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int main()
{
    int r,c,x,y,res = 0;
    cin >> r >> c >> x >> y;
    for (int i = 1;i <= r;i ++ ) {
        for (int j = 1;j <= c;j ++ ) {
            if (abs(i - x) + abs(j - y) == 1) {
                res ++;
            }
        }
    }
    cout << res << 'n';
    return 0;
}

点击此处查看对应的题目.
本题设计算法：模拟

通过观察可得我们可以把一个大方块划分为多个中方块，分别按中方块的次序交替输出即可，次序为偶数则里面的所有小方块输出点，次序为奇数则里面的所有小方块输出点 # 即可。

时间复杂度 O ( r ∗ c ∗ n 2 ) O(r * c * n^2) O(r∗c∗n2)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1010;
int n,r,c;
char g[N][N];

void out(int id,int x,int y)
{
    for (int i = 1;i <= r;i ++) {
        for (int j = 1;j <= c;j ++ ) {
            if (!id) g[i + x * r][j + y * c] = '.';
            else g[i + x * r][j + y * c] = '#';
        }
    }
}
int main()
{
    cin >> n >> r >> c;
    int t = 0;
    for (int i = 0;i < n;i ++ ) {
        int x = t;
        for (int j = 0;j < n;j ++ ) {
            out(x,i,j);
            x ^= 1;
        }
        t ^= 1;
    }
    for (int i = 1;i <= r * n;i ++,cout << 'n') {
        for (int j = 1;j <= c * n;j ++ ) {
            cout << g[i][j];
        }
    }
    return 0;
}

点击此处查看对应的题目.
本题设计算法：模拟 + map统计

我们可以开一个 map，记录一下所有说的下标，然后每次询问交换值和 map 所统计的下标即可。

时间复杂度 O ( n ) O(n) O(n)

#include 
#include 
#include 
#include 
using namespace std;
const int N = 2e5 + 10;
int a[N];

int main()
{
    int n,q;
    cin >> n >> q;
    
    unordered_map mp;
    for (int i = 1;i <= n;i ++ ) { 
        a[i] = i;
        mp[a[i]] = i;
    }
    while (q -- ) {
        int x;
        cin >> x;
        if (mp.count(x)) {
            int id = mp[x];
            if (id == n) {
                mp[a[id - 1]] = id;
                mp[a[id]] = id - 1;
                swap(a[id - 1],a[id]);
            }else {
                mp[a[id + 1]] = id;
                mp[a[id]] = id + 1;
                swap(a[id],a[id + 1]);
            }
        }
    }

    for (int i = 1;i <= n;i ++ ) cout << a[i] << ' ';
    puts("");
    return 0;
}

点击此处查看对应的题目.
本题设计算法：质数筛 + 前缀和

由于题目要求 q * q * q * p <= 1e18 ，p < q ，且 q 都为质数。

所以这题所有的 q 和 p 最多 1e6， 所以我们可以通过质数筛法 用大约 O(n) 的时间复杂度筛出所有小于或等于1e6 的所有的质数。

由于p < q，所以每一个筛出的质数 q 都有 q - 1 或者 n / i / i / i 以内的质数的数量的 p (这里要取一下最小值)。

note ：取值的过程需要用到前缀和，这样就可以快速取出 x 以内的所有质数数量

时间复杂度 O ( N ) O(N) O(N)

#include 
#include 
#include 
#include 
#include 

点击此处查看对应的题目.
本题设计算法：序列哈希化 + 前缀和

用一个的唯一标识的随机数表示一个值，然后用一个hash数组，存入所有hash值，这样就可以 快速判定 两数组任意点的前缀是否相同(哈希前缀和相同即为前缀相同)。

hash化的做法就是开一个随机数种子

srand((unsigned long long)time(NULL));

时间复杂度 O ( n ) O(n) O(n)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N],b[N],ha[N],hb[N];
unordered_map hashmp;
set sta,stb;

int main()
{
    int n;
    cin >> n;
    srand((unsigned long long)time(NULL));
    for (int i = 1;i <= n;i ++ ) scanf("%lld",&a[i]);
    for (int i = 1;i <= n;i ++ ) scanf("%lld",&b[i]);
    
    for (int i = 1;i <= n;i ++ ) {
        if (!hashmp.count(a[i])) hashmp[a[i]] = rand();
        ha[i] = ha[i - 1];
        if (!sta.count(a[i])) ha[i] += hashmp[a[i]];
        sta.insert(a[i]);

        if (!hashmp.count(b[i])) hashmp[b[i]] = rand();
        hb[i] = hb[i - 1];
        if (!stb.count(b[i])) hb[i] += hashmp[b[i]];
        stb.insert(b[i]);
    } 

    int q;
    cin >> q;
    while (q -- ) {
        int x,y;
        scanf("%d%d",&x,&y);
        if (ha[x] == hb[y]) puts("Yes");
        else puts("No");
    }
    return 0;
}