当前位置: 首页 > news >正文

题目:Wangzyy的卡牌游戏

登录 - XYOJ


思路:

        使用动态规划,设dp[n]表示当前数字之和模三等于0的组合数。

        状态转移方程:因为是模三,所以和的可能就只有0、1、2。等号右边的f和dp都表示当前一轮模三等于k的组合数。以第一行为例:等号右边表示 j转移到0的方案数+(当前j方案数*反正面等于0的个数)。ps:j转移到0表示  上一轮牌和为j到本轮的牌模三为0

			f[(j + 0) % 3] = (f[(j + 0) % 3] + dp[j] * c[0]) % MOD;f[(j + 1) % 3] = (f[(j + 1) % 3] + dp[j] * c[1]) % MOD;f[(j + 2) % 3] = (f[(j + 2) % 3] + dp[j] * c[2]) % MOD;

代码:

#include <bits/stdc++.h>
using namespace std;const int N = 1e5+9, MOD = 1e9 + 7;
int dp[3] = {1, 0, 0}; // dp[i]:和模三为i的组合数。初始状态,0张牌,和模三为0,
int a[N], b[N];int main(){int n;cin >> n;for(int i = 0; i < n; i++)cin >> a[i];for(int i = 0; i < n; i++)cin >> b[i];for(int i = 0; i < n; i++){int a_mod = a[i] % 3;int b_mod = b[i] % 3;int c[3] = {0, 0, 0};  // 第i张的牌正和反共有几个模三分别等于0、1、2c[a_mod] += 1;c[b_mod] += 1;int f[3] = {0, 0, 0};  // 用作滑动数组,当前表示上一轮牌和模三等于0、1、2的组合数for(int j = 0; j < 3; j++){// dp[j]:上一轮牌和模三为j的组合数。 f[(j + 0) % 3] = (f[(j + 0) % 3] + dp[j] * c[0]) % MOD;f[(j + 1) % 3] = (f[(j + 1) % 3] + dp[j] * c[1]) % MOD;f[(j + 2) % 3] = (f[(j + 2) % 3] + dp[j] * c[2]) % MOD;}for(int j = 0; j < 3; j++)dp[j] = f[j];  // 到此dp和f都表示本轮牌和模三为j的组合数}cout << dp[0] << '\n'; return 0;
} 

知识点:动态规划

相关文章:

题目:Wangzyy的卡牌游戏

登录 - XYOJ 思路&#xff1a; 使用动态规划&#xff0c;设dp[n]表示当前数字之和模三等于0的组合数。 状态转移方程&#xff1a;因为是模三&#xff0c;所以和的可能就只有0、1、2。等号右边的f和dp都表示当前一轮模三等于k的组合数。以第一行为例&#xff1a;等号右边表示 j转…...

国外云服务器高防多少钱一年?

国外云服务器高防多少钱一年&#xff1f;入门级高防云主机&#xff1a;这类主机通常具有较低的防御峰值&#xff0c;如30G或60G&#xff0c;价格相对较低。例如&#xff0c;30G峰值防御的高防云主机年费可能在2490元左右&#xff0c;而60G峰值防御的则可能在5044元左右。中等防…...

架构篇(04理解架构的演进)

目录 学习前言 一、架构演进 1. 初始阶段的网站架构 2. 应用服务和数据服务分离 3. 使用缓存改善网站性能 4. 使用应用服务器集群改善网站的并发处理能力 5. 数据库读写分离 6. 使用反向代理和CDN加上网站相应 7. 使用分布式文件系统和分布式数据库系统 8. 使用NoSQL和…...

【363】基于springboot的高校竞赛管理系统

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统高校竞赛管理系统信息管理难度大&#xff0c;容错率低&am…...

Spring Boot 监视器

一、Spring Boot 监视器概述 &#xff08;一&#xff09;什么是 Spring Boot 监视器 定义与作用 Spring Boot 监视器&#xff08;Spring Boot Actuator&#xff09;是一个用于监控和管理 Spring Boot 应用程序的工具集。它提供了一系列的端点&#xff0c;可以获取应用程序的运…...

Javascript如何获取指定网页中的内容?

这两天有一个需求&#xff0c;就是通过JS去获取网页的内容&#xff0c;当然&#xff0c;除了今天我要分享的这个方法以外&#xff0c;其实通过Ajax的Get方法也是可以实现这个功能的&#xff0c;但是Ajax就比较麻烦一些了&#xff0c;如果只是单纯的想要获取一下纯内容&#xff…...

第2章2.3立项【硬件产品立项的核心内容】

硬件产品立项的核心内容 2.3 硬件产品立项的核心内容2.3.1 第一步&#xff1a;市场趋势判断2.3.2 第二步&#xff1a;竞争对手分析1.竞争对手识别2.根据竞争对手分析制定策略 2.3.3 第三步&#xff1a;客户分析2.3.4 第四步&#xff1a;产品定义2.3.5 第五步&#xff1a;开发执…...

区块链:Raft协议

Raft 协议是一种分布式共识机制&#xff0c;这种机制适用于网络中存在一定数量的故障节点&#xff0c;但不考虑“恶意”节点的情况&#xff0c;所以更适合作为私有链和联盟链的共识算法。 在此协议中&#xff0c;每个节点有三种状态&#xff1a; 候选者 &#xff0c;可以被选…...

【C语言】位运算

我们在上学计算机的第一节课&#xff0c;就应该见过这些常见的运算符。然而&#xff0c;你可能有印象&#xff0c;但记不住众多操作符当中的位运算符&#xff0c;以及它们的作用和使用场景&#xff0c;我们的大脑会选择性地遗忘它认为没用的信息&#xff0c;存储下那些“有实际…...

计算机体系结构之多级缓存、缓存miss及缓存hit(二)

前面章节《计算机体系结构之缓存机制原理及其应用&#xff08;一&#xff09;》讲了关于缓存机制的原理及其应用&#xff0c;其中提出了多级缓存、缓存miss以及缓存hit的疑问。故&#xff0c;本章将进行展开讲解&#xff0c; 多级缓存、缓存miss以及缓存hit存在的意义是为了保持…...

【R78/G15 开发板测评】串口打印 DHT11 温湿度传感器、DS18B20 温度传感器数据,LabVIEW 上位机绘制演化曲线

【R78/G15 开发板测评】串口打印 DHT11 温湿度传感器、DS18B20 温度传感器数据&#xff0c;LabVIEW 上位机绘制演化曲线 主要介绍了 R78/G15 开发板基于 Arduino IDE 环境串口打印温湿度传感器 DHT11 和温度传感器 DS18B20 传感器的数据&#xff0c;并通过LabVIEW上位机绘制演…...

Oracle Fetch子句

FETCH 子句在 Oracle 中可以用来限制查询返回的行数 Oracle FETCH 子句语法 以下说明了行限制子句的语法&#xff1a; [ OFFSET offset ROWS]FETCH NEXT [ row_count | percent PERCENT ] ROWS [ ONLY | WITH TIES ]OFFSET 子句 OFFSET 子句指定在行限制开始之前要跳过行…...

Linux应用——线程池

1. 线程池要求 我们创建线程池的目的本质上是用空间换取时间&#xff0c;而我们选择于 C 的类内包装原生线程库的形式来创建&#xff0c;其具体实行逻辑如图 可以看到&#xff0c;整个线程池其实就是一个大型的 CP 模型&#xff0c;接下来我们来完成它 2. 整体模板 #pragma …...

95.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

目录 1.双向链表的头插 方法一 方法二 2.双向链表的头删 3.双向链表的销毁 4.双向链表的某个节点的数据查找 5.双向链表的中间插入 5.双向链表的中间删除 6.对比顺序表和链表 承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章 1.双向链表的头插 方法…...

leetcode82:删除排序链表中的重复节点||

给定一个已排序的链表的头 head &#xff0c; 删除原始链表中所有重复数字的节点&#xff0c;只留下不同的数字 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,3,4,4,5] 输出&#xff1a;[1,2,5]示例 2&#xff1a; 输入&#xff1a;head [1,1,1,2…...

【C#】使用.net9在C#中向现有对象动态添加属性

在 C# 中向现有对象动态添加属性并不像在 Python 或 JavaScript 中那样容易&#xff0c;因为 C# 是一种强类型语言。 但是&#xff0c;我们可以通过使用一些技术和库来实现这一点&#xff0c;例如扩展方法、字典等。本文将详细介绍如何在 C# 中实现这一点。ExpandoObject 方法 …...

Linux进程信号(信号的产生)

目录 什么是信号&#xff1f; 信号的产生 信号产生方式1&#xff1a;键盘 前台进程 后台进程 查看信号 signal系统调用 案例 理解进程记录信号 软件层面 硬件层面 信号产生方式2:指令 信号产生方式3:系统调用 kill系统调用 案例 其他产生信号的函数调用 1.rais…...

97_api_intro_imagerecognition_pdf2word

通用 PDF OCR 到 Word API 数据接口 文件处理&#xff0c;OCR&#xff0c;PDF 高可用图像识别引擎&#xff0c;基于机器学习&#xff0c;超精准识别率。 1. 产品功能 通用识别接口&#xff1b;支持中英文等多语言字符混合识别&#xff1b;formdata 格式 PDF 文件流传参&#xf…...

【算法】【优选算法】二分查找算法(上)

目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚…...

springboot初体验

目录 环境 controller 修改端口号 更改banner图标 运行结果 最核心的:自动装配 环境 jdk17springboot3.3.5maven3.8.2 controller controller层和启动类同级 package com.example.demo.controller; ​ import org.springframework.web.bind.annotation.RequestMapping;…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...