头像

谁把可乐的名字拿走了

衡水学院




离线:4小时前


最近来访(337)
用户头像
kai_35
用户头像
跟月亮说晚安ღ
用户头像
流妍
用户头像
烟尘墨
用户头像
诺诺
用户头像
顽童
用户头像
AC别闹
用户头像
cornelia.
用户头像
转身匿于人海
用户头像
sealt
用户头像
白哈哈
用户头像
Lqi
用户头像
XZ916
用户头像
zeng9999jian
用户头像
kzyz
用户头像
uboat2022
用户头像
徐凤年_3
用户头像
稚宇
用户头像
恶魔波刚
用户头像
入囚_1

活动打卡代码 AcWing 112. 雷达设备

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

const int N = 1010;
const double eps = 1e-6, inf = 1e10;

typedef std::pair<double, double> PDD;

int n, d;
PDD seg[N];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    std::cin >> n >> d;
    bool ok = true;

    for(int i = 0;i < n;i ++)
    {
        double x, y;
        std::cin >> x >> y;

        if(y > d)
        {
            ok = false;
            break;
        }
        double r = sqrt(d * d - y * y);
        seg[i] = {x + r, x - r};
    }

    if(ok)
    {
        std::sort(seg, seg + n);
        int res = 0;
        double last = -inf;
        for(int i = 0;i < n;i ++)
        {
            if(seg[i].second > last + eps) 
            {
                res ++;
                last = seg[i].first;
            }
        }

        std::cout << res << '\n';
    }
    else puts("-1");

    return 0;
}


新鲜事 原文

再不用unordered_map
图片


活动打卡代码 AcWing 1084. 数字游戏 II

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

using namespace std;

const int N = 11, M = 110;

int P;
int f[N][10][M];

int mod(int x, int y)
{
    return (x % y + y) % y;
}

void init()
{
    memset(f, 0, sizeof f);

    for (int i = 0; i <= 9; i ++ ) f[1][i][i % P] ++ ;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k < P; k ++ )
                for (int x = 0; x <= 9; x ++ )
                    f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}

int dp(int n)
{
    if (!n) return 1;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = 0; j < x; j ++ )
            res += f[i + 1][j][mod(-last, P)];

        last += x;

        if (!i && last % P == 0) res ++ ;
    }

    return res;
}

int main()
{
    int l, r;
    while (cin >> l >> r >> P)
    {
        init();

        cout << dp(r) - dp(l - 1) << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1083. Windy数

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

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
    for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

    for (int i = 2; i < N; i ++ )
        for (int j = 0; j <= 9; j ++ )
            for (int k = 0; k <= 9; k ++ )
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if (!n) return 0;

    vector<int> nums;
    while (n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = -2;
    for (int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for (int j = i == nums.size() - 1; j < x; j ++ )
            if (abs(j - last) >= 2)
                res += f[i + 1][j];

        if (abs(x - last) >= 2) last = x;
        else break;

        if (!i) res ++ ;
    }

    // 特殊处理有前导零的数
    for (int i = 1; i < nums.size(); i ++ )
        for (int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main()
{
    init();

    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l - 1) << endl;

    return 0;
}



超宝赛高

算法1

树状数组$O(nlogn)$

就一点,树状数组每个tr[x]存储的是tr[x - lowbit(x) + 1] - tr[x]之间的最大值!

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 100010;

int n, m;
int h[N], trmin[N], trmax[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for(int i = x;i <= n;i += lowbit(i))
    {
        trmin[i] = std::min(trmin[i], c);
        trmax[i] = std::max(trmax[i], c);
    }
}

int get_max(int l, int r)
{
    if(r > l)
    {
        if(r - lowbit(r) >= l) return std::max(trmax[r], get_max(l, r - lowbit(r)));
        else return std::max(h[r], get_max(l, r - 1));
    }

    return h[l];
}

int get_min(int l, int r)
{
    if(r > l)
    {
        if(r - lowbit(r) >= l) return std::min(trmin[r], get_min(l, r - lowbit(r)));
        else return std::min(h[r], get_min(l, r - 1));
    }

    return h[l];
}

void solve()
{
    scanf("%d%d", &n, &m);
    memset(trmin, 0x3f, sizeof trmin);
    for(int i = 1;i <= n;i ++) 
    {
        scanf("%d", h + i);
        add(i, h[i]);
    }

    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", get_max(a, b) - get_min(a, b));
        printf("max = %d\n", get_max(a, b));
    }
}

int main()  
{
    int t = 1;

    while(t --) solve();

    return 0;
}

算法2

(st表 / RMQ算法) $O(O(n)$

RMQ yyds

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using LL = long long;

const int N = 100010, M = 17;

int n, m;
int f[N][M], g[N][M];
int h[N];

void init()
{
    for(int j = 0;j < M;j ++)
        for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            if(!j) f[i][j] = h[i];
            else f[i][j] = std::max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

    for(int j = 0;j < M;j ++)
        for(int i = 1;i + (1 << j) - 1 <= n;i ++)
            if(!j) g[i][j] = h[i];
            else g[i][j] = std::min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}

int query_max(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

int query_min(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return std::min(g[l][k], g[r - (1 << k) + 1][k]);
}

void solve()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++) scanf("%d", h + i);

    init();

    while(m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(l, r) - query_min(l, r));
    }
}

int main()
{
    int t = 1;

    while(t --) solve();

    return 0;
}




算法1

树状数组

时间复杂度 $O(nlogn)$

由ai + aj > bi + bj -> ai - bi > aj - bj, 相当于对于所有的i,存在多少j(i < j)满足ai - bi > aj - bj
满足树状数组求前缀和后对于每一个ai - bi有多少个aj - bj小于它。

蠢在两个地方:1.树状数组只存储了aj - bj的前缀和,所以不需要考虑ai - bi的影响
2.对于存储的树状数组,因为是排序去重后的结果,所以最坏的情况下,下标最大为2 * n,而不是n

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 400010;

int n, m;
int a[N], b[N], x[N], y[N], tr[N], res[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int c)
{
    for(int i = x;i <= n * 2;i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i;i -= lowbit(i)) res += tr[i];

    return res;
}

void solve()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++) scanf("%d", a + i);
    for(int i = 1;i <= n;i ++) scanf("%d", b + i);

    for(int i = 1;i <= n;i ++)
    {
        x[i] = a[i] - b[i];
        y[i] = b[i] - a[i];
        res[++ m] = x[i], res[++ m] = y[i];
    }

    std::sort(res + 1, res + m + 1);
    m = std::unique(res + 1, res + m + 1) - res - 1;
    for(int i = 1;i <= n;i ++)
    {
        x[i] = std::lower_bound(res + 1, res + m + 1, x[i]) - res;
        y[i] = std::lower_bound(res + 1, res + m + 1, y[i]) - res;
        add(y[i], 1);
    }

    LL ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        add(y[i], -1);
        ans += sum(x[i] - 1);
    }

    printf("%lld\n", ans);
}

int main()
{
    int t = 1;
    //scanf("%d", &t);

    while(t --) solve();

    return 0;
}


活动打卡代码 AcWing 1. A + B

let fs = require('fs');
let buf = '';

process.stdin.on('readable', function() {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
    buf.split('\n').forEach(function(line) {
        let tokens = line.split(' ').map(function(x) { return parseInt(x); });
        if (tokens.length != 2) return;
        console.log(tokens.reduce(function(a, b) { return a + b; }));
    });
});


分享 2023/1/23

深感人生之艰难,就像那不息之长河,虽有东去大海之志,却流程缓慢,征程多艰,然,江河水总有入海之时,而人生之志,却常常难以实现,令人抱恨终生。



活动打卡代码 工程课 Web-2.10. homework_10

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>

    <style>
        .container {
            width: 50%;
            height: 500px;
            background-color: lightblue;
            display: flex;
            margin: 10px;
        }

        .container>* {
            width: 120px;
            height: 120px;
        }

        .container>*:nth-child(odd) {
            background-color: lightsalmon;
        }

        .container>*:nth-child(even) {
            background-color: lightgreen;
        }

        .container:nth-child(1) {
            flex-wrap: wrap;
            justify-content: space-between;
            align-content: flex-start;
        }

        .container:nth-child(2) {
            flex-direction: row-reverse;
            flex-wrap: nowrap;
        }

        .container:nth-child(2)>*:nth-child(odd) {
            flex-grow: 3;
            flex-shrink: 3;
        }

        .container:nth-child(2)>*:nth-child(even) {
            flex-grow: 1;
            flex-shrink: 1;
        }
    </style>
</head>

<body>
    <div class="container">
        <div>1</div>
        <div>2</div>
        <div>3</div>
        <div>4</div>
        <div>5</div>
        <div>6</div>
    </div>

    <div class="container">
        <div>1</div>
        <div>2</div>
        <div>3</div>
        <div>4</div>
        <div>5</div>
        <div>6</div>
    </div>
</body>

</html>



活动打卡代码 工程课 Web-2.9. homework_9

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>

    <style>
        .container {
            height: 500px;
            width: 500px;
            background-color: lightblue;
        }

        .item {
            height: 100px;
            width: 100px;
            margin: 10px;
            background-color: lightcoral;
            float: left;
        }

        .next-line {
            width: 150px;
            height: 150px;
            background-color: rgba(0, 0, 255, 0.5);
            clear: both;
        }
    </style>
</head>

<body>
    <div class="container">
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="item"></div>
        <div class="next-line"></div>
    </div>
</body>

</html>