首页 > 其他分享 >9.25模拟赛

9.25模拟赛

时间:2022-09-25 21:57:29浏览次数:62  
标签:9.25 黑点 归属 信息 管辖 操作 维护 模拟

T1 数数

贪个心,比较显然

T2 数树

考虑求出不合法的部分,然后做容斥,但是容斥系数我不会配

T3 鼠树

大nb题

单点权实际上就是它的归属点的权,动态维护每个点的归属点是比较好做的,树剖一下拿个set维护重链上的黑点就行,注意求归属点时的细节,不是简单的prev upperbound

考虑查询修改都怎么做。由上面的性质,我们实际上只需要维护黑点有关信息就行了。上线段树维护黑点的权,黑点的管辖点的个数,权与个数的乘积。

  • 操作1
    找到归属点,查询它的值。
  • 操作2
    直接在维护黑点信息的树上单点修改
  • 操作3
    子树内的黑点显然都是完全贡献的,与根相连的一个联通块的归属点可能在子树外,找到根的归属点的权,乘上这个联通块的大小就可以跑路了
  • 操作4
    直接在维护黑点信息的树上区间修改
  • 操作5
    计算出它的管辖点的个数,并继承它原来的归属点的权,修正它原来的归属点的管辖大小。
  • 操作6
    将这个点的权与上一层黑点的权作差下放到管辖点,实现就另开一棵线段树直接做子树加,然后调一次四操作把多的去掉。

T4 ckw的树

nb题 不会


T1 回文

比较水的Dp,枚举步数只记录行信息就能推出列信息,转移很显然。统计答案时分奇回文偶回文选一下交点就行

T2 快速排序

对着它给的Qsort优化是没有任何前途的。如果是nan就直接输出跑路,否则就是把比它严格小的数排好序丢到它前边,维护个当前扫过的数的最大值就行了。

T3 混乱邪恶

数学题,直接粘了,为什么错误的DFS和贪心能拿那么多分
image

T4 校门外歪脖树上的鸽子

最后俩字比较符合这题。

zkw线段树的思想。考虑把给的树剖掉,区间变成左开右开,跳一边维护另一边就行。
码咕了。

标签:9.25,黑点,归属,信息,管辖,操作,维护,模拟
From: https://www.cnblogs.com/Delov/p/16729076.html

相关文章

  • 闲话?2020.9.25
    //闲话的真正形态是什么?我至今为止的可以称之为闲话的博都有在“雕琢”(用输入法打you第一个字是幼,不愧是我。),但这是否违背了闲话的初衷?一篇闲话会用VScode写上一两......
  • 【闲话】2022.09.25
    考试++虽然我个人习惯是++i。hereRSY大佬大家快去关注\(\texttt{_RSY_}\)大佬!顺便记得不要像我一样写题解的时候老爱加空格。失踪人口回归L回来了(说起来L......
  • CSP-S模拟11[回文, 快速排序, 混乱邪恶, 校门外歪脖树上的鸽子]
    T1回文显然,这玩意和传纸条长得贼像,然后对于我赛时调了\(1\)个多小时的\(n^{2}\)做法感到抱歉....我tnm竟然想优化复杂度?看到数据范围,显然可以发现\(n^{4}\)过......
  • 9.25
    本周学习总结1.计算机基础2.typora软件和markdown语法3.python解释器和环境4.pycharm5.PEP8规范计算机基础1.计算机的本质​ 计算机也称之为"电脑">>>:通电的大脑......
  • CSP-S模拟11
    T1.回文传纸条——坐标dp。对于学过坐标dp的人来说应该是签到题吧。把回文抽象成两个人分别从\((1,1),(n,m)\)出发,走路径相同的方案数。直接定义\(dp[i][j][s][t]\)为......
  • 20220925 - CSP-S 模拟赛 #2
    20220925-CSP-S模拟赛#2时间记录\(8:00-8:20\)浏览题面\(8:20-8:45\)T1想到了分块计算,但是在手推样例的过程中,发现样例的数据并不能真正构成一局“扫雷”......
  • 「模拟赛20220924」巧立名目
    题目给定一棵\(n\)个结点的树。现在有\(k\)个人,每个人最初在\(s_k\),最终必须到达\(t_k\)。每个结点有一个势能\(\varphi\)。某一时刻,如果\(k\)个人的位置分别为......
  • 20220924模拟赛解题报告
    概要我AK了,srds因为有Q老师的免费测试套餐,才发现题目名错了(。题目难度不大题目T1随便脚算一下人数完了比赛后\(-\)比赛前\(+\)晋级的。code:#include<bits/......
  • 20220924--CSP-S模拟10
    A.欧几里得的噩梦首先发现第一问所询问的异或值数量就是所求的第二问的最小集合的元素个数次方因为除去集合里的任一一个元素,其中若干个元素异或之后的集合就不可能为原......
  • CSP-S模拟10
    T1.欧几里得的噩梦第一眼,这不是线性基板子题吗。但是值域是\(2^{5e5}\),但是我们发现它的一个神奇性质,一个数的二进制中只有两个一。我们定义高位为x,低位为y。如果线性基中......