首页 > 其他分享 >题解:CF573D Bear and Cavalry

题解:CF573D Bear and Cavalry

时间:2024-09-25 16:23:34浏览次数:7  
标签:ch CF573D 题解 Bear fa 数组 ib 我们 dp

因为这是远古题目,所以根据现在的评测机速度,用 \(O(nq)\) 的做法也是可以过的。

也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种 \(O(n)\) 的算法求解答案。

这道题类似资源分配型动态规划,所以我们可以设 \(dp_i\) 表示分配前 \(i\) 个人的答案。

直接写是不行的,我们根据排序不等式先把 \(a\) 和 \(b\) 数组排序,然后进行转移。首先有一个结论,在当前的状态下,\(i\) 只能由 \([i-2,i]\) 中间的状态转移过来,因为我们要求人和马连边以后逆序对数量最少,但是因为题目限制,所以 \([i-2,i]\) 之间的状态我们都需要考虑。

所以我们分四种情况转移,画个图方便理解(图很丑谅解一下):

然后根据上图我们可以列出来四个方程:

\[dp_i=\max \left\{ \begin{array}{lc} dp_{i-1}+a_ib_i&ch(i,i)\\ dp_{i-2}+a_ib_{i-1}+a_{i-1}b_i&ch(i,i-1)~and~ ch(i-1,i)\\ dp_{i-3}+a_ib_{i-2}+a_{i-2}b_{i-1}+a_{i-1}b_{i}&ch(i-2,i-1)~and~ch(i-1,i)~and~ch(i,i-2)\\ dp_{i-3}+b_ia_{i-2}+b_{i-2}a_{i-1}+b_{i-1}a_{i}&ch(i-2,i)~and~ch(i,i-1)~and~ch(i-1,i-2)\\ \end{array} \right. \]

其中 \(ch(i,j)\) 的含义是 \(a_i\) 和 \(b_j\) 可以匹配。

为了维护 \(ch\) 这个条件,我们不妨存储 \(a\) 数组和 \(b\) 数组每个元素的编号,并设立一个新数组 \(fa\),然后令 \(fa_i\) 表示 \(a_i\) 对应的 \(b\) 的编号。

然后我们可以给出 \(ch\) 的代码。

bool ch(int x,int y)
{
    return fa[a[x].id]!=b[y].id&&x>0&&y>0;
}

每次修改的时候对于修改的两个位置 \(x,y\) 我们直接交换 \(fa_x\) 和 \(fa_y\) 即可。

然后这道题就结束了。

提交记录

标签:ch,CF573D,题解,Bear,fa,数组,ib,我们,dp
From: https://www.cnblogs.com/Lydic/p/18431592

相关文章

  • 题解:AT_abc204_e [ABC204E] Rush Hour 2
    变形的dijkstra。先思考什么情况下需要等待以及等待多长时间最优。我们把题目上的计算方法按照当前的时间\(t\)和通过所需的时间\(f(t)\)列个函数关系:\[f(t)=t+c+\lfloor\frac{d}{t+1}\rfloor\]然后用Desmos画个图可以得到图像(其实就是对勾函数):因为\(c,d\geq0\),所......
  • [湖北省选模拟 2023] 棋圣 / alphago 题解
    很牛的题目啊。-Alex_Wei发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。容易发现若为二分图,则初始颜色不同的一定不能移动到一起。又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令\(c_{i,j}\)为初......
  • CF1119H Triple 题解
    DescriptionSK酱送给你了一份生日礼物。礼物是\(n\)个三元组\((a_i,b_i,c_i)\)和四个正整数\(x,y,z,k\)。你利用这\(n\)个三元组填充了\(n\)个数组,其中第\(i\)个数组中有\(x\)个\(a_i\),\(y\)个\(b_i\),\(z\)个\(c_i\)(所以第\(i\)个数组长度为\((x+y+z)\)。......
  • Codeforces Round 974 (Div. 3)题解记录
    A.RobinHelps签到模拟,遍历一遍即可,注意没钱时不给钱。\(O(n)\)#include<iostream>#include<set>#include<map>#include<vector>#include<algorithm>#include<bitset>#include<math.h>#include<string>#include<string.h>#......
  • [ARC122E] Increasing LCMs 题解
    感觉像比较套路的构造题。思路假如我们正着进行构造,可以发现我们加入一个数以后,对后面的数产生的影响是很大的。但是如果我们从最后一个数开始构造,那么可以发现它是不会对之后的构造产生任何影响的。应为越前面的数的限制会越少,那么可以填的数一定是不减的。一个数可以填在后......
  • 算法题之图论 [NOIP2001 提高组] Car的旅行路线详细题解
    P1027[NOIP2001提高组]Car的旅行路线这道题的思路呢,就是建个图,然后跑一遍Floyd,比较最小值就可以解决了。but!它每个城市只给三个点(共四个),所以还得计算出第四个点坐标。这里根据矩形的中点公式来表示未知点的坐标:(这个思路源于大佬 _jimmywang_       ......
  • [ARC121E] Directed Tree 题解
    简单容斥题。思路题面的条件相当于一个位置上填的点不能是自己的祖先。发现直接做并不好做。考虑容斥。我们想要求出\(f_i\)为至少有\(i\)个不合法位置的方案数。那么答案为:\[\sum_{i=0}^nf_i(-1)^i\]如何求解。设\(f_{i,j}\)为\(i\)子树下有\(j\)个不合法位......
  • 2024-2025专题一题单 - 题解
    A-Virus原题链接题解B-Coverage原题链接题解C-Sensors原题链接题解D-MakeTakahashiHappy原题链接题解E-Don’tbecycle原题链接题解F-AlmostEqual原题链接题解G-StepUpRobot原题链接题解H-SnukeMaze原题链接题解I-MEX原题链接......
  • P5329 [SNOI2019] 字符串 题解
    Description给出一个长度为\(n\)的由小写字母组成的字符串\(a\),设其中第\(i\)个字符为\(a_i\(1\leqi\leqn)\)。设删掉第\(i\)个字符之后得到的字符串为\(s_i\),请按照字典序对\(s_1,s_2,……,s_n\)从小到大排序。若两个字符串相等,则认为编号小的字符串字典序更小。......
  • CF164D Minimum Diameter 题解
    最小点覆盖模板题。思路考虑二分直径\(x\)。我们将距离\(>x\)的点对连一条边,那么每一条边的两端至少有一端需要被删掉。这是最小点覆盖的定义。那么就是判断最小点覆盖是否小于等于\(k\)。发现这个问题并不好用一些多项式复杂度的做法解决。考虑暴搜。每一次我们把度......