首页 > 其他分享 >34. CF-Robots on a Grid

34. CF-Robots on a Grid

时间:2023-03-07 23:55:14浏览次数:61  
标签:环上 黑点 Robots CF Grid times 数量

链接

写一下思路好了:

  1. 必须存在一些环才能无限走下去
  2. 那么最大总数量就是所有环上的节点数量
  3. 最大黑点数量就是环上的黑点数量+能走到环上白点处的环外黑点数量
  4. 判环的手段很多,难点在于统计那些黑点
  5. 注意到至多经过 \(n\times m\) 的时间,环外的点一定能走到环上
  6. 那么直接看 \(n\times m\) 的时间后这些点走到哪里去了
  7. 对于这些终点进行统计,讨论它们的源点的颜色
  8. 复杂度可以用倍增优化到 \(O(nm\log(nm))\)

代码实现的时候注意空间消耗。套多层 vector 容易 MLE。

标签:环上,黑点,Robots,CF,Grid,times,数量
From: https://www.cnblogs.com/theophania/p/p34.html

相关文章

  • CCF 2014-3
    一:试题编号:2014-3-1试题名称:​相反数时间限制:1.0s内存限制:256.0MB问题描述:问题描述有N个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数(a和-a为一对......
  • CF1700板刷
    CF1700板刷前言:vpedu的时候逐渐力不从心,于是滚回来板刷1700qwqhttps://codeforces.com/problemset?order=BY_RATING_ASC&tags=1700-log3.5466C3.6474D3.7339D,1......
  • DBGrid鼠标滚动控制
    typeprocedureOnMouseWheel(VarMsg:TMsg;varHandled:Boolean);//注意,需先在type里声明////////////////////////////////////////////////////////////////////////......
  • 「解题报告」CF1178B WOW Factor
    ¿题目链接这是一道非常富有启发性的题目,值得一做,闪耀着人类和机器人的智慧光辉的绝佳题目.首先注意到(vv)o(vv)的结构,可以考虑枚举中间的o,这样只需要算两边的选法......
  • CF1780F Codeforces Round 846 (Div. 2) F. Three Chairs
    https://codeforces.com/contest/1780/problem/F计算\[\sum_{i,j,k}[gcd(min(a_i,a_j,a_k),max(a_i,a_j,a_k))=1]\]对\(a_i\)排序,则需计算\[\sum_{i<k......
  • CF1796E Colored Subgraphs
    个人思路:换根。从\(1\)开始DFS遍历。对于一个点,维护\(mx1_u=\min\limits_{v\inchild_u}mx1_v+1\),\(mx2_u\)为\(\min\limits_{v\inchild_u}mx2_v\)和\(m......
  • CF955C Sad powers
    CF955CSadpowersLuoguCF955C题面翻译给你\(q\)个询问,每次询问\([l,r]\)这个区间内满足\(x=a^p(a>0,p>1)\)的\(x\)的数量。数据范围:\(1\leqslantq\leqsla......
  • 3月CF杂题
    CodeforcesRound853(Div.2)打的VP。E.ServalandMusicGame妙妙题。F.ServalandBrainPower妙妙题+1。对\(k\ge5\)的情况,我们把整个序列分成5段,那......
  • [CF1648D]Serious Business 题解
    [CF1648D]SeriousBusiness题解首先容易想到一个\(dp\)转移式子:\[dp_{i}=\max_{j\lei}s_{1,j}-cost_{j,i}-s_{2,j-1}+s_{2,i}+s_{3,n}-s_{3,i-1}\]其中\(dp_i\)......
  • 33. CF-Divisor Paths
    链接求从\(x\)到\(y\)的最短路径的数量。显然应该从\(x\)走到\(\gcd(x,y)\)再走到\(y\),容易证明这样走是最优的。那么现在只需要把两段的最短路径数量分别求出......