首页 > 其他分享 >E - Remove Pairs(状压dp+博弈论)

E - Remove Pairs(状压dp+博弈论)

时间:2024-05-22 18:58:34浏览次数:22  
标签:Pairs 21 int 状压 Remove tie dp

 

思路:

容易发现,我们取走一张牌后:

如果下一步的人必败,则这一步的人必胜,因为可以走这个状态。反之,这个人必败。

代码:

#include <bits/stdc++.h>
using namespace std;
int n, a[21], b[21], f[2000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for (int S = 0; S <= ((1 << n) - 1); S++)//状压dp
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (!(S & (1 << i - 1)))
                    if (!(S & (1 << j - 1)))//两张牌都没选才能 dp
                        if (a[i] == a[j] || b[i] == b[j])
                            if (!f[S])   //如果当前状态的上一个状态为先手必败,那么可以转移,因为上次必败,那么这次先手必胜。
                                f[S | (1 << i - 1) | (1 << j - 1)]++;
    if (!f[(1 << n) - 1])//判断是否先手必胜
        cout << "Aoki";
    else
        cout << "Takahashi";
}

 

标签:Pairs,21,int,状压,Remove,tie,dp
From: https://www.cnblogs.com/litianyu1969/p/18206908

相关文章

  • 提升WordPress网站加载速度的8个小技巧
    提升WordPress网站加载速度是至关重要的,它不仅可以提高用户体验,还有助于SEO排名。以下是提升WordPress网站加载速度的8个小技巧,希望能帮助到大家。优化图片:使用适当大小和格式的图片。利用插件(如Smush或EWWWImageOptimizer)对图片进行压缩。启用缓存:使用WordPress缓存......
  • 决策单调性优化DP
    @目录决策单调性四边形不等式决策单调性形式1法1分治法2二分队列例题P3515Solution形式2例题P3195Solution形式3例题CF833BSolution形式4例题Solution后话同步发表于CSDN决策单调性四边形不等式定义:对于二元函数\(w(x,y)\),若\(\foralla,b,c,d\in\mathbb{Z}\),且\(a......
  • 三次握手和四次挥手、UDP、TCP、粘包问题、模块回顾
    【一】三次握手和四次挥手【1】TCP协议的三次握手和四次挥手TCP协议位于osi七层协议中的传输层(1)使用三次握手来建立连接一次握手:客户端发送带有SYN(SEQ=x)标志的数据包---》服务端,然后客户端进入SYN_SEND状态,等待服务器的确认。二次握手:服务端发送带有SYN+A......
  • m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码率
    1.算法仿真效果matlab2022a仿真结果如下:   2.算法涉及理论知识概要      低密度奇偶校验码(Low-DensityParity-CheckCode,LDPC码)是一种高效的前向纠错码,广泛应用于无线通信、数据存储等领域。BP(BeliefPropagation)译码算法,又称为消息传递算法,是LDPC码最常用......
  • EDP .Net开发框架--自动化日志
    平台下载地址:https://gitee.com/alwaysinsist/edp自动化日志不需要额外调用日志相关功能即可无感实现程序集方法调用的日志记录。创建业务逻辑处理类publicclassStudentBLL:BusinessLogicBase<StudentBLL>继承基类BusinessLogicBase<T>定义业务逻辑方法点击查看代......
  • 树形DP
    树形DP即在树上进行的DP。常见的两种转移方向:父节点\(\rightarrow\)子节点:如求节点深度,\(dp_u=dp_{fa}+1\)子节点\(\rightarrow\)父节点:如求子树大小,\(dp_u=1+\sumdp_v\)习题:P5658[CSP-S2019]括号树暴力本题\(n\)小的数据点保证为链,直接枚举\(i\),代......
  • CF Div. 3 C Beautiful Triple Pairs
    原题链接标签组合数学(combinatorics)数据结构(datastructures)题目大意一个数组\(a\)。对于每个\(j\)(\(1\lej\len-2\))写出一个由\([a_j,a_{j+1},a_{j+2}]\)组成的三元组。满足以下条件之一,那么这对三元组就是美丽的:\(b_1\nec_1\)和\(b_2=c_2\)......
  • EDP .Net开发框架--WebApi
    平台下载地址:https://gitee.com/alwaysinsist/edp按分类管理EDP所提供的WebApi接口,以供其他应用调用。WebApi接口不仅可以进行访问控制管理,同时还提供了版本管理,同一WebApi接口支持多个不同版本以满足接口调用方的多版本支持。WebApi接口的数据是通过调用业务方法来获取的,而业......
  • DP32RF002 是深基于 ARM Cortex-M0+内核的超低功耗、高性能的、单片集成 (G)FSK/OOK
    产品简介DP32RF002是深基于ARMCortex-M0+内核的超低功耗、高性能的、单片集成(G)FSK/OOK无线收发机的32位SoC芯片。工作于200~960MHz范围内,支持灵活可设的数据包格式,支持自动应答和自动重发功能,支持跳频操作,支持FEC功能,同时内部集成了完整的射频接收机、射频发射机......
  • EDP .Net开发框架--业务模型
    https://www.cnblogs.com/alwaysinsist/p/18190582 业务模型管理中所涉及的业务模型,业务模型的属性,业务模型的视图都是可以通过权限设置来实现数据的行(视图),列(属性)权限管控。业务模型是整个EDP平台的核心基础,数据的查询、新增、修改、删除、行列权限都是通过业务模型来实现的。......