今日总结2024/5/27
今日学习了状态压缩DP,状态压缩DP分为棋盘型(基于连通性)和集合型
Acwing.1064 小国王
在 n×n的棋盘上放 k个国王,国王可攻击相邻的 8个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n和 k。
输出格式
共一行,表示方案总数,若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n^2
每一行的状态都由上一行来决定,因此要分别枚举上一行状态和下一行状态来判断是否能合法转移,再进行计算,因此要将能合法转移的状态进行预处理,(a&b)==0代表二者不能出现在同一列,a|b不能出现连续的1代表二者不能不能出现在相邻的列
#include <bits/stdc++.h>
using namespace std;
//把一堆方案归类成一类来划分集合
//int f[i][j][s] 前i行放完,放了j个棋子,最后一行状态为s(二进制)属性为count方案数
const int N=12,M=1<<10,K=110;
int n,m,cnt[M];
long long f[N][K][M];//要开longlong不然会爆int
vector<int> h[M];
vector<int> state;bool check(int u){for(int i=0;i<n;i++)if((u>>i&1)&&((u>>i+1)&1))return false;return true;
}int count(int u){int res=0;for(int i=0;i<n;i++)if(u>>i&1) res++;return res;
}int main(){cin>>n>>m;for(int i=0;i<1<<n;i++)if(check(i)){state.push_back(i);//将合法的一行状态放入cnt[i]=count(i);}for(int i=0;i<state.size();i++)for(int j=0;j<state.size();j++){int a=state[i],b=state[j];//处理好i-1到i的映射关系if((a&b)==0&&check(a|b))h[i].push_back(b);//一定要是下标映射,不同方案的十进制可能相等}f[0][0][0]=1;for(int i=1;i<=n+1;i++)for(int j=0;j<=m;j++)for(int k=0;k<state.size();k++){int a=state[k],c=cnt[a];for(auto b:h[k])if(j>=c)//一定要大于放的f[i][j][a]+=f[i-1][j-c][b];}cout<<f[n+1][m][0];//第n+1行的状态为0return 0;
}
相关文章:
今日总结2024/5/27
今日学习了状态压缩DP,状态压缩DP分为棋盘型(基于连通性)和集合型 Acwing.1064 小国王 在 nn的棋盘上放 k个国王,国王可攻击相邻的 8个格子,求使它们无法互相攻击的方案总数。 输入格式 共一行,包含两个整数 n和 k。 输出格式 共一行&…...
使用 Snort 进行入侵检测
使用 Snort 进行入侵检测 Snort 是一种流行的开源入侵检测系统。您可以在http://www.snort.org/上获取它。Snort 分析流量并尝试检测和记录可疑活动。Snort 还能够根据其所做的分析发送警报。 Snort 安装 在本课中,我们将从源代码安装。此外,我们不会安…...
C++ | Leetcode C++题解之第116题填充每个节点的下一个右侧节点指针
题目: 题解: class Solution { public:Node* connect(Node* root) {if (root nullptr) {return root;}// 从根节点开始Node* leftmost root;while (leftmost->left ! nullptr) {// 遍历这一层节点组织成的链表,为下一层的节点更新 next…...
计算机网络学习
文章目录 第一章信息时代的计算机网络因特网概述电路交换,分组交换,报文交换计算机网络的定义和分类计算机网络的性能指标常见的三种计算机网络体系计算机网络体系结构分层的必要性计算机网络体系结构分层思想举例计算机网络体系结构中的专用术语 第二章…...
代码随想录算法训练营第四天| 24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
24.两两交换链表中的节点 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 解题思路 很麻烦的一道题目,不是很理解。还是看视频文章才AC的。 解法1 …...
职业探索--运维体系-SRE岗位/CRE岗位/运维岗位-服务心态-运维职业发展方向-运维对象和运维场景
参考来源: 极客时间专栏:赵成的运维体系管理课 极客时间专栏:全栈工程师修炼指南 赵成大佬在鹏讯云社区的文章(77篇) 有了CMDB,为什么还要应用配置管理 故障没有根因,别再找了 如何理解CMDB的套…...
深入理解C++智能指针系列(五)
引言 前面两篇介绍了std::unique_ptr的自定义删除器以及如何优化删除器的使用。本文将介绍std::unique_ptr在使用过程中的一些“奇技淫巧”。 正文 删除器和std::move std::move是将对象的所有权转移给另一个对象,那如果通过std::move来转移带自定义删除器的std::…...
1.Nginx上配置 HTTPS
1.安装 Nginx: 如果还没有安装 Nginx,可以使用包管理工具安装。例如,在 Ubuntu 上: sudo apt update sudo apt install nginx2.上传证书和私钥文件: 将你的证书文件和私钥文件上传到服务器上的某个目录,…...
wordpress教程视频 wordpress教程网盘 wordpress教程推荐wordpress教程网
WordPress,作为一款强大且灵活的开源内容管理系统,已成为许多网站开发者与运营者的首选。其强大的功能、丰富的插件以及易于上手的特点,使得无论是初学者还是专业开发者都能轻松构建出个性化的网站。然而,对于初学者来说ÿ…...
vue3 3D炫酷模型banner图
项目场景: 在官网首页展示3D炫酷动画模型,让整个模型都展示出来。 问题描述 主要是3D动画的展示效果,有些3d模型网站可以从51建模网站中获取。 案例代码: <script setup> import * as imgs from ../units/img import { o…...
小程序内使用路由
一:使用组件 1)创建组件 2)在需要的页面的json/app.json可实现局部使用和全局使用 在局部的话,对象内第一层,window配置也是第一层,而在全局配置也是在第一层,window在window对象内.第二层.内部执行遍历不一样. 3)页面使用 上述所写可实现在页面内使用组件.效果是页面内可以将…...
【数据结构】第七节:堆
个人主页: 深情秋刀鱼-CSDN博客 数据结构专栏:数据结构与算法 源码获取:数据结构: 上传我写的关于数据结构的代码 (gitee.com) 目录 一、堆 1.堆的概念 2.堆的定义 二、堆的实现 1.初始化和销毁 2.插入 向上调整算法 3.删除 向下调整算法…...
前端大师-高级Web开发测验
目录 前言 1.按正确的执行顺序排列脚本 2.哪些说法是正确的?(D) 3.填写正确的术语 4.程序的输出 5.将资源提示与其定义匹配 6.以下程序的输出是? 7.将PerformanceNavigationTimings按正确的顺序排列 8.将缓存指令与其定义…...
延迟初始化和密封类
Kotlin 延迟初始化(Lazy Initialization) 定义 在 Kotlin 中,延迟初始化允许你延迟一个对象的初始化,直到首次访问该对象时才进行初始化。这通常用于那些初始化开销较大,或者只在程序运行的某个特定点才需要的对象。…...
Kotlin基础之基本语法
Kotlin 简介 Kotlin 是一种由 JetBrains 开发的静态类型编程语言,设计用于与 Java 虚拟机 (JVM) 兼容,同时也可用于 Android、JavaScript(通过 Kotlin/JS)和原生(通过 Kotlin/Native)开发。Kotlin 旨在提供…...
多态(难的起飞)
注意 virtual关键字: 1、可以修饰原函数,为了完成虚函数的重写,满足多态的条件之一 2、可以菱形继承中,去完成虚继承,解决数据冗余和二义性 两个地方使用了同一个关键字,但是它们互相一点关系都没有 虚函…...
安装GO环境
#windows 1.下载go的安装包msi,下载完双击运行,指定一个目录进行安装 #msi安装时,会自动设置以下环境变量: #GOPATH(默认设置为C:\Users\hhx\go), #C:\Users\hhx\go\bin, #go安装位置下的bin目录 2.检查是否安装成功,终端中运行go version解释一些环境变量 GOROOT:go的安装位置…...
记一次由于代码原因导致Mysql连接被打满和唯一索引重复问题
先说一下事情产生的背景:原先的代码逻辑是消费MQ,然后请求其他服务的接口,对接口的返回值result做落库操作,现在要新加个逻辑,做完落库操作后还要再将result封装落到新表中;即消费一次MQ(MQ消息的频率非常高…...
redis数据类型之string,list
华子目录 key操作说明SCAN cursor [MATCH pattern] [COUNT count]dump与restorekeys 通配符 示例演示 string说明setbit key offset valuegetbit key offsetsetrange key offset value List结构图相关命令lrem key count valueltrim key count value示例:使用 LTRIM…...
Android android.os.DeadObjectException aidl通信异常分析及解决
问题描述 做一款音乐播放应用,播放服务是通过AIDL形式对外暴露,允许跨进程调用且多个App同时操作音乐播放,偶现android.os.DeadObjectException问题 12-15 09:28:12.371: W/System.err(5412): android.os.DeadObjectException 12-15 09:28:…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
