分类 BZOJ 下的文章

[BZOJ 3930] [CQOI 2015] 选数

题目链接

[BZOJ 3930] [CQOI 2015] 选数

题解

中档题。题意大概是求从L到H中取N个数使它们的最大公约数为K的选区方案数。
考虑原题让你求l-r中gcd(i,j)=k的个数。
等价于求l/k-r/k中gcd(i,j)=1的个数.
我们设d[i]表示l/k-r/k中gcd(i,j)=i的个数,
容斥一下即可.注意特判所有数都相等的情况。

代码

Time: 220ms
Memory: 2068kB
#include<iostream>
using namespace std;

const long long  MOD = 1e9 + 7;
const int  MAXN = 100050;

long long a[MAXN], N, K, L, H, l, r;

long long quick_power(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1)ans = ans * a%MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int main() {
    cin >> N >> K >> L >> H;
    l = L / K, r = H / K;
    if (L % K)l++;
    for (int i = H - L; i; i--) {
        int ll = l / i, rr = r / i;
        if (l % i)ll++;
        if (l <= r) {
            a[i] = (quick_power(rr - ll + 1, N) - (rr - ll + 1)) % MOD;
            for (int j = i * 2; j <= H - L; j += i)a[i] = (a[i] - a[j]) % MOD;
        }
    }
    if (l == 1)a[1]++;
    cout << (a[1] + MOD) % MOD << endl;
    return 0;
}

[BZOJ 4710] [Jsoi 2011] 分特产

题目链接

[BZOJ 4710] [Jsoi 2011] 分特产

题解

中档题。题意大概是给定多种不同的物品分给若干个人,每种物品又有一定数量,要求每个人至少拥有一样物品。
首先考虑只分一种物品,且不考虑是否为空,根据隔板法有P(n+m-1,m-1)种方法。
考虑多种物品的话只要把每一种都乘上即可。
接下来考虑没有空余的情况。上述方法算出来的并不能保证每个人均不为空,求出的只有至少0个为空的情况。我们根据同样的方法可以求出至少1个为空,至少2个为空……根据容斥原理,至多0个为空的答案为至少0个为空-至少1个为空+至少2个为空-至少3个为空+……

代码

Time:148ms
Memory:1328kB
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
const int MOD = 1e9 + 7;
long long n, m, ans;
long long  fac[MAXN], inv[MAXN], input[MAXN];

inline long long C(long long a, long long b) {
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    inv[0] = inv[1] = fac[0] = 1;
    for (int i = 2; i < MAXN; i++) {
        inv[i] = inv[MOD%i] * (MOD - MOD / i) % MOD;
    }
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i%MOD;
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> input[i];
    }
    for (int i = 0; i < n; i++) {
        long long temp = C(n, i);
        for (int j = 1; j <= m; j++) {
            temp = temp * C(input[j] + n - i - 1, n - i - 1) % MOD;
        }
        ans += (i & 1) ? MOD - temp : temp;
        ans %= MOD;
    }
    cout << ans << endl;
}

[NOI 2005] 维修数列

题目链接

[BZOJ 1500] [NOI 2005] 维修数列

题解

高档题。题意大概是给定一组数列和一定的操作,包含插入、删除、修改、翻转、求和、求和最大的子列。
这种包含了翻转、删除、插入等操作的维护序列问题很容易校内感到splay。
套模板即可,不过写起来很麻烦。

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 500005;
const int INF = 1 << 30;
int i, j, k, l, n, m, ans, root, posi;
int f[maxn], a[maxn], d[maxn], b[maxn], x, y, key[maxn], shan[maxn], num, zhi, son[maxn][2];
string s;

struct node {
    int maxSum, sum, size, l, r, flag, add;
}tree[maxn];

void update(int x) {
    if (!x)return;
    tree[x].size = 1 + tree[son[x][0]].size + tree[son[x][1]].size;
    tree[x].sum = key[x] + tree[son[x][0]].sum + tree[son[x][1]].sum;
    tree[x].l = max(tree[son[x][0]].l, tree[son[x][0]].sum + key[x] + tree[son[x][1]].l);
    tree[x].r = max(tree[son[x][1]].r, tree[son[x][1]].sum + key[x] + tree[son[x][0]].r);
    tree[x].maxSum = max(max(tree[son[x][0]].maxSum, tree[son[x][1]].maxSum), tree[son[x][0]].r + tree[son[x][1]].l + key[x]);
}

void makesame(int x, int y) {
    if (!x)return;
    tree[x].sum = tree[x].size*y;
    key[x] = y; tree[x].add = y;
    if (y>0)tree[x].l = tree[x].r = tree[x].maxSum = tree[x].sum;
    else tree[x].l = tree[x].r = 0, tree[x].maxSum = y;
}

bool issoneq(int x) {
    if (son[f[x]][0] == x)return 0; return 1;
}

void rotate(int x) {
    int y = f[x], z = issoneq(x);
    son[y][z] = son[x][1 - z];
    if (son[x][1 - z])f[son[x][1 - z]] = y; f[x] = f[y];
    if (f[y])son[f[y]][issoneq(y)] = x;
    f[y] = x; son[x][1 - z] = y;
    update(y); update(x);
}

void overturn(int x) {
    if (!x)return;
    swap(son[x][0], son[x][1]);
    swap(tree[x].l, tree[x].r);
    tree[x].flag ^= 1;
}

void down(int x) {
    if (!x)return;
    if (tree[x].flag) {
        overturn(son[x][0]);
        overturn(son[x][1]);
        tree[x].flag = 0;
    }
    if (tree[x].add != maxn) {
        makesame(son[x][0], tree[x].add);
        makesame(son[x][1], tree[x].add);
        tree[x].add = maxn;
    }
}

void remove(int x, int y) {
    do {
        d[++d[0]] = x;
        x = f[x];
    } while (x != y);
    while (d[0])down(d[d[0]--]);
}

int insert(int x) {
    int temp;
    if (shan[0])temp = shan[shan[0]--]; else temp = ++num;
    key[temp] = tree[temp].sum = tree[temp].maxSum = x; tree[temp].size = 1; tree[temp].l = tree[temp].r = max(0, x);
    f[temp] = tree[temp].flag = son[temp][0] = son[temp][1] = 0; tree[temp].add = maxn;
    return temp;
}

void splay(int x, int y) {
    if (x == y)return;
    remove(x, y);
    while (f[x] != y) {
        if (f[f[x]] != y)if (issoneq(f[x]) == issoneq(x))rotate(f[x]); else rotate(x);
        rotate(x);
    }
    if (!y)root = x;
}

int build(int l, int r, int y) {
    if (l>r)return 0;
    int mid = (l + r) / 2;
    int x = insert(a[mid]); f[x] = y;
    if (l == r)return x;
    son[x][0] = build(l, mid - 1, x);
    son[x][1] = build(mid + 1, r, x);
    update(x);
    return x;
}

int findpos(int x, int k) {
    down(x);
    if (tree[son[x][0]].size + 1 == k)return x;
    if (tree[son[x][0]].size + 1>k)return findpos(son[x][0], k);
    else return findpos(son[x][1], k - tree[son[x][0]].size - 1);
}

void del(int x) {
    if (!x)return;
    shan[++shan[0]] = x;
    del(son[x][0]); del(son[x][1]);
}

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

    cin >> n >> m;
    tree[0].maxSum = -INF;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    root = build(0, n + 1, 0);

    while (m--) {
        cin >> s;
        if (s[0] == 'I') {
            cin >> posi >> k; posi++;

            for (int i = 1; i <= k; i++)
                cin >> a[i];

            x = findpos(root, posi); splay(x, 0);
            y = findpos(root, posi + 1); splay(y, x);

            son[y][0] = build(1, k, y);

            update(y); update(x);
        }
        else if (s[0] == 'D') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            del(son[y][0]);
            son[y][0] = 0;

            update(y); update(x);
        }
        else if (s[2] == 'K') {
            cin >> posi >> k >> zhi; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            makesame(son[y][0], zhi);

            update(y); update(x);
        }
        else if (s[0] == 'R') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            overturn(son[y][0]);

            update(y); update(x);
        }
        else if (s[0] == 'G') {
            cin >> posi >> k; posi++;

            x = findpos(root, posi - 1); splay(x, 0);
            y = findpos(root, posi + k); splay(y, x);

            cout << tree[son[y][0]].sum << endl;
        }
        else if (s[2] == 'X') {
            x = findpos(root, 1); splay(x, 0);
            y = findpos(root, tree[root].size); splay(y, x);

            cout << tree[son[y][0]].maxSum << endl;
        }
    }
}

[HNOI 2004] 宠物收养所

题目链接

[BZOJ 1208] [HNOI 2004] 宠物收养所

题解

高档题。题意大概是一个宠物收养所在某一时刻只存在宠物或人,每次来人或宠物时会选取特点值最接近的宠物或人。求特点值之差的总和。
Treap树模板套一套即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 1000000;
const long long INF = 1ll << 60;
const int MAXN = 80005;

struct Node
{
    int son[2], num, ran;
} treap[MAXN];
int n, ans, q1, q2, root, pd, temploc;

void rotate(int &loc, int drt) {
    int temp = treap[loc].son[drt ^ 1];
    treap[loc].son[drt ^ 1] = treap[temp].son[drt];
    treap[temp].son[drt] = loc;
    loc = temp;
}

void insert(int &loc, int num) {
    if (!loc) {
        loc = ++temploc;
        treap[loc].son[1] = treap[loc].son[0] = 0;
        treap[loc].num = num;
        treap[loc].ran = rand();
        return;
    }
    int temp = num > treap[loc].num;
    insert(treap[loc].son[temp], num);
    if (treap[loc].ran > treap[treap[loc].son[temp]].ran)rotate(loc, temp ^ 1);
}

void remove(int &loc, int num) {
    if (!loc)return;
    if (num == treap[loc].num) {
        if (!treap[loc].son[0] || !treap[loc].son[1]) {
            loc = treap[loc].son[0] + treap[loc].son[1];
            return;
        }
        if (treap[treap[loc].son[0]].ran > treap[treap[loc].son[1]].ran)rotate(loc, 0);
        else rotate(loc, 1);
        remove(loc, num);
    }
    else {
        remove(treap[loc].son[num > treap[loc].num], num);
    }
}

int query(int num) {
    long long pre(-INF), nxt(INF);
    int loc(root);
    while (loc) {
        if (num > treap[loc].num) {
            pre = treap[loc].num;
            loc = treap[loc].son[1];
        }
        else loc = treap[loc].son[0];
    }
    loc = root;
    while (loc) {
        if (num < treap[loc].num) {
            nxt = treap[loc].num;
            loc = treap[loc].son[0];
        }
        else loc = treap[loc].son[1];
    }

    if (nxt - num < num - pre) {
        remove(root, nxt);
        return nxt - num;
    }
    else {
        remove(root, pre);
        return num - pre;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (cin >> n; n; n--) {
        cin >> q1 >> q2;
        if (!root || q1 == pd) {
            insert(root, q2);
            pd = q1;
        }
        else {
            ans += query(q2);
            ans %= MOD;
        }
    }
    cout << ans << endl;
}

数颜色

本该是暑假集训的高级数据结构的练习题,按照出题大佬的本意要用树套树做的,然而那玩意太麻烦了不会写于是学了学传闻中能解决一切区间问题的莫队算法。具体的使用在我题目中写的注释很详细网上也有很多莫队算法的教程我就不展开说明了。

学习笔记:

  • 不带修改的分块每块大小:sqrt(n),理论时间复杂度O(n*sqrt(n))
  • 带单点修改的分块大小:n2/3,理论时间复杂度O(n5/3)
  • 单点修改的修改过程记录修改前和修改后的值而不是初始值和修改后的值
  • 排序关键字:左区间所在块号,右区间所在块号,修改的时间(如果存在修改)
  • 主要结构

    • 状态转移函数

      • 区间转移(步长为1)
      • 时间转移(步长为1)
    • 数据读入
    • 询问(修改)排序
    • 对询问循环

      • 对时间进行状态转移
      • 对区间进行转移
      • 记录当前询问的答案
    • 输出答案

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题解

高档题。题意大概是单点修改和区间查询,区间查询要求得到某一区间内的颜色数。
套可持久化的莫队算法。

代码

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

const int N = 10005;
const int COLORNUM = 1000005;

struct Query {
    int l, r, time, id;
}q[N];//询问情况
struct Change {
    int pos, New, Old; 
}c[N];//改变情况
int n, m;
int s[N], color[COLORNUM], now[N],ans[N];//s初始输入 now记录某次变量转移后的情况 color记录某种颜色的数量情况 ans记录询问的答案情况
int t, Time, unit, Ans, l(1), r, T;//t记录询问次数 Time记录更改次数 unit记录单元大小 Ans记录当前区间与修改时间的答案 l,r记录当前区间左右端点 T记录当前修改到具体某一次

inline int whichUnit(int a) {//判断当前位置处于哪一个unit
    return a / unit + 1;
}

inline bool cmp(Query a, Query b)//以区间左,右端点,询问时间排序,其中左,右端点分别以unit来划分;
{
    return whichUnit(a.l) == whichUnit(b.l) ? (whichUnit(a.r) == whichUnit(b.r) ? a.time<b.time : a.r<b.r) : a.l<b.l;
}

inline void revise(int x, int d) {//转移状态,以某次区间修改转移
    color[x] += d; 
    if (d>0)Ans += color[x] == 1;
    if (d<0)Ans -= color[x] == 0;
}

inline void going(int x, int d) {//转移状态,以某次颜色修改转移
    if (l <= x && x <= r) {
        revise(d, 1);
        revise(s[x], -1);
    }
    s[x] = d;
}

int main() {
    scanf("%d%d", &n, &m);
    unit = pow(n, (double)2 / 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        now[i] = s[i];
    }
    for (int i = 1; i <= m; i++) {
        char type; 
        int x, y; 
        scanf(" %c %d%d", &type, &x, &y);
        if (type == 'Q')q[++t] = Query{ x, y, Time, t };
        if (type == 'R')c[++Time] = Change{ x, y, now[x] }, now[x] = y;
    }
    sort(q + 1, q + t + 1, cmp);

    for (int i = 1; i <= t; i++)
    {
        while (T<q[i].time)going(c[T + 1].pos, c[T + 1].New), T++;
        while (T>q[i].time)going(c[T].pos, c[T].Old), T--;

        while (l<q[i].l)revise(s[l], -1), l++;
        while (l>q[i].l)revise(s[l - 1], 1), l--;
        while (r<q[i].r)revise(s[r + 1], 1), r++;
        while (r>q[i].r)revise(s[r], -1), r--;

        ans[q[i].id] = Ans;
    }
    for (int i = 1; i <= t; i++)
        printf("%d\n", ans[i]);
}