头像

Aikin

战略忽悠局局长


访客:14023

在线 


活动打卡代码 AcWing 2171. EK求最大流

Aikin
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(st, false, sizeof st);
    q[0] = S, st[S] = true, d[S] = INF;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (!st[ver] && f[i])
            {
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int EK()
{
    int r = 0;
    while (bfs())
    {
        r += d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
            f[pre[i]] -= d[T], f[pre[i] ^ 1] += d[T];
    }
    return r;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", EK());

    return 0;
}


活动打卡代码 AcWing 253. 普通平衡树

Aikin
1个月前
// fhq 平衡树
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cctype>
namespace FastIO
{
char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n';
int p, p3 = -1;
void read() {}
void print() {}
inline int getc()
{
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline void flush()
{
    fwrite(buf2, 1, p3 + 1, stdout), p3 = -1;
}
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth)
{
    int f = 0;
    x = 0;
    char ch = getc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = 1;
        ch = getc();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getc();
    }
    x = f ? -x : x;
    read(oth...);
}
template <typename T, typename... T2>
inline void print(T x, T2... oth)
{
    if (p3 > 1 << 20)
        flush();
    if (x < 0)
        buf2[++p3] = 45, x = -x;
    do
    {
        a[++p] = x % 10 + 48;
    } while (x /= 10);
    do
    {
        buf2[++p3] = a[p];
    } while (--p);
    buf2[++p3] = hh;
    print(oth...);
}
} // namespace FastIO
#define read FastIO::read
#define print FastIO::print
//======================================
const int maxn = 1e5+5;
struct Node
{
    int l,r;
    int val,key;
    int size;
}fhq[maxn];
int cnt,root;
#include <random>
std::mt19937 rnd(233);
inline int newnode(int val)
{
    fhq[++cnt].val=val;
    fhq[cnt].key=rnd();
    fhq[cnt].size=1;
    return cnt;
}
inline void update(int now)
{
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y)
{
    if(!now) x=y=0;
    else 
    {
        if(fhq[now].val<=val)
        {
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else 
        {
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(fhq[x].key>fhq[y].key)           // > >= < <=
    {
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
    else 
    {
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
int x,y,z;
inline void ins(int val)
{
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}
inline void del(int val)
{
    split(root,val,x,z);
    split(x,val-1,x,y);
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}
inline void getrank(int val)
{
    split(root,val-1,x,y);
    print(fhq[x].size+1);
    root=merge(x,y);
}
inline void getnum(int rank)
{
    int now=root;
    while(now)
    {
        if(fhq[fhq[now].l].size+1==rank)
            break;
        else if(fhq[fhq[now].l].size>=rank)
            now=fhq[now].l;
        else 
        {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    print(fhq[now].val);
}
inline void pre(int val)
{
    split(root,val-1,x,y);
    int now = x;
    while(fhq[now].r)
        now = fhq[now].r;
    print(fhq[now].val);
    root=merge(x,y);
}
inline void nxt(int val)
{
    split(root,val,x,y);
    int now = y;
    while(fhq[now].l)
        now = fhq[now].l;
    print(fhq[now].val);
    root=merge(x,y);
}
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    clock_t c1 = clock();
    //======================================
    int t;
    read(t);
    while(t--)
    {
        int opt,x;
        read(opt,x);
        switch(opt)
        {
            case 1:
                ins(x);
                break;
            case 2:
                del(x);
                break;
            case 3:
                getrank(x);
                break;
            case 4:
                getnum(x);
                break;
            case 5:
                pre(x);
                break;
            case 6:
                nxt(x);
                break;
        }
    }
    //======================================
    FastIO::flush();
    std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}


活动打卡代码 AcWing 1184. 欧拉回路

Aikin
1个月前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
const int N = 1e5 + 100, M = N * 4 + 100000;
int n, m;
int din[N], dout[N], type;
int h[N], ne[M], e[M], idx;
bool st[M];
int ans[M], cnt;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    for(int& i = h[u]; ~i;)
    {
        if(st[i]){
            i = ne[i];
            continue;
        }
        int j = e[i];
        // 删边
        st[i] = true;
        // 无向图的另一条边.
        if(type == 1) st[i ^ 1] = true;
        int t;
        if(type == 1){
            t = i / 2 + 1;
            if(i & 1) t = -t;
        }
        else t = i + 1;
        // 统计后删边.
        i = ne[i];
        dfs(j);
        ans[++ cnt] = t;
    }
}

int main()
{
    // freopen("pat.input", "r", stdin);
    // freopen("pat.output", "w", stdout);

    cin >> type >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        // add的先后顺序, 影响t的值.
        add(a, b);
        if(type == 1) add(b, a);
        dout[a] ++, din[b] ++;
    }
    // 欧拉回路, 入度等于出度, 无向图只有0个.
    if(type == 1){
        for(int i = 1; i <= n; i ++)
            if((din[i] + dout[i]) & 1)
             {
                 puts("NO");
                 return 0;
             }   
    }
    else if(type == 2){
        for(int i = 1; i <= n; i ++)
            if(din[i] != dout[i]){
                 puts("NO");
                 return 0;
             }
    }
    // 欧拉回路, 是联通图, 然后求方案;
    // 有独立点没有关系, 这里只要求边满足即可.
    for(int i = 1; i <= n; i ++)
        if(h[i] != -1){
            dfs(i);
            break;
        }
    if(cnt < m){
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i = cnt; i; i --)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 1305. GT考试

Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m, mod;
char str[N];
int ne[N];
int a[N][N];

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < m; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int k = 0; k < m; k ++ )
                t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;

    memcpy(c, t, sizeof t);
}

int qmi(int k)
{
    int f0[N][N] = {1};
    while (k)
    {
        if (k & 1) mul(f0, f0, a);  // f0 = f0 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

    int res = 0;
    for (int i = 0; i < m; i ++ ) res = (res + f0[0][i]) % mod;
    return res;
}

int main()
{
    cin >> n >> m >> mod;
    cin >> str + 1;

    // kmp
    for (int i = 2, j = 0; i <= m; i ++ )
    {
        while (j && str[j + 1] != str[i]) j = ne[j];
        if (str[j + 1] == str[i]) j ++ ;
        ne[i] = j;
    }

    // 初始化A[i][j]
    for (int j = 0; j < m; j ++ )
        for (int c = '0'; c <= '9'; c ++ )
        {
            int k = j;
            while (k && str[k + 1] != c) k = ne[k];
            if (str[k + 1] == c) k ++ ;
            if (k < m) a[j][k] ++ ;
        }


    // F[n] = F[0] * A^n
    cout << qmi(n) << endl;

    return 0;
}



Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 4;

int n, m;

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

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

    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = {1, 1, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
    };

    int k = n - 1;

    // 快速幂
    while (k)
    {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

    cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}



Aikin
2个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][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(c, temp, sizeof temp);
}

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

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}


活动打卡代码 AcWing 1315. 网格

Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool st[N];
int a[N], b[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p)
{
    int s = 0;
    while (n) s += n / p, n /= p;
    return s;
}

void mul(int r[], int &len, int x)
{
    int t = 0;
    for (int i = 0; i < len; i ++ )
    {
        t += r[i] * x;
        r[i] = t % 10;
        t /= 10;
    }
    while (t)
    {
        r[len ++ ] = t % 10;
        t /= 10;
    }
}

void sub(int a[], int al, int b[], int bl)
{
    for (int i = 0, t = 0; i < al; i ++ )
    {
        a[i] -= t + b[i];
        if (a[i] < 0) a[i] += 10, t = 1;
        else t = 0;
    }
}

int C(int x, int y, int r[N])
{
    int len = 1;
    r[0] = 1;

    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        int s = get(x, p) - get(y, p) - get(x - y, p);
        while (s -- ) mul(r, len, p);
    }

    return len;
}

int main()
{
    init(N - 1);

    int n, m;
    cin >> n >> m;
    int al = C(n + m, m, a);
    int bl = C(n + m, n + 1, b);

    sub(a, al, b, bl);

    int k = al - 1;
    while (!a[k] && k > 0) k -- ;
    while (k >= 0) printf("%d", a[k -- ]);

    return 0;
}


活动打卡代码 AcWing 1316. 有趣的数列

Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n, p;
int primes[N], cnt;
bool st[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if  (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

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

int get(int n, int p)
{
    int s = 0;
    while (n)
    {
        s += n / p;
        n /= p;
    }
    return s;
}

int C(int a, int b)
{
    int res = 1;
    for (int i = 0; i < cnt; i ++ )
    {
        int prime = primes[i];
        int s = get(a, prime) - get(b, prime) - get(a - b, prime);

        res = (LL)res * qmi(prime, s) % p;
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &p);
    init(n * 2);

    cout << (C(n * 2, n) - C(n * 2, n - 1) + p) % p << endl;

    return 0;
}


活动打卡代码 AcWing 1312. 序列统计

Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int p = 1000003;

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

int C(int a, int b)
{
    if (a < b) return 0;

    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (LL)up * i % p;
        down = (LL)down * j % p;
    }

    return (LL)up * qmi(down, p - 2) % p;
}

int Lucas(int a, int b)
{
    if (a < p && b < p) return C(a, b);
    return (LL)Lucas(a / p, b / p) * C(a % p, b % p) % p;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        int n, l, r;
        cin >> n >> l >> r;
        cout << (Lucas(r - l + n + 1, r - l + 1) + p - 1) % p << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1310. 数三角形

Aikin
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

LL C(int n)
{
    return (LL)n * (n - 1) * (n - 2) / 6;
}

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

    n ++, m ++ ;

    LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

    cout << res << endl;

    return 0;
}