2020.1.15考试总结

T1
01分数规划
很明显我们需要的区间最大值和最小值在区间两端，因为有L的限制，所以我们可以先做一遍长度为L的滑动窗口。
问题判定的转化,设我们二分的值是v：
\(\displaystyle \frac{A[r]-A[l]}{r-l+k} > v\)
\(\displaystyle (A[r]-rv)-(A[l]-lv) > kv\)
再用一个单调队列维护一下就好了。

#include <iostream>
#include <cstdio>
#define LL long long
#define DB double
using namespace std;
int T, n, k, L, R, head1 = 1, tail1, head2 = 1, tail2;
DB ans;
const int N = 50010;
const DB eps = 1e-7;
int a[N], q1[N], q2[N]; /*小 大*/
DB b[N];
inline int read() 
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int dd(DB mid) 
{
    head1 = head2 = 1; tail1 = tail2 = 0;
    for (int i = L; i <= n; ++i) 
    {
        while (head1 <= tail1 && b[i - L + 1] <= b[q1[tail1]])--tail1;
        q1[++tail1] = i - L + 1;
        while (head1 <= tail1 && i - q1[head1] + 1 > R)++head1;
        if (b[i] - b[q1[head1]] >= mid * k)return 1;
    }
    return 0;
}
int check(DB mid) 
{
    for (int i = 1; i <= n; ++i)b[i] = a[i] - mid * i;    if (dd(mid))return 1;
    for (int i = 1; i <= n; ++i)b[i] = a[n - i + 1] - mid * i; if (dd(mid))return 1;
    return 0;
}
void solve() 
{
    DB l, r, mid;
    head1 = head2 = 1; tail1 = tail2 = 0;
    for (int i = 1; i <= n; ++i) 
    {
        while (head1 <= tail1 && a[i] <= a[q1[tail1]])--tail1;
        while (head2 <= tail2 && a[i] >= a[q2[tail2]])--tail2;
        q1[++tail1] = i; q2[++tail2] = i;
        while (head1 <= tail1 && i - q1[head1] + 1 > L)++head1;
        while (head2 <= tail2 && i - q2[head2] + 1 > L)++head2;
        ans = max(ans, (DB)(a[q2[head2]] - a[q1[head1]]) / (L - 1 + k));
    }
    l = 0; r = 1000;
    while (r - l > eps) 
    {
        mid = (l + r) / 2;
        if (check(mid))l = mid;
        else r = mid;
    }
    printf("%.4f\n", max(ans, mid));
}
int main() 
{
    cin >> T;
    while (T--) 
    {
        n = read(); k = read(); L = read(); R = read(); ans = 0;
        for (int i = 1; i <= n; ++i)a[i] = read();
        solve();
    }
    fclose(stdin); fclose(stdout);
    return 0;
}

T2 给定一个长度为 \(n\) 的序列 \(a_i\), 求有多少个区间的和 \(\%k\) 等于区间的最小值。(\(n \le 2 \times 10^5\))

看到这类题首先想到每一个值的贡献，确定左右边界就用单调栈。
然后左右边界那边小就枚举哪一边，类似于启发式合并。
时间复杂度\(O(nlog^2n)\)
关于边界的细节处理比较复杂，需要注意。

#include <iostream>
#include <cstdio>
#define int long long
#define LL long long
using namespace std;
int n, k, ans, top, cnt;
const int N = 200010;
int a[N], zhan[N], l[N], r[N], s[N], root[N];
int sum[N * 100], lson[N * 100], rson[N * 100];
inline int read() 
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void change(int pre, int &k, int l, int r, int pos, int val) 
{
    if (!k)k = ++cnt; sum[k] = sum[pre] + val;
    if (l == r)return; int mid = (l + r) >> 1;
    if (pos <= mid)rson[k] = rson[pre], change(lson[pre], lson[k], l, mid, pos, val);
    else lson[k] = lson[pre], change(rson[pre], rson[k], mid + 1, r, pos, val);
}
int ask(int pre, int k, int l, int r, int pos) 
{
    if (l == r)return sum[k] - sum[pre];
    int mid = (l + r) >> 1;
    if (pos <= mid)return ask(lson[pre], lson[k], l, mid, pos);
    else return ask(rson[pre], rson[k], mid + 1, r, pos);
}
signed main() 
{
    cin >> n >> k;
    change(root[0], root[1], 0, k, 0, 1);
    for (int i = 2; i <= n + 1; ++i)a[i] = read(), s[i] = (a[i] + s[i - 1]) % k, change(root[i - 1], root[i], 0, k, s[i], 1);
    for (int i = 2; i <= n + 1; ++i) 
    {
        while (top && a[i] <= a[zhan[top]])r[zhan[top--]] = i;
        l[i] = zhan[top]; zhan[++top] = i;
    }
    for (int i = 2; i <= n + 1; ++i) 
    {
        if (!l[i])l[i] = 1;
        if (!r[i])r[i] = n + 2;
    }
    for (int i = 2; i <= n + 1; ++i) 
    {
        if (a[i] >= k)continue;
        if (i - l[i] < r[i] - i)for (int j = l[i] + 1; j <= i; ++j)ans += ask(root[i - 1], root[r[i] - 1], 0, k, (s[j - 1] + a[i]) % k);
        else for (int j = i; j <= r[i] - 1; ++j)ans += ask(root[l[i] - 1], root[i - 1], 0, k, (s[j] - a[i] + k) % k);
    }
    cout << ans;
    fclose(stdin); fclose(stdout);
    return 0;
}

T3 给定你n,m,求\(\displaystyle \sum_{i=1}^ni^mm^i\) (\(mod\) \(10^9+7\)) (\(n \le 10^9 ,m \le 1000\))

老师说是套路题...
我们设\(\displaystyle f(j)=\sum_{i=1}^ni^jm^i\)
那么
\[ \begin{aligned} \displaystyle (m-1)f(j)=&\sum_{i=1}^n i^j m^{i+1} - \sum_{i=1}^ni^jm^i\\ \displaystyle (m-1)f(j)=&\sum_{i=2}^{n+1} (i-1)^j m^{i} - \sum_{i=1}^{n}i^{j}m^{i}\\ \displaystyle (m-1)f(j)=&\sum_{i=1}^{n} (i-1)^j m^{i} - \sum_{i=1}^{n}i^{j}m^{i}+n^{j}m^{n+1}\\ \displaystyle (m-1)f(j)=&\sum_{i=1}^{n}((i-1)^j - i^{j})m^{i}+n^{j}m^{n+1}\\ \displaystyle (m-1)f(j)=&\sum_{i=1}^{n}(\sum_{k=0}^{j}C_{j}^{k}i^{k}(-1)^{j-k}-i^j)m^{i}+n^{j}m^{n+1}\\ \displaystyle (m-1)f(j)=&\sum_{i=1}^{n}(\sum_{k=0}^{j-1}C_{j}^{k}i^{k}(-1)^{j-k})m^{i}+n^{j}m^{n+1}\\ \displaystyle (m-1)f(j)=&\sum_{k=0}^{j-1}C_{j}^{k}(-1)^{j-k}(\sum_{i=1}^{n}i^{k}m^{i})+n^{j}m^{n+1}\\ \displaystyle (m-1)f(j)=&\sum_{k=0}^{j-1}C_{j}^{k}(-1)^{j-k}f(k)+n^{j}m^{n+1}\\ \displaystyle f(j)=&\frac{\displaystyle \sum_{k=0}^{j-1}C_{j}^{k}(-1)^{j-k}f(k)+n^{j}m^{n+1}}{m-1}\\ \end{aligned} \]
然后就是一个和\(n\)无关的\(O(m^2)\)的递推式了.

注意\(f(0)\)需要单独求。

#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
#define LL long long
using namespace std;
int n, m;
const int mod = 1e9 + 7, N = 1005;
LL ans;
LL jc[N], inv[N], F[1005];
inline int read() 
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
LL ksm(LL a, LL b, LL mod) 
{
    LL res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)res = res * a % mod;
    return res;
}
LL C(int n, int m) {return jc[n] * inv[m] % mod * inv[n - m] % mod;}
LL f(int k) 
{
    if (F[k] != -1)return F[k];
    LL res = 0;
    for (int j = 0; j <= k - 1; ++j)(res += ((k - j) & 1 ? -1 : 1) * C(k, j) % mod * f(j)) %= mod;
    (res += ksm(n, k, mod) * ksm(m, n + 1, mod) % mod) %= mod;
    return F[k] = res * ksm(m - 1, mod - 2, mod) % mod;
}
signed main() 
{
    memset(F, -1, sizeof(F));
    cin >> n >> m;
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for (int i = 2; i <= 1000; ++i)jc[i] = jc[i - 1] * i % mod;
    inv[1000] = ksm(jc[1000], mod - 2, mod);
    for (int i = 999; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;
    F[0] = (ksm(m, n + 1, mod) - m) * ksm(m - 1, mod - 2, mod) % mod;
    cout << (f(m) % mod + mod) % mod;
    fclose(stdin); fclose(stdout);
    return 0;
}