首页 > 其他分享 >[CSP-S 2021] 回文

[CSP-S 2021] 回文

时间:2024-10-07 15:00:08浏览次数:8  
标签:瓶颈 一个 2021 区间 CSP 回文

算法

暴力

容易发现双指针可以找到每一个区间 \([L, R]\), 使得这个区间覆盖 \(1\) ~ \(n\) 的每一个数, 也即区间外覆盖 \(1\) ~ \(n\) 的每一个数, 这是 \(O(n)\) 的
考虑判断

对于两个数列 \(A\), \(B\)
显然, 在 \(A\) 中先取出的要在 \(B\) 中最后取出, 所以把 \(A\) 压入栈中, 判断栈顶是否在 \(B\) 的两端出现, 完事之后记录一下

正解

发现瓶颈在 \(O(n)\) 找区间上
如果假设第一次取左端
那么与之相对应唯一确定的一个数就必须最后一个取
于是分成两段

于是易得

代码

??? 有时间补

总结

善于运用基础数据结构

分析瓶颈之后想办法优化

标签:瓶颈,一个,2021,区间,CSP,回文
From: https://www.cnblogs.com/YzaCsp/p/18450102

相关文章

  • 信息学奥赛复赛复习14-CSP-J2021-03网络连接-字符串处理、数据类型溢出、数据结构Map
    PDF文档公众号回复关键字:202410071P7911[CSP-J2021]网络连接[题目描述]TCP/IP协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机......
  • CSP-S 模拟赛 35
    CSP-S模拟赛35rnk14,\(45+45+15+18=123\)。T1送花愚蠢题。看到区间想到线段树,预处理出每个位置的颜色上一次出现的位置,记为\(\mathit{las}_i\)。从左到右扫右端点,给\([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\)减去\(d(c_i)\),给\((\mathit{las}_i,i]\)......
  • CSP-S 模拟赛 34
    CSP-S模拟赛34rnk12,\(24+50+20+0=94\)。T1玩游戏有一个痿正解:从\(k\)到\(1\)扫左端点,对于每个左端点扫它最远能到达的右端点。如果在任何一时刻它的右端点位置\(<k\),则断定输出No。否则检查当左端点到\(1\)时右端点能否到\(n\)。注意这里扫右端点的方式,不要每次都......
  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19,\(30+20+40+15=105\)。T1构造字符串10pts:输出\(-1\)。30pts:对于所有\(z_i=0\)的情况,也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的,然后从\(1\)到\(n\)扫一遍,输出除去不同的字符之外的字典序最小的字符。70pts:暴搜。枚举每个......
  • 10.5牛客CSP-S考试总结
    10.5牛客CSP-S考试总结为什么牛客不允许我:main(){}T1看到题目感觉是道规律题,就把题目给的式子写出来,跑了几十组随机数据,发现好像是恒等式,于是直接大胆猜测任选三个数都可以满足等式。T2题面数学公式有点诈骗,求自然常数的多个自然对数相加的和的次方,形式化的求\(e^{\ln\......
  • CSP-S 2024 第九次
    A设\(f_{i,S}\)表示考虑前\(i\)行,选出的矩形在第\(i\)行上形成\(S\)中的区间的方案数,每行的\(S\)只有\(O(2^m)\)种,总复杂度\(O(n2^{2m})\)。B考虑先修改再查询怎么做。考虑左下角为\((x_1,y_1)\),右上角为\((x_2,y_2)\)的矩形,发现斜率在\(\left[\dfrac{y_1}{......
  • 多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9
    多校A层冲刺NOIP2024模拟赛02四道题因为暑假被拉去当模拟赛暑假集训CSP提高模拟22了,遂直接把赛后代码交了上去,然后就被通知换题了。原\(100+100+100+20\)被在accodersNOI上被卡成了\(100+100+90+10\),更改longlong和int后达到了\(100+100+100+30\)。\(T1\)P318......
  • E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟
    视频链接:  P8744[蓝桥杯2021省A]左孩子右兄弟-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DPO(n)#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,f[N],son[N];inthead[N],idx;structE{intv,ne;}e[N<<1];voidadd(intu......
  • CCF-CSP认证资格考试题解系列——第4次第2题数字排序
    #include<iostream>#include<algorithm>usingnamespacestd;structre{ intvalue;//数值 intnum;//次数}re[1010];boolcmp(structrea,structreb){ if(a.num==b.num)returna.value<b.value;//次数相同是小的优先 returna.num>b.num;//次数不相同是次数优......
  • CCF-CSP认证资格考试题解系列——第4次第3题节日
    #include<iostream>usingnamespacestd;intm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};intis_run(intyear){ if(year%400==0||(year%4==0&&year%100))return1; return0;}intgetdays(intyear,intmonth){ if(month==2)returnm[month]+i......