首页 > 其他分享 >The 2024 CCPC Shandong Invitational Contest and Provincial Collegiate Programming Contest

The 2024 CCPC Shandong Invitational Contest and Provincial Collegiate Programming Contest

时间:2024-10-04 22:01:06浏览次数:10  
标签:Provincial Shandong le log Contest dep 线段 pos ls

比赛链接

C. Colorful Segments 2

考虑最小的分组数量,可以先按左端点排序,然后每次贪心地找到前面一个最大右端点 \(r_j < l_i\) 的组加入。

考虑计数,还是同样地按左端点排序,那么假设现在有 \(k\) 个组,每个组最大右端点是 \(g_i\)(没有元素则 \(g_i = 0\)),那么每次可以选择一个 \(g_j < l_i\) 的组并且把 \(g_j\) 更新为 \(l_i\)。注意到我们不需要关心具体的 \(g_j\),只用关心 \(g_j < l_i\) 的数量。由于 \(l_i\) 是单增的,所以所有 \(g_j < l_i\) 的组 \(j\) 本质相同。那么就是每次查询 \(g_j < l_i\) 的数量,并且将其减 \(1\),并插入一个 \(r_i\),可以用堆模拟。复杂度 \(\Theta(n \log n)\)。

E. Sensors

由于恰好有 \(1\) 个点的线段是有用的,且每个点不会被重新加入,那不妨考虑每次删除点的时候快速找到所有从 \(>1\) 个变成 \(1\) 个的线段,和从 \(1\) 个变成 \(0\) 个的线段。

从 \(1\) 个变成 \(0\) 个是好维护的,只需要把 \(1\) 个的线段插入到那个点的 vector 中,删除的时候直接减去所有的贡献即可。

从 \(>1\) 个变成 \(1\) 个时,线段的左右端点恰好跨越一个点。设当前剩下的点坐标是 \(pos_1 < pos_2 < ... < pos_m\) 那么不妨用一个 multiset 维护每个 \(r_j \in [pos_i, pos_{i+1} - 1]\) 的 \(l_j\),删除 \(pos_i\) 时直接把 \(st_{pos_i}\) 合并到 \(st_{pos_{i-1}}\),并访问 \(st_{pos_{i-1}}\) 和 \(st_{pos_{i+1}}\) 最大的 \(l_j\) 更新即可。复杂度 \(\Theta(n\log^2n)\)。

考虑更优秀的复杂度,把每个线段插入到线段树上的 \(\log n\) 个节点,然后对于每个线段维护它所在的所有节点中点个数 \(=0,=1,>1\) 的节点个数,当更新一个节点 \(u\) 时,若 \(sum_u \le 1\) 就访问所有这个节点上的线段更新即可。复杂度 \(\Theta(n\log n)\)。

G. Cosmic Travel

差分转化为 \(x \le m\) 的第 \(k\) 大和,那么套路地枚举 \(x\) 和 \(m\) 的 lcp 下一位,在 trie 上模拟前这些位(若这一位是 \(0\),则先看 \(siz_{ls}\),不够就到 \(rs, k \leftarrow k - siz_{ls}\)),然后拆成 \(\Theta(\log V)\) 个询问一个子树异或任意数(不能超过这个子树能表示的最大数)的第 \(k_i\) 大和。注意到这个东西是与询问无关的,设 \(dp_{i,j}\) 为 \(i\) 子树异或任意数的第 \(j\) 大和,状态数量为 \(\Theta(n \log V)\) 的(每个叶子统计 \(\Theta(\log V)\) 次)。

这里为了方便,可以把和设为只看子树里的这些位的和,类似地模拟转移即可。

复杂度 \(\Theta((n+q)\log V)\)。

L. Intersection of Paths

考虑对于一个 \(k\),有那些点可能成为并的一个端点,考虑每一条边 \((u,v)\),如果删掉这条边后 \(\min(siz_u,siz_v) \ge k\) 这条边就合法,那么 \(u,v\) 就合法。那么假如不考虑更改边的话,答案就是只取这些点组成的虚树(一定是原树的一个联通块)的直径。

考虑 \(k\) 不同,并且加入更改边,由于大的 \(k\) 对应联通块一定被小 \(k\) 对应的完全包含,那么可以直径从小到大扫描线,每次从 \(k \to k + 1\) 时,把 \(\min(siz_u,siz_v) = k\) 的边删掉(更改边权为 \(0\))。

那么就是要实现动态修改边权,查询直径。考虑在欧拉序上做,每次遍历到 \(u\) 在 dfs 序后加入 \(u\),遍历 \(u\) 的 每个 儿子回来后再加入 \(u\)。然后就是要找到一个区间 \([l,r]\) 的 \(\max\limits_{l\le L \le a \le R\le r} dep_L + dep_R - 2 \times dep_a\),其中 \(a\) 肯定是 \([L,R]\) 中 \(dep\) 最小那个。于是线段树上维护区间信息 \(ans,ansl,ansr,maxd,mind\) 对应上述答案、\(\max\limits_{L \le a} dep_L - 2 \times dep_a\)、\(\max\limits_{a \le R} dep_R - 2 \times dep_a\),最大和最小 \(dep\)。合并时 \(ans = \max(ans_{ls},ans_{rs},ansl_{ls}+maxd_{rs},maxd_{ls}+ansr_{rs})\),\(ansl = \max(ansl_{ls},ansl_{rs},maxd_{ls} - 2\times mind_{rs}),ansr=\max(ansr_{ls},ansr_{rs},maxd_{rs} - 2\times mind_{ls})\)。

显然支持修改,复杂度 \(\Theta((n+q)\log n)\)。

标签:Provincial,Shandong,le,log,Contest,dep,线段,pos,ls
From: https://www.cnblogs.com/MiniLong/p/18447323

相关文章

  • The 2024 CCPC Shandong Invitational Contest and Provincial Collegiate Programmin
    Preface传说中被杭电1h十题的比赛,结果打到结束也只会10题这场开局就不太顺,一个Easy题C卡到2h的时候才出,虽然中期题基本都能想到但还是出的很慢最后1h讨论了下L的大致做法发现了几个关键性质后觉得写不完了,遂摆烂滚去打炉石了A.Printer签到,二分答案大力检验即......
  • The 2021 ICPC Asia Shenyang Regional Contest
    B-BitwiseExclusive-ORSequence题意\(n\)个数,\(m\)个关系,每个关系形如\(a_u⊕a_v=w\),表示第\(u\)个数与第\(v\)数的异或运算结果为\(w\)。求是否有这样的\(n\)个数满足所有关系要求,如果没有输出\(-1\),如果有输出所有满足要求的方案中,所有数字的和的最小值。思路建图......
  • Skills - 2022 International Collegiate Programming Contest, Jinan Site, Problem
    有3种技能,\(n(\le10^3)\)天内每天可以对一个技能进行学习,第i天学习第j个技能可以为第j个技能增加\(a_{i,j}(\le10^4)\)的熟练度。在第i天结束时,每个技能的熟练度会减去距离上次学习该技能的天数,但最多减到0。求n天后能得到的熟练度的和的最大值。首先容易有一个显然的dp状态:\(f......
  • AtCoder Beginner Contest 373
    省流版A.暴力即可B.求出字母位置,绝对值相加即可C.显然答案为两个数组的最大值的和D.注意直接BFS的点权范围不超过题目范围,直接BFS即可E.发现单调性,二分票数,用前缀和\(O(1)\)判断可行性即可F.朴素背包DP,相同重量的物品一起考虑,用优先队列求解\(l\)个相同重量物品最大......
  • The 2023 ICPC Asia Macau Regional Contest
    A.(-1,1)-Sumplete首先只取\(-1\),这样的话选1和不选-1产生的贡献就是都是+1。枚举每一行,然后贪心选择需求最大的若干列。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;usingpi......
  • The 2024 Guangdong Provincial Collegiate Programming Contest
    Preface这场据说题挺毒的?但实际打的时候感觉也还好,3h就出了7个题,然后被H卡飞了赛后发现是没有观察到构造的解的性质,把Dinic换成匈牙利就过了,只能说对flow的理解不够B.腊肠披萨神秘string题,被徐神开场一眼秒了,虽然中间我和祁神上去写了三个签到,但徐神还是在1h不......
  • AtCoder Beginner Contest 365
    A-LeapYear思路模拟即可;AC代码#include<bits/stdc++.h>#defineendl'\n'#defineintintlonglong#definepbpush_back#definebsbitsetusingnamespacestd;typedefpair<char,int>PCI;typedefpair<......
  • ABC 模拟赛 | A Passing Contest 001题解记录(A,B,C,D)
    比赛链接https://www.luogu.com.cn/contest/126344[APC001]A-CT不必多说,多次取模#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<queue>#include<deque>#include<math.h>#include<map>......
  • The 2024 ICPC Asia East Continent Online Contest (II)
    A.GamblingonChoosingRegionals最差情况就是,强队都和你去一起。因此赛站越小,排名也一定越小。然后只要动态实现出每个学校最强的若干只队伍就好了。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64using......
  • 题解:AtCoder Beginner Contest AT_abc373_d ABC373D Hidden Weights(格式美化版)
    题目传送门题目翻译给你一个NNN个点,MMM条边的有向图,其中边有边......