头像

imnoob




离线:14小时前


最近来访(18)
用户头像
yxc
用户头像
KkkkkkkkkKK
用户头像
能鸽善武
用户头像
Sonicyouth
用户头像
33号花卷
用户头像
Gerchart
用户头像
一撇亿惊鸿
用户头像
Tinkerbell
用户头像
RyanMoriarty
用户头像
小-胡-胡
用户头像
不知道_不知道
用户头像
郑若辰
用户头像
Sun@Wind
用户头像
𝐑𝐨𝐬𝐦𝐨𝐧𝐭𝐢𝐬_g

活动打卡代码 AcWing 1934. 贝茜放慢脚步

imnoob
14小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

priority_queue<int, vector<int>, greater<int>> d;
priority_queue<int, vector<int>, greater<int>> t;

int main()
{
    int N;
    cin >> N;
    while(N --){
        char a;int b;
        cin >> a >> b;
        if(a == 'T')
            t.push(b);
        else d.push(b);
    }
    d.push(1000);
    double ct = 0.0, cd = 0.0;
    int rate = 1;

    while(!d.empty() || !t.empty()){
        bool istime = false;
        if(d.empty())
            istime = true;
        else if(!d.empty() && !t.empty())
            if(t.top() < ct + (d.top() - cd) * rate)
                istime = true;
        if(istime){
            cd += (t.top() - ct) / (double)(rate);
            ct = t.top();
            t.pop();
        }else{
            ct += (d.top() - cd) * rate;
            cd = d.top();
            d.pop();
        }
        rate ++;
    }
    cout << (int)round(ct);
}



imnoob
1天前

学了算法提高课-矩阵快速幂后的奇思妙想

我们知道两个二进制数据异或即为两个数相加取余,我们可以将矩阵表示出来

当前运算用矩阵表示即
矩阵表示

res 矩阵即为单位矩阵,让运算矩阵进行快速幂
单位矩阵

结果矩阵需要输入便不再提供图片

算法复杂度为$O(logB)$
与找环结果相比
结果对比

下面那个19ms的为找环算法
可见,矩阵快速幂几乎无法被卡

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

using namespace std;

int n;
long long b;

void mutli(int ans[][16], int a[][16], int b[][16]){
    int temp[16][16] = {0};
    for(int i = 0;i < n;i ++)
        for(int j = 0;j < n;j ++)
            for(int k = 0;k < n;k ++)
                temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % 2;
    memcpy(ans, temp, sizeof temp);
}

int main()
{
    cin >> n >> b;
    int f[16][16] = {0}, r[16][16] = {0}, res[16][16] = {0};

    for(int i = 0;i < n;i ++)
        cin >> f[i][0];
    for (int i = 1; i < n; ++i)
        r[i][i - 1] = r[i][i] = 1;
    r[0][n - 1] = r[0][0] = 1;
    for(int i = 0;i < n;i ++)
        res[i][i] = 1;
        //init matrix

    while(b){
        if(b & 1) mutli(res,res,r);
        mutli(r,r,r);
        b >>= 1;
    }
    //fast pow
    mutli(f, res, f);
    for(int i = 0;i < n;i ++)
        cout << f[i][0] << '\n';
}



imnoob
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3;
int n, m;
typedef long long LL;

void multi(int ans[][N],int a[][N], int b[][N]){
    int temp[N][N] = {0};
    for(int i = 0;i < N;i ++)
        for(int j = 0;j < N;j ++)
            for(int k = 0;k < N;k ++)
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(ans, temp, sizeof temp);
}

int main(){
    cin >> n >> m;
    n --;
    int f[N][N] = {
        {1, 1, 1},
        {0, 0, 0},
        {0, 0, 0},
    }, p[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1},
    };
    while(n){
        if(n & 1) multi(f,f,p);
        multi(p,p,p);
        n >>= 1;
    }
    cout << f[0][2];
}


活动打卡代码 AcWing 1290. 越狱

imnoob
1天前

容斥原理:
即将两个种类的情况统计出来,此处不越狱的情况较为简单 -》
第一个犯人有$M$种选择,他右边的犯人有$M - 1$种选择,那他右边隔了一个的犯人也只有$M - 1$种选择,则将其与总情况相减,即为选择数
则有式子$ans = M^n - M*(M - 1)^{N - 1}$

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

using namespace std;
typedef long long LL;

const int MOD = 100003;
LL qmi(LL a, LL k, int p = MOD)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main(){
    LL n, m;
    cin >> m >> n;
    cout <<((qmi(m, n) - (LL)m * qmi(m - 1,n - 1) ) % MOD + MOD) % MOD;
}


活动打卡代码 AcWing 1282. 搜索关键词

imnoob
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10010, S = 55, M = 1e6 + 10;
int tr[N * S][26], cnt[N * S];
char str[M];
int q[N * S], ne[N * S];
int idx;

void insert()  // 将str插入tr中
{
    int p = 0;
    for(int i = 0;str[i];++i){
        int u = str[i] - 'a';
        if(!tr[p][u]) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    cnt[p]++;
}

void build()  // 创建AC自动机
{
    int hh = 0, tt = -1;
    for(int i = 0;i < 26;i ++){
        if(tr[0][i]) q[++ tt] = tr[0][i];
    }

    while(hh <= tt){
        int t = q[hh ++];
        for(int i = 0;i < 26;i ++){
            if(!tr[t][i]){
                tr[t][i] = tr[ne[t]][i];
            }else{
                 ne[tr[t][i]] = tr[ne[t]][i];
                q[++tt] = tr[t][i];
            }
        }
    }
}

void sol(){
    memset(tr, 0, sizeof tr);
    memset(cnt, 0, sizeof cnt);
    memset(ne, 0, sizeof ne);
    idx = 0;
    int n;cin >> n;

    for(int i = 0;i < n;i ++){
        cin >> str;
        insert();
    }
    build();

    cin >> str;
    int res = 0;

    for(int i = 0,j = 0;str[i];i ++){
        int t = str[i] - 'a';
        j = tr[j][t];
        int p = j;
        while(p){
            res += cnt[p];
            cnt[p] = 0;
            p = ne[p];
        }
    }
    cout << res << '\n';
}

int main(){
    int t;
    cin >> t;
    while(t --)
        sol();
}


活动打卡代码 AcWing 1945. 奶牛棒球

imnoob
2天前

朴素写法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
int lis[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++){
        cin >> lis[i];
    }
    sort(lis, lis + n);

    int res = 0;
    for(int i = 0;i < n - 2;i ++)
        for(int j = i + 1;j < n - 1;j ++){
            for(int k = j + 1;k < n;k ++){
                int x = lis[j] - lis[i],y = lis[k] - lis[j];
                if(x <= y && x * 2 >= y)
                    res ++;
            }
        }
    cout << res;
}

map离散化优化写法

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

using namespace std;
const int N = 5010;
int lis[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i ++){
        cin >> lis[i];
    }
    sort(lis, lis + n);

    map<int, int> mp;
    for(int i = 0;i < n;i ++){
        mp[lis[i]] = i;
    }

    int res = 0;

    for(int i = 0;i < n - 2;i ++){
        for(int j = i + 1;j < n - 1;j ++){
            int len = lis[j] - lis[i];
            auto l = mp.lower_bound(lis[j] + len);
            if(l != mp.end()){;
                auto r = mp.lower_bound(lis[j] + 2 * len + 1);
                r --;
                if(r->first < lis[j] + len) continue;
                res += r->second - l->second + 1;
            }
        }
    }
    cout << res;
}



imnoob
2天前

d[n]代表了我距离最开始的一个根节点的距离。在维护并查集时,同时也需要维护并查集的距离,那么如何代表该物种吃与不被吃呢?
用该节点到当前节点的距离表示,由于有且仅有三个物种,可以利用对3取模判断,当结果为1时表示有吃和被吃关系,结果为0时表示为同类,同时由于我们利用并查集维护了距离,所以查询速度为$O(1)$,算法时间复杂度为$O(N)$

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

using namespace std;
const int N = 50100;
int p[N], d[N];

int find(int n){
    if(p[n] != n){
        int root = find(p[n]);
        d[n] += d[p[n]];
        p[n] = root;
    }
    return p[n];
}

int main()
{
    int _, n;
    cin >> _ >> n;
    for(int i = 0;i <= _; i ++)
        p[i] = i;
    int ans = 0;

    while(n --){
        int a, b, c;
        cin >> a >> b >> c;
        if(b > _ || c > _){ ans ++;continue;}
        else if(a == 2 && b == c){ans ++;continue;}

        int xx = find(b), yy = find(c);
        int dis;
        if(a == 2) dis = 1;else dis = 0;

        if(xx == yy){
            if( ( ( (d[b] - d[c]) % 3) + 3) % 3 != dis)
                ans ++;
        }else{
            p[xx] = yy;
            d[xx] += d[c] - (d[b] - dis);
        }
    }
    cout << ans;
}


活动打卡代码 AcWing 238. 银河英雄传说

imnoob
2天前

带权并查集

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

using namespace std;
const int N = 30010;
int p[N], f[N], l[N];

int find(int n){
    if(p[n] != n){
        int root = find(p[n]);
        f[n] += f[p[n]];
        p[n] = root;
    }
    return p[n];
}

int main()
{
    for(int i = 0;i < N;i ++)
        p[i] = i,l[i] = 1;
    int t, a, b;
    char tp;
    cin >> t;
    while(t --){
        cin >> tp >> a >> b;
        if(tp == 'M'){
            int xx = find(a), yy = find(b);
            f[xx] = l[yy];
            l[yy] += l[xx];
            p[xx] = yy;
        }else{
            if(find(a) != find(b)) cout << "-1\n";
            else cout << max(0, abs(f[a] - f[b]) - 1) << '\n';
        }
    }
}


活动打卡代码 AcWing 107. 超快速排序

imnoob
3天前

归并排序求其逆序对

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

using namespace std;
const int N = 500010;

long long res;
int lis[N];
int t[N];

void marge(int l,int r){
    if(l >= r) return;
    int mid = l + r >> 1;
    marge(l, mid), marge(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(lis[i] > lis[j])
            t[k ++] = lis[j ++], res += mid - i + 1;
        else
            t[k ++] = lis[i ++];
    }
    while (i <= mid) t[k ++ ] = lis[i ++];
    while (j <= r) t[k ++ ] = lis[j ++];
    for(int i = l, j = 0;i <= r;i ++,j ++){
        lis[i] = t[j];
    }
}

int main(){
    int n;
    while(cin >> n && n){
        for(int i = 0;i < n;i ++){
            cin >> lis[i];
        }
        marge(0, n - 1);
        cout << res << '\n';
        res = 0;
    }
}


活动打卡代码 AcWing 100. 增减序列

imnoob
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
int lis[N];
int lis1[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n && cin >> lis1[i];i ++){
        lis[i] = lis1[i] - lis1[i - 1];
    }
    long long q = 0,p = 0;
    for(int i = 2;i <= n;i ++){
        if(lis[i] > 0) p += lis[i];
        else q -= lis[i];
    }
    cout << max(q, p) << '\n';
    cout << abs(p - q) + 1;
}