T1 COCI2019 Quiz

Description

Solution

考虑暴力思路：设 f[i][j] 表示取了 $i$ 次，最后一次取到 $j$ 的最大值。转移方程如下：

f_{i,j} = \max_{k=0}^{j-1}\{f_{i-1,k}+\frac{j-k}{n-k}\}

然后内层可以用斜率优化，并且有决策单调性，可以做到 $\mathcal{O}(n^2)$ 。
接下来我们发现，进一步地优化必然涉及本质上的改变——因为状态数就是 $\mathcal{O}(n^2)$ 了。

Kewth ：这种「拆分最优化」的题目基本上都是凸函数。

考虑带权二分。因为我们需要控制的是段数，所以我们每新增一段，就增加一个新的费用 delta 。由于是要求最大值，故当拆分数大于 $k$ 时就调小 delta ，否则调大 delta。

剩下的就是些带权二分的细节了。最后的时候要 check(L) ，以及 check 内应该是 > 而非 >= 。

Code

#define ldb long double 
const int N = 1e5 + 5;
using namespace std;
int n, k;
int q[N], cnt[N];
ldb f[N], X[N], Y[N];
inline bool cmp(ldb a, ldb b, ldb c, ldb d){
    return a * d <= b * c;
}
bool check(ldb delta){
    int l = 1, r = 1;
    X[0] = n;
    for(int j = 1; j <= n; ++j)
        X[j] = n - j, cnt[j] = 0;
    for(int j = 1; j <= n; ++j){
        while(l < r and cmp(Y[q[l]] - Y[q[l + 1]], X[q[l]] - X[q[l + 1]], Y[q[l + 1]] + j, X[q[l + 1]]))    // k1 < k2
            ++l; 
        f[j] = f[q[l]] + 1.0 * (j - q[l]) / (n - q[l]) + delta;
        Y[j] = (n - j) * f[j] - j;
        cnt[j] = cnt[q[l]] + 1;
        while(l < r and cmp(Y[q[r]] - Y[j], X[q[r]] - X[j], Y[q[r - 1]] - Y[q[r]], X[q[r - 1]] - X[q[r]])) --r;
        q[++r] = j;
    }
    return cnt[n] > k;
}
const ldb eps = 1e-15;
int main(){

    cin >> n >> k;
    ldb L = -1e3, R = 0, ans = 0.0;
    while (R - L > eps){
        ldb mid = (L + R) * 0.5;
        if(check(mid)) R = mid;
        else L = mid;
    }
    check(L); ans = f[n] - cnt[n] * L;
    printf("%.9Lf\n", ans);
    return 0;
}

T2 JSOI2011 柠檬

Description

题面挺长那就放个链接吧

Solution

~~一道题学两个算法针不戳~~
首先考虑一个关键性质：每次转移一定是从相同颜色处的前一位转移过来。
可以这么想：这次划分当前颜色必然有贡献。可以根据「不限制划分次数」这一点感性理解。
设 f[i] 表示前 $i$ 个贝壳的最大值， $a_i$ 是第 $i$ 个贝壳的颜色， $c_i$ 是前 $i$ 个贝壳中颜色为 $a_i$ 的贝壳的个数，那么有

f_i = \max_{a_i=a_j}\{f_{j-1}+a_i(c_i-c_j+1)^2\}

里面的式子打开就是斜率优化的形式（注意 $a_i=a_j$ 所以可以任意换）：

f_{j-1}+a_j(c_j-1)^2=2a_jc_jc_i+f_i-a_i(c_i^2+2c_i)

可以发现 $X_j,Y_j,K_i$ 都是递增的。而我们的要求是截距最大。
画画图可以发现，应该是用「栈」来维护上凸壳。

也可以使用二分决策栈来简化思维难度。假设栈顶为 $p$ ，弹掉栈顶后的栈顶为 $q$ ，那么 $q$ 比 $p$ 优秀一定是在某个时间以后。我们可以二分这个时间，并且与 $q$ 什么时候比新增元素更优秀的时间判断 $p$ 是否弹掉。

Code

const int N = 1e5 + 5;
using namespace std;
int n;
int s[N], buc[N], pre[N], cnt[N];
ll f[N], X[N], Y[N];
vector<int>st[N];
inline bool cmp(ll a, ll b, ll c, ll d){
    return a * d <= b * c;
}
int main(){

    r(n);
    for(int i = 1; i <= n; ++i) r(s[i]);
    for(int i = 1; i <= n; ++i)
        pre[i] = buc[s[i]], buc[s[i]] = i, cnt[i] = cnt[pre[i]] + 1;
    for(int i = 1; i <= n; ++i)
        X[i] = 2ll * s[i] * cnt[i]; 
    for(int i = 1; i <= n; ++i){
        int c = s[i];
        f[i] = f[i - 1] + s[i];
#define p st[c].back()
#define q st[c][st[c].size() - 2]
        while(st[c].size() >= 2 and cmp(Y[p] - Y[q], X[p] - X[q], cnt[i], 1)) st[c].pop_back();
        if(st[c].size()){
            int k = p;
            f[i] = max(f[i], f[k - 1] + 1ll * s[i] * (cnt[i] - cnt[k] + 1) * (cnt[i] - cnt[k] + 1));
        }
        Y[i] = 1ll * s[i] * (cnt[i] - 1) * (cnt[i] - 1) + f[i - 1];
        while(st[c].size() >= 2 and cmp(Y[p] - Y[q], X[p] - X[q], Y[i] - Y[p], X[i] - X[p])) st[c].pop_back();
        st[c].push_back(i);
    }
    w(f[n]);
    return 0;
}

T3 CF1096G Lucky Tickets

Description

题面挺短但是讲不清楚

Solution

令 $F(x)$ 是数码的 OGF。d[i] 表示第 $i$ 个数是否出现。

F(x) = \sum_{0}^{9}d_ix^{i}

要求的最后背包的 OGF 就是 $G(x)=F^{\frac{n}{2}}(x)$ 。~~直接多项式快速幂淦就完了~~
可以用差值的方式。因为 DFT 求出来的最后事实上就是在特定步长下的 $G(g^0),G(g^1),\cdots$ ，然后 IDFT 回去就可以得到原多项式。本题中，我们 $\mathcal{O}(nk)$ 暴力求出来 $G(g_0),G(g_1),\cdots$ 的值，再插值回去即可。
最后的答案就是

\sum_{i=0}G^2_i

Code

const int N = 2e6 + 5, mod = 998244353, G = 3;
using namespace std;
int n, k;
int h[10], f[N], rev[N];
int Q(long long b, int t){
    long long ret = 1;
    for(int i = 1; i <= t; i <<= 1, b = b * b % mod)
        if(i & t) ret = ret * b % mod;
    return ret;
}
void NTT(int *a, int len){
    for(int i = 0; i < len; ++i)
        if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int i = 1; i < len; i <<= 1){
        int wn = Q(G, (mod - 1)/(i << 1));
        for(int j = 0; j < len; j += (i << 1)){
            int w = 1, t1, t2;
            for(int k = 0; k < i; ++k, w = 1ll * w * wn % mod)
                t1 = a[j + k], t2 = 1ll * w * a[i + j + k] % mod,
                a[j + k] = (t1 + t2) % mod, a[i + j + k] = (t1 + mod - t2) % mod; 
        }
    }
    reverse(a + 1, a + len);
    int inv = Q(len, mod - 2);
    for(int i = 0; i < len; ++i)
        a[i] = 1ll * a[i] * inv % mod;
}
int main(){

    r(n, k);
    for(int i = 1, x; i <= k; ++i)
        r(x), h[x] = 1;
    int len = 1, cnt = 0;
    for(int l = 9 * n / 2; len <= l; len <<= 1, ++cnt);
    for(int i = 0; i < len; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
    int v = 1, wn = Q(G, (mod - 1) / len);   // 注意要在特定步长下
    for(int i = 0; i < len; ++i){
        for(int j = 0; j <= 9; ++j)
            if(h[j]) (f[i] += Q(v, j)) %= mod;
        f[i] = Q(f[i], n / 2);
        v = 1ll * v * wn % mod;
    }
    NTT(f, len);
    int ans = 0; 
    for(int i = 0; i < len; ++i)
        (ans += 1ll * f[i] * f[i] % mod) %= mod;
    w(ans);
    return 0;
}

Analysis

技不如人甘拜下风
学习了带权二分栈实现斜优插值的灵活运用海星😙

Quiz 0127 summary

T1 COCI2019 Quiz

Description

Solution

Code

T2 JSOI2011 柠檬

Description

Solution

Code

T3 CF1096G Lucky Tickets

Description

Solution

Code

Analysis

感谢您的支持，我会继续努力的!