暑假杭二day5测试总结"/>
2019暑假杭二day5测试总结
2019暑假杭二day5测试总结
- T1
- 题目大意
- sol
- T2
- 题目大意
- sol
- T3
- 题目大意
- sol
T1
题目大意
吹雪养了一只猫,但是猫跑走了,于是她要把猫抓回来。
众所周知,猫总是喜欢乱跑,而且总是会跑进奇怪的地方:这个奇怪的地方可以被抽象成一张n个点m条边的无向图,且边的长度都为1;吹雪站在1号点,而跑走的猫可能出现在标号为2…n的点中的任意一个。
为了节省时间,吹雪一定要走两点间的最短路。
不幸的是,有q个事件,每个事件中都有一条边会被破坏,这使得某些点不能通过原有的最短路走到。
吹雪想知道前i个事件发生后有多少点到1号点的最短路长度被改变。
sol
这题我想了一个并查集的做法,将所有可能在最短路上的边都提取出来,建一个新图,然后将询问倒过来,在新图上执行加边操作,与1在同一个集合的点最最短路不变。
交上去后却发现并不能AC,边是有向的,并查集并不能直接将两个集合合并:
实线是已有边,虚线是要加的边。很明显并查集不能将1和3所在的集合合并。
正解是一个看似很暴力的解法,同样将所有可能在最短路上的边都提取出来,建一个新图,与1在同一个集合的点最最短路不变。维护方式为:给每个点记一个入度,入度为0就与1不连通(除1号点)。如果某个点的入度为0,再将从它出发的边都删除,维护其他点的入度,有时可能还需递归删除。
这个做法看似很暴力,但每条边只会被删一次,所以复杂度为 Θ ( n + m ) \Theta(n+m) Θ(n+m)。
T2
题目大意
夕立是一个总喜欢说poi~poi~
的女孩子。
有一天,夕立捡到一张写着 n ( n < = 1 0 7 ) n(n<=10^7) n(n<=107)个大写字母的纸条。她发现这些字母都属于POI
中的某一个。
出于对poi
的热爱,夕立定义这样一个字符串的优美度为字符串中恰好组成POI
的子序列个数。
她本想让你计算这个字符串的优美度,但仔细一想,这个问题太简单了。于是她提出了这样的问题:在原字符串中插入一个大写字母后最大的优美度是多少(可以插在开头和结尾或任意两个原有字母的中间)?
sol
先考虑计算原字符串的优美度,依次考虑每个字符,设 f 1 f_1 f1为出现了多少个P, f 2 f_2 f2为出现了多少个PO, f 3 f_3 f3为出现了多少个POI,每出现一个P, f 1 f_1 f1++,出现O, f 2 f_2 f2+= f 1 f_1 f1,出现I, f 3 f_3 f3+= f 2 f_2 f2。最终答案为 f 3 f_3 f3。
很容易发现P一定插在最前,I一定插在最后,先把这种情况算出来。对于O,设 p r e i pre_i prei为i之前有多少个P, l a s i las_i lasi为i之后有多少个I,如果O插在第i个字符之后,优美度为原串的优美度加 p r e i × l a s i pre_i\times las_i prei×lasi, Θ ( n ) \Theta(n) Θ(n)扫一遍即可。
解法应该到此为止,可串长有 1 0 7 10^7 107,优美度会爆long long
,且不能用__int128
,还要手写高精度。
T3
题目大意
长门和她的妹妹陆奥在玩臆象石。
臆象石是一种神奇的石头,每一块臆象石上都写着两个数字a[i]和b[i]。如果相邻的两块臆象石i和i+1满足gcd(a[i],a[i+1])>1,它们将可以融合在一起,并转化为b[i]+b[i+1]单位的石油(转化后两块石头都会消失,具体的转化方式参见样例2及其解释)。
由于臆象石的数量过多,长门使用了钞能力使得a[i]满足一些奇妙的性质。
请你帮助两姐妹确定转化顺序以获取尽可能多的石油。
臆象石数目为 n , n < = 6000 n,n<=6000 n,n<=6000。
样例2
4
2 1
3 1
3 1
2 1
4
样例2解释:先删去第二和第三颗石子,使得第一和第四颗石子相邻。最后删去第一和第四颗石子
sol
我开始想了一个 Θ ( n 3 ) \Theta(n^3) Θ(n3)的算法,设 f ( i , j ) f(i,j) f(i,j)为i到j能否消掉,算出这个后就好写了,转移为 f ( i , j ) = ( f ( i + 1 , j − 1 ) & & g c d ( a [ i ] , a [ j ] ) > 1 ) ∣ ∣ ( f ( i , k ) & & f ( k + 1 , j ) , i < = k < j ) f(i,j)=(f(i+1,j-1)\&\&gcd(a[i],a[j])>1)||(f(i,k)\&\&f(k+1,j),i<=k<j) f(i,j)=(f(i+1,j−1)&&gcd(a[i],a[j])>1)∣∣(f(i,k)&&f(k+1,j),i<=k<j)。
正解将这个转移进行了优化,从右往左依次计算,对于每个i,若 f ( i + 1 , j − 1 ) & & g c d ( a [ i ] , a [ j ] ) > 1 f(i+1,j-1)\&\&gcd(a[i],a[j])>1 f(i+1,j−1)&&gcd(a[i],a[j])>1,则i向j连一条边,连完后从i跑dfs,若能到达j,则 f ( i , j ) = 1 f(i,j)=1 f(i,j)=1,题目中的特殊性质为满足 f ( i + 1 , j − 1 ) & & g c d ( a [ i ] , a [ j ] ) > 1 f(i+1,j-1)\&\&gcd(a[i],a[j])>1 f(i+1,j−1)&&gcd(a[i],a[j])>1的情况为 c × n c\times n c×n, c c c为不大常数,则时间复杂度为 Θ ( n 2 ∗ c + n 2 l o g ( n ) ) \Theta(n^2*c+n^2log(n)) Θ(n2∗c+n2log(n)),前面是n次dfs,后面是连边的复杂度。
更多推荐
2019暑假杭二day5测试总结
发布评论