头像

莫小莫




离线:1个月前


最近来访(9)
用户头像
Y_cpper
用户头像
1e0n
用户头像
垫底抽風
用户头像
wuliaodea
用户头像
Cold_heartless
用户头像
一只野生の彩色铅笔
用户头像
liberty..
用户头像
max2021

活动打卡代码 AcWing 90. 64位整数乘法

莫小莫
2个月前
#include <iostream>
#define int long long

using namespace std;

main () {
    int a, b, p, res = 0;
    cin >> a >> b >> p;

    while (b) {
        if (b & 1) {
            res = (res + a) % p;
        }
        b >>= 1;
        a = 2 * a % p;
    }

    cout << res << endl;
    return 0;
}



莫小莫
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool pr (int n) {
    if (n < 2) return 0;

    for (int i = 2; i <= n / i; i ++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}
int main () {
    int n;
    cin >> n;
    while (n --) {
        int a;
        cin >> a;
        if (pr (a)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}


活动打卡代码 AcWing 1118. 分成互质组

莫小莫
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
}

const int N = 10;
int n, p[N], gr[N][N];
int ans = N;
bool a[N];

bool check (int gr[], int gc, int i) {
    for (int j = 0; j < gc; j ++) {
        if (__gcd (p[gr[j]], p[i]) > 1) {
            return 0;
        }
    }
    return 1;
}
void dfs (int g, int gc, int tc, int st) {
    if (g >= ans) return ;
    if (tc == n) ans = g;

    bool flag = 1;
    for (int i = st; i < n; i ++) {
        if (! a[i] && check (gr[g], gc, i)) {
            a[i] = 1;
            gr[g][gc] = i;

            dfs (g, gc + 1, tc + 1, i + 1);

            a[i] = 0;
            flag = 0;
        }
    }

    if (flag) dfs (g + 1, 0, tc, 0);
}
int main () {
    Ios ();
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> p[i];

    dfs (1, 0, 0, 0);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1117. 单词接龙

莫小莫
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
}

const int N = 25;
string st[N];
int n, a[N][N], u[N], ans = 0;

void dfs (string str, int la) {
    ans = max ((int)str.size (), ans);
    u[la] ++;

    for (int i = 0; i < n; i ++)
        if (a[la][i] && u[i] < 2) {
            dfs (str + st[i].substr (a[la][i]), i);
        }


    u[la] --;
}

int main () {
    Ios ();
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> st[i];
    }
    char c; cin >> c;

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            string a1 = st[i], b = st[j];
            for (int k = 1; k < min (a1.size (), b.size ()); k ++) {
                if (a1.substr (a1.size () - k, k) == b.substr(0, k)) {
                    a[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i = 0; i < n; i ++)
        if (st[i][0] == c) {
            dfs (st[i], i);
        }

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1116. 马走日

莫小莫
2个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
}

const int N = 10;
int m, n, x, y, ans = 0;
int a[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs (int x, int y, int s) {
    if (s == n * m) {
        ans ++;
        return ;
    }

    a[x][y] = 1;

    for (int i = 0; i < 8; i ++) {
        int t1 = x + dx[i], t2 = y + dy[i];

        if (t1 < 0 || t1 >= n || t2 < 0 || t2 >= m) continue;
        if (a[t1][t2] == 1) continue;

        dfs (t1, t2, s + 1);
    }

    a[x][y] = 0;
}
int main () {
    Ios ();
    int tot;
    cin >> tot;
    while (tot --) {
        ans = 0;

        cin >> n >> m >> x >> y;
        dfs (x, y, 1);

        cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

莫小莫
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
}

const int N = 25;
int n, m, a[N][N];
char c[N][N];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int dfs (int x, int y) {
    int cnt = 1;
    a[x][y] = 1;

    for (int i = 0; i < 4; i ++) {
        int t1 = x + dx[i], t2 = y + dy[i];

        if (t1 < 0 || t1 >= n || t2 < 0 || t2 >= m) continue;
        if (c[t1][t2] == '#') continue;
        if (a[t1][t2] == 1) continue;

        cnt += dfs (t1, t2);
    }

    return cnt;
}
int main () {
    Ios ();
    while (cin >> m >> n, n || m) {
        memset (a, 0, sizeof a);

        for (int i = 0; i < n; i ++) {
            cin >> c[i];
        }

        int x, y;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (c[i][j] == '@') {
                    x = i, y = j;

                }
            }
        }

        cout << dfs (x, y) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1112. 迷宫

莫小莫
2个月前
#include <bits/stdc++.h>
using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie ();
    cout.tie ();
}

const int N = 110;
int n, h1, h2, l1, l2;
int a[N][N];
int dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
char c[N][N];

int dfs (int h1, int h2) {
    if (c[h1][h2] == '#')
        return 0;
    if (h1 == l1 && h2 == l2) 
        return 1;

    a[h1][h2] = 1;

    for (int i = 1; i <= 4; i ++) {
        int a1 = h1 + dx[i], a2 = h2 + dy[i];

        if (a1 < 0 || a1 >= n || a2 < 0 || a2 >= n ) 
            continue;
        if (a[a1][a2] == 1) 
            continue;
        if (c[a1][a2] == '#') 
            continue;

        if (dfs (a1, a2)) 
            return true;
    }
    return false;
}
int main () {
    Ios ();
    int tot;
    cin >> tot;

    while (tot --) {
        memset (a, 0, sizeof a);
        cin >> n;

        for (int i = 0; i < n; i ++) 
            cin >> c[i];
        cin >> h1 >> h2 >> l1 >> l2;

        int ans = dfs (h1, h2);
        if (ans) {
            cout << "YES\n";
        }
        else cout << "NO\n";
    }
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

莫小莫
2个月前
//拉链法 
#include <bits/stdc++.h>
using namespace std;
void Ios () {
    ios :: sync_with_stdio (false) ;
    cin.tie () ;
    cout.tie () ;
}

const int N = 100003;
int h[N], e[N], ne[N], idx;

void insert (int x) {
    int k = (x % N + N) % N;
    e[idx] = x, ne[idx] = h[k], h[k] = idx ++;
}

bool find (int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x)
            return true;
    }
    return false;
}
int main () {
    Ios ();
    int n;
    cin >> n;

    memset (h, -1, sizeof h);

    while (n --) {
        string op; 
        int x;
        cin >> op >> x;

        if (op == "I") insert (x);
        else {
            if (find (x)) cout << "Yes" << endl;
            else cout << "No" << endl; 
        }
    }
    return 0;
}

//开放寻址法
#include <bits/stdc++.h>
using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie ();
    cout.tie ();
} 

const int N = 200003, null = 0x3f3f3f3f;
int h[N]; 

int find (int x) {
    int k = (x % N + N) % N;

    while (h[k] != null && h[k] != x) {
        k ++;
        if (k == N) {
            k = 0;
        }
    }

    return k;
}   

int main () {
    Ios ();
    int n;
    cin >> n;

    memset (h, 0x3f, sizeof h);

    while (n --) {
        string op; 
        int x;
        cin >> op >> x;
        int k = find (x);

        if (op == "I") {
            h[k] = x;
        }
        else {
            if (h[k] != null) cout << "Yes" << endl;
            else cout << "No" << endl; 
        }
    }
    return 0;
}


活动打卡代码 AcWing 876. 快速幂求逆元

莫小莫
2个月前
#include <bits/stdc++.h>
#define int long long
using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie ();
    cout.tie ();
}

int ksm (int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) {
            res = (long long) res * a % p;
        }
        k >>= 1;
        a = (long long) a * a % p;
    }
    return res;
}
main () {
    Ios ();
    int n;
    cin >> n;
    while (n --) {
        int a, p;
        cin >> a >> p;

        int res = ksm (a, p - 2, p);
        if (a % p) cout << res << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}


活动打卡代码 AcWing 875. 快速幂

莫小莫
2个月前
#include <bits/stdc++.h>
#define int long long
using namespace std;
void Ios () {
    ios :: sync_with_stdio (false);
    cin.tie ();
    cout.tie ();
}

int n, a, k, p;

int ksm (int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) {
            res = (long long) res * a % p;
        }
        k >>= 1;
        a = (long long) a * a % p;
    }
    return res;
}
main () {
    Ios ();
    cin >> n;
    while (n --) {
        cin >> a >> k >> p;
        ksm (a, k, p);
        cout << ksm (a, k, p) << endl;
    }
    return 0;
}