洛谷P11243 繁花

洛谷P11243 繁花

繁花

题目背景

English statement. You must submit your code at the Chinese version of the statement.

我已经知道,在设置好循环播放时就已经知道,我是在麻痹自己,在逃避问题。

我承认如此,可捞起那些沉于水底的细节时,却一瞬间突然和所有所有真实的心跳共鸣。

那时总想的太少,现在常想得太多,不知所措似荒塘里的绿藻蔓延着。

然而这世间情感太多,小 R 也只能体会更开心和更难过。

题目描述

小 R 想对上面的问题进行探究,她想先做一些统计,于是她抽象了这个问题。

小 R 有 n n n 个未知量 a 1 … a n a_1\dots a_n a1an,对每个 1 ≤ i < n 1 \leq i < n 1i<n,她都比较了 a i a_i ai a i + 1 a_{i+1} ai+1 并写下了一个字符 c i ∈ { < , > , = } c_i \in \{\texttt <, \texttt >, \texttt =\} ci{<,>,=},表示两个未知量之间的比较结果。具体地:

  • c i = > c_i = \texttt > ci=>,则 a i > a i + 1 a_i > a_{i+1} ai>ai+1
  • c i = < c_i = \texttt < ci=<,则 a i < a i + 1 a_i < a_{i+1} ai<ai+1
  • 否则( c i = = c_i = \texttt = ci==),表示 a i = a i + 1 a_i = a_{i+1} ai=ai+1

小 R 称 a i \bm{a_i} ai a j \bm{a_j} aj 更开心,当且仅当对任何 满足上述 n − 1 \bm{n - 1} n1 条约束的 [ a 1 , … , a n ] ∈ R n [a_1, \dots, a_n] \in \mathbb R^n [a1,,an]Rn,都有 a i < a j a_i < a_j ai<aj。请你帮她数出 1 ≤ i , j ≤ n 1 \leq i, j \leq n 1i,jn a i a_i ai a j a_j aj 更开心的整数数对 ( i , j ) (i, j) (i,j) 个数。

因为要循环播放,所以有多组数据。

输入格式

本题有多组数据。

第一行,一个整数 T T T,表示数据组数。对于每组数据:

  • 第一行一个整数 n n n
  • 接下来一行,一个长度为 n − 1 n - 1 n1 的字符串 c 1 c 2 … c n − 1 c_1c_2\dots c_{n-1} c1c2cn1

输出格式

对于每组数据,输出仅一行一个整数,表示符合条件的整数数对个数。

样例 #1

样例输入 #1

5
5
<<<<
7
<=><=<
9
=<<><==<
11
>=<<=>>>=>
13
=><<=<=>=><>

样例输出 #1

10
9
13
29
25

提示

样例解释

  • 对于第一组数据, a i a_i ai a j a_j aj 开心当且仅当 1 ≤ i < j ≤ n 1 \leq i < j \leq n 1i<jn,故共有 5 × 4 2 = 10 \frac{5\times 4}{2} = 10 25×4=10 对合法的 ( i , j ) (i, j) (i,j)
  • 对于第二组数据,合法的 ( i , j ) (i, j) (i,j) 分别为: ( 1 , 2 ) , ( 1 , 3 ) , ( 4 , 2 ) , ( 4 , 3 ) , ( 4 , 5 ) , ( 4 , 6 ) , ( 4 , 7 ) , ( 5 , 7 ) , ( 6 , 7 ) (1, 2), (1, 3), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (5, 7), (6, 7) (1,2),(1,3),(4,2),(4,3),(4,5),(4,6),(4,7),(5,7),(6,7),共 9 9 9 对。
  • 对于其他几组数据,聪明的读者可以自行验证。

数据规模与约定

本题采用捆绑测试和子任务依赖。

  • Subtask 0(0 pts):样例。
  • Subtask 1(10 pts): n ≤ 8 n \leq 8 n8 T ≤ 8 T \leq 8 T8
  • Subtask 2(20 pts): n ≤ 5000 n \leq 5000 n5000 T ≤ 8 T \leq 8 T8。依赖于子任务 0 , 1 0, 1 0,1
  • Subtask 3(20 pts): c i ≠ = c_i \neq \texttt = ci==
  • Subtask 4(50 pts):无特殊限制。依赖于子任务 0 ∼ 3 0 \sim 3 03

对于所有数据,保证 2 ≤ n ≤ 2 × 1 0 5 2 \leq n \leq 2\times 10^5 2n2×105 1 ≤ T ≤ 1 0 4 1 \leq T \leq 10^4 1T104 c i ∈ { < , > , = } c_i \in \{\texttt <, \texttt >, \texttt =\} ci{<,>,=} ∑ n ≤ 5 × 1 0 5 \sum n \leq 5\times 10^5 n5×105

双指针

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int n,t,l,x,ans,p;
char ls;
string s;
signed main(){scanf("%d",&t);while(t--){scanf("%lld",&n);cin>>s;s=" "+s;ans=0;l=1;x=1;p=0;for(int i=1;i<n;i++){
//			printf("i:%d\n",i);x=1;l=i-1;while(s[i]=='='){ans+=p;
//				printf("i:%d  p:%d\n",i,p);if(i==n){break;}i++;x++;}if(i==n)break;if(s[i]!=s[l]){p=x;}else p+=x;ans+=p;
//			printf("i:%d  p:%d\n",i,p);}printf("%lld\n",ans);}return 0;
}
/*
1
4
<<==
*/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/8505.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

数据迁移: 安全高效转移数据, 满足企业业务需求和技术改进

天津鸿萌科贸发展有限公司从事数据安全服务二十余年&#xff0c;致力于为各领域客户提供专业的数据存储、数据恢复、数据备份、数据迁移等解决方案与服务&#xff0c;并针对企业面临的数据安全风险&#xff0c;提供专业的相关数据安全培训。 鸿萌数据迁移业务为众多企业顺利高效…

可视化建模与UML《类图实验报告》

史铁生&#xff1a; 余华和莫言扛着我上火车&#xff0c; 推着走打雪仗&#xff0c; 还带我偷西瓜&#xff0c; 被人发现后他们拔腿就跑&#xff0c; 却忘了我还在西瓜地里。 一、实验目的&#xff1a; 1、熟悉类图的构件事物。 2、熟悉类之间的泛化、依赖、聚合和组合关系…

Zypher Network:全栈式 Web3 游戏引擎,服务器抽象叙事的引领者

近期&#xff0c;《黑神话&#xff1a;悟空》的爆火不仅让 AAA 游戏重回焦点&#xff0c;也引发了玩家与开发者的热议。Web2 游戏的持续成功导致部分 Web3 玩家们的倒戈&#xff0c;对比之下 Web3 游戏存在生命周期短且商业模式难以明确的问题&#xff0c;尤其在当前加密市场环…

C++11的简介

杀马特主页&#xff1a;羑悻的小杀马特.-CSDN博客 ------ ->欢迎阅读 欢迎阅读 欢迎阅读 欢迎阅读 <------- 目录 一列表初始化的变化&#xff1a; 二左右值即各自引用的概念&#xff1a; 2.1左右…

Java 上机实践3(分支与循环语句)

&#xff08;大家好&#xff0c;今天分享的是Java的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 目录 实验一&#xff1a;回文数 一、实验目的 二、实验要求 三、程序代码 四、实验结果 实验二&#xff1a;猜数字…

[MRCTF2020]PYWebsite1

如果输入的密钥是对的那么我们就直接跳转到flag.php页面 那么我们直接访问&#x1f60e;&#xff0c;他不带我们去我们自己去. 那就用XFF呗. 知识点&#xff1a; 定义&#xff1a;X-Forwarded-For是一个HTTP请求头字段&#xff0c;用于识别通过HTTP代理或负载均衡方式连接到W…

实时离线融合计算的数据同步实践

实时批量融合计算时&#xff0c;一般需要批量将数据推送到hbase供实时使用。 本文将通过两个典型场景--累计场景与最新分区场景&#xff0c;讨论批量和实时衔接的设计方案&#xff0c;解决批量延迟可能导致的问题。 累计场景 在之前的文章中讲述了实时离线结合共同计算客户1…

怎么做自己公司的小程序

我是【码云数智】平台的黄导&#xff0c;今天分享&#xff1a;怎么做自己公司的小程序 企业小程序怎么制作&#xff0c;利用可视化小程序模板搭建&#xff0c;企业能够轻松跨越技术门槛&#xff0c;快速响应市场变化。 01、小程序制作流程 02、微信小程序开发多少钱 03、微…

外包干了5年,技术退步太明显了。。。。。

先说一下自己的情况&#xff0c;本科生生&#xff0c;19年通过校招进入杭州某软件公司&#xff0c;干了差不多五年的功能测试&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了五年的功能测试&#xff0c;已经…

Java | Leetcode Java题解之第530题二叉搜索树的最小绝对差

题目&#xff1a; 题解&#xff1a; class Solution {int pre;int ans;public int getMinimumDifference(TreeNode root) {ans Integer.MAX_VALUE;pre -1;dfs(root);return ans;}public void dfs(TreeNode root) {if (root null) {return;}dfs(root.left);if (pre -1) {pr…

仪表板展示|DataEase看中国:历年双十一电商销售数据分析

背景介绍 2024年“双十一”购物季正在火热进行中。自2009年首次推出至今&#xff0c;“双十一”已经成为中国乃至全球最大的购物狂欢节&#xff0c;并且延伸到了全球范围内的电子商务平台。随着人们消费水平的提升以及电子商务的普及&#xff0c;线上销售模式也逐渐呈现多元化…

机器人课程——使用TIA Portal V15博图软件进行西门子组态——带显示屏

一.打开TIA Portal V15博图软件创建项目 1.选择创建新项目 创建完成后选择PLC 二.创建完成后选择设备PLC (此处以S7-1200 1214FC DC/DC/DC 为例) 三.添加扩展板&#xff08;如有——这里以223-1BL32-0XB0为例&#xff09; 四.更改扩展版地址 五.添加触摸屏&#xff08;这里以…

Java代码与数据库纽带——JDBC

ok&#xff0c;看了题目&#xff0c;就可以知道今天要分享的是JDBC 讲这个这之前&#xff0c;想讲讲之前的。 之前我们操作数据库基本都是通过MySQL客户端&#xff0c;进行编写sql语句来操作的。 但是我们在开发中一般都是通过代码来操控数据库的。 而且在我们日常开发中&a…

Webserver(5.6)服务器压力测试

目录 webbench是linux上一款知名的优秀的web性能压力测试工具。 测试处在相同硬件上&#xff0c;不同服务的性能以及在不同硬件上同一个服务的运行状况 展示服务器的两项内容&#xff1a;每秒钟响应请求数和每秒钟传输数据量 webbench首先fork多个子进程&#xff0c;每个子进程…

MySQL数据库基础(一) MySQL安装及数据类型

目录 一、MySQL数据裤简介 二、MySQL数据的安装 2.1、MySQL安装 2.2、修改MySQL密码登录策略 三、数据库基础管理 3.1、连接方式及数据储存流程 3.2、库管理命令 3.3、表管理命令 3.4、记录管理命令 四、MySQL数据类型 4.1、常见信息种类 4.2、字符型 4.3、数值型 4.4、日期时间…

好用的远程控制安卓和IOS端的手机软件有哪些?

在数字化时代&#xff0c;我们的工作和娱乐活动越来越依赖于移动设备。无论是在家中、办公室还是旅途中&#xff0c;能够远程控制我们的设备成为了一种高效便捷的需求。市场上涌现出了许多远程控制软件&#xff0c;它们各具特色&#xff0c;旨在提供最佳的用户体验。那么&#…

领夹无线麦克风哪个牌子好?双十一选无线领夹麦克风避开选购陷阱

在多媒体和远程通信日益普及的今天&#xff0c;无线领夹麦克风已成为提升音质和便利性的关键&#xff0c;它们在视频制作、网络直播、在线教育等多个领域中扮演着重要角色。面对市场上众多的产品和技术参数&#xff0c;消费者往往感到无从下手。不过不用过于担心&#xff0c;在…

开发中使用UML的流程_01概述

目录 CIM-1:定义业务流程 CIM-2:分析业务流程 ​CIM-3:定义系统范围 ​PIM-1:分析系统流程 PIM-2:分析业务规则 PIM-3:定义静态结构 PIM-4:定义操作和方法 开发中使用UML的流程,主要分为7部分,具体如下: CIM-1:定义业务流程 定义及分析业务流程是为了尽快理…

ArcGIS/QGIS按掩膜提取或栅格裁剪后栅格数据的值为什么变了?

问题描述&#xff1a; 现有一栅格数据&#xff0c;使用ArcGIS或者QGIS按照矢量边界进行按掩膜提取或者栅格裁剪以后&#xff0c;其值的范围发生了变化&#xff0c;如下&#xff1a; 可以看到&#xff0c;不论是按掩膜提取还是进行栅格裁剪后&#xff0c;其值的范围均与原来栅…

劫持微信聊天记录并分析还原 —— 合并解密后的数据库(三)

本工具设计的初衷是用来获取微信账号的相关信息并解析PC版微信的数据库。 程序以 Python 语言开发&#xff0c;可读取、解密、还原微信数据库并帮助用户查看聊天记录&#xff0c;还可以将其聊天记录导出为csv、html等格式用于AI训练&#xff0c;自动回复或备份等等作用。下面我…