ABC278 F - Shiritori

不懂博弈和状压DP,今晚加训状压DP!

博弈太难了,东西太多了,等蓝桥杯打完再说QwQ

F - Shiritori (atcoder.jp)

题意:

思路:

注意到数据范围是到16,因此可以考虑状压DP

状态设计:(考虑影响决策的因素+转移的特殊性质+记录答案)

因为要字符串头和另一个字符串的尾相同才转移,因此需要记录最后一个选的是第几个

设dp[i][j]表示选的情况为i,最后一次选的是第j个

然后去考虑SG函数

遍历后面的状态,如果有一个为必败态,那么该状态就是必胜态

如果后面的状态全是必胜态,那么该状态就是必败态

因此我们需要倒着考虑状态

然后在枚举状态和决策的时候注意把不符合条件的状态筛去

Code:

#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int mxn=3e2+10;
const int mxe=2e5+10;

string s[mxn];
int n,dp[1<<16][30];
void solve(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=(1<<16)-1;i>=1;i--){
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                for(int k=0;k<n;k++){
                    if((i>>k)&1) continue;
                    int p=i|(1<<k);
                    if(s[j].back()==s[k][0]&&dp[p][k]==0) dp[i][j]=1;
                }
            }
        }
    }
    int ok=0;
    for(int i=0;i<n;i++){
        if(dp[(1<<i)][i]==0) ok=1;
    }
    if(ok) cout<<"First"<<'\n';
    else cout<<"Second"<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int __=1;//cin>>__;
    while(__--)solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/2584.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java-Collections and Lambda

Java SE API know how 集合API 根据算法访选择合适集合 linkedlist不适合搜索 随机访问数据用hashmap 数据保持有序使用treemap 通过索引访问使用数组集合 同步和非同步 访问性能统计 与简单的非同步访问相比&#xff0c;使用任何数据保护技术都会有较小的损失 设置集合…

AI绘画关键词网站推荐 :轻松获取百万个提示词!完全免费

一、lexica.art 该网站拥有数百万Stable Diffusion案例的文字描述和图片&#xff0c;可以为大家提供足够的创作灵感。 使用上也很简单&#xff0c;只要在搜索框输入简单的关键词或上传图片&#xff0c;就能为你提供大量风格不同的照片。点击照片就能看到完整的AI关键词&#…

利用客户支持建立忠诚度和竞争优势

客户支持可以极大地改变您的业务;最细微、最微妙的差异都会使拥有一次性客户和拥有终身客户之间产生差异。在这篇博文中&#xff0c;我们将揭示客户对企业的忠诚度的三种核心类型&#xff0c;以及如何利用强大的客户支持工具和原则来提高理想的忠诚度并获得决定性的竞争优势。一…

11.12安全进阶:SSH实验配置指导

实验拓扑 实验需求 完成PC及交换机的配置,使得PC能够通过SSH的方式登录到交换机。 实验步骤及配置 交换机完成基础配置 [SW] interface Vlanif 1 [SW-Vlanif1] ip address 192.168.1.100 24简单起见,我们就直接使用VLAN1与PC对接,因此将交换机的IP地址配置在Vlanif1 交换机…

第16天-性能压测:压力测试,性能监控,优化QPS,Nginx动静分离

1.性能监控 1.1.JVM架构 运行时数据区&#xff1a; 方法区&#xff1a;最重要的内存区域&#xff0c;多线程共享&#xff0c;保存了类的信息&#xff08;名称、成员、接口、父类&#xff09;&#xff0c;反射机制是重要的组成部分&#xff0c;动态进行类操作的实现&#xff1b;…

[排序算法]堆排序

参考&#xff1a;《漫画算法-小灰的算法之旅》 目录 一、堆排序过程 二、堆排序的代码实现 三、时间复杂度和空间复杂度 四、从宏观上看&#xff0c;堆排序和快速排序相比&#xff0c;有什么区别和联系呢 回顾二叉堆&#xff1a; 1.最大堆的堆顶是整个堆中的最大元素。 2…

基于SpringBoot的外卖项目(详细开发过程)

基于SpringBootMyBatisPlus的外卖项目1、软件开发整体介绍软件开发流程角色分工2、外卖项目介绍项目介绍产品展示后台系统管理移动端技术选型功能结构角色3、开发环境的搭建开发环境说明建库建表Maven项目搭建项目的目录结构pom.xmlapplication.ymlReggieApplication启动类配置…

[JAVA]继承

目录 1.继承的概念 2.继承的语法 3.父类成员访问 3.1子类中访问父类成员变量 3.2子类中访问父类成员方法 4.super关键字 5.子类构造方法 6.继承方式 7.final关键字和类的关系 面向对象思想中提出了继承的概念&#xff0c;专门用来进行共性抽取&#xff0c;实现代码复…

2023年顶级编程语言趋势

对于开发人员和软件工程师来说&#xff0c;选择更优秀的编程语言使编写可以在任何地方运行的软件变得更加容易&#xff0c;工作效率更高。从 Java 的缓慢衰落到 MATLAB 的惊人流行&#xff0c;对当今最流行的编程语言的分析&#xff0c;可以帮助你了解最新趋势并响应最新趋势。…

总结:K8S运维常用命令

一、部署./kubectl apply -f biz-healing-pod.yaml 二、查看部署的资源1、podkubectl get pod -A&#xff1a;获取所有pod没有IP&#xff1f;用-o wide参数看详细信息&#xff1a;./kubectl get pod -n deepflow -o wide2、service查看hubble-manager命名空间下有哪些service/d…

Excel函数公式大全—函数真经

EXCEL系列文章目录 Excel系列文章是本人亲身经历职场之后萌发的想法&#xff0c;为什么Excel覆盖如此之广&#xff0c;几乎每个公司、学校、家庭都在使用&#xff0c;但是它深藏的宝藏功能却很少被人使用&#xff0c;PQ、BI这些功能同样适用于数据分析&#xff1b;并且在一些需…

ViewService——一种保证客户端与服务端同步的方法

简介在分布式系统中&#xff0c;最常见的场景就是主备架构。但是如果主机不幸宕机&#xff0c;如何正确的通知客户端当前后端服务器的状况成为一个值得研究的问题。本文描述了一种简单的模型用于解决此问题。背景以一个分布式的Key-Value数据库为背景。数据库对外提供3个接口Ge…

有哪些计算机网络和通讯领域的SCI期刊推荐? - 易智编译EaseEditing

IEEE/ACM Transactions on Networking: 这是由IEEE和ACM联合出版的计算机网络领域的顶级期刊&#xff0c;涵盖了网络协议、体系结构、性能评估、网络管理、安全等多个方面。 Computer Networks: 这是一本综合性的计算机网络期刊&#xff0c;包括分布式系统、网络协议、移动计…

Spring注册Bean的方式

文章目录一、xml方式注册Bean二、ConfigurationBean注册Bean三、ComponentScan注册Bean1. 使用XML文件配置包扫描2. 使用注解配置包扫描3. ComponentScans源码4. ComponentScan源码5. ComponentScan value includeFilters6. ComponentScan value excludeFilters7. Componen…

rabbitMQ介绍及使用方法

目录 一、MQ概述 二、RabbitMQ简介 三、RabbitMQ的五种工作模式 1、简单模式 2、work queues工作队列模式 3、Pub/Sub 订阅模式 4、Routing 路由模式 5、Topics 通配符模式 一、MQ概述 MQ全称Message Queue (消息队列)&#xff0c;是在消息的传输过程中保存消息的容器…

电商项目后端框架SpringBoot、MybatisPlus

后端框架基础 1.代码自动生成工具 mybatis-plus &#xff08;1&#xff09;首先需要添加依赖文件 <dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.2.2</version></dependency><de…

【linux】进程信号——信号的产生

进程信号一、信号概念1.1 信号理解二、产生信号2.1 通过键盘产生信号2.2 捕捉信号自定义signal2.3 系统调用接口产生信号2.3.1 向任意进程发送任意信号kill2.3.2 给自己发送任意信号raise2.3.3 给自己发送指定信号abort2.3.4 理解2.4 硬件异常产生信号2.4.1 除0异常2.4.2 野指针…

蓝桥杯刷题冲刺 | 倒计时17天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.长草2.分考场1.长草 题目 链接&#xff1a; 长草 - 蓝桥云课 (lanqiao.cn) 题目描述 小明有一…

Feign远程调用

之前在一篇博客中写了利用RestTemplate发起远程调用的代码&#xff0c;但是存在一下问题&#xff1a;代码可读性差&#xff0c;编程体验不统一&#xff1b;如果参数特别多的话&#xff0c;参数复杂URL难以维护。Feign官方地址&#xff1a;https://github.com/OpenFeign/feignFe…

行业观察 | 来了解一下AI加速器

本文参考网上可查询到的资料简要总结AI加速器的概念和应用等信息 1。 未完待续 更新&#xff1a; 2023 / 3 / 22 行业观察 | 来了解一下AI加速器前言加速器处理器处理器是什么&#xff1f;处理器进化史加速器架构指令集 ISA特定领域的指令集 ISA超长指令字&#xff08;VLIW&a…
最新文章