©2020-2024 ioDraw All rights reserved,
Privacy Policy
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题金牌题，真的没想到，还是有点难度的。