首页 > 其他分享 >abc 330E mex

abc 330E mex

时间:2023-12-11 15:01:44浏览次数:30  
标签:abc 复杂度 330E 每次 枚举 set mex

题意: 对单个固定序列多次操作,输出每次操作后的mex函数值。

E - Mex and Update (atcoder.jp)

不能用博弈论求sg函数那种直接枚举(TLE),因为最差可能达到O(n2),就算每次基于上一次的mex来剪枝也会被卡到这个复杂度,因为每次都只能线性枚举,所以这个方法不合适。

因为mex可能取值的情况最多不超过n+1个,所以可以使用stl中的set,来枚举没有在0~n出现的数字,这样做的好处是每次都可以O(1)的找到对应的数(set的第一个元素),并且维护这个单调递增的序列每次只需要O(logn)的复杂度,总的来说就是O(nlogn)。

标签:abc,复杂度,330E,每次,枚举,set,mex
From: https://www.cnblogs.com/Fluoresce/p/17894415.html

相关文章

  • [ABC304Ex] Constrained Topological Sort 题解
    题意给定一张有向图\(G\),有\(n\)个点和\(m\)条边,问是否存在一种拓扑序的排列\(P\)使得\(l_{i}\lep_{i}\ler_{i}\)。思路首先对于一条边\(u\tov\),如果限制满足\(r_{v}\ler_{u}\)或者\(l_{v}\gel_{u}\)的话,那么这个限制其实是不完全正确的。因为最终的序列......
  • 【题解】AtCoder abc322_f Random Update Query
    传送门:https://atcoder.jp/contests/abc332/tasks/abc332_f容易发现,对于一个位置$i$,$A_i$的最终值是由对$i$的最后一次赋值操作决定的;因此,将所有操作按时间顺序倒过来考虑,则由第$j$次操作决定$A_i$最终值的概率为"在第$(j+1)$~$m$次操作中没有修改过$i$的概率"与"第......
  • AtCoder_abc332
    AtCoder_abc332比赛链接A-OnlineShoppingA题链接题目大意这里有\(N\)件商品,第\(i\)件商品价格为\(P_i\),你要购买\(Q_i\)件,除了购买的费用外,他还要支付运费。如果购买的总价大于\(S\),运费为0元,否则他需要支付\(K\)元的运费。他一共要花多少钱呢?解题思路无代码//Prob......
  • 【题解】AtCoder abc332_g Not Too Many Balls
    传送门:https://atcoder.jp/contests/abc332/tasks/abc332_g看完题,第一眼反应为最大流。建模方式为:以颜色为左部点,盒子为右部点,源点$S$向颜色$i$连一条容量为$A_i$的边,盒子$j$向汇点$T$连一条容量为$B_j$的边,颜色$i$向盒子$j$连一条容量为$ij$的边;在这张图......
  • Atcoder abc301 复盘(更新中)
    跳转比赛链接A-OverallWinner简述:高桥和青木下了\(N\)盘棋。给你一个长度为\(N\)的字符串\(S\),表示这两盘棋的结果。如果\(S\)的\(i\)个字符是t,那么高桥赢得了\(i\)局;如果\(S\)的\(i\)个字符是A,那么青木赢得了这局。高桥和青木之间的胜负关系是谁赢的局......
  • ABC312 复盘
    ABC312复盘At链接LG链接AChord思路解析:水题,一个if即可#include<bits/stdc++.h>usingnamespacestd;strings;intmain(){ cin>>s; if(s=="ACE"||s=="BDF"||s=="CEG"||s=="DFA"||s=="EGB&qu......
  • ABC301 复盘
    ABC301复盘At链接LG链接[ABC301A]OverallWinner思路解析:从头开始遍历字符串,遇到一个字符就给对应的一方加分,输出第一个胜场大于\(\lceiln/2\rceil\)的一方。#include<bits/stdc++.h>usingnamespacestd;intn;stringstr;intmain(){ cin>>n; cin>>str......
  • [ABC241Ex] Card Deck Score 题解
    题目链接点击打开链接题目解法个人认为推式子很妙的生成函数题暴力套上生成函数,\(ans=[x^m]\prod\limits_{i=1}^{n}(\sum\limits_{j=1}^{b_i}(a_ix)^j)\)\(\sum\limits_{j=1}^{b_i}(a_ix)^j=\frac{1-(a_ix)^{b_i+1}}{1-a_ix}\)所以\(ans=[x^m]\prod\limits_{i=1}^{n}\frac{......
  • AT_abc312复盘
    AT_abc312复盘A一眼过去直接\(if\)秒了ACcode:#include<bits/stdc++.h>usingnamespacestd;strings;intmain(){cin>>s;if(s=="ACE"||s=="BDF"||s=="CEG"||s=="DFA"||s=="E......
  • [ABC254Ex] Multiply or Divide by 2
    [ABC254Ex]MultiplyorDivideby2题意:给定大小为$n$的集合$A$和$B$,你可以对集合$A$中的元素$a_i$进行两种操作,分别为$a_i\leftarrow\lfloor\dfrac{a_i}{2}\rfloor$,和$a_i\leftarrowa_i\times2$。你需要操作集合$A$直至集合$A,B$完......