首页 > 其他分享 >2021 Hubei Provincial Collegiate Programming Contest/2021湖北省赛 题解

2021 Hubei Provincial Collegiate Programming Contest/2021湖北省赛 题解

时间:2024-11-16 22:40:09浏览次数:1  
标签:Provincial 题解 复杂度 枚举 团内点 b0 2021 权值

按解决顺序排列

目录

F

二分答案ans,放最小的前ans个bi(变成必须放完)

因为bi=2^k,所以小的放了可能会拆散大的空间,大的把小的地方占了的话小的可以塞其他地方,所以先放大的

然后暴力能放则放,最多log次指针回到开头

所以一次求解O(nlogn),总复杂度log^2

A

模拟,暴力枚举暴力异或

注意X串要多留k-1位

I

把限制Pa!=b变成叉掉点(a,b),画一下发现问题等于求多少个内部没有叉的合法矩形 (a~b,L~R)

经典问题(疑似),枚举R,维护每个点(x,R)左边的最大长度,那么一对a0,b0对应 min L[x] (x in (a0,b0)) 个 (a0~b0,某L,R) 的矩形,单调栈维护,在弹掉时可以求出跨过某x的方案

D

枚举r,倒着枚举l,依次把a[l]在权值数轴上点亮

然后经典问题维护连续区间个数,个数=点-边,边就是相邻两个都点亮了的,个数<=2合法

(tips:可以做到O(nlogn)……)

H

题意:每次把当前图的x->y->z->...->x且权值和<=3的环的权值变为0,然后持续操作直到不能变为止,求最短路

一开始会把三元环给边0,然后 三元环点->x->(y)->三元环点 的点变0,如此反复

可以发现权值变为0等于缩点,缩得的团内的边都是0,团外边位1,现在要模拟缩点的过程

记点x的入边对应团集合为In[x],出为Out[x],那么 团内点->x->(y)->团内点 的判定条件为 In[x]&Out[y]!=0,枚举x,y(若没有y则会枚举y=团内点,也可以判到),bitset优化判断即可

一共缩n次,每次枚举m条边,check复杂度n/ω,所以总复杂度O(n^2m/ω)

E

神题,我懂得欣赏

https://www.cnblogs.com/gmh77/p/18550020

C

(咕)

K

J

G

B

标签:Provincial,题解,复杂度,枚举,团内点,b0,2021,权值
From: https://www.cnblogs.com/gmh77/p/18550028

相关文章

  • ABC380题解(F&G)
    ABC380F.ExchangeGame因为\(n+m+k\leq12\),考虑状压dp,设\(f(x,s1,s2,s3)\)表示先手,后手,桌子上的牌分别是哪一些,这有\(O(3^n)\)种状态。然后只要枚举出哪一张即可,有\(f(s1,s2,s3)\tof(s2,s1-i+j,s3+i-j)(i\ins1,j\ins3,a_j<a_i)\)\(f(s1,s2,s3)\tof(s2,s1-i,s3+i......
  • 2024ICPC南京部分题解
    LeftShifting3题面:给定一个长度为\(n\)的字符串\(S=s_0s_1\cdotss_{n-1}\),你可以将\(S\)向左移动最多\(k\)次(包括零次)。计算在操作后字符串中包含的“nanjing”子字符串的最大数量。更正式地说,让\(f(S,d)\)成为将\(S\)向左移动\(d\)次得到的字符串。也就是......
  • NOIP集训 P4137 Rmq Problem / mex 题解
    前置指使:可持久化线段树题解:P4137RmqProblem/mex有一个长度为\(n\)的数组\(\{a_1,a_2,...,a_n\}\)。\(m\)次询问,每次询问一个区间内最小没有出现过的自然数。Input第一行,两个正整数\(n,m\)。第二行,\(n\)个非负整数\(a_1,a_2,...,a_n\)。接下来\(m\)行,每......
  • 蓝桥杯模拟赛(第一期)个人题解&感想
    林专大一牲第一次写blog,更新较慢,写的不好的地方请见谅(好多题目忘记了题号and暂时没有题目要求的内容…后面会补充的!)本次带来的是蓝桥杯模拟赛第一期的个人题解(笨人水平较低,大家可以在评论区指出错误/讨论更优解~)大多题我是用c++写的,但也掺了几道c,为以后全面用c++打比赛作过......
  • AI|经常崩溃的问题解决
    AdobeIllustratorCrashes网络上大部分说法都是重装AI,兼容性问题,管理员权限或者是版本不对,经测试均无效,甚至出现重装系统这种离谱的办法,正确的解决办法是把首选项的性能里的GPU取消勾选,或者再把电脑的虚拟内存扩大即可。 Step1:打开首选项 Step2:取消勾选GPU性能......
  • CF987 Div2 F 题解
    阶段1考虑我们每次随机删除两个然后询问,若中位数为\(\frac{n}{2},\frac{n}{2}+1\)称被删除的两个为基准数,用\(v_1,v_2\)代表。每次询问得到解的概率约为\(\frac{1}{2}\)。发现基准数一定一个\(<\frac{n}{2}\)一个\(>\frac{n}{2}+1\),且对于一次四个数的询问\(x......
  • [AGC018C] Coins 题解
    先全部选\(a_i\),假设\(b_i=b_i-a_i,c_i=c_i-a_i\)。那么题目转化为选\(y\)个\(b\)和\(z\)个\(c\)使得答案最大。会发现若\(i\)位置选的\(b\),\(j\)位置选的\(c\),那么需要满足\(b_i-c_i>b_j-c_j\)。我们按上述条件排序,这样一定是在左边选\(b\),右边选\(c\)。那......
  • 题解:ABC013D 阿弥陀
    先考虑\(D=1\),明显可以\(O(M)\)模拟预处理出在最上面的每个位置往下走会走到什么位置,之后每次就可以\(O(1)\)查询了。当\(D>1\)时,可以依赖预处理的数据每次\(O(D)\)暴力查询。又注意到每次对所有位置进行的变换操作是一样的,可以倍增后用类似快速幂的方法优化到\(O(\log......
  • CF2031D 题解
    原题链接最后悔的一集,感觉D\(<\)everything。考虑由确定的点推出其他点的答案,发现最高点的答案是确定的,设其位置为\(x\)。然后根据题目定义,发现可以分成\([1,x-1],[x,n]\)两个区间,\([x,n]\)答案均为\(h_x\)。对于\([1,x-1]\)区间,我们找到第一个\(>[x,n]\)区间最小......
  • 读数据质量管理:数据可靠性与数据质量问题解决之道05数据标准化
    1. 批处理1.1. 批处理在一段时间内收集数据,然后将大量数据“批处理”在离散的数据包中1.2. 直到20世纪10年代中期,批处理都是处理分析型数据最常用的方法1.3. 批处理比流处理要便宜得多,即使是对时间要求最苛刻的处理需求也足以满足1.4. 批处理是经过时间考验的标准,并且仍......