头像

xjtu_zfw




离线:5小时前


最近来访(552)
用户头像
ShawnWen
用户头像
zfw
用户头像
辣鸡号航母
用户头像
BeiHai
用户头像
Bochi
用户头像
ヾ凉城づ
用户头像
怎样共勉_7
用户头像
Tranquility
用户头像
ypfyyj
用户头像
ncepu_GJJ
用户头像
damn_it
用户头像
Feelme
用户头像
今天刷题了嘛
用户头像
Q.青青
用户头像
有马公生
用户头像
海问香
用户头像
從薪開始
用户头像
fluo
用户头像
卫一诺的小弟丶
用户头像
2850g

活动打卡代码 AcWing 98. 分形之城

xjtu_zfw
5小时前

在这里插入图片描述在这里插入图片描述

#include <iostream>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

PLL get(LL n, LL a)
{
    if (n == 0) return {0, 0};
    LL block = 1ll << 2 * n - 2, len = 1ll << n - 1;
    auto p = get(n - 1, a % block);
    LL x = p.x, y = p.y;
    int z = a / block;

    if (z == 0) return {y, x};
    else if (z == 1) return {x, y + len};
    else if (z == 2) return {x + len, y + len};
    return {2 * len - 1 - y, len - 1 - x};
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        LL n, a, b;
        scanf("%lld%lld%lld", &n, &a, &b);
        auto pa = get(n, a - 1);
        auto pb = get(n, b - 1);
        double dx = pa.x - pb.x, dy = pa.y - pb.y;
        printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 10);
    }

    return 0;
}


活动打卡代码 AcWing 97. 约数之和

在这里插入图片描述
在这里插入图片描述

AC

#include <iostream>

using namespace std;

const int mod = 9901;

int qmi(int a, int k)   // a^k
{
    int res = 1;
    a %= mod;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int sum(int p, int k)   // p^0 + p^1 + ... + p^(k-1) + p^k
{
    if (k == 0) return 1;
    if (k % 2 == 0) return ((1 + qmi(p, k / 2)) * sum(p, k / 2 - 1) + qmi(p, k)) % mod;
    else return (qmi(p, k) + sum(p, k - 1)) % mod;
}

int main()
{
    int a, b;
    cin >> a >> b;

    if (a == 0) 
    {
        puts("0");
        return 0;
    }

    int res = 1;
    // 对a分解质因数
    for (int i = 2; i <= a / i; i ++)
    {
        int s = 0;
        while (a % i == 0)
        {
            a /= i;
            s ++;
        }
        res = res * sum(i, s * b) % mod;
    }

    if (a > 1) res = res * sum(a, b) % mod;
    cout << res << endl;

    return 0;
}

TLE做法

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 9901;

unordered_map<int, int> m;

int qmi(int a, int k, int p)    // a^k % p
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int a, b;
    cin >> a >> b;
    for (int i = 2; i <= a / i; i ++)
    {
        m[i] ++;
        a /= i;
    }
    if (a > 1) m[a] ++;

    int res = 1;
    for (auto prime : m)
    {
        int p = prime.first, a = prime.second * b;  // p是底数,a是指数
        int t = 1;
        while (a --) t = (t * p + 1) % mod;     // 秦久韶算法
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6;
char g[N][N], bg[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void turn(int x, int y) // 按一下(x, y)的开关
{
    g[x][y] ^= 1;
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] ^= 1;
    }
}

int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        for (int i = 0; i < 5; i ++) cin >> bg[i];

        int res = 10;
        for (int op = 0; op < 32; op ++)
        {
            int cnt = 0;
            memcpy(g, bg, sizeof g);
            // 操作第一行的开关
            for (int i = 0; i < 5; i ++)
                if (op >> i & 1)
                {
                    turn(0, i);
                    cnt ++;
                }

            // 递推出第1~4行的开关状态
            for (int i = 0; i < 4; i ++)
                for (int j = 0; j < 5; j ++)
                    if (g[i][j] == '0')
                    {
                        turn(i + 1, j);
                        cnt ++;
                    }

            // 检查最后一行灯是否全亮
            bool success = true;
            for (int i = 0; i < 5; i ++)
                if (g[4][i] == '0')
                    success = false;
            if (success && cnt < res) res = cnt;
        }
        if (res > 6) res = -1;
        cout << res << endl;
    }

    return 0;
}


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

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)    // 快速幂
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

LL qadd(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, c;
    cin >> a >> b >> c;
    // cout << qmi(a, b, c) << endl;
    cout << qadd(a, b, c) << endl;

    return 0;
}


活动打卡代码 AcWing 803. 区间合并

在这里插入图片描述

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg: segs)
    {
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}


活动打卡代码 AcWing 802. 区间和

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;       // 存储所有待离散化的值
vector<PII> add, query;

// 二分求出值x对应的离散化的位置
int find(int x)     // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    sort(alls.begin(), alls.end());     // 排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

    // 处理插入
    for (auto item : add) a[find(item.first)] += item.second;

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];

    // 处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 794. 高精度除法

xjtu_zfw
29天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i --)
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }

    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    int r = 0;
    vector<int> C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i --) cout << C[i];
    cout << endl << r << endl;

    return 0;
}


活动打卡代码 AcWing 793. 高精度乘法

xjtu_zfw
29天前
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> res;
    int t = 0;
    for (int i = 0; i < A.size(); i ++)
    {
        t += A[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        res.push_back(t % 10);
        t /= 10;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto res = mul(A, b);
    for (int i = res.size() - 1; i >= 0; i --) cout << res[i];

    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> res;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++)
    {
        if (i < A.size()) t += A[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }

    while (res.size() > 1 && res.back() == 0) res.pop_back();

    return res;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');

    auto res = mul(A, b);
    for (int i = res.size() - 1; i >= 0; i --) cout << res[i];

    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

xjtu_zfw
30天前
#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();

    for (int i = A.size() - 1; i >= 0; i --)
        if (A[i] != B[i]) 
            return A[i] > B[i];

    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> res;
    for (int i = 0, t = 0; i < A.size(); i ++)
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        res.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (res.size() > 1 && res.back() == 0) res.pop_back();

    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

    vector<int> res;
    if (cmp(A, B)) res = sub(A, B);
    else res = sub(B, A), cout << '-';

    for (int i = res.size() - 1; i >= 0; i --) cout << res[i];
    cout << endl;

    return 0;
}


活动打卡代码 AcWing 791. 高精度加法

xjtu_zfw
30天前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> res;

    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++)
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(1);

    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;

    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');

    vector<int> C = add(A, B);
    reverse(C.begin(), C.end());
    for (int x : C) cout << x;
    cout << endl;

    return 0;
}