AGC031到040

AGC031到AGC040题解合集

AGC的题面一般都不难懂,就不给出翻译了

好题:AGC039E、AGC040C

6/10

AGC031

old_link

AGC032

old_link

AGC037

old_link

AGC038

人傻做法傻,大家散了吧

AGC038A - 01 Matrix

请先思考后再展开

code

枚举任意一组i和j满足$i(m-A)+(n-i)A=j(n-B)+(m-j)B$即1的个数相同,然后考虑每列,每次贪心选1最多的行,$O(n^2logn)$

正常人的做法是右上角和左下角是1之类的

AGC038B - Sorting a Segment code

请先思考后再展开

看完题意考虑按题意模拟,就是区间排序,从左往右枚举这个区间,用个线段树维护值域hash即可,其实不难写,就是要写双hash才行,错的点有些多我还以为我是错的,$O(nlogn)$

正常人的做法是考虑「i开始」和「i+1开始」相同,当且仅当ai为「i开始」中最小且a[i+m]为「i+1开始」最大,可能还有些特殊情况要判

AGC038C - LCMs code

AGC038D - Unique Path code

请先思考后再展开

先把op=0的点并查集在一起成一条链(m–),顺序不重要,主要是以后参与其他东西只能派唯一一个点,相当于缩点

然后考虑op=1的边,新建图,并查集起来,对于siz=2的需要找一个外援,m-=3,然后siz>2的就m-=siz,相当于最小代价,然后还需要判上界,这个需要按一些顺序算

正常人的做法是必须用的边其实是n条(包括两类),上界是所有缩点成环后补边,大概是这样吧,见rose代码

AGC038E - Gachapon

请先思考后再展开

做法一:期望有个套路的转化,就是如果求恰好到达的状态的概率*步数之和,等价于所有未到达的状态的概率之和,这个你可以通过「把当前概率推到上面的步数个祖先上」理解

min-max容斥,那么考虑对于某个元素的集合State,就是$ans=\sum_{State \ne \emptyset} (-1)^{|State|+1} min(State)$

对于本做法,恰好到达指恰好有一个元素的出现次数为bi,其他都更小;则未到达为所有都在bi-1以内

然后你会发现基本做完了,大致思路基本上就是推推式子,dp优化之类的,这个是min-max容斥的常见套路

对于每个未到达状态,显然按每种State内元素的出现个数表示(记为数组c,和为C)

记$sumA=\sum_{i \in State} A_i,P\ of\ min(State)=\frac{C!}{sumA^{C+1}/S} \prod_{i \in State} \frac{A_i^{c_i}}{c_i!}$,这里是为了方便先只考虑State内元素的期望步数,然后乘上$\frac{1}{p}=\frac{S}{sumA}$放缩,即实际这么多步顶里面一步

设$f(n,sum_A,C)$表示考虑前n个数,类似二维背包那样dp,第一维可以去掉

转移的复杂度为bi,故复杂度为$O((\sum a_i)*(\sum b_i)^2)$,code

做法二概率生成函数,有经验的长者的首选
$f为恰结束g为未结束的OGF,f+g=zg+1,ans=f’(1)=g(1)=转OGFe^z-\prod (e^{\frac{A_i}{S}z}-\sum_{j=0}^{B_i-1} \frac{(\frac{A_i}{S}z)^j}{j!}$
背包求$z^ie^{\frac{j}{S} z}$的系数,复杂度为$O(B^2S)$,code

AGC038F - Two Permutations code

请先思考后再展开

注意到选择的形式很特殊:$i或P_i$,将P看做置换,则等价于一个若干个轮换的图,选择若干个轮换,将其改为$i \to i$

注意到时限很大,考虑用最小割求解,对每个i分类讨论,因为决策是对于整个轮换的,所以要缩点保证依然是排列

设P中轮换选的话在st集合不选ed,Q与其相反
$$
\begin{aligned}
& 1)p_i=i=q_i,直接忽略,\\
& 2)p_i=i\ne q_i,对q改则-1,st \to Q\\
& 3)p_i\ne i = q_i,对p改则-1,P \to ed\\
& 4)p_i=q_i \ne i,改的状态相同则-1(给原答案+1),P \leftrightarrow Q \\
& 5)互不相同,都改则-1,P \to Q
\end{aligned}
$$
需要加个当前弧

AGC039

AGC039A - Connection and Disconnection code,忘记判n=1;其实复制一遍会好写很多

AGC039B - Graph Partition code,只有偶环,这样搞肯定合法且是上界

AGC039C - Division by Two with Something

请先思考后再展开

注意到每个数都能被到达,所以一定是若干个环组成,考虑如何计算一个数所在环的环长

转化一下操作,每次就是把最后一个字符0/1去掉并在最前面加上1/0

设rev为01反转,在A+rev(A)+A中选取最右边一个段使得和原串相同,距离就是环长

做2n次肯定能回到自己,考虑更短的那些有什么特性,欢乐玩耍一下发现:rev(A)+A一定存在一个循环节(也是环长)2d,并且$\frac{2n}{2d}$一定是奇数(否则断点都在串里面,等价于rev(A)=A,显然不可能),而且这个2d一定形如B+rev(B)

考虑枚举d求有$f(d)$个串满足存在循环节2d(环长可能是d的约数*2,莫反解决)

注意到确定了d和B整个串就确定了,而B是受到题目中上界的限制,

对于每个d,随便判一下就能求出有多少个合法的B,复杂度不超过$O(n^{3/2})$,code

AGC039 D - Incenters

请先思考后再展开

三角形五心复习

那么现在就是求圆弧中点形成三点坐标之和,贡献拆开,枚举两点i和j,统计中间圆弧中点被统计次数,讨论一下在哪一侧即可

$O(n^2)$,code

AGC039 E - Pairing Points

题意补充:所谓树形结构,考虑的是线不成环,跟点没关系

请先思考后再展开

考虑怎么理解、应用直线上的树形结构;特判n=1后相邻不能连边

设$1 \to pp$为根,画出若干条一级孩子,你发现这些孩子的子树用的点一定是连续的两个区间
$$
设f(l,r,k)表示l到r区间的点,并且k号点向区间外配对,ans=\sum_{pp} f(2,2n,pp) \\
f(l,r,k)=\sum_{x=l}^{k-1} \sum_{y=k+1}^r [(x \to y) \in Edges]
\sum_{a=x}^{k-1} \sum_{b=k+1}^y f(l,a,x)*f(a+1,b-1,k)*f(b,r,y)
$$
$O(n^7)$且常数很小,实际跑得飞快,code

AGC039 F - Min Product Sum

请先思考后再展开

题意转化,对于矩阵A的权值,其实就等价于填一个B满足$B[i][j] \le min(A[i][1..m],A[1..n][j])$的方案数

每个位置都考虑其行列有点恶心,再转化一下,$B[i][1..m] \le min\ A[i,1..m],B[1..n][j] \le min\ A[1..n][j]$

然后如果你直接填A找B或填B找A,似乎都至少要$O(n^5)$,下面直接给出正解做法(需要整体看理解正确性):
$$
设B第t行的mx为X_t,A第t列的mi为Y_t,考虑同时填A和B \\
f(u,i,j)表示处理了i行j列,之前确定过的X,Y \le u \\
枚举增加ad行X_t=u+1,考虑每行新产生什么信息,系数^{ad}*C_{n-i}^{ad} 即可\\
对于Y_t \le u的那j个位置,A中必须要填>u的数,即(K-u)^j;\\
对于另外的m-j个位置,B中必须填\le u+1的数且至少一个u+1,即(u+1)^{m-j}-u^{m-j} \\
接着枚举ad列Y_t=u+1,考虑每列新产生什么信息,和上面类似 \\
对于X_t \le u的那i个位置,A中必须填>u且至少一个u+1,即(K-u)^i-(K-u-1)^i\\
对于另外的n-i个位置,B中必须填\le u+1的数,即(u+1)^{n-i} \\
ans=f(K,n,m),行和列的增加是u到u+1的两个阶段,增加一维0/1即可 \\
预处理系数(行与i无关,列与j无关)或者直接预处理((A+1)^{B}-u^{B})^C,O(n^4)
$$

未优化版,懒得优化了(这个好看):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
f[0][0][0][0]=1;
fo(u,0,K-1)
{
fo(i,0,n) fo(j,0,m) fo(ad,0,n-i)
{
int ss=qpower(K-u,j)*mm(pp[u+1][m-j]+MOD-pp[u][m-j])%MOD;ss=qpower(ss,ad);
add(f[u][1][i+ad][j],f[u][0][i][j]*C[n-i][ad]%MOD*ss%MOD );
}
fo(i,0,n) fo(j,0,m) fo(ad,0,m-j)
{
int ss=qpower(u+1,n-i)*mm(pp[K-u][i]+MOD-pp[K-u-1][i])%MOD;ss=qpower(ss,ad);
add(f[u+1][0][i][j+ad],f[u][1][i][j]*C[m-j][ad]%MOD*ss%MOD );
}
}
write(f[K][0][n][m]);

并没有看懂这个做法

AGC040

AGC040A - >< code

AGC040B - Two Contests code

按照左端点排序后枚举左端点较小的那个集合的左端点,然后考虑谁负责肝那个最小的右端点

AGC040C - Division by Two with Something code

请先思考后再展开

肯定要先想清楚,串合法的充要条件

每次删掉连续的两个格子,考虑黑白染色,那么将黑色格子上的A改成B,B改成A,规则改成不能删除AA、BB

这个改变初看没啥,但细想一下你会发现后面没有难点了

我们肯定希望A和B消,搞不定的就C帮忙消,所以显然有个必要条件:$C \ge |A-B|$

思考一下你会发现其实这个条件是也是充分的,可以感性理解,于是相当于$\sum_x \sum_y [|x-y| \le n-x-y] \frac{n!}{x!y!(n-x-y)!}$

分类讨论一下,发现其实就是$\sum_{x=0}^{n/2} \sum_{y=0}^{n/2} \frac{n!}{x!y!(n-x-y)!}=\sum_{x=0}^{n/2} \frac{n^{\overline x}}{x!} (\sum_{y=0}^{n/2} C_{n-x}^y)$,可以用$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$,设后面部分为now,则$now(x)=2now(x+1)-C_{n-x-1}^{n/2}$,从大往小枚举x计算即可,$O(n)$

upd:我是脑残吗?x和y不可能同时比n/2大,直接减去各自非负情况就好了,是独立的……

AGC040D - Balance Beam ,注意选点是实数点,code

请先思考后再展开

如果已知排列方式,那么Ringo能选的让Snuke胜利的点一定是一段前缀,设最大能选点为p,那么$ans=p/n$

注意到选的是实数点,考虑二维折线图,x轴为距离,y轴为时间(设$S=\sum_{i=1}^n a_i$),那么只要两人的折线有超过一个交点,就能将Ringo的折线竖直向下平移,则Ringo的折线与x轴交点就是$(p,0)$

那么枚举k表示$(p,0)$在线段k上,考虑到两折线只有一个交点怎么利用,考虑用折线C表示一种方案:从$(p,0)$出发,先按斜率b走,到交点的时候按照斜率a走,最后到达$(n,S)$,这个C的优点主要在于终点是确定的,而且因为恰有一个交点一定能去到。

于是就好做多了,既然开始和结束的y坐标都固定而要最大化起点的x坐标,肯定是选尽量少的线段让y快速上升(线段数决定q的整数部分,第二关键字为上升量决定q的小数部分),而一条线段放在右边的最大贡献显然是$max(a_i,b_i)$,而这个上界是可以达到的,将想要a的放交点右边,其他放交点左边就行了

于是枚举k,二分一下最小的q,合法q满足$(排序后)S<\sum_{i=1}^q max(a_i,b_i)<=S-b_k$,$O(nlogn)$

AGC040E - Prefix Suffix Addition code

请先思考后再展开

如果只有操作1,显然答案为$\sum_{i=0}^n A_i>A_{i+1}$,同理只有操作2,答案为$\sum_{i=0}^n A_i<A_{i+1}$,于是考虑每个数$A_i=x_i+y_i$表示两种操作分别的贡献,然后$val=\sum x_i>x_{i+1}+\sum y_i<y_{i+1}$,问一种拆分最小化val

注意到现在权值的计算只和相邻两项有关,明显考虑

$dp(i,x_i)=minval,dp(i+1,x_{i+1})=min\ dp(i,x_i)+[x_{i+1}<x_i]+[x_{i+1}<A_{i+1}+x_i-A_i]$

观察一下这个dp形式,你发现他就是$A_i$个函数min在一起,这些函数的是一段x+2,一段x+1,一段x这样的形式

然后相同值的一段,只有最小那个x是有用的,用它给后面转移就好了

AGC040F - Two Pieces 咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/127faea6.html
转载请注明出处,谢谢!