当前位置: 首页 > 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;您可以从任何工作表搜索您的应用程序中的完整数据集。 信息注释 智…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

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

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

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...