当前位置: 首页 > 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;…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...