题解

NOIP半年集训day5


打$zr$的比赛考得最崩的一次。。。
听完题解之后觉得挺简单的,但是这些题型我确实很陌生。

A.Part

没什么好说的,开个桶记录一下以有哪些数是结尾,扫一遍,能接上去就接。
时间复杂度: $O(n)$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <climits>
#include <queue>
const int MAXN = 1e6 + 7;
int t[MAXN];
int a[MAXN];
int ans, n;
int main(int argc, char *argv[]) {
    scanf("%d", &n);
    ans = n;
    for (int i = 1; i <= n; i++) {scanf("%d", a + i);}
    t[a[n]] = 1;
    for (int i = n - 1; i >= 1; i--) {
        if (a[i] - 1 != 0)
        if (t[a[i] - 1]) {
            t[a[i] - 1]--;
            ans--;
        }
        t[a[i]]++;
    }
    printf("%d\n", ans);
    return 0;
}

B.Pref

这道题的切入点在于满足条件的字符串的特殊限制。
必须前后缀相同才能更新。
怎么比较是否相同呢?
那我们就把前后缀 $Hash$ 一下,就可以比较了。据说也可以 $Trie$ 树或者 $KMP$ 之类的做,但是还是 $Hash$ 好写啊。
这又是一个最优解问题,求满足条件的最长的子序列,我们可以 $DP$。
用 $Map$ 把 $Hash$ 值映射到答案就可以了。
$f[u] = max(f[v] +1)$

代码

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
const int base = 41;
const ll HA = 19260817;
const int MAXN = 2e6 + 7;
int n;
char s[MAXN];
std::map<ll, int> map;
ll fac[MAXN];
int ans = 1, max;
int main(int argc, char *argv[]) {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = (fac[i - 1] * base) % HA;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        max = 0;
        scanf("%s", s);
        int len = strlen(s);
        ll pre = 0, suc = 0, num = 0;
        for (int j = 0; j < len; j++) {
            pre = ((pre * base) + s[j] - 'a' + 1) % HA;
            suc = ((s[len - 1 - j] - 'a' + 1) * fac[j] % HA + suc) % HA;
            num = ((num * base) + s[j] - 'a' + 1) % HA;
            if (pre == suc) max = std::max(max, map[pre]);
        }
        map[num] = std::max(map[num], max + 1);
        ans = std::max(ans, max + 1);
    }
    printf("%d\n", ans);
    return 0;
}

C.Chess

一个車 $k$ 会把它所在的行和列除自己以外的格子都异或上它的权值。其实只要把行和列各异或一次,交点也就是点 $k$ 会被异或两次,相当于没异或。
这道题的核心在于想明白可以把一个点 $(x, y)$ 的权值异或和用该点所在的行的异或和和列的异或和求出来。
设 $a_x$ 表示第 $x$ 行的异或和, $b_y$ 表示 第 $y$ 列的异或和。
那么
$$ans = \sum_{i=1}^{n} \sum_{j=1}^{n}a_i \neq b_j$$
再开两个 $map$ 像桶记录一下所有异或和的行和列有多少个。
那么每次移动一个棋子,要修改的东西其实很少,无非就是行和列的异或值和桶里的元素数量。答案的偏差值也可以很快地算出来。

代码

#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <algorithm>
int n, k, q;
long long ans = 0;
std::map<int, int> xorC, xorR, cntC, cntR;
std::map<std::pair<int, int>, int> val;
inline void addC(int r, int c) {
    int tmp = xorC[r];
    cntC[tmp] += c;
    ans += 1ll * c * (n - cntR[tmp]);
}
inline void addR(int r, int c) {
    int tmp = xorR[r];
    cntR[tmp] += c;
    ans += 1ll * c * (n - cntC[tmp]);
}
inline void update(int x, int y, int z) {
    addC(x, -1);
    xorC[x] ^= z;
    addC(x, 1);
    addR(y, -1);
    xorR[y] ^= z;
    addR(y, 1);
}
inline void read(int &x) {
    int ret = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ret = ret * 10 + ch - '0';
        ch = getchar();
    }
    x = ret * flag;
}
int main(int argc, char *argv[]) {
    read(n), read(k), read(q);
    int x, y, w;
    cntC[0] = cntR[0] = n;
    for (int i = 1; i <= k; i++) {
        read(x), read(y), read(w);
        val[std::make_pair(x, y)] = w;
        update(x, y, w);
    }
    int x1, y1, x2, y2;
    for (int i = 1; i <= q; i++) {
        read(x1), read(y1), read(x2), read(y2);
        int tmp = val[std::make_pair(x1, y1)];
        update(x1, y1, tmp);
        update(x2, y2, tmp);
        val[std::make_pair(x2, y2)] = tmp;
        printf("%lld\n", ans);
    }
    return 0;
}

D.Seq

我记得我好像在 $\text{LYOI}$ 的模拟赛做过原题,但是居然考场上想不起来了。实际上还是很简单的。。。
连续子序列的话,那就先求个前缀和吧。
$sum_i$ 表示 $1$ 到 $i$ 的前缀和。
一个区间对答案有贡献的话,必然有
$$(r-l+1) \times p \leq sum_r – sum_{l-1}$$
这个式子没什么卵用,我们分类变形一下。
$$sum_{l-1}-(l-1) \times p \leq sum_r-r \times p$$
这个式子的两边都只与一个量有关,我们不妨设 $s_i=sum_i-i \times p$
那上面的式子就是
$$s_{l-1} \leq s_r$$
那就是求序列 $s$ 的逆序对个数,树状数组归并排序都可以做。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <climits>
#include <queue>
typedef long long ll;
const int MAXN = 1e6 + 7;
ll sum[MAXN], s[MAXN];
ll n, t[MAXN], end, a[MAXN], p;
ll ans;
inline int lowbit(int x) {
    return x & (-x);
}
void add(int x, ll delta) {
    for (int i = x; i <= end; i += lowbit(i)) {
        t[i] += delta;
    }
}
ll query(int x) {
    ll ret = 0;
    for (int i = x; i; i -= lowbit(i)) {
        ret += t[i];
    }
    return ret;
}
int main(int argc,char *argv[]) {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
    }
    scanf("%lld", &p);
    for (int i = 1; i <= n; i++) {
        a[i] -= p;
        sum[i] = sum[i - 1] + a[i];
        s[i] = sum[i];
        if (sum[i] >= 0) ans++;
    }
    s[n + 1] = 0;
    std::sort(s + 1, s + n + 2);
    end = std::unique(s + 1, s + n + 2) - s - 1;
    for (int i = 1; i <= n; i++) {
        sum[i] = std::lower_bound(s + 1, s + end + 1, sum[i]) - s;
    }
    for (int i = 1; i <= n; i++) {
        ans += query(sum[i]);
        add(sum[i], 1);
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注