首页 > 其他分享 >代码源Csp-S模拟赛Day10-11赛后总结

代码源Csp-S模拟赛Day10-11赛后总结

时间:2024-10-07 21:21:49浏览次数:9  
标签:11 暴力 格子 精灵 T1 Day10 Csp 赛后

代码源Csp-S模拟赛Day10-11赛后总结

Day 10

赛时

T1 赛时感觉很难维护时间以及多个精灵同时到达同一格子的情况,后来想了一种做法:对于每个格子最早被遍历到的时间我们的处理是容易的,你考虑我们可以对每行每列都建一棵线段树(数据范围保证了 \(rc\leq5e5\),所以总空间大致是一个 \(4rc\) 的,动态开点处理的话,空间肯定不会炸),如果一个精灵能向右走,我们就在它这一行的第一个线段树的他这列的那个位置上添加一个 \(t_i-y\) ,\(t_i\) 是该精灵出现时间,y 是他所在的列数,其它方向的同理。然后你求每个格子最早的染色时间的时候先 \(n^2\) 枚举所有格子,分别查询它四个方向的精灵,线段树维护,所以是 \(\log\) 级别的,于是 \(n^2\log\) 可以解决这个问题。然后你得到每个格子最早被到达的时间后你按照精灵的编号去枚举,维护一个指针指向它当前能染色到的格子编号,然后每轮按照他的方向继续移动一格,判一下到达时间不等于这个格子的最早遍历时间那么这个精灵就死了,再继续考虑下一个就可以。每个格子至多遍历一次,所以复杂度 \(O(n^2)\) 。这一系列都很对,但有一个小问题,就是你在预处理每个格子到达的最短时间的时候没有考虑到有的精灵一出生就死了,根本不可能遍历到它,但是你还是统计到了他的贡献,导致有一部分点你本身是可达的,只因最短时间的统计错误致使不可达。赛时是已经码完之后不过样例仔细思考才意识到这点的,而且这个思路实现需要很多细节,包括我线段树还码炸调了半天……意识到思路假的时候已经11点了(我本身是考虑T1A掉,后面都打暴力分数还是可以的,所以在这到题上投入了差不多四分之三的时间)。后面都打的暴力,所以也没啥可说的了。

赛后

T1 糖完了,竟是之间把每个精灵放到优队里暴力模拟……我感觉这个手法也见了不止一次两次了,不过是一年前的事了。已订。
T2是道构造题,容易发现一个性质就是如果我们找到了一个合法序列a,可以合理调整每个元素的值(+k,-k)来得到更多的合法解。所以一种想法是我们求一下序列a的和模n为i时和的最小值,通过枚举 \(a_n\) 的值为多少已经在这种情况下我们考虑原序列前 j 个元素,我们可以dp 求解这个问题。已订。
T3简述的话是只要你会码dfs暴搜后你就很容易想到 \(n^3\) 的dp,然后发现第三维没用优化成 \(n^2\) 的了。如果你还能注意到dp 下标的单调性,就完全转化成了格路计数问题。这就是正解了(感觉上一篇写得太长了所以决定简化题解部分)。可订未订。
T4……未订

Day 11

赛时

时间分配大致是 T1五分之三 T4 五分之一,T2T3五分之一。

T1是在磕正解,T4是20分的dp码炸了在努力的对拍,T2T3是简单的码暴力+T2推一些小性质。
但是T1糖了,没磕出来,所以是全场暴力,每道题的思考过程也没啥好说的了。

赛后

T1 看题面感觉很亲切,因为类似的题我做了两道,都是让你建的图有 \(n^2\) 规模的边让你求最小生成树的总边权的。一道是今年打的应该是abc35x的一道F题,另外一道是P9488 ZHY的生成树,它们的思路都是考虑一些不必要的建边然后暴力跑Kruscal。其实都说到这儿了这道题的解法也呼之欲出了。你考虑建的新图正常建是 \(m^2\) 个点,但你考虑建图的过程,枚举每个点它所连的每条边互相连边,那么你考虑只需要让边权最小的那条跟其它的连就行了,其它的连边都是无意义的,于是总边数为 \(O(m)\) 级别的。然后就做完了。

T2 T3 T4 都待订吧,视频还没看完,T1订过了。

总结

1.我觉得还是先把暴力都码完再磕正解比较稳妥一些,不然我这两天的比赛暴力分都没拿多少,都是仓仓促促最后三四十分钟码的。

2.思考的时候有的时候不够缜密,这种码了一两个小时最后发现思路是错的情况发生并不少见。

标签:11,暴力,格子,精灵,T1,Day10,Csp,赛后
From: https://www.cnblogs.com/yxans/p/18450569

相关文章

  • Solution - Atcoder ARC116C Multiple Sequences
    一个\(\mathcal{O}(m^{\frac{3}{4}}\logm)\)做法。令\(a_0=1\)。对于倍数问题,考虑类似差分的思想,定义\(b_i=\frac{a_i}{a_{i-1}}(1\lei\len)\),那么合法的\(a\)和\(b\)是双射的,就只需要考虑对\(b\)计数了。考虑到因为有\(\prod\limits_{i=1}^nb_i\lem\)......
  • CSP2024 前集训:csp-s模拟9
    前言T1状压挂了\(10pts\),貌似做法是假的,但是一下午也没调出来哪儿假了,但是错误率很低,几百组能有一组错的。T2赛时数据锅了赛后重测了,赛时想到线段树但是没能具体实现,最后无奈写暴力。T3、T4没看。T1邻面合并\(m\le8\)所以考虑状压表示每一行哪些地方被覆盖,对与相邻两......
  • CF1117E Decypher the String题解
    传送门神奇的题。这是一道交互题。给定一个字符串\(s\),我们拥有若干操作,但是你不知道,第\(i\)个操作形如\(a_i,b_i\)表示交换字符串\(s\)中的第\(a_i\)位和\(a_j\)位。比如操作序列依次为\((1,2),(2,3)\),给定字符串为xyz。那么我们执行第一次操作后......
  • CSP 联训 3
    好吧,又倒数了,就签了个T2,100pts。T1我把相同颜色的存起来,每种颜色找出枚举选哪两个座位不合法的矩阵的左上和右下,如果找到的矩阵左下和右上也相同,则这个矩阵确实不合法,减去,但判断左下和右上的时候写的太急(最后十五分钟才开始打这个暴力)少判了和当前颜色是否相同,挂了80pts,!总......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......
  • Day11-Scanner
    Day11-ScannerScanner介绍Scanner对象:之前我们学的基本语法中我们并没有实现程序和人的交互,但是Java给我们提供了这样一个工具类,我们可以获取用户的输入。java.util.Scanner是Java5的新特征,我们可以通过Scanner类来获取用户的输入。基本语法:Scanners=newScanner......
  • 这里有11种方法,供你用Python下载文件
    今天我们一起学习如何使用不同的Python模块从web下载文件。此外,你将下载常规文件、web页面、AmazonS3和其他资源。最后,你将学习如何克服可能遇到的各种挑战,例如下载重定向的文件、下载大型文件、完成一个多线程下载以及其他策略。如果你正在学习Python并且找不到方向的话可......
  • Windows 11 version 24H2 & LTSC 2024 中文版、英文版 (x64、ARM64) 下载 (updated Oc
    Windows11version24H2&LTSC2024中文版、英文版(x64、ARM64)下载(updatedOct2024)Windows11,version24H2,企业版arm64x64请访问原文链接:https://sysin.org/blog/windows-11/查看最新版。原创作品,转载请保留出处。作者主页:sysin.org全新Windows体验,让您与热......
  • 【前缀和+开区间二分】codeforces 1187 B. Letters Shop
    题意第一行,输入一个正整数\(n(1\leqn\leq2*10^5)\),代表字符串\(s\)的长度。第二行,输入一个字符串\(s\)。第三行,输入一个正整数\(m(1\leqm\leq5*10^4)\),代表接下来要输入的询问次数,对于每次询问:输入一个字符串\(t(1\leq|t|\leq2*10^5)\),并保证\(\sum_{i=1}^m......
  • [CSP-S 2021] 回文
    算法暴力容易发现双指针可以找到每一个区间\([L,R]\),使得这个区间覆盖\(1\)~\(n\)的每一个数,也即区间外覆盖\(1\)~\(n\)的每一个数,这是\(O(n)\)的考虑判断对于两个数列\(A\),\(B\)显然,在\(A\)中先取出的要在\(B\)中最后取出,所以把\(A\)压入栈......