省选前作业-解题报告

i207M · 2019-02-25 18:53:58 · 个人记录

2.25

NOI2017泳池

常系数线性递推。见另一篇博客。

UOJ372 滑稽树下做游戏

好仙啊，不会。

大致口胡一下，我们发现，如果算出g(t)表示答案\le t的概率，且g是关于t的多项式，那么我们积分一下就可以了。

考虑DP：h(G,y,t)表示对于图G，每个变量的取值是[0,y]，最后答案\le t即可。这可以表示为关于y和t的n次齐次多项式。定义域：\frac{t}{2} \leq y \leq \min(1,t)，因为其他范围的y没有意义。

1.如果所有点权值\le t/2

2.至少有1个大于。我们枚举点i是最大值，则有：

h(G,y,t) = (\frac{t}{2})^n + \sum_{i=1}^n \int_{\frac{t}{2}}^{y}h(G_i,w,t)(t-w)^c\text{d}w

c是点i的度数。

这样直接做是O(2^nn^3)。但是我们发现，如果两个图不联通，那么它们之间没有任何关系，所以我们可以直接拆成每个联通子图做。

CF848E

woc，调细节调了半天...差点都要弃疗了。

这道题的DP式子细节很多，不过序列上的DP式子是能推出来的。但是在统计答案的时候不会了，题解的做法是分有一个|和多个|分别考虑；对于多个|的情况我们枚举前两个|的位置，计算答案，由于环可以旋转，于是需要乘上长度。

列出式子之后可以cdq分治FFT或者多项式求逆，不过这道题是一个二元一次方程组。

orz shadowice1984，硬推递推式：https://www.luogu.org/recordnew/show/16747411

UOJ 141 量子态的棋盘

神仙轮廓线DP...

从经过(i,j)的球数：

f_{i,j}=\lfloor \frac{f_{i,j-1}+[w_{i,j-1}=1]}{2} \rfloor + \lfloor \frac{f_{i-1,j}+[w_{i-1,j}=-1]}{2} \rfloor

我们发现，无法确定方向的球只有nm个，于是我们可以轮廓线DP，存从轮廓线过去多少点，然后枚举一下转移。

这道题其实不是插头DP，是状压m个数，表示从m条轮廓线出去的球数。我们同时还要状压ans。

SDOI储能表

数位DP。dp[i][2][2][2]

WF2012E BZOJ 3979

没想到是这样...随机化乱搞；或者发现答案小于等于6，于是O(n^5)枚举，否则返回6。

codeM B轮 #D

给定四个正整数a,b,c,k，回答是否存在一个正整数n，使得a*n在k进制表示下的各位的数值之和模b为c。

判定：\gcd(a,b,k-1)|c。容易发现这是必要条件，充分性也是可以证明的。

2.27

codechef Milestones

随机化。无可奈何。

codechef Knight Moving

codechef也喜欢玩心跳的吗...明明O(k^2)可以做的，非要k=15...

对A和B是否线性相关分类讨论：

线性无关：变换每个点的坐标，变成网格图经典DP

线性相关：在一维上跑拓扑排序（记搜）。

然而这道题有巨量的细节...我TM写了8k还是WA！就当嘴巴AC了吧。

codechef Product of Digits

见到10进制位的乘积，意识到质因数只有2357！

本来想到折半搜索，但是想的是10^{350}次方的...好傻。

我们先枚举2和3的指数，存起来，然后枚举c和d的指数，查表。

然后贪心的拼出这些数。

codechef Sine Partition Function

这题目也太毒瘤了吧...

其实也不难，不过不想写了。

枚举\sum k=N(k\ge 0)的好方法是DP：新加一个0，或者把最后一个数+1

我们同时维护sin和cos的和，就可以转移了。

codechef Reduce string

挖串DP，感觉很熟悉啊...但是还是不会。

还是区间DP，设f[l][r][k]表示区间[l,r]能否删除到Trie树上的点k。（第二维可以bitset优化）

转移有两种：

1.r没有删除：从f[l][r-1][*]添加一个字符过来

2.r删除了，枚举删除的后缀的长度，bitset或一下

最后做一个背包得到答案。

~~zz错误调很久~~

「THUPC2018」密码学第三次小作业 / Rsa

想了半天e1e2不互质怎么做...结果题目保证了互质...我傻了。

不过不互质也能做啊，甚至只给c1和e1也能做啊，毕竟题干都说了，难度只和质因数分解的复杂度有关，直接rho一下把N分解了不就行了。

「THUPC2018」赛艇 / Citing

~~当时的官方题解竟然是O(n^4/32)过1500...~~

其实就是我们把两个矩阵匹配，看有多少个位置匹配上。

当时想到拆成序列，然后FFT解决匹配，FFT的式子为：

C[n][m]=\sum B[i][j]\times A[i+n][j+m]

但是有问题：这样下标相加就可能越界，比如，矩阵大小2\times 2，即下标范围[0,1]，那么

B[0][1]\times A[0][2]\to C[0][1]

但是A[0][2]其实是A[1][0]！这样不就匹配错位了吗？

其实不是，我们统计答案的时候，只统计B在此处不会超出A的位置。这样，B[0][1]就必须是0，C[0][1]才会被我们使用。

「THUPC2018」蛋糕 / Cake

好题！可惜当时没有认真思考。

可以像ztb神仙一样手推式子，但是有更简单的方法。

我们枚举在哪一维顶着边界！

顶着边界只有2的系数，在内部有a-2的系数

要注意某一位长度=1的情况，这样每个块一定同时顶着这一维的上下边界。

const ull md=2148473648;
ull ans[10],a[4];
int siz[1<<4];
ull calc(int s)
{
    ull res=1;
    for(ri i=0; i<4; ++i)
    {
        if(a[i]==1) continue;
        if((s>>i)&1) (res*=2)%=md;
        else (res*=a[i]-2)%=md;
    }
    return res;
}
signed main()
{
    for(ri i=1; i<(1<<4); ++i) siz[i]=siz[i>>1]+(i&1);
    int T; in(T);
    while(T--)
    {
        clr(ans,9);
        for(ri i=0; i<4; ++i) in(a[i]);
        int ret=0,U=(1<<4)-1;
        for(ri i=0; i<4; ++i) if(a[i]==1) ret+=2,U^=1<<i;
        for(ri k=U;; k=(k-1)&U)
        {
            (ans[ret+siz[k]]+=calc(k))%=md;
            if(!k) break;
        }
        prt(ans,9);
    }
    return 0;
}

其实这道题可以出到K=2000

方式是DP：f[i][j]表示考虑前i维，有j维没有顶上下界。转移的话枚举下一维是否顶上下界即可。

「THUPC2018」淘米神的树 / Tommy

意会。

首先，问题转化为，超级根向a和b连边，在a-b环上枚举一条边，删除后变成树，求出树的拓扑序，把所有方案加起来就是答案。

~~然后到这里我就只会O(n^2)了。~~

首先，树的拓扑序为：

\frac{n!}{\prod size(i)}

而改变size的只有a-b链上的点。

如果我们把每个点独有的size在链上做一个前缀和，那么，若切掉c和c+1的边，方案数为：

\frac{\prod_{i=0}^n (S_i-x)}{S_c-x}

在x=S_c处的点值。

使用洛必达法则后多点求值即可。

注意，所有方案都算了两遍。

codechef Annual Parade

环和链的奇怪的限制？其实就是边权-点数×C！（显然一个点只会经过一次）

~~上面都想到了，就是没想到网络流...~~

转化为最小边权和路径覆盖，先默认不选择所有点（ans的初值为N\times C）。建出左右部点，找出增广路。当dis\ge C时停止。（增广一次的收益是dis-C）。存所有路径，每次询问二分。

3.2

POI2015 CZA

好题。但是讨论的情况有点多。

具体看另一篇博客吧。

CF724F

限制比较多，考虑树形DP。

先考虑有根树的情况：

我们如何不考虑顺序的枚举所有儿子？我们可以给DP加一维，做一些限制：f[i][j][k]表示大小为i的树，根节点儿子数为j，最大的子树大小不超过k的方案数。

转移有两种：有（有几个）/无大小为k的子树。

接下来的问题是，知道有根树的数量，如何求无根树的数量。我们可以对一棵树强制以重心为根。但是要减去重心有两个的情况（注意，这时候选择的两棵树不能重复，因为重复的树之前只被算了一遍）。

还有一种思想是，我们强制统计重心只有一个的树，然后加上重心有两个的树，这时候可以重复选。

    f[1][0][0]=1;
    for(ri i=1; i<=n; ++i) g[1][i]=1;
    for(ri i=2; i<=n; ++i)
    {
        for(ri j=1; j<=d; ++j)
            for(ri k=1; k<i; ++k)
            {
                int &r=f[i][j][k];
                r=f[i][j][k-1];
                for(ri h=1; h<=j&&h*k<i; ++h)
                    inc(r,mul(f[i-h*k][j-h][min(k-1,i-h*k-1)],g[k][h]));
            }
        for(ri j=1; j<=d; ++j) g[i][j]=C(f[i][d-1][i-1]+j-1,j);
    }
    int ans=f[n][d][(n-1)/2];
    if(~n&1) inc(ans,(LL)f[n/2][d-1][n/2-1]*(f[n/2][d-1][n/2-1]+1)/2%md);

第一种写法：

    int ans=f[n][d][n/2];
    if(~n&1) dec(ans,(LL)f[n/2][d-1][n/2-1]*(f[n/2][d-1][n/2-1]-1)/2%md);

CF815D Karen and Cards

真心不难，不知道谁说了句cdq分治然后在离正解就差一步的时候被带偏了。

其实这道题就是容斥一下，吉司机线段树+扫描线C即可（对每个A维护不能选择的B的最大值）。（倒着扫，这样每次操作就是区间取max）。

其实不用这么麻烦的，其实动用线段树有些太麻烦了，直接维护单调栈即可处理。

CF603E

给定一棵无向图，选出一些边，使得每个点度数为奇数。找出任意一棵生成树，在树上DP即可（记录每个点已选的度数，决定它的父边是否选）

原因是如果最优解需要选一条非树边，那么我们可以把u,v链上的所有边取反，不选那条边，还是可行解。

在线做法一：

我们要维护“最小偶数联通块森林”，可以直接使用LCT。具体来说：

我们直接维护最小生成树，同时维护每个联通块的奇偶性，把MST上的边都加入大根堆里。当我们需要询问时，一直弹出堆顶（删掉堆顶的边），直到出现奇数联通块。

离线做法二：

整体二分。学到了新的写法：求出mid的答案，然后递归[l,mid-1],[mid+1,r]

类似线段树和平衡树的区别。

代码见另一篇博客

离线做法三：

我们把边从小到大排序，对m建出线段树，dfs它。

先把这个节点上挂的边连上，然后先右后左的递归，回溯时把它加入的边删去。

这样做的好处是答案单调不降。到叶节点，我们维护一个全局的指针，表示当前加入了哪些边。然后遇到边e时，加入这条边，同时把这条边push到线段树上[e,r-1]的区间里（e>r时跳过）。

// 别人的代码
void update(int i, int ll, int rr, int l, int r, int e) {
    if (ll > r || rr < l) {
        return ;
    }
    if (l <= ll && rr <= r) {
        return void (rmq[i].pb(e));
    }
    update(i * 2, ll, (ll + rr) / 2, l, r, e);
    update(i * 2 + 1, (ll + rr) / 2 + 1, rr, l, r, e);
}

void solve(int i, int l, int r) {
    int len = len(dsu.ch);
    for (int e : rmq[i]) {
        dsu.unite(a[e], b[e]);
    }
    if (l != r) {
        solve(i * 2 + 1, (l + r) / 2 + 1, r);
        solve(i * 2, l, (l + r) / 2);
    } else {
        while (it < m && dsu.count > 0) {
            int e = e[it++].sc;
            if (e > r) {
                continue;
            }
            dsu.unite(a[e], b[e]);
            update(1, 0, m - 1, e, r - 1, e);
        }
        if (dsu.count > 0) {
            ans[l] = -1;
        } else {
            ans[l] = l[e[it - 1].sc];
        }
    }
    dsu.revert(len);
}

模拟赛

Forgive

非常Trick的一道题：给定平面上n个点（不存在三点共线），可以在两个点之间连一条线段，两条线段不能在除了端点以，外的地方相交，求最多可以连的线段数的期望。

首先应该发现，最优的连线一定是三角剖分

根据欧拉公式：V-E+F=1（F指有界面）

根据三角剖分：2E=3F+k，k是凸包上的点数。

可以得到：

E=3V-k-3

求凸包的期望点数可以转化为期望边数。注意特判一个点和两个点的情况

~~模数坑死人~~

Palingenesis

数四元环的数量...通过对度数和环的组成分类讨论可以获得O(n^{5/3})的优秀成绩（

不要看题解的辣鸡做法，czy的好方法：

给每个点按照度数大小编号。

枚举点u，枚举和点u相邻的点v，枚举v的相邻且度数比uv大的点z，ans+=cnt[z],++cnt[z];

Destiny

给定一个DAG，支持：对于所有点 u 可以到达的点 v，a[v]变成 x；对于所有点 u 可以到达的点 v，a[v]更新为 min(a[v],x)

bitset+定期重构...

差评

3.6

小 Q 的书架

其实题解就一句话：决策单调性。

BZOJ 2554

orz lrd

核心思想：求出以每种颜色结尾的概率，再求出期望步数。

概率好算，是i/n

期望步数：此时，除了白色的球都可以视为黑色了。

注意这是条件概率，所以每个时刻，白->黑和黑->白的概率是不同的，

设有i个白球的期望结束步数为f[i]

若此时白->黑，则结束的概率为(i-1)/n；否则，为(i+1)/n。也就是说，此时有(i-1)/2i的概率白->黑，另一侧同理。

于是有式子：

f[i]=g[i]+(i+1)/(2i)*f[i+1]+(i-1)/(2i)*f[i-1]

解的方法是设f[i]=k[i]f[i+1]+b[i]，先顺着推，然后倒着推

CF666C

发现答案只和模版串的长度有关，如果知道了长度，所有dp值可以O(n)求出。发现不同的值最多有2\sqrt{N}个，于是暴力即可。

模拟赛

sequence

自己反演了半天，得到了一个O(N\sqrt{N}\sigma(A))的莫队做法，跑得比暴力还慢...

因为自己太死板了，对因数考虑，事实上我们只需要考虑每个质数即可。

然后用莫队维护每个质数出现次数的平方即可。

3.17

「2017 山东一轮集训 Day6」子序列

发现递推式的矩阵可逆。于是可以前缀和优化。