2019/10/3 CSP-S 模拟测

T1 Permut

题意：

求\(1 - n\)的排列中逆序对数量为\(k\)的排列的个数

SOL：

排除法我们知道一定不是\(O(n!)\)的算法
考虑\(dp\)，现在已经有\(n-1\)的答案了，考虑新加入一个数产生多少新的逆序对
设\(dp[i][j]\)表示\(1 -i\)的排列有\(j\)个逆序对的数量，考虑新加入的数插在哪里会增加多少逆序对数量
有\[dp[i][j] = \sum\limits ^{min(i - 1, j)}_k dp[i - 1][j - k]\]
看起来有点奇怪，变一下形 \[dp[i][j] = \sum\limits^j_{max(0, j - i + 1} dp[i - 1][k]\]
复杂度\(O(n * k ^2)\)，\(O(跑不动)\)
考虑一个前缀和优化，类似“我要长高”和“\(Making the Grade\)”里的一样
由于\(k\)的上界随\(j\)的变化而变化，考虑在循环的时候累加\(dp[i - 1][j]\)到一个变量里，然后赋给\(dp[i][j]\)
注意这里\(k\)的下界在\(j - i + 1 \geq 0\)的时候会发生变化，记得把多加的减掉

#include<bits/stdc++.h>
#define N (1000 + 10)
using namespace std;
int T;
int n, k, sum, f[N][N];
const int mod = 10000;
int main() {
    scanf("%d", &T);
    f[1][0] = 1;
    while (T--) {
        scanf("%d%d", &n, &k);
        if (f[n][k]) {printf("%d\n", f[n][k]); continue;}
        for (register int i = 2; i <= n; ++i) {
            sum = 0;
            for (register int j = 0; j <= k; ++j) {
                sum += f[i - 1][j] % mod;
                f[i][j] = sum % mod;
                if (j - i + 1 >= 0) sum -= f[i - 1][j - i + 1] % mod;
            }
        }
        printf("%d\n", f[n][k]);
    }
    return 0;
}

---

T2 Beautiful

题意：

定义一个数的值\(v_i\)为以它作为中位数的区间的最大长度，\(Q\)次查询询问区间\([l, r]\)内的最大\(v_i\)，原数大小比较时按值为第一关键字，下标为第二关键字
\(n \leq 2000, Q \leq 100000\)

SOL：

看到\(n\)很小，想想能不能怎么操作一下呢

考虑\(O(n)\)枚举每一个数，然后分别向左向右扩展并记录一个变量\(S\)，遇到比它大的就\(--S\)，否则\(++S\)，然后对于每个\(S\)的值记录一个最远位置，最后拼在一起取最大长度得到\(v_i\)
然后随便怎么做一下\(RMQ\)即可

#include<bits/stdc++.h>
#define N (100000 + 10)
using namespace std;
inline int read() {
    int cnt = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
    while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
    return cnt * f;
}
int n, Q, l, r;
int S1[N], S2[N];
int a[N], b[N];
int t[N];
int A[N];
struct node {
    int l, r;
    int gmax;
    #define l(p) tree[p].l
    #define r(p) tree[p].r
    #define gmax(p) tree[p].gmax
}tree[N << 2];


void pushup(int p) {
    gmax(p) = max(gmax(p << 1), gmax(p << 1 | 1));
}

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) {gmax(p) = A[l]; return;}
    int mid = (l + r) >> 1;
    build (p << 1, l, mid);
    build (p << 1 | 1, mid + 1, r);
    pushup(p);
}

long long query(int p, int l, int r) {
    if (l <= l(p) && r >= r(p)) return gmax(p);
    int mid = (l(p) + r(p)) >> 1;
    long long ans = -1;
    if (l <= mid) ans = max(ans, query(p << 1, l, r));
    if (r > mid) ans = max(ans, query(p << 1 | 1, l, r));
    return ans;
}

int main() {
    n = read(); for (register int i = 1; i <= n; ++i) a[i] = read();
    for (register int i = 1; i <= n; ++i) {
        int tmp = 0;
        memset(S1, 255, sizeof(S1));
        memset(S2, 255, sizeof(S2));
        S1[n] = S2[n] = 0;
        for (register int j = i - 1; j >= 1; --j) {
            if (a[j] > a[i]) ++tmp; if (a[j] <= a[i]) --tmp;
            S1[tmp + n] = i - j;
        }
        tmp = 0;
        for (register int j = i + 1; j <= n; ++j) {
            if (a[j] >= a[i]) ++tmp; if (a[j] < a[i]) --tmp;
            S2[tmp + n] = j - i;
        }
        for (register int j = 1 - i; j <= i - 1; ++j) if (S1[n + j] >= 0 && S2[n - j] >= 0) A[i] = max(A[i], S1[n + j] + 1 + S2[n - j]);
    } Q = read();
//  for (register int i = 1; i <= n; ++i) cout<<A[i]<<" ";return 0;
    build (1, 1, n);
    while (Q--) {
        l = read(), r = read();
        printf("%lld\n", query(1, l, r));
    }
    return 0;
}

---

T3 Subset

题意：

维护一个集合\(A\)，支持插入删除查询\(a_i\&S=a_i\)的个数，\(a_i \in A\)，操作\(2e5\)，数字大小\(2^{16}\)

SOL：

奇妙的思路
由二进制去考虑，把数拆成两节，记录\(s[a][b]\)表示前八位是\(a\)，后八位是\(b\)的子集的个数
对于\(add\)和\(del\)定\(b\)枚举\(a\)更新
对于\(cnt\)操作定\(a\)枚举\(b\)更新
平衡了查询和修改之间的复杂度，时间复杂度优化为\(O(n * 2 ^ 8)\)

#include<bits/stdc++.h>
#define N ((1 << 8) + 5)
using namespace std;
int Q, x;
char ope[5];
int s[N][N];
inline int read() {
    int cnt = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
    while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}
    return cnt * f;
}
void add(int x) {
    int a = x >> 8, b = x - (a << 8);
    for (register int i = 0; i < (1 << 8); ++i) if ((i & a) == a) s[i][b]++;
}
void del(int x) {
    int a = x >> 8, b = x - (a << 8);
    for (register int i = 0; i < (1 << 8); ++i) if ((i & a) == a) s[i][b]--;
}
int query(int x) {
    int ans = 0, a = x >> 8, b = x - (a << 8);
    for (register int i = 0; i < (1 << 8); ++i) if ((i & b) == i) ans += s[a][i];
    return ans;
}
int main() {
    Q = read();
    while (Q--) {
        scanf("%s", ope + 1); x = read();
        if (ope[1] == 'a') add(x);
        if (ope[1] == 'd') del(x);
        if (ope[1] == 'c') printf("%d\n", query(x));
    }
    return 0;
}