广二&雅礼考试-解题报告

i207M · 2019-06-19 17:39:05 · 个人记录

广二

6.11

T1原题。

脑部进食

高斯消元，发现有一维单调，所以可以按层高斯消元。

游戏

~~没有题解？？？~~

ri，曾经脑子里闪现过二分的思路，但是后来又否决掉了：博弈题不能二分吧。瞄了眼题解，竟然真是二分！

博弈论二分！

那就好说了，我们把nm种状态分为两类，\le mid,>mid，先手遇到\le mid就立即停止，后手反之。那么博弈就变成了：只能从当前状态转移到对面不可接受的状态，问最后谁不能动了。这和某道棋盘上移动的题相似，求出二分图最大匹配和删掉起点的最大匹配即可。

但是我们需要利用这道题的性质才能快速求出匹配。（恩不错这里我大概是想出来了

把两个序列排序后，把nm个点放在网格里，那么点就分成了两种，一种是左上方的，一种是右下方的。我们求最大匹配不方便，可以转为最大独立集，我们的最优策略一定是选一个点(r,c)，选择在它左上角的白色和右下角的黑色，枚举r，c可以方便的求出来。

6.12

集合

大力讨论

棋盘

啥破玩意。

打表可以发现必胜条件是：

通常情况下就是<SDOI移动金币>的阶梯Nim的胜负态。

当k是偶数且特殊位置不在左边第二个的时候，第一段的间隔-1.

然后考虑如何统计方案数。~~这里的方法把SDOI2019日穿了~~

先回忆SDOI那道题的做法：我们按位DP，然后要存下之前用的数字和。

那么这道题我们显然不能这么做。但是，在状态里记录数字和其实用处不大，我们考虑n的每一位，肯定是这一位填的数，加上后边进位的数得到的，这和梦幻岛宝珠这道题很像！我们可以f[i][j]表示考虑前i位，后边的总进位值是j\times 2^i。显然j最大到m，于是我们枚举这一位，奇数位置填几个1，偶数填几个1，Naive的实现是O(k^3\log n)的，FFT可以优化到O(k\log n\log k)

序列

注意到大小关系的变化量是O(n)级别的，每次暴力重构SA即可。还有一种做法是考虑每对后缀，大小关系只会切换2次，于是切换的时候我们暴力把它俩重新插进set里即可。

正解在这个基础上优化一下就行了。我们建出后缀树（不要老是想着把SAM的parent树的节点看成本质不同的子串，它们其实就是（反串的）后缀树上的节点），注意到一次大小关系的改变其实就是把Trie树上每个点最小的儿子挪到子树最后的过程，这个变化总共是O(n)级别的，用平衡树维护相对关系即可。

6.17

Distinct Boxes

唔...这题有点强的。

Snuke 有 R 个红色球和 B 个蓝色球。他想把它们分到 K 个盒子中，使得不存在空盒子并且任意两个盒子都可通过球的颜色、数量区分。求 K 的最大值。

三重二分！

首先二分答案k

然后，问题变成从平面上选取k个点，设它们的横纵坐标和分别为X,Y，那么Y随X的增大而减小，这形成了一个下凸壳，如果(R,B)在这个凸壳的右上方，那么有解，否则无解。（和最小乘积生成树很像）

然后，如何求凸壳上的一个点？我们二分斜率，把每个点的权值变为ax+by，求前K小的和。我们可以再一次二分，找到第K小的值。

复杂度很玄学的是O(M^{1/3}\log^3M)

Multiple of Nine

lx讲课的bell状压题。

Paths

可以转化为求有多少三元环和四元环经过这个点。

6.19

无向图

分治+并查集。

线段树

线段树定位节点+树上莫队+点分治。

玩游戏

像这种**题，写70分bitset跑路就可以了。

6.20

两道原题...

T2

最近不知道在干嘛，思考的时候老是走神，不专注，经常在那愣神浪费时间。

给长度为n的序列填上[1,m]的数，要求前一个数不能是后一个数的真倍数。

题目的暗示很明显，这样连续的不合法段最多长\log n，于是我们就要容斥！（从这开始我就不知道在想什么然后浪费了好多时间...ri！）方案数不好统计怎么办？我们要DP！把奇偶性记在状态里，转移要么任意填，要么枚举接下来极长的不合法长度，最多\log n，这段的方案数可以预处理出来。

 f[0][0]=1;
 for(int i=1;i<=n;++i)
 for(int j=1,x=0;j<=i && c[j];++j,x=!x)
 {
 f[i][0]=(f[i][0]+f[i-j][ x]*1ll*c[j])%MOD;
 f[i][1]=(f[i][1]+f[i-j][!x]*1ll*c[j])%MOD;
 }
 printf("%d\n",sub(f[n][0],f[n][1]));

6.23

A是APIO数据备份...

B

这是道水题，但是我咋想了那么久...

首先显然的贪心是正确的，就是从后向前扫一遍，遇到前缀和<0的就删掉，然后求这个序列的前缀最小值（相当于再从前往后扫一遍，删掉不合法的），那么正解肯定是扫描线了，但是如何维护这个信息呢？

前缀和最小值好维护。我们希望找出所有后缀和小于0的位置，如何维护呢，其实很简单，维护一个栈，遇到-1就加入，这个位置设为0；遇到1把这个位置设为1，把栈顶位置的值设成-1，弹出栈顶。查询时要把答案加上栈里的元素

你可能会想，当后边+1了，后缀和为-1的位置都合法了，这不是很多位置吗，这是假的，如果两个位置的后缀和都是-1，那么之间的括号是匹配的，那么这一段我们是不用动的！

C

哇塞，这道题牛啊。

显然我们要在AC自动机上跑。但是如何区间查询呢（我只会辣鸡的根号（可能还带log）的做法），正解十分暴力：

我们把母串S和模板串都放到AC自动机上，对于每个节点，我们维护它到根的串的每个后缀的答案，这个答案必须包含后缀的第一个位置，换句话说，每个点有个可持久化treap，里面有len个节点，表示每个后缀的前缀的答案和。这样做有什么好处呢？首先询问很方便。并且，建立这棵树的方法也很巧妙：注意到这个串长度\le len[fail]的答案已经处理完了：就是fail点的Treap，我们直接接过来。那么更长的后缀呢？注意到这些后缀的答案不可能包含当前处理的点（不然就有更长的fail了），那么我们直接把父亲的Treap的前len[x]-len[fail]项拿过来，接在fail的Treap的前边，组成点x的Treap。把两个序列一前一后合并正是fhqTreap擅长做的事。，然后我们把Treap里第一个点的答案加上自己的权值。

6.24

A

n,m\le 10^6,k\le 1000

显然这道题有决策单调性，但是直接做是O(nk\log k)的，如何优化？

我们把所有商店按照a_0+a_1排序，那么除了前k个之外，其他商店选择的个数一定>1（不然可以选前边的商店）；然后把所有剩下的商店按照a_0+a_1+a_2排序，除了前k/2个商店外，选择的个数>2；以此类推，我们最终只会留下k\log k个商店，然后再跑决策单调性就行了。

自己YY的做法：

首先这个DP是凸的，那么我们可以wqs二分。于是对每个商店我们贪心的选\max\{-a_k+k\times mid\}（a做过前缀和了），发现本质不同的斜率只有O(m)个，我们可以先处理出每个斜率区间的答案，然后对k个进行wqs二分。

B

可做的计算几何

C

没有题解...

雅礼

6.20

A

退役了退役了这都没想出来...

对于每个节点 u，\sum_v w_{dis(u,v)} 是多少。

见到树上路径，可以点分治。处理过中心的路径，发现贡献是把每个深度的点数cnt和w卷积起来。

6.22

A

比较简单的数据结构，注意细节的讨论。eg. 不能有重复的数字。

B Epidemic

哇塞好题。看另一篇博客吧。

C

一个排列最多2次就可以交换完成。当一个排列的所有环的大小\le2就只需要一次（已经排序的除外），我们只要统计最大环>2的图。

然后...DP+Bell数爆搜...不会了。

6.23

A是原题...

B

二叉树！

感觉这些树上交互题都是随机剖分/点分治/LCT+链上二分。

既然要链上二分，我们先随便问出一条到根的链。然后把这条重链上的点排序（注意到祖先后代关系具有传递性），然后其他点可以通过链上二分找到位置。复杂度是随机剖分。

但是有一个问题：怎样确定在哪个轻儿子里？

似乎做法是这样的，我们写一个函数f(x,S)表示已知S这个vector内的点在以x为根的子树里（x不在里面）。那么我们从S中随机选一个点y，问出y到x的链（看作把y到x设为重链），然后把其他点定位一下，递归进行。因为是二叉树，所以不会被卡。

如果对比较次数有限制，不要用sort要用stable_sort！

C

这道题的难点在于恶心...

我们只要解决链上的问题就行。显然相交一定是位置相邻的点，而相交之前位置的相对关系是不会变的，所以我们用set维护即可。

6.25

这场我和ywy也考了...然后发现被雅礼神仙虐的很惨...

A

考场上写的是删掉一条链，然后把链上的点的其他的儿子接到根，同时根维护一个优先队列存每个儿子。

其实上边的做法就等价于长链剖分，把每条长链的长度放到vector里取前K大（nth_element）...

const int N=4e6+5;
int n,K;
int val[N],fa[N];
int head[N],cnte=1,v[N],nx[N];
il void adde(const int uu,const int vv) {v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte;}
LL dep[N],len[N]; int cnt;
void solve()
{
    for(ri x=n; x>=1; --x)
    {
        if(!head[x]) {dep[x]=val[x]; continue;}
        for(ri i=head[x]; i; i=nx[i])
            if(dep[x]<dep[v[i]]+val[x])
            {
                if(dep[x]) len[++cnt]=dep[x]-val[x];
                dep[x]=dep[v[i]]+val[x];
            }
            else len[++cnt]=dep[v[i]];
    }
    len[++cnt]=dep[1];
    nth_element(len+1,len+K,len+cnt+1,greater<LL>());
    LL ans=0;
    for(ri i=1; i<=K; ++i) ans+=len[i];
    out(ans);
}
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    in(n,K,val[1]);
    for(ri i=2; i<=n; ++i)
    {
        val[i]=(val[i-1]*23333333ll+6666666)%1000000007;
        fa[i]=(val[i]^23333333)%(i-1)+1;
        adde(fa[i],i);
    }
    solve();
    return 0;
}

B

线段树神仙题？

C是原题。

6.26

A是原题

B

min_25筛加强版？看另一篇博客：Powerful number吧

C

首先如果没有边的限制，我们是可以枚举第一个“自由位”的位置，O(n\log Max)做出来。

有了边的限制，我们就要容斥，强制相等，这形成了若干联通块，每块只有限制最小的点有用（~~然后可以Bell数爆搜~~）。但是怎样优化到指数级复杂度？

看了题解恍然大悟：既然方案数只和每个联通块的最小值有关，我们可以直接暴力状压DPf(s,t)表示已选的集合为s，最小值的集合为t！然后每个联通块的容斥系数可以预处理出来！

分析性质，找到到底需要啥。

求每个联通块的容斥系数有两种方法：类似<城市建设>一样减法，或者枚举删掉最小的点后，次小的点构成的联通块集合。

然后分析复杂度，显然瓶颈在后面的背包，我们以填表法分析复杂度

我们每次枚举的是最小的在t中的点i，考虑点i贡献多少复杂度。

i前边的要么不在s，要么在，这是2^{i-1}种

i后边的，我们枚举比i大的点的在 s中的子集，所有点要么不在s，要么在s且没在枚举的子集里，要么在枚举的子集里。O(3^{n-i})

所以总复杂度O(3^n)

6.28

game

有 n 个人，要分成若干组，对于第 i 个人，它所在的组的人数不能超过 ai ，问分组的方案数模 998244353 的值。

组与组之间是不可区分的，每组的人也是无序的，但人与人之间是可以区分的。

先把a排序

先写出dp[i][j]表示前i个人，所有组的名额剩j的方案数，我们在每组最小的人处加入这个组，并认为组内有顺序，为了去掉顺序，我们在加入组的时候要除以阶乘。NTT优化DP。

貌似题解的做法挺巧妙的，也不依赖模数：dp[i][j]表示考虑完大小为[i,n]的组，用了j人。

rook

一月份安师大考试的原题...但是好恶心啊想鸽了。

collect

（标程13k，摸了？）

但是这个思路是很值得学习的。

首先我们可以求出走z步后横坐标为i的生成函数：

G_z=(Bx+A)^z

我们如何计算贡献呢？我们考虑求出走zD后，横坐标\mod D=0的方案数

这个咋求呢，我们需要把坐标“循环移动”

其实很简单：

F_z=G_z\mod x^D-1

这个\mod x^D-1恰好就是将方程的系数循环移动！

如果没有K的限制，我们要求的就是

[x^0]\sum_i F_{iD}

这其实就是多项式等比数列求和，倍增即可。

那么有K的限制呢？由于左边\le M，我们只需要在每个关键点处，求出

[x^X]G_{X+Y}

的值，然后在F数组的对应位置减去即可！

6.29

T1

26个点的费用流...**zzt的数据是假的调了我半天...

T2

构造题要勇于猜下界

老虎最近得到了一个排列 a。这一次，老虎决定将这个序列排序。

老虎的排序方法是这样的：每次他会选择排列 a 的一个子序列 b，删去这个子序列后，将这个子序列插回到原序列的最前面。

老虎想要考考蒜头，因此他想要蒜头回答出，至少需要几次操作可以将序列 a 排好序。同时，为了说明你不是随便报的，你需要输出操作的方案

按位构造好题。考点：基数排序

看到这道题有一个显然的贪心是把序列分段，分为极长的值域连续且位置递增的段，我们段内部的顺序肯定不用动。然后段之间需要重新排序，那么我们按位从低到高考虑，每次把这一位是0的丢到前边，log次后就排好序了。

T3

神仙构造题，摸了。

7.1

最后一天啦

T1

这一天，老虎和蒜头又聚集到一起讨论有趣的问题了。与往常类似地，蒜头又不知道从哪里摸出了一个无向平面图。讨论完毕后，蒜头提议进行一个游戏：轮流给该图加上一条边，直到无论增加上哪一条边图都会变得不是平面图，无法操作者败。

游戏结束。毫无疑问，老虎又输了，然而老虎现在关心的并不是这样的问题。老虎最近刚刚学习过三分图理论，因此他想要知道，有多少种加边的方案 (不能加重边和自环)，使得加边后的图是一个三分图。

一个图被称为三分图，当且仅当存在一个方案，可以将图划分成三个点集，使得不存在任意一条边在一个点集内部。

首先原图必须是三分图。确定相邻两个点的颜色后，就可以进而确定所有其他点的颜色或判断无解（似乎是因为平面图的性质），我们只要在同颜色点之间加边即可。

T2

我们考虑答案可能的最大值，那就是离散化后，对于相邻关键点之间的区间，我们希望跨过它的区间，一半是黑色一半是白色。

事实上这个上界是可以达到的。我们维护和当前段有交的区间，假如加入一个区间后数量为奇数，那么我们不用处理（因为它黑白无所谓）；如果为偶数：

如果前一个操作是加入，那么两个区间的颜色不同
否则，两个区间的颜色相同

删除也差不多。代码实现起来有一些Trick。

T3是通信题...

3.22

T1

似乎正解就是按题意模拟...?没想到这么简单啊。

我们先预处理出lim数组，表示被修改的值的第k大至少为lim[k]，再记录要合法至少要改变几个点的值。

    int L=0,R=0;
    REP(i,1,n) if(d[Min[id[i]]]<a[i]){L=i;break;}
    if(L==0) return printf("0\n"),0;
    DREP(i,n,1) if(d[Min[id[i]]]<a[i]){R=i;break;}
    int Max=0;
    for(int i=L,j=1;i<=R;++i){
        while(j<=n && a[i]>d[Min[id[j]]]) ++j;
        if(j>i) lim[j-i]=a[i],chkmax(Max,j-i);
    }
    int ans=inf;
    for(int i=1,j;i<=L;i=j+1){
        j=i;
        while(j<n && Min[id[j+1]]==Min[id[i]]) ++j;
        if(j-i+1<Max) continue;
        REP(k,i,j) stk[++top]=Sec[id[k]];
        sort(stk+1,stk+top+1,greater<int>());
        int flag=1;
        REP(k,1,Max) if(stk[k]<lim[k]){flag=0;break;}
        if(flag) chkmin(ans,a[R]-d[Min[id[i]]]);
        top=0;
    }

我们枚举修改某个点，把到根最小值位于这个点的点集找出来，排序，和上面的lim数组对照，看是否按位大于。

T3

这是好交互题：询问3个下标，返回min+max，在n+log V+O(1)次询问中复原整个序列。