2022-10-10总结

猫

CF311B

首先猫在哪个位置是没有影响的，重要的的是猫开始等的时间。

我们可以让每只猫的 $t$ 减去它到起点的距离，也就是人最晚的可以使这只猫不等待的出发时间。

我们将这个时间记为数组 $a$，很明显正好接到 $a$ 大的猫也可以接到 $a$ 小的猫(只是需要等待)，所以我们将 $a$ 从小到大排个序，就可以让每个人接到的猫在 $a$ 中是连续的一段，然后就可以 DP 了。

设 $f(i,j)$ 表示前 $i$ 个人接前 $j$ 只猫，且第 $i$ 个人正好接到第 $j$ 只猫的最小等待时间。

DP 方程就比较好列了:

$$f(i,j) = \min_{0 \le k < j} \left\{ f(i-1,k) + \sum_{s=k+1}^{j}(a_j-a_k) \right\}$$

前缀和一下，式子就变成了:

$$f(i,j) = \min_{0 \le k < j} \left\{ f(i-1,k) + (j-k)a_j - sum_k \right\}$$

直接 DP 是 $O(n^2)$ 的，但是这是个取 $\min$ 的式子，而且只有一个 $j,k$ 相关的乘积项，可以斜率优化一下。

先把式子拆了:

$$f(i,j) = f(i-1,k) + (j-k)a_j - sum_k \\ f(i,j) = f(i-1,k) + ja_j - ka_j - sum_k \\ f(i-1,k) + sum_k = a_j*k + f(i,j) - ja_j$$

可以将每个 $k$ 看作坐标系上 $(k, f(i-1,k)+sum_k)$ 的一个点，因为 $a_j$ 是递增的，要求解的是 $f(i,j)$ 的最小值，也就是用一个斜率不断增大的直线从下往上平移，找到第一个点即为最优决策点，所以维护一个下凸包就行了。

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

typedef long long ll;
const int M = 1e5+10;
const int N = 1e5+10;
const int P = 1005;

int n, m, p;
ll d[N];
ll f[2][M];
ll sum[M], a[M];

int i, j;
int q[N], l, r;
ll X(int k) { return k; }
ll Y(int k) { return f[(i-1)&1][k]+sum[k]; }
double slope(int a, int b){ return double(Y(b)-Y(a))/(X(b)-X(a));}

int main()
{
    cin >> n >> m >> p;
    for(int i = 2; i <= n; i++)
    {
        cin >> d[i];
        d[i] += d[i-1];
    }
    for(int i = 1; i <= m; i++)
    {
        ll h, t; cin >> h >> t;
        a[i] = t-d[h];
    }
    
    sort(a+1, a+m+1);
    for(int i = 1; i <= m; i++)
        sum[i] = sum[i-1]+a[i];
    
    memset(f, 0x3f, sizeof(f));
    for(int j = 1; j <= m; j++)
        f[1][j] = a[j]*j - sum[j];
    
    for(i = 2; i <= p; i++)
    {
        q[l=r=1] = 0;
        for(j = 1; j <= m; j++)
        {
            while(l < r and slope(q[l], q[l+1]) < a[j]) l++;
            
            int k = q[l];
            f[i&1][j] = f[(i-1)&1][k] + a[j]*(j-k) - (sum[j]-sum[k]);
            
            while(l < r and slope(q[r-1], q[r]) >= slope(q[r-1], j)) r--;
            q[++r] = j;
        }
    }
    cout << f[p&1][m] << "\n";
}

Pairwise Modulo

CF1553F

考虑增量法，即从 $p_{k-1}$ 递推得到 $p_k$。

直接写递推式子:

$$p_k = p_{k-1} + \sum_{i=1}^k(a_i \bmod a_k) + \sum_{j=1}^k (a_k \bmod a_j)$$

取模无从下手，改成除法：

$$p_k = p_{k-1} + \sum_{i=1}^k \left( a_i - \lfloor \frac{a_i}{a_k} \rfloor a_k \right) + \sum_{j=1}^k \left( a_k - \lfloor \frac{a_k}{a_j} \rfloor a_j \right)$$

把求和拆开，求个前缀和:

$$p_k = p_{k-1} + sum_k - a_k\sum_{i=1}^k \lfloor \frac{a_i}{a_k} \rfloor + ka_k - \sum_{j=1}^k \lfloor \frac{a_k}{a_j} \rfloor a_j$$

其中第一个求和很好搞，因为题目保证 $a_i$ 互不相等，所以直接枚举倍数就是 $O(n \ln n)$ 的时间复杂度，可以用树状数组维护一个桶。

第二个求和的话直接搞不方便，考虑对于每个 $a_k$ 计算它对后面数的贡献，当 $a_s \in [ba_k, ba_k+a_k-1]$ 时，$a_k$ 会对这个 $a_s$ 造成 $ba_k$ 的贡献，所以还是枚举倍数然后区间加就行了，时间复杂度也是 $O(n \ln n)$。

可以用树状数组维护上面过程，总时间复杂度是 $n \ln n \log n$ 的。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
namespace Octane {
    // non terrae plus ultra
    #define OCTANE
    #define BUFFER_SIZE 100000
    #define ll long long 
    #define db double
    #define ldb long double
    char ibuf[BUFFER_SIZE], obuf[BUFFER_SIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
    #ifdef ONLINE_JUDGE
        #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,BUFFER_SIZE,stdin),p1==p2)?(EOF):(*p1++))
        #define putchar(x) ((p3==obuf+BUFFER_SIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif // fread in OJ, getchar in local

    #define isdigit(ch) (ch>47&&ch<58)
    #define isspace(ch) (ch<33&&ch!=EOF)
    
    const ll pow10[] = {
        (ll)1e0,  (ll)1e1,  (ll)1e2,  (ll)1e3,  (ll)1e4,  (ll)1e5, 
        (ll)1e6,  (ll)1e7,  (ll)1e8,  (ll)1e9,  (ll)1e10, (ll)1e11,
        (ll)1e12, (ll)1e13, (ll)1e14, (ll)1e15, (ll)1e16, (ll)1e17, (ll)1e18,
    };
    
    struct Octane_t {
        ~Octane_t() {
            fwrite(obuf, p3-obuf, 1, stdout);
        }
        bool flag = false;
        operator bool() {
            return flag;
        }
    }io;
    
    template<typename T> inline T read() {
        T s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return 0;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (db)flt/pow10[cnt];
        }
        return s *= w;
    }
    template<typename T> inline bool read(T &s) {
        s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return false;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (db)flt/pow10[cnt];
        }
        return s *= w, true;
    }
    inline bool read(char &s) {
        while(s = getchar(), isspace(s));
        return s != EOF;
    }
    inline bool read(char *s) {
        char ch;
        while(ch=getchar(), isspace(ch));
        if(ch == EOF) return false;
        while(!isspace(ch))
            *s++ = ch, ch=getchar();
        *s = '\000';
        return true;
    } 
    template<typename T> void print(T x) {
        static int t[20]; int top = 0;
        if(x < 0) putchar('-'), x = -x;
        do { t[++top] = x%10; x /= 10; } while(x);
        while(top) putchar(t[top--]+48);
    }
    struct empty_type{}; int pcs = 8;
    empty_type setpcs(int cnt) {
        return pcs = cnt, empty_type();
    }
    inline void print(empty_type x){}
    inline void print(double x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow10[pcs+1];
        print((ll)(x)); x -= (ll)(x);
        if(pcs != 0) putchar('.');
        for(int i = 1; i <= pcs; i++)
        x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(float x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow10[pcs+1];
        print((ll)(x)); x -= (ll)(x);
        if(pcs != 0) putchar('.');
        for(int i = 1; i <= pcs; i++)
        x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(char x) {
        putchar(x);
    }
    inline void print(char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    inline void print(const char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    
    // support for string
    #ifdef _GLIBCXX_STRING
    inline bool read(std::string& s) {
        s = ""; char ch;
        while(ch=getchar(), isspace(ch));
        if(ch == EOF) return false;
        while(!isspace(ch))
            s += ch, ch = getchar();
        return true;
    }
    inline void print(std::string x) {
        for(string::iterator i = x.begin(); i != x.end(); i++)
            putchar(*i);
    }
    inline bool getline(Octane_t &io, string s) {
            s = ""; char ch = getchar();
            if(ch == EOF) return false;
            while(ch != '\n' and ch != EOF)
                s += ch, ch = getchar();
            return true;
        }
    #endif 
    
    // support for initializer_list
    #if __cplusplus >= 201103L 
    template<typename T, typename... T1>
    inline int read(T& a, T1& ...other) {
        return read(a)+read(other...);
    }
    template<typename T, typename... T1>
    inline void print(T a, T1... other) {
        print(a); print(other...);
    }
    #endif 
    
    //  give up iostream
    template<typename T>
    Octane_t& operator >> (Octane_t &io, T &b) {
        return io.flag=read(b), io;
    }
    Octane_t& operator >> (Octane_t &io, char *b) {
        return io.flag=read(b), io;
    }
    template<typename T>
    Octane_t& operator << (Octane_t &io, T b) {
        return print(b), io;
    }

    #define cout io
    #define cin io
    #define endl '\n'
    #undef ll
    #undef db
    #undef ldb
    #undef BUFFER_SIZE
}
using namespace Octane;

typedef long long ll;
const int N = 3e5+10;
const int B = 550;

struct bit_array {
    ll a[N], lim;
    #define lowbit(x) (x&-x)
    void modify(int i, int val)
    {
        for(i += 2; i <= lim; i += lowbit(i))
            a[i] += val;
    }
    ll query(int i)
    {
        ll ans = 0;
        for(i += 2; i >= 1; i -= lowbit(i))
            ans += a[i];
        return ans;
    }
} bit1, bit2;

int n; ll maxv;
ll a[N], sum[N], p[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i-1]+a[i];
        maxv = max(maxv, a[i]);
    }
    bit1.lim = bit2.lim = maxv+2;
    for(int k = 1; k <= n; k++)
    {
        bit1.modify(a[k], 1);
        for(int i = a[k]; i <= maxv; i += a[k])
            bit2.modify(i, a[k]);
        
        p[k] = p[k-1] + k*a[k] + sum[k];
        
        for(int i = a[k]; i <= maxv; i += a[k])
        {
            int r = min(i+a[k]-1, maxv);
            p[k] -= a[k]*(i/a[k])*(bit1.query(r) - bit1.query(i-1));
        }
        p[k] -= bit2.query(a[k]);
        
        cout << p[k] << " ";
    }
}

Decinc Dividing

CF1693D

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

typedef long long ll;
const int N = 2e5+10;

int n;
int p[N];
int ans[N];
int f[N][2];

void dp(int k);
void solve(int l, int r);

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> p[i];
    dp(1); dp(n);
    solve(1, n);
    ll sum = 0;
    for(int i = 1; i <= n; i++)
        sum += ans[i];
    sum -= (ll)n*(n-1)/2;
    cout << sum << "\n";
}

void solve(int l, int r)
{
    if(l+1 >= r) return void();
    if(ans[l] == ans[r])
    {
        for(int i = l; i <= r; i++)
            ans[i] = ans[l];
        return void();
    }
    int mid = (l+r)>>1;
    dp(mid);
    solve(l, mid);
    solve(mid, r);
}
void dp(int k)
{
    f[k][0] = n+1;
    f[k][1] = 0;
    for(int i = k+1; i <= n; i++)
    {
        f[i][0] = 0, f[i][1] = n+1;
        if(p[i-1] < p[i]) f[i][0] = f[i-1][0];
        if(p[i-1] > p[i]) f[i][1] = f[i-1][1];
        if(f[i-1][1] < p[i]) f[i][0] = max(f[i][0], p[i-1]);
        if(f[i-1][0] > p[i]) f[i][1] = min(f[i][1], p[i-1]);
        if(f[i][0] == 0 and f[i][1] == n+1)
        {
            ans[k] = i-1;
            return void();
        }
    }
    ans[k] = n;
}