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 0⊼0=1,0⊼1=1,1⊼0=1,1⊼1=0。
求 ∑ i = 1 n ∑ j = i n f ( i , j ) \sum_{i=1}^n \sum_{j=i}^n f(i,j) ∑i=1n∑j=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,j−1)⊼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的方案数。分以下两种情况考虑:
- 当前数字是 0 0 0, d p [ i ] [ 1 ] dp[i][1] dp[i][1]累计是 1 1 1的情况可以从前面 i − 1 i-1 i−1累计是 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。
- 当前数字是 1 1 1, d p [ i ] [ 1 ] dp[i][1] dp[i][1]累计是 1 1 1的情况只能从前面 i − 1 i-1 i−1累计是 0 0 0的情况转移过来,并且计数增加 1 1 1(算上自己本身的),因为 1 ⊼ 1 = 0 1⊼1=0 1⊼1=0; d p [ i ] [ 0 ] dp[i][0] dp[i][0]累计是 0 0 0的情况从前面 i − 1 i-1 i−1累计是 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题: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⊼01,0⊼11,1⊼01,1⊼10 0⊼01,0⊼11,1⊼01,1⊼10。 求 ∑…...

一款简易的免费抽奖软件
一、介绍 这款抽奖软件设计简洁,操作便捷。用户可以轻松将参与名单通过EXCEL文件导入至程序中,并可根据需要设定各类奖品和对应的中奖人数。在选定了奖品后,用户只需点击“开始”按钮,随后再按下“暂停”按钮,软件便会…...
Kubernetes 监控管理
目录 1. Metrics Server2. Prometheus & Grafana3. cAdvisor4. 日志收集5. 告警与通知6. 最佳实践 Kubernetes 监控管理是确保集群稳定运行和应用服务质量的关键环节。它涉及收集、聚合、分析集群及其上运行的应用程序的各种指标和日志数据。 1. Metrics Server 作用&…...
哈希表第6/9题--四数相加II
题目描述: 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 < i, j, k, l < nnums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1: 输入&…...
使用JavaScript将富文本HTML转换为纯文本
在Web开发中,我们经常需要处理HTML内容,但有时为了特定的目的,比如文本处理、搜索或显示在非HTML环境中,我们可能希望将富文本HTML转换为纯文本。这里,我们将探讨如何使用JavaScript来实现这一功能。 为什么要将HTML转…...
2024-05-13 问AI: 介绍一下 google wavenet 声码器
文心一言 Google的WaveNet声码器是一个深度学习模型,用于生成高质量的音频信号,特别是人类语音。与传统的声码器相比,WaveNet可以生成更加自然和流畅的音频,因为它直接模拟了原始音频信号的波形生成过程。 WaveNet的核心思想是使…...

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

matlab使用教程(70)—修改坐标区属性
1.控制坐标轴长度比率和数据单位长度 您可以控制 x 轴、y 轴和 z 轴的相对长度(图框纵横比),也可以控制一个数据单位沿每个轴的相对长度(数据纵横比)。 1.1图框纵横比 图框纵横比是 x 轴、y 轴和 z 轴的相对长度。默认…...

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

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

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

Ciphey无法安装的解决办法
安装过程纯属自己实践,满满干货 困扰我几天的问题终于解决了 我看着教程在window上安装 python3.8/python3.9/python3.10无论如何都安装不上, 在win10虚拟机仍然安装不上 可能是我电脑环境问题 解决办法: 在kali中安装,但是…...
交互之舞:Processing中的用户互动与响应设计
前言: 🌟在前两篇文章中,我们已经学会了如何绘制静态图形和创建动态动画。今天,我们将迈入一个新的领域——交互设计。在Processing中,用户互动是创造沉浸式体验的关键。让我们一起探索如何让用户与你的艺术作品互动&…...
unetr_plus_plus(UNETR++、nnU-Net)系列数据处理理解汇总
unetr_plus_plus(UNETR、nnU-Net)系列数据处理理解汇总,这是一个 3D 图像分割的任务系列集。 为什么说他们是一个系列集合呢?主要是因为: 论文的训练和评价数据集是一样的,都是来自于10全挑战赛ÿ…...
稻盛和夫《活法》读后感
最近几天又重读了一边稻盛和夫的《活法》,里面的观点让我感触颇多,现分享给诸君。 稻盛和夫毕业后,适逢经济萧条,没有好机会进入大公司深造,只能在一名教授的推荐下进入了一家做陶瓷绝缘体的公司,虽然公司…...

Smurf 攻击是不是真的那么难以防护
Smurf攻击是一种网络攻击方式,属于分布式拒绝服务(DDoS)攻击的变种。以 1990 年代流行的名为 Smurf 的漏洞利用工具命名。该工具创建的 ICMP 数据包很小,但可以击落大目标。 它利用ICMP协议中的回声请求(ping&#x…...
ASP.NET之图像控件
在ASP.NET中,用于显示图像的控件主要是Image控件,Image控件属于ASP.NET Web Forms的一部分,它允许你在Web页面上显示图像。以下是如何在ASP.NET Web Forms中使用 1. 添加Image控件到页面 在ASP.NET Web Forms页面上,你可以通过设…...
二级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(GNU Debugger)是一种Unix下的程序调试工具,用于调试C、C等编程语言编写的程序。以下是一些GDB的常用命令: 启动和退出: run 或 r…...

Qlik Sense :使用智能搜索Smart Search
智能搜索 智能搜索是 Qlik Sense 中的全局搜索工具,可让您从应用程序中的任何工作表搜索应用程序中的整个数据集。可通过点击 从工作表中的选择项栏使用智能搜索。 通过智能搜索字段,您可以从任何工作表搜索您的应用程序中的完整数据集。 信息注释 智…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: 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. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

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

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

springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...

基于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 注意:运行前…...

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主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...

在Zenodo下载文件 用到googlecolab googledrive
方法:Figshare/Zenodo上的数据/文件下载不下来?尝试利用Google Colab :https://zhuanlan.zhihu.com/p/1898503078782674027 参考: 通过Colab&谷歌云下载Figshare数据,超级实用!!࿰…...