首页 > 其他分享 >2023NOIP停课集训总结

2023NOIP停课集训总结

时间:2023-11-15 19:14:17浏览次数:46  
标签:集训 停课 Omicron 分块 2023NOIP 可以 复杂度 贪心

2023NOIP停课集训总结

​ 距离十八次的NOIP模拟赛结束只剩下三四天了,NOIP也将在11.18周六如期举行。

​ 在这次从2023.10.1至2023.11.18的集训中,我确实有了许多收获,感到自己的知识经验积累更加丰富。

​ 下面我将从几个方面对此次集训进行总结。

1.知识点的收获

  • 分块

    分块是一种相当优秀的均摊暴力算法,可以将 \(\Omicron(n)\) 时间复杂度的操作优化至均摊时间复杂度 \(\Omicron(\sqrt n)\)。

    通常当块长为 \(\sqrt n\) 时在块内的操作时间复杂度为 \(\Omicron(\sqrt n)\),而在不同块之间切换复杂度为 \(\Omicron(n)\),总时间复杂度为 \(\Omicron(n\sqrt n)\)。

  • 数论分块

    数论分块可以快速计算一些含有除法向下取整的和式。

    与分块类似,但块长并不是固定的,所有 \(\lfloor \frac{n}{i} \rfloor\) 相同的数将被分进同一块,打包计算(\(n\) 为参数,对 \(i\) 进行分块)。

    因为块长并非不变,数论分块通常使用双指针实现,空间复杂度可以被优化至 \(\Omicron(1)\)。

  • 树状数组

    树状数组可以在 \(\Omicron(logn)\) 的时间复杂度内进行单点的修改和区间查询,同时也可以对前/后缀的min/max进行 \(\Omicron(logn)\) 的维护。

    许多对于区间的查询都可以依靠树状数组将 \(\Omicron(n)\) 的时间复杂度优化至 \(\Omicron(logn)\),是一种非常简洁,实用的数据结构。

    在集训期间常出现需要使用它优化DP或优化区间查询的情况。

  • 动态规划

    我认为动态规划的难点在于其并没有通用的套路或模板。

    可能计数与最值的题可以相对容易的看出需要使用动态规划,但对于每一题的具体情况都需要具体的设计状态与状态转移方程,再在朴素的转移式上通过优化降低时间复杂度。这个过程需要思考与足够的练习才能比较正确与快速地完成。

    对于动态规划的细节会在下个方面进行总结。

  • 贪心

    非常好的得分算法,常常需要对题目进行建模后才能发现贪心性质。

    同时即便不符合贪心性质的算法也可以使用贪心猫分序。

    常使用调整法证明贪心:即通过假设某个最优解不符合贪心要求,然后再调整最优解,通过对其是否变劣来证明贪心策略的正确性。

    同时也存在调整法的贪心方法:每次判断当前情况是否可以通过调整来达到更优状态,不断使得当前局面更更优。

    典:JSOI2007 建筑抢修

  • 反悔贪心

    即可以撤销操作,重新进行更优决策的选择的贪心。

    实现方式通常有两种:

    1.通过堆实现:

    ​ 与调整法贪心类似,使用堆存储并查询最劣的决策并判断更换决策是否会使局面变得更优。

    典:CF865D Buy Low Sell High

    2.反悔自动机:

    ​ 即设计一种反悔策略,使得随便一种贪心策略都可以得到正解。

    ​ 基本的设计思路是:每次选择直观上最接近全局最优解的贪心策略,若发现最优解不对,就想办法自动支持反悔策略。(即自动机)

    ​ 一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。

  • 树链剖分

    树上非常典的操作,常用于处理树上路径问题。

    按照重链剖分或长链剖分的标准将树分成几个连续的部分(同一条链上的点的DFS序是连续的),对于每条链上连续的部分,可以通过线段树或树状数组 \(\Omicron(logn)\) 地维护区间信息。

  • 二维偏序

    最简单的一种二维偏序就是找逆序对了,使用树状数组维护。

    事实上许多问题都可以被转化为二维偏序问题,例如:

    $ i)$ 最长上升/下降/不降/不升子序列

    \(ii)\) 二维数点问题

    等等等等……

    实际上二维偏序就是通过排序来把第一维消掉,再按照第二维建树状数组,时间复杂度可以做到 \(\Omicron(nlogn)\)。

  • 哈希

    也是非常典的字符串算法了,底数常用131,模数常用1e9+7或直接unsigned long long自然溢出。

    对于区间修改或查询字符串值,可以用线段树维护,达到 \(\Omicron(logn)\) 的复杂度。每个节点存储哈希值和对应的区间字符串长度,合并节点 \(l,r\) 时值即为 $val_l+b^{len_r}*val_r $。

  • Trie树

    同样是非常基础万用的字符串数据结构。同时它有许多功能与哈希十分相似,例如字符串判重。

    但Trie树显然比哈希更加稳定。

    在功能相同的情况下,Trie树显然比哈希更加优秀。

2.一些经验积累和小细节及做题技巧

  • 关于DP

    首先在阅读题面时要仔细注意各种约束条件。基本上对于大部分转移约束条件在DP的状态设计与转移过程中都会被体现,也只有这样才能设计出可以被转移的状态。

    在转移过程中,一些区间求min/max或值的操作可以通过数据结构或前缀和来优化,降低时间复杂度。

    同时在状态的设计方面,如果状态设计的好,同样可以优化时间复杂度。

    for Example:

    :\(f_{i~,l~,r}\) 表示对于第 \(i\) 个数,保留区间 \([l,r]\) 的方案数,此时对于每次转移的时间复杂度都是 \(\Omicron(m^2)\) 的,总时间复杂度就是 \(\Omicron(nm^4)\) ;

    但如果考虑让 \(f_{i~,l~,r}\) 表示对于第 \(i\) 个数,保留区间 \([l^`,r^`](l\le l^` \le r^` \le r )\) 的总方案数,则每次转移时都可以用容斥 \(\Omicron(1)\) 地求值与继承值,总时间复杂度 \(\Omicron(nm^2)\)。

    但并非所有DP都需要将所有约束条件体现在状态中。

    for Example:
    :在此题中:对于 \(a_i\) 的限制,可以通过对 \(a_i\) 排序来自动地满足约束条件,同时可以使用组合数学来计算出 \(i\) 个人分配至 \(j\) 组地方案数,所以只需要设计出二维状态 \(f{_i,_j}\),表示确定了人数 \(\le i\) 的组数且有 \(j\) 个 \(a_t > i\) 的人加入的总方案数,再在前面乘上用组合数学计算出的系数,即可 \(\Omicron(n^2logn)\) 地转移。

  • 关于图论

    对于图论题来说,比较重要的一个步骤是建出图论模型,而这个步骤也是比较困难的一步。

    通常将题中有联系的点连边,观察得到的图能否使用图论算法解决。

    \(Trick:\) 对于图中有约束条件的点的连边(例如相邻点 \(u,v\) 选择 \(u\) 或 \(v\) 都只能得到他们的连边的一半的边权贡献,但同时选择则可以获得全部的边权贡献),则可以将边权拆开分至两个点,这样就可以将相联系的边权转化为两个独立的点权,可以方便地使用图论算法解决。

  • 关于题目性质

    对于大部分题目,我们都需要进行更深入地观察与分析。对于题目性质的掌握是至关重要的,他决定着你能否在此题上得到更多的分数。

    手动模拟样例是一种获得题目性质很好的办法。

  • 关于降低复杂度

    对于一些看上去比较朴素的题,第一想法肯定是暴力模拟,复杂度通常很高。

    此时使用线段树/树状数组、分块、数论分块、分治等数据结构与算法可以有效降低复杂度,提高分数。

    3.总结

    最近几周停课集训零零碎碎的收获都差不多在这里总结完了。

    当然,真到了考场上还要考虑做题策略以及杜绝非知识性错误等许多事,但这些也都是老生常谈了,心里还是有点数的。

    同样,我也不能再犯在CSP考场上犯下的题意理解不准确的问题,我需要在仔细阅读题面的同时,结合样例与样例解释,更加准确且快速地把握题意,建出数学模型。当然了,这与平时的练习也是息息相关的。

    就这样吧,愿我NOIP rp++.

标签:集训,停课,Omicron,分块,2023NOIP,可以,复杂度,贪心
From: https://www.cnblogs.com/TimeIsFlying/p/17834529.html

相关文章

  • 2023NOIP A层联测31 T4 民主投票
    2023NOIPA层联测31T4民主投票思维好题。思路首先可以设\(s\)每个人最多获得的票数,一开始所有点都把自己的票投给自己父亲。如果一个点的票数超过\(s\)了,那么这个点肯定要把票分给他的父亲。设\(f_{u,s}\)为\(u\)点在最多获得\(s\)票的情况下要向父亲分的票数(不......
  • 2023NOIP A层联测30 总结
    2023NOIPA层联测30总结题目T1草莓列车\(n\leq10^5,m\leq10^7\)赛时思路一开始看错\(m\)数据范围,以为\(O(m\logm)\)可以过,后来发现问题以后,集中在考虑线段树之类的\(\log\)级别的算法维护序列,或者线段区间,一直没有想过ST表相关数据结构,于是最后只有60。赛后......
  • 2023NOIP A层联测31总结
    2023NOIPA层联测31总结\(T1\)暴力操作:给你一个长度为\(n\)的序列\(a\),你可以花费\(c_x\)使得\(a_i\)变为\([a_i/x]\),你总共有\(k\)元。为最终序列的中位数最小是多少。保证\(n\)为奇数。\(n,m\le5*10^5\)首先想到了二分一个答案,因为只要使得前\((n+1......
  • 2023NOIP A层联测30 总结
    2023NOIPA层联测30总结\(T1\)给定一个序列\(a\),有\(m\)次操作\(l,r,v\),表示将\([l,r]\)内的每个\(a_i\)变为\(\max(a_i,v)\)\(n\le10^5,m\le10^7\)看到\(n\le10^5,m\le10^6\),赶紧打一个\(O(m\log_2n)\)的线段树做法,在看到\(20pts\)的\(l......
  • 2023NOIP A层联测30 T1 草莓列车
    容易想到将询问离线下来,按\(v\)从大到小排序,这样后面的修改一定不会对前面的修改造成影响。然后可以用并查集把已修改过的点缩起来。注意到\(m\)会到\(2\times10^7\),应该使用基数排序,复杂度为\(\mathcalO(\frac{m\max{v_i}}{base}+m\alpha(n))\)。常数较大,卡卡常才能过......
  • 2023NOIP A层联测30 A. 草莓列车
    2023NOIPA层联测30A.草莓列车目录2023NOIPA层联测30A.草莓列车题目大意思路code题目大意给定一个序列\(a\),有\(m\)次操作,将\([l,r]\)的每个\(a_i\)变为\(max(a_i,v)\)\(n\le10^5,m\le10^7\)思路对于每个数,只用用它本身和每个涉及到它的查询里面......
  • [国家集训队] 阿狸和桃子的游戏
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e6+10;intn,m;intk[N],a,b,c;intval[N];//如果一条边的两端点被同一个人选了,那么产生边权的贡献//把边权均分到两端点上,每个端点加上c/2//如果这条边被同一个选了,那......
  • 2023NOIP A层联测26 总结
    2023NOIPA层联测26总结题目T1origen大意\(n,a_i\leq2\times10^5\)赛时思路一开始想固定一个端点递推去求贡献,发现异或加上平方维护不了递推式,痛失40min。后面多的时间分给T1后接着想做法,考虑拆平方化代数式,然后平方项的因式分解忘了,导致后面一直认为平方项会被加多......
  • 2023NOIP A层联测26 T4 abstract
    2023NOIPA层联测26T4abstract乱证明求性质的光速幂优化题。思路对于每一个节点,到该节点的子树内的叶子节点的路径中(包括路径上的点),出现的值只有\(k\times(\logV+\logV)\)个。那么在以该点为终点,以子树内节点为起点的路径中,取值只有\(k\times(\logV+\logV)\)。这是......
  • 2023NOIP A层联测26 T2 competition
    2023NOIPA层联测26T2competitiontjm的做法,很抽象。考场思路考虑每道题被做过多少次肯定不现实,那么考虑每一道题有多少次没有做出来。假设某一次可以做出来题\(x\)的人是\(i\),而\(i\)下一个人可以做出这道题的人是\(j\),于是题\(x\)有\(C_{j-i}^2\)次不会被做出来......