头像

小鱼干吖




离线:2天前


最近来访(13)
用户头像
笨蛋1
用户头像
不拿牌牌不改名
用户头像
Aze
用户头像
小张同学
用户头像
山山而川_93
用户头像
谢楼
用户头像
离离草上原
用户头像
候默
用户头像
史一帆

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

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)

using namespace std;

const int N = 200010, MOD = 200003, _NULL = 0x3f3f3f3f;

int n;
int h[N];

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

    while (h[k] != _NULL && h[k] != x) k = (k + 1) % MOD; 

    return k;
}

void solve () {
    memset(h, 0x3f, sizeof h);

    cin >> n;
    while (n -- ) {
        char op[2];
        int x; scanf("%s%d", op, &x);

        int k = find(x);
        if (*op == 'I') h[k] = x;
        else {
            if (h[k] != _NULL) puts("Yes");
            else puts("No");
        }
    }
}

int main() {
    solve ();
    return 0;
}



活动打卡代码 AcWing 1243. 糖果

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)

using namespace std;

const int N = 110, M = 1 << 20;

int n, m, k;
vector<int> col[N]; 
int log_2[M];

int h(int state) { // 至少需要再选几行 
    int res = 0;
    for (int i = (1 << m) - 1 - state; i; i -= i & -i) {
        int c = log_2[i & -i];
        res ++ ;
        for (auto row : col[c]) i &= ~row;
    }

    return res;
}

bool dfs(int depth, int state) {
    if (!depth || h(state) > depth) return state == (1 << m) - 1;

    // 找到选择性最少的一列 
    int t = -1;
    for (int i = (1 << m) - 1 - state; i; i -= i & -i) {
        int c = log_2[i & -i];
        if (t == -1 || col[c].size() < col[t].size())
            t = c;
    }

    // 枚举选哪行 
    for (auto row : col[t])
        if (dfs(depth - 1, state | row))
            return true;

    return false;
}

void solve () {
    cin >> n >> m >> k;

    _for (i, 0, m - 1) log_2[1 << i] = i;

    _for (i, 1, n) {
        int state = 0;
        _for (j, 1, k) {
            int c; cin >> c;
            state |= 1 << c - 1;
        }

        _for (j, 0, m - 1)
            if (state >> j & 1)
                col[j].emplace_back(state);
    }

    int depth = 0;
    while (depth <= m && !dfs(depth, 0)) depth ++ ;

    if (depth > m) depth = -1;

    cout << depth << endl;
}

int main() {
    solve ();
    return 0;
}




活动打卡代码 AcWing 1225. 正则问题

小鱼干吖
5个月前

#include <iostream>

using namespace std;

int i;
string s;

int dfs() {
    int ans = 0;
    while (i < s.size()) {
        if (s[i] == '(') {
            i ++ ;
            ans += dfs();
            i ++ ;
        } else if (s[i] == 'x') {
            i ++ ;
            ans ++ ;
        } else if (s[i] == '|') {
            i ++ ;
            ans = max(ans, dfs());
        } else break;
    }

    return ans;
}

int main() {
    cin >> s;
    cout << dfs() << endl;
    return 0;
}



活动打卡代码 AcWing 1301. C 循环

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)
#define LL long long
#define DB double

using namespace std;

const int MOD = 1e9 + 7;

LL A, B, C, k;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void solve () {
// A + aC = B + b(2^k-1)   Ca - (2^k-1)b = B - A
    while (scanf("%lld%lld%lld%lld", &A, &B, &C, &k), A || B || C || k) {
        LL t = (1LL << k);
        LL _x, _y;
        LL d = exgcd(C, t, _x, _y);

    //  cout << C << ' ' << t << ' ' << d << ' ' << _x << ' ' << _y << endl;

    //  if (B < A) B += t;

        if ((B - A) % d) puts("FOREVER");
        else {
            _x *= (B - A) / d;
            t /= d;
            printf("%lld\n", (_x % t + t) % t);
        }
    }
}

int main() {
    solve ();
    return 0;
}



活动打卡代码 AcWing 1223. 最大比例

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)
#define LL long long
#define DB double

using namespace std;

const int N = 110, MOD = 1e9 + 7;

int n;
LL x[N];
LL p[N], q[N], idx; 

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

LL gcd_sub(LL a, LL b) {
    if (a < b) swap(a, b);

    return b == 1 ? a : gcd_sub(b, a / b);
}

void solve () {
    cin >> n;
    _for (i, 1, n) cin >> x[i];

    sort(x + 1, x + n + 1);

    _for (i, 2, n) {
        LL d = gcd(x[i], x[1]);
        p[idx] = x[i] / d;
        q[idx ++ ] = x[1] / d;
    }

    LL up = p[0], down = q[0];
    _for (i, 1, idx - 1) {
        up = gcd_sub(up, p[i]);
        down = gcd_sub(down, q[i]);
    }

    cout << up << '/' << down << endl;
}

int main() {
    solve ();
    return 0;
}



活动打卡代码 AcWing 1299. 五指山

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)
#define LL long long
#define DB double

using namespace std;

const int N = 1e9, MOD = 1e9 + 7;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void solve () {
    LL n, d, x, y; scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
    // x + ad = y + bn  -bn + ad = y - x
    LL _x, _y, gcd = exgcd(n, d, _x, _y);

    if ((y - x) % gcd) puts("Impossible");
    else {
        _y *= (y - x) / gcd;
        n /= gcd;
        printf("%lld\n", (_y % n + n) % n);
    }
}

int main() {
    int _; cin >> _;
    while (_ -- ) solve ();
    return 0;
}



活动打卡代码 AcWing 3416. 时间显示

小鱼干吖
5个月前

#include <iostream>

using namespace std;

typedef long long LL;

int main() {
    LL n; cin >> n;
    n /= 1000;  // 一共多少秒
    n %= 24 * 3600; // 一天内多少秒
    int h = n / 3600, m = n % 3600 / 60, s = n % 60;

    printf("%02d:%02d:%02d", h, m, s);
}



活动打卡代码 AcWing 2068. 整数拼接

小鱼干吖
5个月前

#include <bits/stdc++.h>

#define _for(i, l, r) for (int i = l; i <= r; ++ i)
#define __for(i, r, l) for (int i = r; i >= l; -- i)
#define LL long long
#define DB double

using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10, MOD = 1e9 + 7;

int n, k;
int a[N];
int ha[11][N];
//map<PII, int> ha;

void solve () {
    cin >> n >> k;
    _for (i, 1, n) {
        scanf("%d", &a[i]);
        LL t = a[i] % k;
        _for (j, 0, 10) {
            ha[j][t] ++ ;
            //ha[{j, t}] ++ ;
            t = t * 10 % k;
        }
    }

    LL ans = 0;
    _for (i, 1, n) {
        LL t = a[i] % k;
        int len = to_string(a[i]).size();
        ans += ha[len][(k - t) % k];
        //ans += ha[{len, (k - t) % k}];

        LL x = t;
        while (len -- ) x = x * 10 % k;
        if (x == (k - t) % k) ans -- ;
    }

    cout << ans << endl;
}

int main() {
    solve ();
    return 0;
}



活动打卡代码 AcWing 2067. 走方格

小鱼干吖
5个月前

#include <iostream>

using namespace std;

const int N = 33;

int n, m;
int f[N][N];

bool check_valid(int x, int y) {
    return (x & 1 || y & 1);
}

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

    f[1][1] = 1;

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            if (!check_valid(i, j)) continue;

            if (check_valid(i - 1, j)) f[i][j] += f[i - 1][j];
            if (check_valid(i, j - 1)) f[i][j] += f[i][j - 1];
        }

    int ans = 0;
    cout << f[n][m] << endl;
    return 0;
}


#include <iostream>

using namespace std;

const int N = 33;

int n, m;
int f[N][N];

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

    f[1][1] = 1;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j) {
            if (i == 1 && j == 1) continue;
            if (i & 1 || j & 1) f[i][j] = f[i - 1][j] + f[i][j - 1];
        }

    cout << f[n][m] << endl;
    return 0;
}



活动打卡代码 AcWing 2066. 解码

小鱼干吖
5个月前

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i + 1] > '1' && s[i + 1] <= '9')
            for (int j = 1; j <= s[i + 1] - '0'; ++ j)
                cout << s[i];
        else if (s[i] > '9') cout << s[i];
    }

    return 0;
}