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

HDU 学数数导致的

题目解析

首先,数对是有序的,<1,2>和<2,1>被视为不同的两组数字。

其次,数对<p,q>的p和q可以相等。

子序列为 p 0 p q,观察到,中间要出现一个0。那么,我们只需要找到第一个 p 满足与前一个 p 中间隔了最少一个0,并记录它的位置。那么,在它位置之后出现的所有正整数组成的集合的大小,就是 p 对答案的贡献。

那么只需要先把满足条件的p的位置都求出来,然后按照从大到小的顺序排序一下,从后往前维护一个集合,然后遍历到p的位置的时候更新答案值,即可。

代码实现

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <utility>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
long long t, n, a[1000010], sum0, ans, num;
struct node {
    long long num0;
    long long pos;
}e[1000010];
vector<long long>pos;
bool vis[1000010] = {};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--) {
        sum0 = 0;
        ans = 0;
        num = 0;
        pos.clear();
        for (int i = 0; i < 1000010; i++) {
            vis[i] = false;
            e[i].pos = -1;
        }
        vis[0] = true;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] == 0)sum0++;//记录0出现过的次数
            else if (e[a[i]].pos == -1) {//如果a[i]之前没出现过,则记录位置和前导0的数量
                e[a[i]].pos = i;
                e[a[i]].num0 = sum0;
            }
            else if (e[a[i]].pos >= 0 && e[a[i]].num0 != sum0) {//如果出现过,则比较前导0的数量是否相等。若不等,则说明之间出现0,记录位置
                pos.push_back(i);
                e[a[i]].pos = -2;//打上标记,防止再被处理
            }
        }
        sort(pos.begin(), pos.end());//对位置进行排序
        for (int i = pos.size() - 1, j = n - 1; i >= 0; j--) {
            if (j == pos[i]) {//碰到符合的位置,则更新答案值
                ans += num;
                i--;
            }
            if (!vis[a[j]]) {//之前没遇到过,则放入集合中,更新集合大小
                vis[a[j]] = true;
                num++;
            }
        }
        cout << ans << "\n";
    }
}


http://www.kler.cn/a/585148.html

相关文章:

  • pjsip pjsua_media_config 结构体说明
  • 【MySQL】表的约束(上)
  • 如何筛选能实现共享自助健身房“灵活性”的物联网框架?
  • Java8的新特性
  • mov格式视频如何转换mp4?
  • C++ 左值(lvalue)和右值(rvalue)
  • DSTTN
  • Kafka×DeepSeek:智能决策破取经八十一难!
  • 批量压缩与优化 Excel 文档,减少 Excel 文档大小
  • 嵌入式八股ARM篇
  • MyBatis·下
  • AGI大模型(3):大模型生成内容
  • Vi/Vim命令详解:高效文本编辑的利器
  • C语言【数据结构】:理解什么是数据结构和算法(启航)
  • 51c大模型~合集7
  • 架构师论文《论云原生架构及其应用》
  • G-Star 公益行起航,挥动开源技术点亮公益!
  • C#中通过Response.Headers设置自定义参数
  • 万字讲清大模型的发展,按时间排序(1950年到2025年)
  • Python - 爬虫;爬虫-网页抓取数据-工具curl