8-16暑期模拟赛

2022暑

---

期望得分：

T1	T2	T3	Sum
100	40	60	200

实际得分：

T1	T2	T3	Sum
0	0	50	50

T1 dostavljac

思维难度 $B$，代码难度 $B$

1.题意

给你一棵 $n$ 个节点的树，每个时刻你可以获得当前节点的权值，或者移动到相邻的节点上，每个节点不能重复获得权值，问从节点 $1$ 开始，经过 $m$ 时刻，最多能获得多少权值。

$1\leq n,m\leq 500,1\leq val_i\leq 10^6$。

考试的时候出问题最大的题吧。

2.解析

模型很显然，树形背包类的题，考虑最后结束的时候不会回到根，所以要记录回/不回根的状态 $f[x][i]$ 与 $g[x][i]$

$g[x][i]$ 很好求：

$$g[x][i] = \min_{j = 0}^{i - 2}{(g[y][j] + g[x][i - j - 2])},\,\,y\in son(x)$$

但是考场上求 $f[x][i]$ 的时候脑子晕掉了，考虑钦定一个儿子不回来后，一直在优化剩下儿子回来的求和柿子。

最后想到一个，预处理出前缀的背包以及后缀的背包，然后把两个背包合并的做法，感觉好像也是对的，但是十分复杂。

正确的做法应该是直接讨论当前儿子是否回来：

$$f[x][i] = \min_{j = 0} ^ {i - 2}{(g[y][j] + f[x][i - j - 2])}, \,\, y \in son(x)$$

$$f[x][i] = \min_{j = 0} ^ {i - 2}{(f[y][j] + g[x][i - j - 1])}, \,\, y \in son(x)$$

边界：

$g[x][0] = f[x][0] = 0$
$g[x][1] = f[x][1] = a[x]$

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 505;
int n, m;
int a[maxn];
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len;
int f[maxn][maxn], g[maxn][maxn];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline void Search(int x, int fa) {
    f[x][0] = g[x][0] = 0;
    f[x][1] = g[x][1] = a[x];
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Search(y, x);
        for(register int j = m; j >= 0; --j)
            for(register int k = m - j; k >= 0; --k) {
                if(j + k + 2 <= m) g[x][j + k + 2] = max(g[x][j + k + 2], g[y][k] + g[x][j]), f[x][j + k + 2] = max(f[x][j + k + 2], g[y][k] + f[x][j]);
                if(j + k + 1 <= m) f[x][j + k + 1] = max(f[x][j + k + 1], f[y][k] + g[x][j]);
            }
    }
}
int main() {
//  freopen("dostavljac.in", "r", stdin);
//  freopen("dostavljac.out", "w", stdout);
    n = read(), m = read();
    for(register int i = 1; i <= n; ++i) a[i] = read();
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u);
    }
    Search(1, 0);
    printf("%d\n", f[1][m]);
    return 0;
}

3.总结

感觉还是树形背包做的不够到位吧。

T2 range

思维难度：$A^{-}$，代码难度：$B$

1.题意

求 $\bigoplus_{l=1}^{n-k+1}(\prod_{i=l}^{l+k-1} a_i \bmod p)$，其中 $a_1=A,a_i=a_{i-1}\times B+C \bmod D$。

$1\leq k\leq n\leq 2\times 10^7,1\leq A,B,C<D\leq 10^9,1\leq p\leq 10^9$，不保证 $p$ 为质数。

2.解析

后面两题都是那种点子题，奇奇怪怪的。

麻烦的地方在于不能求逆元，所以只能合并区间。

考虑类似分块的做法，把每 $k$ 个当成一块，然后把前后两个块的后缀与前缀拼一下就能得到答案。

经典想到了就水题，但是不知道为啥就是想不到。

//The Code Is From Dawn
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e7 + 5;
int n, k, P;
int A, B, C, D;
int S[maxn], Pre[maxn],  Suf[maxn];
int main() {
//    freopen("range.in", "r", stdin);
//    freopen("range.out", "w", stdout);
    n = read(), k = read(), P = read();
    A = read(), B = read(), C = read(), D = read();
    S[0] = A;
    for(register int i = 1; i < n; ++i) S[i] = (1ll * S[i - 1] * B + C) % D;
    for(register int i = 0; i < n; ++i)
        if(i % k) Pre[i] = 1ll * Pre[i - 1] * S[i] % P;
        else Pre[i] = S[i] % P;
    for(register int i = n - 1; i >= 0; --i)
        if(i % k != k - 1) Suf[i] = 1ll * Suf[i + 1] * S[i] % P;
        else Suf[i] = S[i] % P;
    int Answer = 0;
    for(register int i = 0; i + k - 1 < n; ++i)
        if(i % k) Answer ^= 1ll * Suf[i] * Pre[i + k - 1] % P;
        else Answer ^= Suf[i];
    printf("%d\n", Answer);
    return 0;
}

T3 random

思维难度：$A$，代码难度：$A^-$

1.题意

对于一个长度为 $r$ 的数组 $s$，定义其特征值为 $\max(\underset{1\leq i<j\leq r}{\min}|s_i-s_j|,r)$。给你一个长度为 $n$ 的数组 $a$，求其所有子串的特征值的最小值。

$1\leq n\leq 10^6,1\leq a_i\leq 10^9$。

2.解析

考虑当区间的长度 $r$ 变长，那么差的绝对值一定变小。

考虑双指针，如果当前的 $|s_i - s_j|$ 小于 $r$ ，那么把左端点往后移，否则把右端点往后移。

考虑怎么维护 $|s_i - s_j|$，开个 $multiset$，答案必然在相邻的两个作差。

所以每次维护这些差，删除和插入都把他左右两边的值修改一下。

这维护属实点子，新奇。

//The Code Is From Dawn
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int s=0,f=0;
    char ch=getchar();
    while(!isdigit(ch)){
        f|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return f?-s:s;
}
const int maxn = 1e6 + 5, INF = 1e9 + 7;
int n;
int a[maxn];
multiset <int> S, Ans;
inline void Insert(int x) {
    Ans.erase(Ans.lower_bound(*(S.lower_bound(x))-*(--S.lower_bound(x))));
    Ans.insert(*S.lower_bound(x)-x);
    Ans.insert(x-*(--S.lower_bound(x)));
    S.insert(x);
}
inline void Erase(int x) {
    S.erase(S.lower_bound(x));    
    Ans.erase(Ans.lower_bound(*S.lower_bound(x)-x));
    Ans.erase(Ans.lower_bound(x-*(--S.lower_bound(x))));
    Ans.insert(*S.lower_bound(x)-*(--S.lower_bound(x)));
}
inline void Work() {
    int Answer = INF, l = 1, r = 2;
    while(l <= n && r <= n) {
        if(r - l + 1 >= 2) Answer = min(Answer, max(*Ans.begin(), r - l + 1));
        if(*Ans.begin() > (r - l + 1) || r - l + 1 < 2) Insert(a[++r]);
        else Erase(a[(++l) - 1]);
    }
    printf("%lld\n", Answer);
}
signed main() {
//  freopen("random.in", "r", stdin);
//  freopen("random.out", "w", stdout);
    n = read();
    for(register int i=1;i<=n;i++) a[i] = read();
    S.insert(INT_MAX), S.insert(-INT_MAX), Ans.insert(2ll*INT_MAX);
    Insert(a[1]), Insert(a[2]);
    Work();
    return 0;
}

3.总结

单调性不一定二分，有时候双指针也很好用。

对于后两题这种点子题，嗯多打CF（