首页 > 其他分享 >[湖北省选模拟 2023] 棋圣 / alphago 题解

[湖北省选模拟 2023] 棋圣 / alphago 题解

时间:2024-09-25 15:46:52浏览次数:11  
标签:棋圣 二分 颜色 cdot 题解 上界 alphago 初始

很牛的题目啊。 -Alex_Wei

发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。

容易发现若为二分图,则初始颜色不同的一定不能移动到一起。

又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令 \(c_{i, j}\) 为初始颜色为 \(i\) 的 \(j\) 色棋的数量,上界即为 \((c_{0, 1}\cdot c_{1, 0} + c_{0, 0} \cdot c_{1, 1})\cdot max\ w\),而取到这个上界的必要条件是所有相同的 \(ij\) 合并到一起,并处于最大的边的两端,即初始颜色相同的都到一起,这是较弱的条件,容易达成,考虑什么时候不能达成,即初始颜色相同的不能到一起,此时为链。

偶环和非链二分图是一样的。

非二分图性质比非链二分图还要强,此时答案有取得到的上界 = 黑子个数 * 白子个数 * \(max\ w\)。

考虑链,\(\mathcal O(n^3)\) 做法我没看懂为什么必然是 \([p, d_{p}]\),求教qwq

参考文章

Alex_Wei 的题解

标签:棋圣,二分,颜色,cdot,题解,上界,alphago,初始
From: https://www.cnblogs.com/SkyMaths/p/18431496

相关文章

  • 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\)。发现这个问题并不好用一些多项式复杂度的做法解决。考虑暴搜。每一次我们把度......
  • CF2003F Turtle and Three Sequences 题解
    个人觉得*2800有点虚高。如果做过类似的题(比如[THUSCH2017]巧克力),应该可以想到随机映射,状压dp也不难想。实际上,看到要选出\(m\)种不同的颜色,且\(m\le5\)就可以想到将每种颜色随机映射到\(1\)到\(m\)中,这样子得出来的答案不会更优,而当答案选择的\(m\)种颜色恰好......
  • 20240924 模拟赛 T4 题解
    Description这是一道交互题。有一棵\(n\)个节点的树,现在要求你通过若干次询问得到这棵树的每一条边连接哪两个点。每次询问你需要指定\(n\)个整数\(d_1,d_2,\ldots,d_n\),满足\(-1\leqd_i\leqn\),其中\(1\leqi\leqn\)。每次询问交互库会返回给你一个长度为\(n\)的......