d题意:多次询问,求区间是否存在两个数异或和为x

思路:预处理对于每个ai,最近的左右ai^x的位置,l和r,线段树维护区间最右边的l和最左边的r,只要Q.l<=l或者r<=Q.r即存在,st表,离线树状数组,在线线段树等等都能搞。
莫队做法,开桶维护每个数,当前加入ai的话,去ai^x的桶看是否存在数即可
  e题意:n次跳跃,从i-1跳到i成功的概率为pi,失败的话回到0号点,问跳到n的期望次数
思路:想了近2h没过样例2,不会, 回大一重修高数了
  f题意:n个位置高度为hi,从起点跳到终点往返共2x次,步长为y,从i起跳则hi会减1,当hi=0时无法起跳,求最小步长
思路:二分答案

设当前步长为y,有点网络流思想?首先从起点到终点和从终点到起点本质一样,每个点的流量可以分给[i+1,i+y],我们贪心地把流量分给靠右的点(每个点能容纳的最大流量是hi),对于每个点只会被装满一次,直接维护未被装满的位置,左右两边各来一次,能做到O(n)check
  g题意:给定一个长度为 N 的整数序列:A1, A2, · · · , AN。现在你有一次机会,,将其中连续的 K
个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长,请输出这个最长的长度。
不会做2333
  h题意:给n个点的位置(xi,yi)和价值w,初始给个线,线顺时针转,碰到点就延长w,且点消失,求点消失的时间
思路:计算几何,极角排序后模拟,没板子不会写233
  i题意:问n是否能写成 x 1 y 1 ∗ x 2 y 2 x_1^{y_1}*x_2^{y_2} x1y1​​∗x2y2​​
的形式,其中y1,y2>=2,n<=1e18
不会做,拿十分走人
思路: n = ∑ p i k i n=\sum{p_i^{ki}} n=∑piki​,对于每个质数带上它的次方我们要尽可能给它满足,首先ai要能写成ai=
x 2 y 3 x^2y^3x2y3的形式才是可以的(这样的形式容纳性最强),对于任意大于1的正数,都可以写成2x+3y的形式,也就是说对于 p k p^k
pk我们可以把k分给x和y。当x=1,y=1,我们特判是否为平方数/立方数即可。对于x>1,y>1,由于n<=1e18,min(x,y)<= 1 e 18 /
5 1e^{18/5}1e18/5大概4000左右,如果数据没卡满的话,枚举x,check
y即可,更进一步的话,可以先对ai进行4e3内的质数筛,根据质数的次数看每个质数分到x还是y
  j题意:给若干区间的sum,若干询问求[l,r]的sum是多少
一眼带权并查集板题,奈何没板子不会写,寄了
总结:相比去年少了三道填空,大题难度差不多,让我认识到oi爷的含金量。wls说fg大概铜牌银牌题难度,h银牌题,i题金牌题,真的没想到,还是有点难度的。

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信