首页 > 其他分享 >11.11 NOIP模拟赛

11.11 NOIP模拟赛

时间:2024-11-11 17:19:25浏览次数:1  
标签:连通 NOIP 一个 11.11 2n 赛后 模拟

T1

字符串,两个相同的串一个从前往后,一个从后往前,选完后正着看都一样的话,就能拼成一个回文串,考虑两倍字符串,用 kmp 找到 n~2n 中间的一个 i ,如果 i-n+1 到 i 和 1 到 n组成的字符相同的话,答案就为 (m-1)*n+(2n-i)。m=1 时直接输出 nxt[n] 。

T2

找规律,能 \(O(1)\) 求出任意位置的价值的话有 \(40pts\) ,然后去想 n=1 的情况,发现可以考虑算每一个环对答案的贡献,算出来一个式子,但里面有一串平方的和,不会算。
赛后,听完知道这是二级等差数列。

T3

想每切一条边,只能把一个连通块分成两个,所以再加一个关键点,前面切的边还要切,只用多切一条与这个点在同一个连通块内的点和这个点之间的最小的一条边,复杂度 \(O(n^2)\) ,但是 RE 了。
赛后,正解是边权从大到小排,建Kruskal重构树,一个边连接的两个连通块都有关键点的话就删去。

T4

数据结构,nan。

标签:连通,NOIP,一个,11.11,2n,赛后,模拟
From: https://www.cnblogs.com/shangruolin/p/18540180

相关文章

  • NOIP 2024 游记 & 赛前训练(未完待续)
    NOIP2024游记&赛前训练day-18(11.11)今天做信友错的模拟赛。第一题是和最短路有关的,看到\(n\le500\)就想到了\(n^3\logn\),然而看了很久都不会做,于是果断火速打了\(O(n^4)\)的暴力走人,get50pts。然后看第二题,发现是最大异或路径,正好最近刚学了线性基,于是想到之前做......
  • [2024.11.11]NOIP模拟赛T2
    赛时T1提议看懂以后立马意识到就是让求最长Border。对于\(n\timesm\le10^6\)可以暴力建串然后直接KMP。容易发现如果\(s\)循环元为\(n\),那么答案就是\(n\times(m-1)\)。否则加上最长循环元长度即可。循环元还是用KMP求。T2让我想起了之前一道硬控我3h的题目......
  • NOIP2024加赛4
    NOIP2024加赛4\(T1\)luoguP11267【MX-S5-T1】王国边缘\(85pts\)预处理前缀中最后一个\(1\)出现的位置然后就可以倍增跳了。点击查看代码constllp=1000000007;intnxt[200010][62],f[200010][62],last[200010];chart[200010];lldivide(lls,llk){llan......
  • 11.11随笔
    这里是11.11随笔。课堂作业留档:简单的判断分数,给出等级代码:importjava.util.Scanner;publicclassThrowDemo{publicstaticvoidmain(String[]args){//doubledata;System.out.println("输入分数:");Scannersc=newScanner(System.in);data=sc.nextDouble();......
  • 11.11
    明天有信息会考。A.严格弱于NumbersonaCircle。先做个差分,发现每回就是选择一个数加\(n\),最后使得每个数都相等,那么每个数的操作次数就是与最大值的差值除以\(n\),注意判断无解。B.DivisionintoTwo感觉跟\(CSP-S\)的\(C\)差不多啊。考虑到如果将集合\(S\)中的数......
  • 1分钟学会在Linux下模拟网络延迟
    1.背景为了测试程序的健壮性以及在弱网环境下程序的表现,通常需要创造一个“不那么稳定”的网络环境,但这种模拟十分不好控制变量,比如希望控制网络延迟在500ms时,现实环境则是难以实现的,那有什么解决的办法呢?答案是,可以在Linux下使用tc命令来模拟延迟。2.安装在不同的发行......
  • WebMagic 抓取,selenium模拟点击操作,模拟将抓取的数据入库
    动态页面爬虫前的准备:https://www.cnblogs.com/maohuidong/p/18517953java添加maven依赖:<dependency><groupId>us.codecraft</groupId><artifactId>webmagic-core</artifactId><version>0.7.4</version></dependency><......
  • 拓扑AC NOIP模拟赛2
    100+35+10+10拿下rk7,拓扑AC的A题也太过困难了吧……T1题意给定数组\(a\),数组长度为\(n\)。定义\(f(x)\)表示有多少对\((i,j)\)满足\((a_i+x)\)是\((a_j+x)\)的子集。给定\(k\),保证\(a_i<2^k\),求\(\sum_{i=0}^{2^{k-1}}f(i)\)。\(n\leq20000,k\leq60\)。赛......
  • 代码随想录之滑动窗口、Java日期api、集合(11.4-11.11)
    代码1、长度最小的子数组⭐使用滑动窗口的思想,外层循环控制结束位置j,内层循环控制起始位置i,看似是双层循环,但时间复杂度是o(2n)。 2、水果成篮自己想法:使用backet1和backet2表示篮子1和篮子2;使用backet1Account和backet2Account分别表示两个篮子里水果的数量,内层循环将i指针......
  • 11.11
    实验12:外观模式本次实验属于模仿型实验,通过本次实验学生将掌握以下内容:1、理解外观模式的动机,掌握该模式的结构;2、能够利用外观模式解决实际问题。 [实验任务一]:计算机开启在计算机主机(Mainframe)中,只需要按下主机的开机按钮(on()),即可调用其他硬件设备和软件的启动方法......