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

AtCoder Beginner Contest 310 E题 NAND repeatedly

E题:NAND repeatedly

标签:动态规划
题意:给定一个长度为 n n n 01 01 01字符串 A i A_i Ai,给定规则: 0 ⊼ 0 = 1 , 0 ⊼ 1 = 1 , 1 ⊼ 0 = 1 , 1 ⊼ 1 = 0 0⊼0=1,0⊼1=1,1⊼0=1,1⊼1=0 00=1,01=1,10=1,11=0

∑ i = 1 n ∑ j = i n f ( i , j ) \sum_{i=1}^n \sum_{j=i}^n f(i,j) i=1nj=inf(i,j) 1 < = i < = j < = n 1<=i<=j<=n 1<=i<=j<=n), f ( i , j ) = { A i ( i = j ) f ( i , j − 1 ) ⊼ A j ( i < j ) f(i,j)=\left\{\begin{matrix} A _ i&(i=j)\\ f(i,j-1)\barwedge A _ j\quad&(i\lt j) \end{matrix}\right. f(i,j)={Aif(i,j1)Aj(i=j)(i<j)
题解:显然我们可以通过 O ( n 2 ) O(n^2) O(n2)时间复杂度完成这道题要求,但是 n < = 1 0 6 n<=10^6 n<=106会超时。
d p [ i ] [ 0 / 1 ] dp[i][0/1] dp[i][0/1]:前 i i i个数字累计 n a n d ( ⊼ ) nand(⊼) nand 0 / 1 0/1 0/1的方案数。分以下两种情况考虑:

  1. 当前数字是 0 0 0 d p [ i ] [ 1 ] dp[i][1] dp[i][1]累计是 1 1 1的情况可以从前面 i − 1 i-1 i1累计是 0 0 0 1 1 1的情况转移过来,因为当前数字是 0 0 0,不管和 0 0 0 1 1 1 n a n d ( ⊼ ) nand(⊼) nand都是 1 1 1 d p [ i ] [ 0 ] dp[i][0] dp[i][0]累计是 0 0 0的情况初始化成 1 1 1
  2. 当前数字是 1 1 1 d p [ i ] [ 1 ] dp[i][1] dp[i][1]累计是 1 1 1的情况只能从前面 i − 1 i-1 i1累计是 0 0 0的情况转移过来,并且计数增加 1 1 1(算上自己本身的),因为 1 ⊼ 1 = 0 1⊼1=0 11=0 d p [ i ] [ 0 ] dp[i][0] dp[i][0]累计是 0 0 0的情况从前面 i − 1 i-1 i1累计是 1 1 1的情况转移过来。

最后把每个位置的 d p [ i ] [ 1 ] dp[i][1] dp[i][1]累加一下即可。
代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
typedef long long ll;
ll dp[N][2];int main() {ll n, ans = 0;string s;cin >> n >> s;for (int i = 1; i <= n; i++) {if (s[i-1] == '0') {dp[i][1] = dp[i-1][0] + dp[i-1][1];dp[i][0] = 1;} else {dp[i][1] = dp[i-1][0] + 1;dp[i][0] = dp[i-1][1];}ans += dp[i][1];}cout << ans << endl;return 0;
}

相关文章:

AtCoder Beginner Contest 310 E题 NAND repeatedly

E题&#xff1a;NAND repeatedly 标签&#xff1a;动态规划题意&#xff1a;给定一个长度为 n n n的 01 01 01字符串 A i A_i Ai​&#xff0c;给定规则&#xff1a; 0 ⊼ 0 1 , 0 ⊼ 1 1 , 1 ⊼ 0 1 , 1 ⊼ 1 0 0⊼01,0⊼11,1⊼01,1⊼10 0⊼01,0⊼11,1⊼01,1⊼10。 求 ∑…...

一款简易的免费抽奖软件

一、介绍 这款抽奖软件设计简洁&#xff0c;操作便捷。用户可以轻松将参与名单通过EXCEL文件导入至程序中&#xff0c;并可根据需要设定各类奖品和对应的中奖人数。在选定了奖品后&#xff0c;用户只需点击“开始”按钮&#xff0c;随后再按下“暂停”按钮&#xff0c;软件便会…...

Kubernetes 监控管理

目录 1. Metrics Server2. Prometheus & Grafana3. cAdvisor4. 日志收集5. 告警与通知6. 最佳实践 Kubernetes 监控管理是确保集群稳定运行和应用服务质量的关键环节。它涉及收集、聚合、分析集群及其上运行的应用程序的各种指标和日志数据。 1. Metrics Server 作用&…...

哈希表第6/9题--四数相加II

题目描述&#xff1a; 给你四个整数数组 nums1、nums2、nums3 和 nums4 &#xff0c;数组长度都是 n &#xff0c;请你计算有多少个元组 (i, j, k, l) 能满足&#xff1a; 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1&#xff1a; 输入&…...

使用JavaScript将富文本HTML转换为纯文本

在Web开发中&#xff0c;我们经常需要处理HTML内容&#xff0c;但有时为了特定的目的&#xff0c;比如文本处理、搜索或显示在非HTML环境中&#xff0c;我们可能希望将富文本HTML转换为纯文本。这里&#xff0c;我们将探讨如何使用JavaScript来实现这一功能。 为什么要将HTML转…...

2024-05-13 问AI: 介绍一下 google wavenet 声码器

文心一言 Google的WaveNet声码器是一个深度学习模型&#xff0c;用于生成高质量的音频信号&#xff0c;特别是人类语音。与传统的声码器相比&#xff0c;WaveNet可以生成更加自然和流畅的音频&#xff0c;因为它直接模拟了原始音频信号的波形生成过程。 WaveNet的核心思想是使…...

当代 Qt 正确的 安装方法 及 多版本切换

此文写于 20240511 首先去网站Index of /official_releases/online_installers下载一个安装器 安装器有什么用? 可以浏览安装版本 安装组件 安装器版本越能 能装的东西越多 现在只能选Qt5 和 Qt6 至于你公司用的Qt4 我也没招 见招时再拆招 安装器 默认国外源 可以换国内…...

matlab使用教程(70)—修改坐标区属性

1.控制坐标轴长度比率和数据单位长度 您可以控制 x 轴、y 轴和 z 轴的相对长度&#xff08;图框纵横比&#xff09;&#xff0c;也可以控制一个数据单位沿每个轴的相对长度&#xff08;数据纵横比&#xff09;。 1.1图框纵横比 图框纵横比是 x 轴、y 轴和 z 轴的相对长度。默认…...

手撕C语言题典——反转链表

目录 前言 一.思路 1&#xff09;创建新链表 2&#xff09;创建三个指针 二.代码实现 搭配食用更佳哦~~ 数据结构之单单单——链表-CSDN博客 数据结构之单链表的基本操作-CSDN博客 前面学了单链表的相关知识&#xff0c;我们来尝试做一下关于顺序表的经典算法题~ 前言 反转…...

用lobehub打造一个永久免费的AI个人助理

Lobe Chat是一个开源的高性能聊天机器人框架&#xff0c;它被设计来帮助用户轻松创建和部署自己的聊天机器人。这个框架支持多种智能功能&#xff0c;比如语音合成&#xff08;就是让机器人能说话&#xff09;&#xff0c;还能理解和处理多种类型的信息&#xff0c;不仅限于文字…...

Linux网络编程】传输层中的TCP和UDP(UDP篇)

【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09; 目录 【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09;传输层再谈端口端口号范围划分认识知名端口号netstatiostatpidofxargs UDP协议UDP协议端格式UDP的特点面向数据报UDP的缓冲数据UDP使…...

Ciphey无法安装的解决办法

安装过程纯属自己实践&#xff0c;满满干货 困扰我几天的问题终于解决了 我看着教程在window上安装 python3.8/python3.9/python3.10无论如何都安装不上&#xff0c; 在win10虚拟机仍然安装不上 可能是我电脑环境问题 解决办法&#xff1a; 在kali中安装&#xff0c;但是…...

交互之舞:Processing中的用户互动与响应设计

前言&#xff1a; &#x1f31f;在前两篇文章中&#xff0c;我们已经学会了如何绘制静态图形和创建动态动画。今天&#xff0c;我们将迈入一个新的领域——交互设计。在Processing中&#xff0c;用户互动是创造沉浸式体验的关键。让我们一起探索如何让用户与你的艺术作品互动&…...

unetr_plus_plus(UNETR++、nnU-Net)系列数据处理理解汇总

unetr_plus_plus&#xff08;UNETR、nnU-Net&#xff09;系列数据处理理解汇总&#xff0c;这是一个 3D 图像分割的任务系列集。 为什么说他们是一个系列集合呢&#xff1f;主要是因为&#xff1a; 论文的训练和评价数据集是一样的&#xff0c;都是来自于10全挑战赛&#xff…...

稻盛和夫《活法》读后感

最近几天又重读了一边稻盛和夫的《活法》&#xff0c;里面的观点让我感触颇多&#xff0c;现分享给诸君。 稻盛和夫毕业后&#xff0c;适逢经济萧条&#xff0c;没有好机会进入大公司深造&#xff0c;只能在一名教授的推荐下进入了一家做陶瓷绝缘体的公司&#xff0c;虽然公司…...

Smurf 攻击是不是真的那么难以防护

Smurf攻击是一种网络攻击方式&#xff0c;属于分布式拒绝服务&#xff08;DDoS&#xff09;攻击的变种。以 1990 年代流行的名为 Smurf 的漏洞利用工具命名。该工具创建的 ICMP 数据包很小&#xff0c;但可以击落大目标。 它利用ICMP协议中的回声请求&#xff08;ping&#x…...

ASP.NET之图像控件

在ASP.NET中&#xff0c;用于显示图像的控件主要是Image控件&#xff0c;Image控件属于ASP.NET Web Forms的一部分&#xff0c;它允许你在Web页面上显示图像。以下是如何在ASP.NET Web Forms中使用 1. 添加Image控件到页面 在ASP.NET Web Forms页面上&#xff0c;你可以通过设…...

二级Java第五套真题(乱序版)含真题解析

一. 单选题(共39题,39分) 1. (单选题, 1分) 阅读下列代码 public class Test implements Runnable { public void run (Thread t) { System.out.println("Running."); } public static void main (String[ ] args) { T…...

【C++】GNU Debugger (GDB) 使用示例

文章目录 GDB 使用示例GDB的常用命令示例 GDB 使用示例 GDB的常用命令 GDB&#xff08;GNU Debugger&#xff09;是一种Unix下的程序调试工具&#xff0c;用于调试C、C等编程语言编写的程序。以下是一些GDB的常用命令&#xff1a; 启动和退出&#xff1a; run 或 r&#xf…...

Qlik Sense :使用智能搜索Smart Search

智能搜索 智能搜索是 Qlik Sense 中的全局搜索工具&#xff0c;可让您从应用程序中的任何工作表搜索应用程序中的整个数据集。可通过点击 从工作表中的选择项栏使用智能搜索。 通过智能搜索字段&#xff0c;您可以从任何工作表搜索您的应用程序中的完整数据集。 信息注释 智…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...