首页 > 其他分享 >CF1398E Two Types of Spells 题解 set

CF1398E Two Types of Spells 题解 set

时间:2023-05-30 15:55:04浏览次数:71  
标签:set 题解 sum 元素 Two 数值 st st2 sum2

题目链接:https://codeforces.com/problemset/problem/1398/E

题目大意

你有一个集合,初始为空。

有两种类型的元素,一种是普通元素,一种是强化元素,两种元素都有一个数值。

有 \(n\) 次操作,每次操作会往集合中加入一个元素或者删除一个元素。

每次操作后,你都需要确定集合中元素的一个排列,使得排列的价值最大。

排列价值的计算规则是:

每个元素的价值就是它对应的数字,但是强化元素能够使它在排列中后一个位置的元素的价值翻倍(即:对于排列中某一个元素来说,如果它前一个位置的元素是一个强化元素,则这个元素的价值是它本身的数值 \(\times 2\))。

举个例子,假设现在有三个元素:

  • 第 \(1\) 个元素是一个数值为 \(5\) 的普通元素;
  • 第 \(2\) 个元素是一个数值为 \(1\) 的强化元素;
  • 第 \(3\) 个元素是一个数值为 \(8\) 的强化元素。

则:

  • 如果按照第 \(1\) 个元素,第 \(2\) 个元素,第 \(3\) 个元素排列,对应的价值为 \(5 + 1 + 2 \cdot 8 = 22\) ;
  • 如果按照第 \(1\) 个元素,第 \(3\) 个元素,第 \(2\) 个元素排列,对应的价值为 \(5 + 8 + 2 \cdot 1 = 15\) ;
  • 如果按照第 \(2\) 个元素,第 \(1\) 个元素,第 \(3\) 个元素排列,对应的价值为 \(1 + 2 \cdot 5 + 8 = 19\) ;
  • 如果按照第 \(2\) 个元素,第 \(3\) 个元素,第 \(1\) 个元素排列,对应的价值为 \(1 + 2 \cdot 8 + 2 \cdot 5 = 27\) ;
  • 如果按照第 \(3\) 个元素,第 \(1\) 个元素,第 \(2\) 个元素排列,对应的价值为 \(8 + 2 \cdot 5 + 1 = 19\) ;
  • 如果按照第 \(3\) 个元素,第 \(2\) 个元素,第 \(1\) 个元素排列,对应的价值为 \(8 + 2 \cdot 1 + 2 \cdot 5 = 20\) 。

解题思路

假设任意次操作之后,集合中有 \(m\) 个普通元素,和 \(k\) 个强化元素。则:

  • 若数值最大的 \(k\) 个元素 不全是 强化元素,则答案为:所有元素的数值和 + 数值最大的 \(k\) 个元素的数值和
  • 若数值最大的 \(k\) 个元素 全是 强化元素,则答案为:所有元素的数值和 + 数值最大的 \(k-1\) 个元素(当然它们都是强化元素)的数值和 + 数值最大的 \(1\) 个非强化元素的数值

示例程序

实现时,用:

  • \(st[0]\) 保存普通元素(\(m\) 对应普通元素个数);
  • \(st[1]\) 保存强化元素(\(k\) 对应强化元素个数);
  • \(st2[1]\) 保存数值最大的 \(k\) 个元素;
  • \(st2[0]\) 保存除了数值最大的 \(k\) 个元素以外其余的元素;
  • \(sum\) 对应 \(st2[1]\) 中数值最大的 \(k\) 个元素之和;
  • \(sum2\) 对应目前所有元素之和

(命名比较随意,主要是因为写的时候发现少了又加了一个;包括 \(st2[0]\) 和 \(st2[1]\) 一开始我是开了两个堆,结果发现堆不支持随机删除囧)

#include <bits/stdc++.h>
using namespace std;

int n, p, d, m, k;
set<int> st[2], st2[2];
long long sum, sum2;    // sum 记录前k大值之和,sum2 记录所有值之和

int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &p, &d);
        if (d > 0) {
            st[p].insert(d);
            p ? k++ : m++;
            st2[0].insert(d);
            sum2 += d;
        }
        else {  // d < 0
            d = -d;
            p ? k-- : m--;
            st[p].erase(d);
            if (st2[0].count(d)) st2[0].erase(d);
            else {
                st2[1].erase(d);
                sum -= d;
            }
            sum2 -= d;
        }
        while (st2[0].size() && st2[1].size()) {
            int x = *st2[0].rbegin();
            int y = *st2[1].begin();
            if (x > y) {
                st2[0].erase(x);
                st2[1].erase(y);
                st2[0].insert(y);
                st2[1].insert(x);
                sum += x - y;
            }
            else
                break;
        }
        while (st2[1].size() < k) {
            assert(!st2[0].empty());
            int x = *st2[0].rbegin();
            st2[0].erase(x);
            st2[1].insert(x);
            sum += x;
        }
        while (st2[1].size() > k) {
            assert(!st2[1].empty());
            int x = *st2[1].begin();
            st2[1].erase(x);
            sum -= x;
            st2[0].insert(x);
        }
        long long ans;
        if (st[0].empty())
            ans = sum2 + sum - (*st[1].begin());
        else if (st[1].empty())
            ans = sum2;
        else if (*st[0].rbegin() < *st[1].begin())
            ans = sum2 + sum - (*st[1].begin()) + (*st[0].rbegin());
        else
            ans = sum2 + sum;
        printf("%lld\n", ans);
    }
    return 0;
}

标签:set,题解,sum,元素,Two,数值,st,st2,sum2
From: https://www.cnblogs.com/quanjun/p/17443454.html

相关文章

  • Wallys/Qualcomm network chip/ipq9574/ipq9554/wireless connectivity solutions.
     QualcommWi-Fi7networkchipsolutionsIPQ9574andIPQ9554areadvancedwirelessconnectivitysolutionsdevelopedbyQualcommTechnologies.ThesechipsaredesignedtosupporttheWi-Fi7(802.11be)standard,whichofferssignificantimprovementsinspe......
  • 第十四届蓝桥杯大赛青少组全国总决赛初级组C++C++题解
    第十四届蓝桥杯大赛青少组全国总决赛初级组\(C++\)题解第一题给定一个十进制正整数\(N(1≤N≤10^9)\),请从小到大输出\(1\)~\(N\)之间(含\(1\)和\(N\))所有满足以下要求的数:这个数转换为八进制后是一个回文数;这个数是一个平方数。例如:\(N=20\),在\(1\)~\(20\)之间满足要求......
  • 3.4. Java集合框架(List、Set、Map等)
    Java集合框架是Java提供的一套用于存储和操作数据的接口和类。它包括以下几个主要部分:接口:集合框架定义了一系列接口,如Collection、List、Set、Map等。实现类:集合框架提供了一些实现这些接口的类,如ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等。......
  • [ABC302F]MergeSet
    AGC010BBoxes这道题其实是一道01BFS求最短路的模型,但是建模比较难想。首先需要想到对于每个集合内的点两两连边,边权为\(1\),由于开始和结束时需要从起点到中转点和中转点到终点,而我们要求的其实是中转点的数量,如果我们直接求一遍最短路(这样的话用的是普通bfs),中准点之间是an......
  • bash: 警告:setlocale: LC_TIME: 无法改变区域选项 (zh_CN.UTF-8)
    使用ssh远程登陆centos,出现如下告警信息:bash:警告:setlocale:LC_TIME:无法改变区域选项(zh_CN.UTF-8)原因分析:系统已经设置了默认地区_语言.字符集为zh_CN.UTF-8,但是在系统中没有定义对应的locale文件,所以只需要手动生成这个locale文件即可!解决办法:1)#vim/etc/environment......
  • <script> 和 <script setup> 的一些主要差别
    <scriptsetup>是Vue3中的新特性,它是一种简化和更具声明性的语法,用于编写组件的逻辑部分。相比之下,<script>是Vue2中常用的编写组件逻辑的方式。下面是<script>和<scriptsetup>的一些主要差别:语法简洁性:<scriptsetup>的语法更为简洁。它使用了更少的......
  • 山东二轮省集题解合集
    山东二轮省集题解合集Day1A打表,发现答案是\(\prod\limits_{i=1}^n(2i-1)\)。证明可以考虑拿GF推。首先有dp,\(f(i,j)\)表示到第\(i\)个括号当前左括号减右括号的个数为\(j\),转移是简单的\(f(i,j)=f(i,j+1)+f(i,j-1)\times(j-1)\)把\(f(i,j)\)写成一个形式幂级......
  • 欢乐结训赛题解
    欢乐结训赛题解A题目链接题目大意给你一个字符串,让你求字符串中最大的字母在字母表中排第几例如codeforces中s的是最大的s在字母表中排19位代码#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;constintmod=1e9+7;voidsolve()......
  • [CVPR23 Highlight] Side Adapter Network for Open-Vocabulary Semantic Segmentatio
    **摘要本文提出了一个用于开放词汇语义分割的新框架SAN,将语义分割任务建模为区域识别问题,提取maskproposals并使用CLIP对mask进行识别。SAN可以重新利用CLIP的特征,因此其本身可以非常轻量;同时网络可以端到端地进行训练,从而使SAN适应冻结的CLIP模型。本文方法需要很少的参数量,且......
  • 第十二届蓝桥杯c++b组国赛题解(还在持续更新中...)
    试题A:带宽解题思路:由于小蓝家的网络带宽是200Mbps,即200Mb/s,所以一秒钟可以下载200Mb的内容,根据1B=8b的换算规则,所以200Mb=200/8MB=25MB。所以小蓝家的网络理论上每秒钟最多可以从网上下载25MB的内容。代码实现:#include<iostream>#include<algorithm>usingnamespacestd......