Codeforces 1704 F Colouring Game 题解 (结论,SG函数)

题目链接

首先看R和B的数量不等的情况(很多博弈题都是先比较两种物品的数量,相等的情况再用SG函数之类的技巧),结论是R多Alice必赢,B多Bob必赢。证明:来看R比B多的情况,定义两人的"差距"为当前R的数量减B的数量。发现Alice操作只可能让差距不变或变小,Bob操作只可能让差距不变或变大。定义"一轮游戏"为Alice先操作一次,Bob再操作一次的过程。如果一轮开始前还有"RB"或"BR",那么Alice就随便找一个RB或BR涂了,这一轮差距就肯定不会变小,Alice仍然保持领先;如果没有RB或BR,就看有没有RW或WR,如果有就随便找一个涂了,由于此时没有RB、BR所以Bob也只能涂BW和WB,因此差距仍然不会减小;只有RR的情况是不存在的,除非整个序列全是R,但是这种情况Alice本来就会赢。对于B比R多的情况也是类似(Alice第一次操作后B显然还比R多,所以就变成和上面一样的情况了)。

R和B相等的情况,两人都只能涂RB或BR,否则会导致R和B不相等,根据上面的结论操作这步的人就输了。所以问题变成:两个人每次可以挑相邻的两个RB或BR涂白,不能操作的人输。把序列分成若干段,每段都是极长的RBRBRB交错的区间。被涂的位置肯定是被完全包含在某个段内部,不可能横跨两个段的,因为这样不可能是RB或BR。发现每一段的内部都构成了一个公平的有向图游戏,可以对每一段求SG函数再异或起来得到答案。一个长为i的段的SG函数为:\(sg_i=mex_{l+r=i-1}(sg_l\bigoplus sg_r)\),其中\(\bigoplus\)表示异或。这玩意儿看上去像卷积,但其实不太能用多项式技巧求。正确的求法居然是:sg值除了前几项,后面的均以34为循环节,所以暴力求出前若干项(比如1000)就行了。真的是很无聊(不知道这题怎么过cf审核的),但是也要了解一下,防止以后再出现这种题。

点击查看代码
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int sg[500010];

int dfs(int pos)
{
  if(sg[pos]>-1) return sg[pos];
  if(pos<2) return sg[pos]=0;
  map <int,int> mp;
  rep(i,pos-1)
  {
    int l=i,r=pos-l-2;
    int val=dfs(l)^dfs(r);
    mp[val]=1;
  }
  rep(i,1000) if(mp.find(i)==mp.end()) return sg[pos]=i;
}

int t,n;
string s;
char c[500010];

int main()
{
  fileio();

  rep(i,1005) sg[i]=-1;
  dfs(1000);
  for(int i=1001;i<=500005;++i) sg[i]=sg[i-34];
  cin>>t;
  rep(tn,t)
  {
    scanf("%d%s",&n,c);s=c;
    int cr=0,cb=0;
    rep(i,n) if(s[i]=='R') ++cr;else ++cb;
    if(cr>cb) puts("Alice");
    else if(cb>cr) puts("Bob");
    else
    {
      int ans=0;
      rep(i,n)
      {
        int p=i;
        while(p+1<n&&s[p+1]!=s[p]) ++p;
        ans^=sg[p-i+1];i=p;
      }
      puts(ans ? "Alice":"Bob");
    }
  }

  termin();
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 在 SwiftUI 中用 zIndex 调整视图显示顺序

    本文将对SwiftUI的zIndex修饰符做以介绍,包括:使用方法、zIndex的作用域、通过zIndex避免动画异常、为什么zIndex需要设置稳定的值以及在多种布局容器内使用zIndex等内容。访问我的博客www.fatbobman.com[1]可以获得更好的阅读体验zIndex修饰符在SwiftUI中,开发者使用zIndex修饰符来控制重叠视图间的显示顺序,具有较大zIndex值的视图将显示在具有较小zIndex值的视图之上。在没有指定zIndex值的时候,SwiftUI默认会给视图一个为0的zIndex值。ZStack{ Text("Hello")//默认zIndex值为0,显示在最后面 Text("World") .zIndex(3.5)//显示在最前面 Text("Hi") .zIndex(3.0) Text("Fat") .zIndex(3.0)//显示在Hi之前,相同zIndex值,按布局顺序显示 } 复制可以在此处获取本文的全部代码[2]zIndex的作用域zIndex的作用范围被限

  • 微服务接口的防刷、防重、限量应该如何设计?

    安全兜底分级:无限额涉及钱 比如退款限额涉及钱 为用户提供的红包奖励等,通常限额无门槛虚拟货币 无门槛优惠券、积分等,由于这部分基本与货币可以等值,但是由于存在可以追回的机会,所以尚存一些容错)有门槛虚拟货币 因为是为了促销,并不会带来实质经济损失,所以没有那么敏感分级之后,再进一步划分处理的级别。因为人力和时间都是有限的,很难将所有的安全兜底都控制的那么完美,那就优先保证一些损失影响可能较大的业务上。权重更高的业务,可以予以更严谨的测试,以及附加的人工审核机制,更频繁的监控等。相对权重较低的,就可能重视程度不那么高,仅保留较低限度的兜底。安全第一步,防刷 最常见的短信验证码服务,由于是注册用,所以无需登录就能调用。若发短信接口无任何保护措施,直接调用三方短信通道,很容易被短信轰炸平台滥用。那么,如何防刷? 验证额外参数信息 验证客户端请求头的一些额外参数,比如是否存在浏览器或手机型号、设备分辨率请求头。因为像那些爬虫,一般就只能接收到URL。先过注册页 无论何种客户端注册,一定要先进入注册页,才能看到验证码按钮。 所以可以在页面打开时请求固定的前置接口,为这个设备开启允许发送验证码的

  • python测试开发django-139.Bootstrap 中关于图片的显示

    前言在设置个人头像的时候,可以显示原型图片,也可以显示方形图片,Bootstrap提供了三个可对图片应用简单样式的class:.img-rounded: 添加border-radius:6px来获得图片圆角。.img-circle: 添加border-radius:50%来让整个图片变成圆形。.img-thumbnail: 添加一些内边距(padding)和一个灰色的边框。.img-responsive图片响应式(将很好地扩展到父元素)div添加图片显示在div区放一张图片时<divclass="container"> <divclass="row"> <divclass="col-md-3col-xs-3"style="background-color:#5e5e5e"> 第1块div </div> <divclass="col-md-3col-xs-3"style="background-color:#d43d49&qu

  • 【Java核心面试宝典】Day6、面向对象常见面试题汇总(一)

    Hello,你好呀,我是灰小猿!一个超会写bug的程序猿! 用坚持缔造技术、用指尖敲动未来! 和很多小伙伴们一样,我也是一名奔波在Java道路上的“创造者”。也想靠技术来改未来,改变世界!因为我们坚信每一次敲动键盘都能让生活变得更智能、世界变得更有趣! 在此专栏《Java核心面试宝典》记录我们备战梦想的【day6】! 今天来和小伙伴们记录有关于面向对象的一些面试题,一部分是LeetCode上比较经典且最常见的面试题。 一、面向对象和面向过程的区别有哪些?分别有什么优缺点?面向过程是将问题分解成步骤,按照步骤实现函数,并依次调用,数据和数据的实现是分离的, 而面向对象是将问题分解成对象,描述事物在解决问题的步骤中的行为,对象与属性和行为是关联的。面向过程的优点:性能方面比面向对象高,不需要面向对象的实例化, 面向过程的缺点:因为是按照步骤实现函数并依次调用的,因此不容易复用、维护和扩展。 面向对象的优点:具有封装、继承和多态的特征,因而易于维护、扩展和复用。可以设计出低耦合的系统。 面向对象的缺点:由于需要实例化对象,因此性能方面比面向过程低。 二、对象和类之间有哪些联系?对象是对类的实

  • Python selenium使用autoIT上传附件过程详解

    1.首先打开AutoItWindowsInfo工具,鼠标点击FinderTool(按住左键不松手),鼠标将变成一个小风扇形状的图标,移动到目标控件上;如图2.通过AutoItWindowsInfo获得以下信息。窗口的title为“打开”,标题的Class为“#32770”。文件名输入框的class为“Edit”,Instance为“1”,ClassnameNN为“Edit1”。打开按钮的class为“Button”,Instance为“1”,所以ClassnameNN为“Button1”。3.编写脚本(因为IE、Chrome、FireFox文件上传的左上角位置title不一致,所以我们坐下适配) 编写工具:SciTEScriptEditor应用程序4.转换成exe文件:打开autoit安装目录下的应用程序:CompileScriptto.exe(x86)或者CompileScriptto.exe(x64)5.在selenium中的调用:以上就是本文的全部内容,希望对大家的学习有所帮助。

  • 呆滞物料,你真的会处理吗?

    导读:仓库管理是企业管理中不可缺少的一部分,事关企业能否正常运行的关键之一,古人有云:“三军未动粮草先行”。一个企业仓库作业效率的高低,影响到企业的是否按时交货,进而影响公司信誉。仓库,是中小企业企业资产管理的重要部门。如何提高仓库效率呢?总结了18条投资小见效快的方法,这些方法在中小企业是非常容易做到的。1、制定作业规范,测量关键作业指标仓库员工接受作业规范培训后,根据关键作业指标,管理人员要观察培训效果是否达标。根据“霍桑效应”理论,如果员工知道他们正在被观察,他们会提高生产效率。2、每天的工作负荷努力做到均衡化,降低波动性仓库每天的工作量波动性非常大,努力做到均衡化。达到这个目标确实非常困难,但是我们也要“尽人事”。每年的“双11”,是电商、物流的噩梦,现在有些电商采取“优惠提前,延长打折天数”的方案,这就是朝着工作均衡化的方向努力。3、坚持“三现主义”仓库管理者每天70--80%的时间要在工作现场观察,流程是否落地?是否有更好、更快的作业技巧?员工的士气如何?坚持“现场、现物、现实”,观察工作场所中的浪费,然后想办法减少、消除浪费。4、减少走动距离造成仓库效率低下的主要原因之一

  • 【程序源代码】《Spring Boot开发笔记系列》第一节总结

    关键字:Springboot开发笔记 各位亲爱的小伙伴:大家,上午好!《SpringBoot开发笔记系列》;这套笔记和源码是我自己在学习springboot开发中实际一个字一个字敲出来的。《SpringBoot开发笔记》第一个总结(四)pom文件的研究parent父项目spring-boot-dependencies它是真正管理springboot应用;其实可以说理解成它来管理所有的依赖。可以把它理解成springboot的管理中心。spring-boot-starter场景启动器;帮我们导入了web模块正常运行所依赖的组件;Springboot将所有的功能场景都抽取出来做成一个个的starters启动器,只需要在项目里面引入这些场景依赖就可以了;也就是说需要什么功能的时候就引入什么功能就可以了。这是一种开箱即用的思想;(五)类文件的研究SpringBootApplication其实是一个组合注解,它用来标在类上说明书这个类是springboot的主配置类,springboot就应用于运行这个类的main方法来启动springboot应用;SpringBootConfiguration

  • 干货 | 写好Java代码的30个技巧

    成为一个优秀的Java程序员,有着良好的代码编写习惯是必不可少的。下面就让我们来看看代码编写的30条建议吧。(1)类名首字母应该大写。字段、方法以及对象(句柄)的首字母应小写。对于所有标识符,其中包含的所有单词都应紧靠在一起,而且大写中间单词的首字母。例如:ThisIsAClassNamethisIsMethodOrFieldName若在定义中出现了常数初始化字符,则大写staticfinal基本类型标识符中的所有字母。这样便可标志出它们属于编译期的常数。Java包(Package)属于一种特殊情况:它们全都是小写字母,即便中间的单词亦是如此。对于域名扩展名称,如com,org,net或者edu等,全部都应小写(这也是Java1.1和Java1.2的区别之一)。(2)为了常规用途而创建一个类时,请采取”经典形式”,并包含对下述元素的定义:equals()hashCode()toString()clone()(implementCloneable)implementSerializable(3)对于自己创建的每一个类,都考虑置入一个main(),其中包含了用于测试那个类的代码。为使用一个

  • Apache优化——日志管理 原

    11.22访问日志不记录静态文件编辑虚拟主机配置文件“httpd-vhosts.conf”: [root@adailinux~]#vim/usr/local/apache2.4/conf/extra/httpd-vhosts.conf …… <VirtualHost*:80>   DocumentRoot"/data/wwwroot/111.com"   ServerName111.com   ServerAliaswww.example.com   <IfModulemod_rewrite.c>     RewriteEngineon     RewriteCond%{HTTP_HOST}!^111.com$     RewriteRule^/(.*)$http://111.com/$1[R=301,L]   </IfModule>   ErrorLog"logs/111.com-error_log"   SetEnvIfRequest_URI".*\.gif$"img   SetEnvI

  • c语言_头文件

    传统C++1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17#include<assert.h>//设定插入点 #include<ctype.h>//字符处理 #include<errno.h>//定义错误码 #include<float.h>//浮点数处理 #include<fstream.h>//文件输入/输出 #include<iomanip.h>//参数化输入/输出 #include<iostream.h>//数据流输入/输出 #include<limits.h>//定义各种数据类型最值常量 #include<locale.h>//定义本地化函数 #include<math.h>//定义数学函数 #include<stdio.h>//定义输入/输出函数 #include<stdlib.h>//定义杂项函数及内存分配函数 #include<string.h>//字符串处理 #include<

  • Spark详解05架构Architecture架构

    架构前三章从job的角度介绍了用户写的program如何一步步地被分解和执行。这一章主要从架构的角度来讨论master,worker,driver和executor之间怎么协调来完成整个job的运行。实在不想在文档中贴过多的代码,这章贴这么多,只是为了方面自己回头debug的时候可以迅速定位,不想看代码的话,直接看图和描述即可。 部署图重新贴一下Overview中给出的部署图:deploy接下来分阶段讨论并细化这个图。Job提交下图展示了driverprogram(假设在masternode上运行)如何生成job,并提交到workernode上执行。JobSubmission.pngDriver端的逻辑如果用代码表示:finalRDD.action() =>sc.runJob() //generatejob,stagesandtasks =>dagScheduler.runJob() =>dagScheduler.submitJob() =>dagSchedulerEventProcessActor!JobSubmitted =>dagScheduler

  • dotnet6的R2R技术,加速程序的第一启动

    R2R技术是微软为了加速程序的启动,而进行的一种Native头编译行为。主要是把函数编译的结果,存储在IL代码的结尾处(也就是Native头处),这样在第一次启动的时候,就可以直接调用这个结果,而不用经过RyuJit来进行繁琐的编译过程,加速了启动的速度。在dotnet6里面R2R技术有两种部署方式: 一:在项目的csproj文件里面添加如下xml代码<PropertyGroup> <PublishReadyToRun>true</PublishReadyToRun> </PropertyGroup>复制二:直接用命令行生成R2R结果dotnetpublish-cRelease-rwin-x64复制以上是R2R编译技术的一个方法,实际上微软的高度封装导致了这些东西用法非常简单,但是实际上背后的原理非常复杂而且晦涩难懂。 三:原理简要剖析R2R技术的一个主要功能就是存储函数编译的结果,下次直接调用。首先是需要知道这个函数编译结果的偏移地址(offset),因为函数的结果在IL代码的尾部,所以需要知道IL代码的头地址(ILHeader)。 在

  • 树莓派:设置与软件安装

    作者:Vamei,严禁任何形式转载。    拿到树莓派后,你需要进行一些初始化设置,以便于用起来更方便。除此之外,你可能需要安装一些软件,以便树莓派能实现更加强大的功能。   常见初始化设置 1)设置密码: 树莓派的默认用户名是pi,没有密码。这意味着别人可以随意使用你的树莓派。你可以在终端中为pi用户设置密码:  $sudopasswdpi复制   2)拓展文件系统 一开始的Raspbian镜像只有4G。这意味着你的树莓派也只会使用SD卡上4G的空间。如果SD卡有16G大小,那么就浪费了12G的空间。为此,我们可以让Raspbian的文件系统扩展到整张SD卡。你可以进入树莓派的图形化设置页面设置。在终端输入: $sudoraspi-config复制 然后在图形化页面中操作:   或者,你也可以用一整行命令来代替图形化操作,把Raspbian拓展到整张SD卡上: $sudoraspi-config--expand-rootfs复制   3)设置LOCALE 打开终端时,终端有可能提醒你Locale未设置

  • 函数指针和函数指针类型

    函数指针 1.     定义 每一个函数都占用一段内存单元,它们有一个起始地址,指向函数入口地址的指针称为函数指针。 注意:函数指针的本质是一个指针变量,且指针指向的函数的入口地址 2.     语法 指向函数的指针变量的一般定义形式为:     数据类型  (*指针变量名)  (参数表); 3.     说明 函数指针定义形式中的数据类型是指函数的返回值的类型。 区分下面两个语句: int(*p)(inta,intb); //p是一个指向函数的指针变量,函数返回类型为整型 int*p(inta,intb);   //p是函数名,函数返回类型为整型指针 函数指针指向的变量不是固定的某一个函数的,只是定义了一个变量专门用来存放函数的入口地址的;在程序中把哪一个函数的地址赋给它,它就指向哪一个函数。 在给函数指

  • nodejs抓取12万壁纸图片

    这两天刚换了linux系统,一直感觉自带的桌面图片有限而且不是特别“性感”,决定去弄几张图片回来当桌面壁纸,搜索了一下壁纸站点,觉得zol的还不错,分类清晰,壁纸质量上乘,就决定下载几张,但是网站繁琐的导流量页面导致下载一个图片非常繁琐和缓慢,而且效率太低下了,作为码农怎么能忍,分析一下,给他来个一锅端,12万的壁纸,尽收硬盘中。好了,上边的就是需求的描述了,下边是干货抓取过程。 1.开发环境Nodejs。环境搭建就不累述了,知道的去nodejs官网自己简单科普一下就好了。传送到nodejs官网 2.手把手过程 2.1初始化工程    #新建个项目目录 mkdirzol_desk #进入项目目录 cdzol_desk #初始化npm npminit #一路回车知道完成 #安装crawler工具 npminstallcrawler--save #安装个lodash工具,有可能会用到,处理数据方便一些。 npminstalllodash--save #创建个list.js文件,用来抓取列表数据 touchlist.js 复制 2.2list.js内容 1constfs=require

  • uri和url的区别

      URL(UniformResourceLocator):统一资源定位符 顾名思义,URL就是一个表示资源位置的字符串,基本的URL格式为"协议://IP地址/路径和文件名",如:ftp://ftp.is.co.za/rfc/rfc1808.txt 最重要的一点,URL对于我们而言,就是将URL输入到浏览器地址栏上就可以访问到对应资源。 URI(Uniform Resource Identifier):统一资源标识符 “AUniformResourceIdentifier(URI)是一个紧凑的字符串用来标示抽象或物理资源”,来自RFC中的定义。可以看出其和URL的目的是相同的,都是通过使用字符串来标示资源,这样看来,像开头绿色字体部分的字符串似乎并不能完整标识资源。  

  • kvm虚拟化网络管理

    brctladdif br1ens37 将网口添加到网桥 brctldelif br1ens37 删除   brctlshow 显示当前网桥连接状态 一、Linux Bridge 实现 VLAN   1、查看核心是否提供VLAN功能 dmesg| grep-i802 检查/proc/net/vlan 目录是否存在 如果没有提供VLAN功能,/proc/net/vlan目录是不存在的 安装查看用于查看VLAN配置的工具------vconfig 提前准备好vconfig-1.9-16.el7.x86_64.rpm rpm-ivh vconfig-1.9-16.el7.x86_64.rpm rpm-qavconfig (安装完成即会出现vlan目录)   如果8021q模块没有载入系统,则可以通过使用modprobe模组命令载入 802.1q模组,並且利用lsmod命令确认模组是否已经载入到核心内。 modprobe8021q lsmod| 

  • linux撤销命令编辑文档打错了怎么撤销

    linux撤销命令   u撤销上一步操作 ctrl+r恢复上一步被撤销的操作

  • 元素居中的两种方法,transform和margin

    1.transform:translate(-50%,-50%) <!DOCTYPEhtml> <htmllang="en"> <head> <metacharset="UTF-8"> <metaname="viewport"content="width=device-width,initial-scale=1.0"> <metahttp-equiv="X-UA-Compatible"content="ie=edge"> <title>Document</title> <style> body, html{ width:100%; height:100%; margin:0; padding:0 } .box{ width:100%; height:100%; background:red } .div1{ width:200px; height:200px; background:black; position:absolute; left:50%; top:50%;

  • 高性能最终一致性框架Ray之基本功能篇

    一、Event(事件) Event是Actor产生的记录状态变化的日志,由StateId(状态Id),UID(幂等性控制),TypeCode(事件类型),Data(事件数据),Version(事件版本),Timestamp(时间戳)组成。   持久化:Ray提供Mongodb、Postgresql、Sqlserver、Mysql的拓展支持,可以单独使用其中一个,也可以混合使用。   EventBus:当Event持久化之后进行分发以驱动后续业务流程、同步到读库以及自定义消费者,目前支持RabbitMQ和Kafka的拓展。   订阅:基于Ray提供的ObserverGrain、ShadowGrain的订阅者不依赖于EventBus的可靠性和有序性,框架会对Event的顺序进行校验,对丢失的Event进行恢复,自定义订阅者只能用来执行对Event可靠性要求不高的任务。     ObserverGrain:订阅Event执行后续流程和同步到读库。     ShadowGrain:订阅Event执行后续流程,但流程需要用到实时状态。 二、State(状态) State是一个聚合对象(等价DDD

  • 【基础组件19】redis入门(一)简介、哨兵模式、集群搭建、常用命令、性能高可用、高并发概述

    哨兵模式,集群搭建参考: https://blog.csdn.net/yangshangwei/article/details/82899159  (主要看这个) https://blog.csdn.net/q649381130/article/details/79931791 https://blog.csdn.net/xujiamin0022016/article/details/82194616 redis简介参考: https://blog.csdn.net/middleware2018/article/details/80355418 redis教程参考: https://www.bilibili.com/video/av49517046?p=2   一、redis简介 1.redis是一个完全开源免费的,高性能的、NoSQL的、key-value数据库,可基于内存,亦可持久化的key-value数据库   redis有0-15共16个数据库,连接客户端后,若不选择数据库,则默认在数据库0     

相关推荐

推荐阅读