头像

DPH

西南民族大学




离线:10小时前


最近来访(123)
用户头像
空号AcWing
用户头像
AC_5
用户头像
等风来111
用户头像
iron
用户头像
AmihuaLau
用户头像
Tinkerbell
用户头像
パメラ
用户头像
青衣程碟衣
用户头像
Ars
用户头像
YikN
用户头像
Salem
用户头像
omemi
用户头像
鸢一折纸
用户头像
Magic_Zq
用户头像
magicat
用户头像
noobcode091
用户头像
Windy_0
用户头像
zx_explorer
用户头像
吕启航
用户头像
你听得到

分享 反素数

DPH
3天前

知道 n 所有质因数后,通过搜索求 n 所有因数

void dfs(int dept,LL ans = 1)
{
    if(dept == cnt)
    {
        fac[ct++] = ans;
        return;
    }
    for(int i=0;i<=num[dept];i++)
    {
        dfs(dept+1,ans);
        ans *= pri[dept];
    }
}

而且一个反素数的所有质因子必然是从 2 开始的连续若干个质数
因为反素数是保证约数个数为的这个数尽量小
所以说
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
就可以了

来个模板题
http://codeforces.com/problemset/problem/27/E

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

int n, ans;

// 为什么要拿前16个素数 因为它们各取一个相乘够1e18 并且是最小的
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

// dept 要用到多少个质因数
// ans  最终拼出的数字
// tmp  当前拼出的数字
// num  有多少个因数


// 一开始是均匀摊开的 大家都是一个 后来慢慢开始往前面浓缩
void dfs(int dept, int tmp, int num)
{
    if(num > n) return ;

    // cout << "要用到多少个质因数" << dept << ' ' << "当前拼出的数字" << tmp << ' ' << "有多少个因数" << num << endl;

    if(num == n && tmp < ans) ans = tmp;

    // long long 范围 2^64 - 1
    for(int i = 1; i <= 64; i ++ )
    {
        // 会炸掉 long long
        // if(tmp * p[dept] > ans) break;
        if(tmp > ans / p[dept]) break;

        dfs(dept + 1, tmp * p[dept], num * (i + 1));

        tmp *= p[dept];
    }
    return ;
}

void solve()
{
    cin >> n;
    ans = 0x3f3f3f3f3f3f3f3f;
    // 一开始 根节点数字是1 0个质因数被用 当前拼出的数字为1 只有一个因数 
    dfs(0, 1, 1);
    cout << ans << endl;
    return ;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T = 1;
    // int T; cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        solve();
    }
    return 0;
}

求n以内的最多因子数的数 n=1e16
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1562
本来是浙大的题 但浙大OJ好像搬到PTA上面去了

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

int n, ans = -1, vis = -1;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

// 用第几个素数 当前的值 有几个因数

// 为什么 24 和 30 都是 8 个因子 输出的是30
// 因为30 = 2 * 3 * 5 分布的很散 所以先出来
// 24 = 2 * 2 * 2 * 3 后来才聚出来的 然而因为 ans 并不会更大所以不更新
void dfs(int x, int y, int z)
{
    if(y > n) return ;

    if(z > ans) ans = z, vis = y;

    for(int i = 1; i <= 64; i ++ )
    {
        if(y > n / p[x]) break;

        dfs(x + 1, y * p[x], z * (i + 1));

        y *= p[x];
    }
}

void solve()
{
    cin >> n;
    // for(int i = 1; i <= 100; i ++ )
    // {
    //     n = i;
        dfs(0, 1, 1);
        cout << vis << endl;
        // cout << n << ' ';
        // cout << vis << ' ' << ans << endl;

    // }
    return ;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T = 1;
    // int T; cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        solve();
    }
    return 0;
}

为什么今天学反素数呢?因为要补题
https://ac.nowcoder.com/acm/contest/24809/G

#include <bits/stdc++.h>

#define int unsigned long long
#define endl '\n'

using namespace std;

int n, ans;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

// 用第几个素数 当前的值 有几个因数
void dfs(int x, int y, int z)
{
    if(y > n) return ;

    if(z > ans) ans = z;

    for(int i = 1; i <= 64; i ++ )
    {
        if(y > n / p[x]) break;

        dfs(x + 1, y * p[x], z * (i + 1));

        y *= p[x];
    }
}

void solve()
{
    ans = 0;
    cin >> n;
    dfs(0, 1, 1);
    cout << ans << endl;
    return ;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // int T = 1;
    int T; cin >> T;
    for(int i = 1; i <= T; i ++ )
    {
        solve();
    }
    return 0;
}



DPH
5天前
#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
double a[N][N], b[N][N];

void gauss()
{
    for(int r = 1, c = 1; r <= n; r ++ , c ++ )
    {
        int t = r;
        for(int i = r + 1; i <= n; i ++ )
        {
            if(fabs(b[t][c]) < fabs(b[i][c])) t = i;
        }

        for(int i = c; i <= n + 1; i ++ ) swap(b[t][i], b[r][i]);

        for(int i = n + 1; i >= c; i -- ) b[r][i] /= b[r][c];

        for(int i = r + 1; i <= n; i ++ )
        {
            for(int j = n + 1; j >= c; j -- )
            {
                b[i][j] -= (b[r][j] * b[i][c]);
            }
        }
    }

    for(int i = n; i >= 1; i -- ) // dui jiao xian
    {
        for(int j = i - 1; j >= 1; j -- ) // gai bian row
        {
            b[j][n + 1] -= (b[j][i] * b[i][n + 1]);
            b[j][i] = 0;
        }
    }

    return ;

}

int main()
{
    cin >> n;

    for(int i = 0; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ ) cin >> a[i][j];
    }

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            b[i][j] += 2 * (a[i][j] - a[0][j]);
            b[i][n + 1] += ( a[i][j] * a[i][j] - a[0][j] * a[0][j] );
        }
    }

    // for(int i = 1; i <= n; i ++ )
    // {
    //     for(int j = 1; j <= n; j ++ ) printf("%.3lf ", a[i][j]);
    //     cout << endl;
    // }
    // cout << "*****" << endl;
    // for(int i = 1; i <= n; i ++ )
    // {
    //     for(int j = 1; j <= n + 1; j ++ ) printf("%.3lf ", b[i][j]);
    //     cout << endl;
    // }
    // cout << "*****" << endl;

    gauss();

    // for(int i = 1; i <= n; i ++ )
    // {
    //     for(int j = 1; j <= n; j ++ ) printf("%.3lf ", a[i][j]);
    //     cout << endl;
    // }
    // cout << "#####" << endl;
    // for(int i = 1; i <= n; i ++ )
    // {
    //     for(int j = 1; j <= n + 1; j ++ ) printf("%.3lf ", b[i][j]);
    //     cout << endl;
    // }
    // cout << "#####" << endl;

    for(int i = 1; i <= n; i ++ ) printf("%.3lf ", b[i][n + 1]);

    return 0;
}



DPH
15天前
#include <bits/stdc++.h>

#define int long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 5e5 + 10;

int n, m, w[N];

struct Node
{
    int l, r, sum;
    int lmax, rmax, tmax;
};

Node tr[N << 2];

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max( max(l.tmax, r.tmax), l.rmax + r.lmax);
    return ;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    return ;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        tr[u].sum = w[l];
        tr[u].lmax = w[l];
        tr[u].rmax = w[l];
        tr[u].tmax = w[l];
    }
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
    return ;
}

void modify(int u, int x, int d)
{
    if(tr[u].l == x && tr[u].r == x)
    {
        tr[u].sum = d;
        tr[u].lmax = d;
        tr[u].rmax = d;
        tr[u].tmax = d;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, d);
        else modify(u << 1 | 1, x, d);
        pushup(u);
    }
    return ;
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid && r > mid)
        {
            auto ll = query(u << 1, l, r);
            auto rr = query(u << 1 | 1, l, r);

            Node ans;
            pushup(ans, ll, rr);
            return ans;
        }
        else if(r <= mid) return query(u << 1, l, r);
        else if(l > mid) return query(u << 1 | 1, l, r);

        // 这个也行
        // Node res;
        // Node left = {0, 0, 0, -INF, -INF, -INF};
        // Node right = {0, 0, 0, -INF, -INF, -INF};
        // if (l <= mid) left = query(u << 1, l, r);
        // if (r > mid) right = query(u << 1 | 1, l, r);
        // pushup(res, left, right);
        // return res;
    }
}

int32_t main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];

    build(1, 1, n);

    while(m -- )
    {
        int x, l, r; cin >> x >> l >> r;
        if(x == 1)
        {
            if(l > r) swap(l, r);
            cout << query(1, l, r).tmax << endl;
        }
        else
        {
            modify(1, l, r);
        }
    }
    return 0;
}



DPH
15天前
#include <bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 10;

int n, m, w[N];

struct Node
{
    int l, r;
    int sum, add;
};

Node tr[N << 2];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    return ;
}

void pushdown(int u)
{
    Node &Root = tr[u];
    Node &Left = tr[u << 1];
    Node &Right = tr[u << 1 | 1];

    if(Root.add)
    {
        Left.add += Root.add;
        Left.sum += (Left.r - Left.l + 1) * Root.add;

        Right.add += Root.add;
        Right.sum += (Right.r - Right.l + 1) * Root.add;

        Root.add = 0;
    }

    return ;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};

    if(l == r)
    {
        tr[u].sum = w[l];
        return ;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);

    return ;
}

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;

    int ans = 0;
    if(l <= mid) ans += query(u << 1, l, r);
    if(r > mid) ans += query(u << 1 | 1, l, r);

    return ans;
}

void modify(int u, int l, int r, int d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += d;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, d);
        if(r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
    return ;
}

int32_t main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> w[i];

    build(1, 1, n);

    while(m -- )
    {
        string op; cin >> op;

        if(op == "Q") 
        {
            int x, y; cin >> x >> y;
            cout << query(1, x, y) << endl;
        }
        else
        {
            int x, y, z; cin >> x >> y >> z;
            modify(1, x, y, z);
        }
    }
    return 0;
}


活动打卡代码 AcWing 1275. 最大数

DPH
18天前
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2e5 + 10;

int m, p;

struct Node
{
    int l, r;
    int v;
};

Node tr[N * 4];

void pushup(int u)
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
    return ;
}


// 建立一个节点编号为 u 的树 囊括了[l, r]
void build(int u, int l, int r)
{
    // 标记左右端点
    tr[u] = {l, r};
    if(l == r) return ;

    // 递归建左右子树
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    return ;
}

int query(int u, int l, int r)
{
    // 树中节点已经被完全包含在 [l, r] 中了
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r);
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));

    return v;
}

void modify(int u, int x, int v)
{
    if(tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);

        // 用儿子的点来更新父亲
        // 因为上面的 if 是精准修改所以只改自己就完事了
        // 但下面的 else 条件囊括了别人所以要修改上层
        pushup(u);
    }
    return ;
}

int32_t main()
{
    int n = 0, last = 0;

    cin >> m >> p;
    build(1, 1, m); // 长度为 m 的区间对应的线段树

    int x;
    string y;
    while(m -- )
    {
        cin >> y >> x;
        if(y == "Q")
        {
            // 从节点为 1 的编号开始往下找区间 [n - x + 1, n] 的最大值
            last = query(1, n - x + 1, n);
            cout << last << endl;
        }
        else
        {
            // 从节点为 1 的编号开始往下更新在末尾添加 (last + x) % p 后的情况
            modify(1, n + 1, (last + x) % p);
            n ++ ;
        }
    }
    return 0;
}


活动打卡代码 AcWing 241. 楼兰图腾

DPH
1个月前
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int n, a[N], tr[N], G[N], L[N];

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

int sum(int x)
{
    int ans = 0;
    for(int i = x; i > 0; i -= lowbit(i))
    {
        ans += tr[i];
    }
    return ans;
}

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

int32_t main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    int ansA = 0;
    int ansV = 0;

    for(int i = 1; i <= n; i ++ )
    {
        int y = a[i];
        L[i] = sum(y - 1);
        G[i] = sum(n) - sum(y);
        add(y, 1);

        int t = L[i] * (a[i] - 1 - L[i]);
        ansA += t;

        int tt = G[i] * (n - a[i] - G[i]);
        ansV += tt;
    }

    cout << ansV << ' ' << ansA << endl;
    return 0;
}



DPH
1个月前

DFS简单例题

#include <bits/stdc++.h>

using namespace std;

int n;
int path[10];
bool vis[10];

void dfs(int x)
{
    if(x == n)
    {
        for(int i = 1; i <= n; i ++ )
        {
            cout << path[i] << ' ';
        }
        cout << endl;
        return ;
    }

    for(int i = 1; i <= n; i ++ )
    {
        if(!vis[i])
        {
            vis[i] = 1;
            path[x + 1] = i;
            dfs(x + 1);
            path[x + 1] = 0;
            vis[i] = 0;
        }
    }
    return ;
}

int main()
{
    cin >> n;

    dfs(0);

    return 0;
}

n-皇后
一行行的枚举

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
char g[N][N];
int col[N], dj[N], udj[N];

void dfs(int h)
{

    if(h == n + 1)
    {
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= n; j ++ ) cout << g[i][j];
            cout << endl;
        }
        cout << endl;
        return ;
    }

    for(int i = 1; i <= n; i ++ )
    {
        if(!col[i] && !udj[h - i + n] && !dj[h + i])
        {
            g[h][i] = 'Q';
            col[i] = udj[h - i + n] = dj[h + i] = 1;
            dfs(h + 1);
            col[i] = udj[h - i + n] = dj[h + i] = 0;
            g[h][i] = '.';
        }
    }
    return ;
}

int main()
{
    cin >> n;

    // 一定先要初始化 不然能拿的就只有串的头 后面相当于没有定义 不存在
    // 想要参悟dfs的过程 可以g[i][j] = '#'
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ ) g[i][j] = '.';
    }

    dfs(1);

    return 0;
}

一个个格子的枚举

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
char g[N][N];
int row[N], col[N], dj[N], udj[N];

void dfs(int x, int y, int s)
{
    if(y > n) x ++ , y %= n;
    if(x == n + 1)
    {
        if(s == n)
        {
            for(int i = 1; i <= n; i ++ )
            {
                for(int j = 1; j <= n; j ++ ) cout << g[i][j];
                cout << endl;
            }
            cout << endl;
        }
        return ;
    }

    // 这个格子不放皇后
    dfs(x, y + 1, s);

    // 想放 看能不能放
    if(!row[x] && !col[y] && !dj[y + x] && !udj[y - x + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dj[y + x] = udj[y - x + n] = 1;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dj[y + x] = udj[y - x + n] = 0;
        g[x][y] = '.';
    }

    return ;
}

int main()
{
    cin >> n;

    // 一定先要初始化 不然能拿的就只有串的头 后面相当于没有定义 不存在
    // 想要参悟dfs的过程 可以g[i][j] = '#'
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ ) g[i][j] = '.';
    }

    dfs(1, 1, 0);

    return 0;
}

走迷宫-简单的BFS

八数码-把状态转移为点-然后BFS

#include <bits/stdc++.h>

using namespace std;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs(string x)
{
    queue<string> q;
    // 普通map会T
    unordered_map<string, int> d;

    q.push(x); d[x] = 0;

    while(q.size())
    {
        auto t = q.front(); q.pop();

        if(t == "12345678x") return d[t];

        int dis = d[t];

        int po = t.find('x');
        int px = po / 3;
        int py = po % 3;

        for(int i = 0; i <= 3; i ++ )
        {
            int xx = px + dx[i];
            int yy = py + dy[i];
            if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
            {
                int npo = xx * 3 + yy;
                swap(t[po], t[npo]);
                if(!d.count(t)) 
                {
                    q.push(t);
                    d[t] = dis + 1;
                }
                swap(t[po], t[npo]);
            }
        }
    }
    return -1;
}

int main()
{
    string x, y;
    for(int i = 1; i <= 9; i ++ )
    {
        cin >> y;
        x += y;
    }
    cout << bfs(x) << endl;
    return 0;
}

树的重心-图的深度优先遍历

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
bool st[N];
int ans = 0x3f3f3f3f;

vector< vector<int> > g(N);

int dfs(int x)
{
    int cnt = 0;
    int sum = 1;

    for(int i = 0; i < g[x].size(); i ++ )
    {
        if(!st[g[x][i]])
        {
            st[g[x][i]] = 1;
            int xx = dfs(g[x][i]);

            sum += xx;
            cnt = max(cnt, xx);

            st[g[x][i]] = 0;
        }
    }

    cnt = max(cnt, n - sum);

    ans = min(ans, cnt);
    return sum;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n - 1; i ++ )
    {
        int x, y; cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }

    st[1] = 1; dfs(1);

    cout << ans << endl;
    return 0;
}

图中点的层次-图的广度优先遍历

拓扑排序-广搜应用

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int main()
{
    int n, m; cin >> n >> m;
    vector<int> id(n + 10, 0);
    vector< vector<int> > g(n + 10);
    for(int i = 1; i <= m; i ++ )
    {
        int x, y; cin >> x >> y;
        g[x].emplace_back(y);
        id[y] ++ ;
    }
    queue<int> q, qq;
    for(int i = 1; i <= n; i ++ )
    {
        if(!id[i]) q.push(i);
        // cout << id[i] << ' ';
    }

    while(q.size())
    {
        auto t = q.front(); q.pop();

        qq.push(t);
        for(int i = 0; i < g[t].size(); i ++ )
        {
            id[g[t][i]] -- ;
            if(!id[g[t][i]]) q.push(g[t][i]);
        }
    }

    if(qq.size() < n) cout << -1 << endl;
    else
    {
        while(qq.size())
        {
            cout << qq.front() << ' ';
            qq.pop();
        }
    }

    return 0;
}

最短路算法总结
——单源最短路
————边权皆正
——————朴素Dijkstra O(n^2)
——————堆优化Dijkstra O(mlogn)
————有负权边
——————Bellman-Ford O(nm)
——————SPFA 一般O(m),最坏O(nm) // 最常用 Dijkstra能写的大部分题SPFA都能写 卡了再说
——多源最短路 Floyd O(n^3)

朴素dijkstra

#include <string.h>
#include <iostream>
#include <math.h>

using namespace std;

const int N = 505;

int g[N][N] = {0};
int dist[N] = {0};
bool st[N] = {0};
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n ; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        st[t] = true;
        for(int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    while(m--)
    {
        int a, b, c; cin>>a>>b>>c;
        g[a][b] = min(g[a][b], c);
    }
    int t = dijkstra();
    cout<<t<<'\n';
    return 0;
}

堆优化Dijkstra

#include <bits/stdc++.h>

using namespace std;

#define PII pair<int, int>

const int N = 150000 + 10;

int n, m;
bool st[N];
int dist[N];
vector<PII> g[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);

    priority_queue< PII, vector<PII>, greater<PII> > q;

    dist[1] = 0;
    q.push({0, 1});

    while(q.size())
    {
        auto t = q.top(); q.pop();
        int dis = t.first;
        int id = t.second;

        if(st[id]) continue;
        st[id] = 1;

        for(int i = 0; i < g[id].size(); i ++ )
        {
            dist[g[id][i].first] = min(dist[g[id][i].first], dis + g[id][i].second);
            q.push({dist[g[id][i].first], g[id][i].first });
        }
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, c; cin >> x >> y >> c;
        g[x].emplace_back(y, c);
    }
    int t = dijkstra();
    cout << t << endl;
    return 0;
}

除了这题一般用不上的Bellman-Ford

#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 10;
const int M = 1e4 + 10;

int n, m, k;
int dist[N], last[N];

struct Edge
{
    int x, y, w;
};
Edge a[M];

void flod()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 1; i <= k; i ++ )
    {
        memcpy(last, dist, sizeof last);
        for(int j = 1; j <= m; j ++ )
        {
            auto t = a[j];
            dist[t.y] = min(dist[t.y], last[t.x] + t.w);
        }
    }

    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, w; cin >> x >> y >> w;
        a[i].x = x; a[i].y = y; a[i].w = w;
    }

    flod();

    return 0;
}

SPFA既能求最短路

#include <bits/stdc++.h>

using namespace std;

#define PII pair<int, int>

const int N = 1e5 + 10;

int n, m, st[N], dist[N];

vector<PII> g[N];

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1); st[1] = 1;

    while(q.size())
    {
        int t = q.front(); q.pop(); st[t] = 0;
        for(int i = 0; i < g[t].size(); i ++ )
        {
            int y = g[t][i].first;
            int w = g[t][i].second;

            if(dist[y] > dist[t] + w)
            {
                dist[y] = dist[t] + w;
                if(!st[y])
                {
                    st[y] = 1; q.push(y);
                }
            }
        }
    }

    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;

    return ;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, w; cin >> x >> y >> w;
        g[x].emplace_back(y, w);
    }
    spfa();
}

SPFA还能判负环

#include <bits/stdc++.h>

using namespace std;

#define PII pair<int, int>

const int N = 1e5 + 10;

int n, m, st[N], cnt[N], dist[N];

vector<PII> g[N];

bool spfa()
{
    queue<int> q;
    for(int i = 1; i <= n; i ++ )
    {
        q.push(i); st[i] = 1;
    }

    while(q.size())
    {
        int t = q.front(); q.pop(); st[t] = 0;
        for(int i = 0; i < g[t].size(); i ++ )
        {
            int y = g[t][i].first;
            int w = g[t][i].second;

            if(dist[y] > dist[t] + w)
            {
                dist[y] = dist[t] + w;
                cnt[y] = cnt[t] + 1;

                if(cnt[y] >= n) return 1;

                if(!st[y])
                {
                    st[y] = 1; q.push(y);
                }
            }
        }
    }
    return 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, w; cin >> x >> y >> w;
        g[x].emplace_back(y, w);
    }
    if( spfa() ) cout << "Yes" << endl ;
    else cout << "No" << endl;

    return 0;
}

Floyd求最短路

#include <bits/stdc++.h>

using namespace std;

const int N = 200 + 10;
const int M = 20000 + 10;
const int INF = 0x3f3f3f3f;

int n, m, Q;
int g[N][N];

void floyd()
{
    for(int k = 1; k <= n; k ++ )
    {
        for(int i = 1; i <= n; i ++ )
        {
            for(int j = 1; j <= n; j ++ )
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    return ;
}

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

    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }

    for(int i = 1; i <= m; i ++ )
    {
        int x, y, w; cin >> x >> y >> w;
        g[x][y] = min(g[x][y], w);
    }

    floyd();

    for(int i = 1; i <= Q; i ++ )
    {
        int x, y; cin >> x >> y;
        if(g[x][y] > INF / 2) cout << "impossible" << endl;
        else cout << g[x][y] << endl;
    }

    return 0;
}

最小生成树算法
——Prim
————朴素版 O(n^2)
————堆优化版 O(mlogn)
——Kruskal O(mlogm)

Prim朴素版

#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 10;

bool st[N];
int n, m, g[N][N], dist[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int ans = 0;

    for(int i = 0; i < n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
        {
            if( (!st[j]) && (t == -1 || dist[j] < dist[t]) ) t = j;
        }

        st[t] = 1;

        if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;

        if(i)
        {
            ans += dist[t];
        }

        for(int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return ans;
}

int main()
{
    memset(g, 0x3f, sizeof g);

    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        int x, y, w; cin >> x >> y >> w;
        g[x][y] = g[y][x] = min(g[x][y], w);
    }

    int t = prim();

    if(t == 0x3f3f3f3f) cout << "impossible" << endl;
    else cout << t << endl;

    return 0;
}

Kruskal




DPH
1个月前

链表(单双) 栈 队列 先放一边

单调栈
与双指针类似 通过利用某些性质 达到压缩时间的目的

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

using namespace std;

int main()
{
    int n; cin >> n;
    stack<int> s;
    while(n -- )
    {
        int t; cin >> t;

        while(s.size() && s.top() >= t) s.pop();

        if(s.size()) cout << s.top() << ' ';
        else cout << -1 << ' ';

        s.push(t);
    }
    return 0;
}

单调队列
类似单调栈 另:Y总的数组模拟队列是双端的 比STL快

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

using namespace std;

const int INF = 0x3f3f3f3f;

struct Node
{
    int x, y;
};

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

    int mx = -INF;
    int mi = INF;

    vector<int> a(n + 10);
    deque<Node> q;

    for(int i = 1; i <= n; i ++ )
    {
        int t; cin >> t; a[i] = t;

        while(q.size() && q.back().x >= t) q.pop_back();
        while(q.size() && q.front().y <= i - m) q.pop_front();

        if(i - m >= 0)
        {
            if(q.size()) cout << q.front().x << ' ';
            else cout << t << ' ';
        }

        q.push_back({t, i});
    }
    cout << endl;

    deque<Node> qq;
    for(int i = 1; i <= n; i ++ )
    {
        int t; t = a[i];

        while(qq.size() && qq.back().x <= t) qq.pop_back();
        while(qq.size() && qq.front().y <= i - m) qq.pop_front();

        if(i - m >= 0)
        {
            if(qq.size()) cout << qq.front().x << ' ';
            else cout << t << ' ';
        }

        qq.push_back({t, i});
    }
    cout << endl;

    return 0;
}

KMP
和字符串哈希各有千秋的字符串匹配
先一层循环得到next数组 再一层循环得答案

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

int n, m;
int ne[N];
char a[N], b[M];

int main()
{
    cin>>n>>a + 1>>m >> b + 1;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && a[i] != a[j + 1]) j = ne[j];
        if(a[i] == a[j + 1]) j++;
        ne[i] = j;
    }
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && b[i] != a[j + 1]) j = ne[j];
        if(b[i] == a[j + 1]) j++;
        if(j == n)
        {
            cout<<i - j<<' ';
            j = ne[j];
        }
    }
    return 0;
}

Trie树 快速存储字符串集合
先来个手写的板子

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

char s[N];
int son[N][26], cnt[N], idx;

void Insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
    return ;
}

int Query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n; cin >> n;
    while(n -- )
    {
        char op[5]; cin >> op >> s;
        if(op[0] == 'I') Insert(s);
        else cout << Query(s) << endl;
    }
    return 0;
}

来个Trie的应用

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = N * 32;

int idx, a[N], son[M][2];

void Insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    return ;
}

int Query(int x)
{
    int p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if(son[p][!u])
        {
            res = res * 2 + !u;
            p = son[p][!u];
        }
        else
        {
            res = res * 2 + u;
            p = son[p][u];
        }
    }
    return res;
}

int main()
{
    int ans = 0;
    int n; cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        Insert(a[i]);
        ans = max(ans, a[i] ^ Query(a[i]));
    }
    cout << ans << endl;
    return 0;
}

普通并查集 和 带连通块点的并查集 都巨简单
这里记一下食物链的两种解法
首先是Y总版本

#include <bits/stdc++.h>

using namespace std;

const int N = 50000 + 10;

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

int find(int x)
{
    if(f[x] != x)
    {
        int u = find(f[x]);
        d[x] += d[f[x]];
        f[x] = u;
        // 这里的f[x]其实是当前点的祖宗
        // 所以d[x]是当前点到它祖宗节点的距离
        // 所以d[f[x]]表示的是 x之前的祖宗节点 到它现在的祖宗节点的距离
    }
    return f[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++ ) f[i] = i, d[i] = 0;

    int ans = 0;
    while(m -- )
    {
        int o, x, y; cin >> o >> x >> y;
        if(x > n || y > n || (o == 2 && x == y)) ans ++ ;
        else
        {
            int xx = find(x);
            int yy = find(y);
            int t = d[y] - d[x];

            if(o == 1)
            {
                if(xx == yy)
                {
                    if(t % 3) ans ++ ;
                }
                else
                {
                    f[xx] = yy;
                    d[xx] += t;
                }
            }
            else
            {
                if(xx == yy)
                {
                    if((t - 1) % 3) ans ++ ;
                }
                else
                {
                    f[xx] = yy;
                    d[xx] += (t - 1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

然后是扩展域并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 50000 + 10;
const int M = N * 3;

int n, m, f[M];

int find(int x)
{
    if(f[x] != x)
    {
        f[x] = find(f[x]);
    }
    return f[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n * 3; i ++ ) f[i] = i;
    int ans = 0;
    while(m -- )
    {
        int o, x, y; cin >> o >> x >> y;
        if(x > n || y > n || (o == 2 && x == y)) ans ++ ;
        else
        {
            // x_eat x吃的物种
            // x_enemy 吃x的物种
            int x_eat = x + n;
            int x_enemy = x + 2 * n;

            int y_eat = y + n;
            int y_enemy = y + 2 * n;

            if(o == 1)
            {
                if(find(x_eat) == find(y) || find(x_enemy) == find(y)) ans ++ ;
                else
                {
                    f[find(x)] = find(y);
                    f[find(x_eat)] = find(y_eat);
                    f[find(x_enemy)] = find(y_enemy);
                }
            }
            else
            {
                if(find(x) == find(y) || find(x_enemy) == find(y)) ans ++ ;
                else
                {
                    f[find(x_eat)] = find(y);
                    f[find(y_enemy)] = find(x);
                    f[find(x_enemy)] = find(y_eat);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

补充一题(暂时还没有搞懂)
https://codeforces.com/contest/1594/problem/D

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int M = N * 2;

int n, m, f[M], s[M];

int find(int x)
{
    if(x != f[x])
    {
        f[x] = find(f[x]);
    }
    return f[x];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while(T -- )
    {
        cin >> n >> m;
        for(int i = 1; i <= n * 2; i ++ ) f[i] = i, s[i] = 0;

        bool flag = 1;
        while(m -- )
        {
            int x, y; cin >> x >> y;
            string o; cin >> o;

            int xx = x + n;
            int yy = y + n;

            if(o == "crewmate")
            {
                if(find(x) == find(yy) || find(y) == find(xx)) flag = 0;
                else
                {
                    f[find(x)] = find(y);
                    f[find(xx)] = find(yy);
                }
            }
            else
            {
                if(find(x) == find(y) || find(xx) == find(yy)) flag = 0;
                else
                {
                    /*
                    为什么都是认祖宗
                    f[find(xx)] = find(y);
                    f[find(yy)] = find(x);
                    就不行?
                    */
                    f[find(y)] = find(xx);
                    f[find(yy)] = find(x);
                }
            }
        }

        if(!flag) cout << -1 << endl;
        else
        {
            // 这整一个else里面的东西都没怎么懂

            for(int i = 1; i <= n; i ++ ) s[find(i)] ++ ;

            int ans = 0;
            for(int i = 1; i <= n; i ++ )
            {
                if(i != find(i)) continue;
                ans += max(s[find(i)], s[find(i + n)]);
            }
            cout << ans << endl;
        }
    }

    return 0;
}

哈希表
开放寻址法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 100003;

int a[N];

int Find(int x)
{
    int t = (x % M + M) % M;
    while(a[t] != 0x3f3f3f3f)
    {
        t ++ ;
        if(t >= M) t %= M;
    }
    return t;
}

bool Query(int x)
{
    int t = (x % M + M) % M;
    while(a[t] != x && a[t] != 0x3f3f3f3f)
    {
        t ++ ;
        if(t >= M) t %= M;
    }
    if(a[t] == 0x3f3f3f3f) return 0;
    return 1;
}

int main()
{
    memset(a, 0x3f, sizeof a);

    int n; cin >> n;
    while(n -- )
    {
        string x; int y;
        cin >> x >> y;

        // cout << t << endl;

        if(x == "I")
        {
            int t = Find(y);
            a[t] = y;
        }
        else
        {
            if(Query(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    // for(int i = 1; i <= M; i ++ ) cout << a[i] << ' ';

    return 0;
}

拉链法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 100003;

int idx;
int h[N], e[N], ne[N];

void Insert(int x)
{
    int k = (x % M + M) % M;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx; idx ++ ;
    return ;
}

bool Find(int x)
{
    int t = (x % M + M) % M;
    for(int i = h[t]; i != -1; i = ne[i])
    {
        if(e[i] == x) return 1;
    }
    return 0;
}

int main()
{
    memset(h, -1, sizeof h);

    int n; cin >> n;
    while(n -- )
    {
        string x; int y;
        cin >> x >> y;

        if(x == "I")
        {
            Insert(y);
        }
        else
        {
            if(Find(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

字符串哈希

#include <bits/stdc++.h>

using namespace std;

#define int unsigned long long

const int N = 1e5 + 10;
const int M = 131;

int n, m;
int a[N], b[N];
char c[N];

int32_t main()
{
    a[0] = 0; b[0] = 1;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> c[i];
        a[i] = a[i - 1] * M + c[i];
        b[i] = b[i - 1] * M;
    }

    while(m -- )
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        // int x = a[r1] % b[r1 - l1];
        // int y = a[r2] % b[r1 - l1];

        // Hack样例
        // 10 3
        // Ac1Ac1Ac1A
        // 1 6 4 9
        // 1 5 3 7
        // 2 3 5 6

        // 因为你用 ULL模2的64次方 只能保证模后+—*/结果相同
        // 并不能保证末位取模后还是你想要的
        // 所以 老实用Y总方法
        // h[r] - h[l - 1] * p[r - l + 1];
        int x = a[r1] - a[l1 - 1] * b[r1 - l1 + 1];
        int y = a[r2] - a[l2 - 1] * b[r2 - l2 + 1];

        // cout << x << ' ' << y << endl;

        if(x == y) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}



DPH
1个月前

快速排序
先用一个x把所有数组元素大致分成两半
分治递归直到分无可分
应用 快速查找 通过筛选只要quick_sort()一半

归并排序
先用一个x把原数组分治递归 使得左右两边各自有序
然后合并

二分
分为 整数二分 和 浮点数二分
整数二分需要考虑边界和各种意外
浮点数二分只需要无脑分下去就可以了

高精度 用vector存储每一位上的数字

前缀和 是第一个学的可以方便求区间和的算法 有一维有二维
差分 是前缀和的逆操作 可以快速让一个区间加同样的数

双指针算法 就是通过思维的优化用两个指针压缩时间解决问题

位运算 很基础的二进制位的运算 lowbit操作 return x & -x;

离散化 在范围很大密度很小的时候很有用

#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;

int find(int x)
{
    int l = 0;
    int 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;
    // alls下标从0开始 返回的是下标在所有下标中排第几位从1开始
}

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

        alls.emplace_back(x);
    }
    for(int i = 1; i <= m; i ++ )
    {
        int l, r; cin >> l >> r;
        query.emplace_back(l, r);

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

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for(auto item : add)
    {
        int x = find(item.first);
        a[x] += 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);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

区间合并 一个没什么难度的可以手写的算法



活动打卡代码 AcWing 3955. 统一大小写

DPH
1个月前
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int n; cin >> n;
    while(n -- )
    {
        string s; cin >> s;
        int a = 0; 
        int b = 0;
        for(int i = 0; i < s.size(); i ++ )
        {
            if(s[i] >= 'a' && s[i] <= 'z') a ++ ;
            else b ++ ;
        }
        if(a >= b)
        {
            for(int i = 0; i < s.size(); i ++ )
            {
                if(s[i] >= 'a' && s[i] <= 'z') cout << s[i];
                else
                {
                    char t = s[i] - 'A' + 'a';
                    cout << t;
                }
            }
        }
        else
        {
            for(int i = 0; i < s.size(); i ++ )
            {
                if(s[i] >= 'a' && s[i] <= 'z')
                {
                    char t = s[i] - 'a' + 'A';
                    cout << t;
                }
                else
                {
                    cout << s[i];
                }
            }
        }
        cout << endl;
    }
    return 0;
}