codeforces C. Largest Subsequence

思路

  • 首先是要选出 L a r g e s t S u b s e q u e n c e Largest Subsequence LargestSubsequence ,第一个字符是整个串最大的,第二个是第一个的位置后面最大的 … \dots ,我用的是优先队列第一关键字大小,第二关键字位置。(其实不用这样,用栈就行,我复杂了)
  • 然后你会发现其 c y c l i c cyclic cyclic 次数是字符串长度减 1 1 1 ,过程就是交换首位字符的位置,向中心扩展。
  • 有可能你选出来的字符串从第一个开始有连续一样的,如: z z z d c zzzdc zzzdc z z z zzz zzz 就是连续一样的,试想如果是这样还是需要字符串长度减 1 1 1 次?当然不是,而是长度减去连续的长度。
  • 最后结束检查一遍是否 s o r t e d sorted sorted

Think Twice, Code Once

#include <bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define endl '\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
#define ct cin.tie(nullptr),ios_base::sync_with_stdio(false)
using namespace std;
typedef unsigned int ull;
typedef pair<int, int> pii;
int read(void) {
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x) {
    if (x < 0) x = -x, put(45);
    if (x > 9) write(x / 10);
    put((x % 10) ^ 48);
}
#define writeln(a) write(a), put(10)
#define writesp(a) write(a), put(32)
#define writessp(a) put(32), write(a)
const int N = 1e5 + 10, M = 1e5 + 10, SN = 1e3 + 10, mod = 998244353;
struct p {
    char s;
    int pos;
    il bool operator <(const p & b) const {
        return s < b.s || (s == b.s && pos > b.pos);
    }
};
signed main() {
    int T = read();
    while (T--) {
        int n = read();
        priority_queue<p> q;
        string s;
        cin >> s;
        bool f2 = 1;
        for (int i = 0; i < s.size(); ++i) q.push({s[i], i});
        vector<p> a;
        while (!q.empty()) {
            a.push_back(q.top());
            int pos = q.top().pos; q.pop();
            while (!q.empty() && q.top().pos < pos) q.pop();
        }
        int l = 0, r = a.size() - 1, cnt = a.size() >> 1;
        int cnt1 = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i].s == a[0].s) ++cnt1;
        }
        while (cnt--) swap(s[a[l++].pos], s[a[r--].pos]);
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] < s[i - 1]) {f2 = 0; break;}
        }
        f2? (write(a.size() - cnt1), put(10)): puts("-1");
    }
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

51单片机定时器

51单片机有两个16位定时器&#xff0c;今天复习了一下使用方法&#xff0c;发现当初刚开始学习51单片机时并没有记录&#xff0c;特此今天补上这篇博客。 下面是定时器的总览示意图&#xff0c;看到这个图就能想到定时器怎么设置&#xff0c;怎么开始工作。 第一步&#xff1a…

刷完这个笔记,18K不能再少了....

大家好&#xff0c;最近有不少小伙伴在后台留言&#xff0c;得准备年后面试了&#xff0c;又不知道从何下手&#xff01;为了帮大家节约时间&#xff0c;特意准备了一份面试相关的资料&#xff0c;内容非常的全面&#xff0c;真的可以好好补一补&#xff0c;希望大家在都能拿到…

EmbedAI:一个可以上传文件训练自己ChatGPT的AI工具,妈妈再也不用担心我的GPT不会回答问题

功能介绍&#xff1a; 个性化定制&#xff1a;提供灵活的训练选项&#xff0c;用户能够通过文件、网站、Notion文档甚至YouTube等多种数据源对ChatGPT进行训练&#xff0c;以满足不同领域和需求的个性化定制。广泛应用场景&#xff1a;ChatGPT支持多种用例&#xff0c;包括智能…

Jmeter吞吐量控制器使用小结

吞吐量控制器(Throughput Controller)场景: 在同一个线程组里, 有10个并发, 7个做A业务, 3个做B业务,要模拟这种场景,可以通过吞吐量模拟器来实现.。 添加吞吐量控制器 用法1: Percent Executions 在一个线程组内分别建立两个吞吐量控制器, 分别放业务A和业务B 吞吐量控制器采…

【算法系列篇】递归、搜索和回溯(三)

文章目录 前言什么是决策树1. 全排列1.1 题目要求1.2 做题思路1.3 代码实现 2. 子集2.1 题目要求2.2 做题思路2.3 代码实现 3. 找出所有子集的异或总和再求和3.1 题目要求3.2 做题思路3.3 代码实现 4. 全排列II4.1 题目要求4.2 做题思路4.3 代码实现 前言 前面我们通过几个题目…

蚂蚁集团5大开源项目获开放原子 “2023快速成长开源项目”

12月16日&#xff0c;在开放原子开源基金会主办的“2023开放原子开发者大会”上&#xff0c;蚂蚁集团主导开源的图数据库TuGraph、时序数据库CeresDB、隐私计算框架隐语SecretFlow、前端框架OpenSumi、数据域大模型开源框架DB-GPT入选“2023快速成长开源项目”。 &#xff08;图…

Kafka中Ack应答级别和数据去重

在Kafka中&#xff0c;保证数据安全可靠的条件是&#xff1a; 数据完全可靠条件 ACK级别设置为-1 分区副本大于等于2 ISR里应答的最小副本数量大于等于2&#xff1b; Ack应答级别 可靠性总结&#xff1a; acks0&#xff0c;生产者发送过来数据就不管了&#xff0c;可靠性差…

2023年国赛高教杯数学建模D题圈养湖羊的空间利用率解题全过程文档及程序

2023年国赛高教杯数学建模 D题 圈养湖羊的空间利用率 原题再现 规模化的圈养养殖场通常根据牲畜的性别和生长阶段分群饲养&#xff0c;适应不同种类、不同阶段的牲畜对空间的不同要求&#xff0c;以保障牲畜安全和健康&#xff1b;与此同时&#xff0c;也要尽量减少空间闲置所…

人工智能深度学习:探索智能的深邃奥秘

导言 人工智能深度学习作为当今科技领域的明星&#xff0c;正引领着智能时代的浪潮。深度学习和机器学习作为人工智能领域的两大支柱&#xff0c;它们之间的关系既有协同合作&#xff0c;又存在着显著的区别。本文将深入研究深度学习在人工智能领域的角色&#xff0c;以及其在各…

Android Termux安装MySQL数据库并通过内网穿透实现公网远程访问

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…

鸿蒙端H5容器化建设——JSB通信机制建设

1. 背景 2023年鸿蒙开发者大会上&#xff0c;华为宣布为了应对国外技术封锁的潜在风险&#xff0c;2024年的HarmonyOS NEXT版本中将不再兼容Android&#xff0c;并推出鸿蒙系统以及其自研的开发框架&#xff0c;形成开发生态闭环。同时&#xff0c;在更高维度上华为希望将鸿蒙…

GPT-4V被超越?SEED-Bench多模态大模型测评基准更新

&#x1f4d6; 技术报告 SEED-Bench-1&#xff1a;https://arxiv.org/abs/2307.16125 SEED-Bench-2&#xff1a;https://arxiv.org/abs/2311.17092 &#x1f917; 测评数据 SEED-Bench-1&#xff1a;https://huggingface.co/datasets/AILab-CVC/SEED-Bench SEED-Bench-2&…

基于主动安全的AIGC数据安全建设

面对AIGC带来的数据安全新问题&#xff0c;是不是就应该一刀切禁止AIGC的研究利用呢&#xff1f;答案是否定的。要发展AIGC&#xff0c;也要主动积极地对AIGC的数据安全进行建设。让AIGC更加安全、可靠的为用户服务。为达到此目的&#xff0c;应该从三个方面来开展AIGC的数据安…

C++中的并发多线程网络通讯

C中的并发多线程网络通讯 一、引言 C作为一种高效且功能强大的编程语言&#xff0c;为开发者提供了多种工具来处理多线程和网络通信。多线程编程允许多个任务同时执行&#xff0c;而网络通信则是现代应用程序的基石。本文将深入探讨如何使用C实现并发多线程网络通信&#xff…

【Netty】Netty核心概念

目录 NIO编程NIO介绍NIO和BIO的比较缓冲区(Buffer)基本介绍常用API缓冲区对象创建添加数据读取数据 通道(Channel)基本介绍Channel常用类ServerSocketChannelSocketChannel Selector (选择器)基本介绍常用API介绍示例代码 NIO 三大核心原理 Netty核心概念Netty 介绍原生 NIO 存…

verilog基础语法-计数器

概述&#xff1a; 计数器是FPGA开发中最常用的电路&#xff0c;列如通讯中记录时钟个数&#xff0c;跑马灯中时间记录&#xff0c;存储器中地址的控制等等。本节给出向上计数器&#xff0c;上下计数器以及双向计数器案例。 内容 1. 向上计数器 2.向下计数器 3.向上向下计数…

Minio文件服务器(上传文件)

官网&#xff1a;https://www.minio.org.cn/ 开源的分布式对象存储服务器 Window安装 用户名和密码相同 创建bucket&#xff0c;并且将策略改成public 一、添加依赖 二、代码 public class FileUploadTest{public static void main(String[] args) throws Exception{//…

RHEL8_Linux_Ansible常用模块的使用

本章主要介绍Ansible中最常见模块的使用 shell模块文件管理模块软件包管理模块服务管理模块磁盘管理模块用户管理模块防火墙管理模块 ansible的基本用法如下。 ansible 机器名 -m 模块x -a "模块的参数" 对被管理机器执行不同的操作&#xff0c;只需要调用不同的模块…

做计算,找天玑算!

天玑算科研服务_DFT计算_MD模拟_FEA_ML_相图计算200余位计算工程师均来自己TOP高校及科研院所&#xff0c;涉及第一性原理&#xff0c;分子动力学&#xff0c;有限元&#xff0c;机器学习&#xff0c;可为催化、电池、能源、化工、生物等重多领域提供技术支持&#xff0c;计算软…

基于Springboot的旅游网站设计与实现(论文+调试+源码)

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…
最新文章