2022-2023:teams:fire_and_blood:week_summary_1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2022-2023:teams:fire_and_blood:week_summary_1 [2022/10/14 00:39] clap |
2022-2023:teams:fire_and_blood:week_summary_1 [2022/10/14 00:41] (当前版本) clap |
||
|---|---|---|---|
| 行 17: | 行 17: | ||
| ====ljz==== | ====ljz==== | ||
| VP的签到题就不写了。 | VP的签到题就不写了。 | ||
| - | CF1730D | + | ===CF1730D=== |
| 题意：每次可以把a的前k位和b的后k位交换，问a是否可以变成b。 | 题意：每次可以把a的前k位和b的后k位交换，问a是否可以变成b。 | ||
| 容易发现，对于ai和bn-i+1这两个元素的对应关系不管怎么操作都是不会变的。所以有解无解的判断方法就是相同的pair（无序）有偶数个，或者有一个奇数且n是奇数。 | 容易发现，对于ai和bn-i+1这两个元素的对应关系不管怎么操作都是不会变的。所以有解无解的判断方法就是相同的pair（无序）有偶数个，或者有一个奇数且n是奇数。 | ||
| - | CF1730E | + | |
| + | ===CF1730E=== | ||
| 题意：计算有多少个区间满足最大值可以整除最小值。 | 题意：计算有多少个区间满足最大值可以整除最小值。 | ||
| 先用单调栈求出以每个元素为最大值最小值的最长区间。我们对每个ai都求出以ai为最大值的满足条件的区间，枚举ai的每个约数（ai在一百万以内因此可以AlogA预处理），对于一个约数d，可以找到离ai最近的d（左右各一个），我们只需要计算包含ai和d的满足条件的区间，对于左右的d注意去重。 | 先用单调栈求出以每个元素为最大值最小值的最长区间。我们对每个ai都求出以ai为最大值的满足条件的区间，枚举ai的每个约数（ai在一百万以内因此可以AlogA预处理），对于一个约数d，可以找到离ai最近的d（左右各一个），我们只需要计算包含ai和d的满足条件的区间，对于左右的d注意去重。 | ||
| - | CF1730F | + | |
| + | ===CF1730F=== | ||
| 题意：给定一个排列p和k，找到一个排列q，满足任意i<j，都有pqi<=pqj+k，使得q的逆序对数量最少。(n<=5000,k<=8) | 题意：给定一个排列p和k，找到一个排列q，满足任意i<j，都有pqi<=pqj+k，使得q的逆序对数量最少。(n<=5000,k<=8) | ||
| 我们一个一个考虑q，对于q1，pq1的值只可能是[1,k+1]中的的一个，如果pq1取了1那pq2的值只可能是[1,k+1]中的一个，如果pq1没有取1那么pq2的值还是只能在[1,k+1]中取，后面以此类推，也就是说每放置一个q，我们需要考虑的值只有最小的没被选过的数到这个数+k的范围内，这样就可以状压DP了。 | 我们一个一个考虑q，对于q1，pq1的值只可能是[1,k+1]中的的一个，如果pq1取了1那pq2的值只可能是[1,k+1]中的一个，如果pq1没有取1那么pq2的值还是只能在[1,k+1]中取，后面以此类推，也就是说每放置一个q，我们需要考虑的值只有最小的没被选过的数到这个数+k的范围内，这样就可以状压DP了。 | ||
| - | CF1733E | + | |
| + | ===CF1733E=== | ||
| 题意：n*m的方格图上每个格子有一个箭头，初始时(0,0)上有一个小球，以后每一个时刻所有小球都会按照箭头的方向走一个格子，然后(0,0)上会新出现一个小球，所有上一个时刻有球的格子都会转换箭头方向（只有向右和向下两种状态）。问第t时刻给定的格子是否有球。(t<=1e18，x0y0<=120) | 题意：n*m的方格图上每个格子有一个箭头，初始时(0,0)上有一个小球，以后每一个时刻所有小球都会按照箭头的方向走一个格子，然后(0,0)上会新出现一个小球，所有上一个时刻有球的格子都会转换箭头方向（只有向右和向下两种状态）。问第t时刻给定的格子是否有球。(t<=1e18，x0y0<=120) | ||
| 我们把所有小球统一考虑，也就是说一共会生成t个小球，小球走到(x0,y0)需要x0+y0-1个时刻，我们考虑有可能经过(x0,y0)的小球一共t-x0-y0+1个，如果经过当前格子的小球有n个，那么其中会有\left\lfloor n/\left.2\right\rfloor\right.个经过下方的格子，剩下的会经过右边的格子。我们只需要知道t时间经过(x0,y0)的小球数量和t-1时间经过(x0,y0)的小球数量是否相等就可以判断是否在t时刻(x0,y0)上有球。 | 我们把所有小球统一考虑，也就是说一共会生成t个小球，小球走到(x0,y0)需要x0+y0-1个时刻，我们考虑有可能经过(x0,y0)的小球一共t-x0-y0+1个，如果经过当前格子的小球有n个，那么其中会有\left\lfloor n/\left.2\right\rfloor\right.个经过下方的格子，剩下的会经过右边的格子。我们只需要知道t时间经过(x0,y0)的小球数量和t-1时间经过(x0,y0)的小球数量是否相等就可以判断是否在t时刻(x0,y0)上有球。 | ||
| - | CF1720D | + | |
| + | ===CF1720D=== | ||
| 题意：给定一个序列ai求ai的一个最长子序列bi，满足a_{b_p}\oplus b_{p+1}<a_{b_{p+1}}\oplus b_p对于任意p成立。 | 题意：给定一个序列ai求ai的一个最长子序列bi，满足a_{b_p}\oplus b_{p+1}<a_{b_{p+1}}\oplus b_p对于任意p成立。 | ||
| 注意到两个数a<b在二进制意义下，一定是前一段二进制a=b，后一位上a是0，b是1。前一段二进制表示a_{b_p}\oplus b_{p+1}=a_{b_{p+1}}\oplus b_p\ \Rightarrow\ a_{b_p}\oplus b_p=a_{b_{p+1}}\oplus b_{p+1} 这样就可以用0/1trie维护a_i\oplus i，对于每个a_i都在trie中查找前面可以接的最长段。 | 注意到两个数a<b在二进制意义下，一定是前一段二进制a=b，后一位上a是0，b是1。前一段二进制表示a_{b_p}\oplus b_{p+1}=a_{b_{p+1}}\oplus b_p\ \Rightarrow\ a_{b_p}\oplus b_p=a_{b_{p+1}}\oplus b_{p+1} 这样就可以用0/1trie维护a_i\oplus i，对于每个a_i都在trie中查找前面可以接的最长段。 | ||
| - | CF1717E | + | |
| + | ===CF1717E=== | ||
| 题意：求\sum_{a+b+c=n} l c m\left(c,gcd\left(a,b\right)\right)，其中abc都是正整数。n\le300000 | 题意：求\sum_{a+b+c=n} l c m\left(c,gcd\left(a,b\right)\right)，其中abc都是正整数。n\le300000 | ||
| 我们枚举c，则a+b=n-c\Rightarrow\ gcd(a,b)|n-c枚举n-c的约数d，即gcd(a,b)=d，问题转化为求a0+b0=\frac{n-c}{d},\left(a0,b0\right)=1的(a0,b0)对数，即\varphin-cd。 | 我们枚举c，则a+b=n-c\Rightarrow\ gcd(a,b)|n-c枚举n-c的约数d，即gcd(a,b)=d，问题转化为求a0+b0=\frac{n-c}{d},\left(a0,b0\right)=1的(a0,b0)对数，即\varphin-cd。 | ||
| - | CF1717F | + | |
| + | ===CF1717F=== | ||
| 题意：给定一张无向图，和一个点集S，要给每条边定向，使得每个S中的结点i满足，入度-出度=一个给定值ai。n,m<=10000。 | 题意：给定一张无向图，和一个点集S，要给每条边定向，使得每个S中的结点i满足，入度-出度=一个给定值ai。n,m<=10000。 | ||
| 对于规定的结点，需要有bi=(ai+度数)/2个入度，以此可以判掉一部分NO。考虑网络流的做法，建立超级源点S，S向每条边连一条流量为1的边，每条边分别向两个端点连一条流量为1的边，建立超级汇点T，对于每个点集中规定的点，向T连一条流量为bi的边。跑一遍网络流，这个建图其实相当于一个二分图，因此网络流复杂度是比较优秀的。如果最终最大流和所有的bi的和相等则可能存在一组解，否则无解。但这样跑完网络流之后并不能保证每条边都被选择了一次，因为我们忽略了不在给定点集中的点，我们在上一次跑完网络流的图的基础上给每个不在给定点集中的点向T连一条流量为无穷的边，再跑一次网络流，如果两次最大流加起来是m才能保证有解。为什么不一开始就连？因为网络流很可能会优先把无穷的边都流满，这样构造的方案并不满足我们的条件。最终输出构造方案就看每条边的流向即可。 | 对于规定的结点，需要有bi=(ai+度数)/2个入度，以此可以判掉一部分NO。考虑网络流的做法，建立超级源点S，S向每条边连一条流量为1的边，每条边分别向两个端点连一条流量为1的边，建立超级汇点T，对于每个点集中规定的点，向T连一条流量为bi的边。跑一遍网络流，这个建图其实相当于一个二分图，因此网络流复杂度是比较优秀的。如果最终最大流和所有的bi的和相等则可能存在一组解，否则无解。但这样跑完网络流之后并不能保证每条边都被选择了一次，因为我们忽略了不在给定点集中的点，我们在上一次跑完网络流的图的基础上给每个不在给定点集中的点向T连一条流量为无穷的边，再跑一次网络流，如果两次最大流加起来是m才能保证有解。为什么不一开始就连？因为网络流很可能会优先把无穷的边都流满，这样构造的方案并不满足我们的条件。最终输出构造方案就看每条边的流向即可。 | ||
| - | CF1716E | + | |
| + | ===CF1716E=== | ||
| 题意：有2^n个数，每次操作选定一个i，对每个k交换a_k，ak+2i，已经被交换过就跳过。有q次操作每次操作给定一个i，求操作完的序列的最大子段和，每次操作的改变保留。 | 题意：有2^n个数，每次操作选定一个i，对每个k交换a_k，ak+2i，已经被交换过就跳过。有q次操作每次操作给定一个i，求操作完的序列的最大子段和，每次操作的改变保留。 | ||
| q<=200000,n<=18。 | q<=200000,n<=18。 | ||
| 如果下标从0开始，我们发现，每次就是a_k，ak⊕2i，交换，每次操作的改变保留的话，就是把每个操作数异或起来得到一个x，a_k，ak⊕x交换，我们可以对每个0<=i<2^n都预处理出答案，而对于最大子段和，可以用线段树维护。对于每个i我们并不需要建出完整的线段树，我们可以利用i异或掉最高位的1之后的i’的线段树，这样总共只需要n·2n个结点。 | 如果下标从0开始，我们发现，每次就是a_k，ak⊕2i，交换，每次操作的改变保留的话，就是把每个操作数异或起来得到一个x，a_k，ak⊕x交换，我们可以对每个0<=i<2^n都预处理出答案，而对于最大子段和，可以用线段树维护。对于每个i我们并不需要建出完整的线段树，我们可以利用i异或掉最高位的1之后的i’的线段树，这样总共只需要n·2n个结点。 | ||
| - | CF1716F | + | |
| + | ===CF1716F=== | ||
| 题意：有n个口袋，每个口袋中有编好分别为1~m的m个球，从每个口袋中都拿出一个球来，设编号为奇数的球的个数为F，求所有F^k的和，多组数据对998244353取模。(n,m<998244353,k<=2000,T<=5000) | 题意：有n个口袋，每个口袋中有编好分别为1~m的m个球，从每个口袋中都拿出一个球来，设编号为奇数的球的个数为F，求所有F^k的和，多组数据对998244353取模。(n,m<998244353,k<=2000,T<=5000) | ||
| 令a=\left\lfloor\frac{m+1}{2}\right\rfloor,b=\left\lfloor\frac{m}{2}\right\rfloor则，ans=\sum_{i=1}^{n}\binom{n}{i}·ai·bn-i·ik | 令a=\left\lfloor\frac{m+1}{2}\right\rfloor,b=\left\lfloor\frac{m}{2}\right\rfloor则，ans=\sum_{i=1}^{n}\binom{n}{i}·ai·bn-i·ik | ||
| 行 49: | 行 57: | ||
| \ \ \ \ \ \ \ =j=1ksk,j·n!n-j!·i=1nn-ji-j·ai·bn-i | \ \ \ \ \ \ \ =j=1ksk,j·n!n-j!·i=1nn-ji-j·ai·bn-i | ||
| =j=1ksk,j·n!n-j!·aj·(a+b)n-j | =j=1ksk,j·n!n-j!·aj·(a+b)n-j | ||
| - | CF1715E | + | |
| + | ===CF1715E=== | ||
| 题意：有一张n个点，m条有边权的边的无向图，求一个人从1出发到达各个结点的最短用时，任意两个结点u,v之间可以乘坐飞机，用时{(u-v)}^2,最多坐k次飞机。(n,m<=100000,k<=20) | 题意：有一张n个点，m条有边权的边的无向图，求一个人从1出发到达各个结点的最短用时，任意两个结点u,v之间可以乘坐飞机，用时{(u-v)}^2,最多坐k次飞机。(n,m<=100000,k<=20) | ||
| 考虑dpi,j表示恰好坐j次飞机到i号点的最短用时，状态由dpk,j-1转移过来，是很标准的斜率优化形式，但是要注意这样转移完成后，dpi,j表示的是恰好坐j次飞机到i号点并且最后一步是坐飞机抵达i的，因此还要用迪杰斯特拉跑一遍dpi,j。 | 考虑dpi,j表示恰好坐j次飞机到i号点的最短用时，状态由dpk,j-1转移过来，是很标准的斜率优化形式，但是要注意这样转移完成后，dpi,j表示的是恰好坐j次飞机到i号点并且最后一步是坐飞机抵达i的，因此还要用迪杰斯特拉跑一遍dpi,j。 | ||
| - | CF1715F | + | |
| + | ===CF1715F=== | ||
| 题意：交互，有一个n*m的网格，有一个1*1的方格需要你确定他的位置，每次你可以询问给出一个多边形，交互器返回此多边形和那个1*1交的面积，最多询问5次，n,m<=100。 | 题意：交互，有一个n*m的网格，有一个1*1的方格需要你确定他的位置，每次你可以询问给出一个多边形，交互器返回此多边形和那个1*1交的面积，最多询问5次，n,m<=100。 | ||
| IQtest，考虑锯齿状的多边形， 这种多边形可以根据面积确定一维坐标，其实只需要询问两次就行了。 | IQtest，考虑锯齿状的多边形， 这种多边形可以根据面积确定一维坐标，其实只需要询问两次就行了。 | ||
| - | CF1713E | + | ===CF1713E=== |
| 题意：有一个n*n的矩阵，每次操作可以选择一个k，把矩阵的第k行和第k列转置，问通过操作可以得到的最小字典序的矩阵。 | 题意：有一个n*n的矩阵，每次操作可以选择一个k，把矩阵的第k行和第k列转置，问通过操作可以得到的最小字典序的矩阵。 | ||
| 对于a_{i,j}，aj,i如果要交换，只能选择i或者j操作，对于1<=i<=n只有两种状态，操作或者不操作，因为对于同一个位置操作多次是抵消的，而且操作顺序与最终答案无关。按顺序枚举，a_{i,j}<a_{j,i}则i，j的状态应该是相同的，反之，i，j的状态应该不相同。可以用带权并查集或者种类并查集维护这些关系。同时还有一个观察，就是对于一种可行的操作，操作他的补集后的结果也是一样的。因此对于一个并查集的根随便选择操作或不操作都可。 | 对于a_{i,j}，aj,i如果要交换，只能选择i或者j操作，对于1<=i<=n只有两种状态，操作或者不操作，因为对于同一个位置操作多次是抵消的，而且操作顺序与最终答案无关。按顺序枚举，a_{i,j}<a_{j,i}则i，j的状态应该是相同的，反之，i，j的状态应该不相同。可以用带权并查集或者种类并查集维护这些关系。同时还有一个观察，就是对于一种可行的操作，操作他的补集后的结果也是一样的。因此对于一个并查集的根随便选择操作或不操作都可。 | ||
| - | CF1712E | + | |
| + | ===CF1712E=== | ||
| 题意：T次询问，每次给了l,r，求满足lcm(i,j,k)\geq i+j+k,l\le i<j<k\le r的对数。T<=100000,l,r<=200000。 | 题意：T次询问，每次给了l,r，求满足lcm(i,j,k)\geq i+j+k,l\le i<j<k\le r的对数。T<=100000,l,r<=200000。 | ||
| 我们发现满足条件的三元组数量应该是很多的，如果lcm(i,j,k)\geq3\ast k那么肯定满足条件，所以可以考虑反面，因此我们只需要计算lcm\left(i,j,k\right)=k，lcm(i,j,k)=2*k的三元组数量。首先考虑lcm(i,j,k)=2\ast k的情况，还需要满足k<i+j其中ij都是2k的约数，这种情况下只有两种可能i=\frac{1}{2}k,j=\frac{2}{3}k或者i=\frac{2}{5}k,j=\frac{2}{3}k，这都很好统计。接下来考虑lcm\left(i,j,k\right)=k那么只要满足ij是k的约数。预处理处每个数的约数，离线把询问按右端点排序，按顺序计算i<j<k\le r的三元组数量，回答询问时减去i<l的三元组，这可以用树状数组维护。 | 我们发现满足条件的三元组数量应该是很多的，如果lcm(i,j,k)\geq3\ast k那么肯定满足条件，所以可以考虑反面，因此我们只需要计算lcm\left(i,j,k\right)=k，lcm(i,j,k)=2*k的三元组数量。首先考虑lcm(i,j,k)=2\ast k的情况，还需要满足k<i+j其中ij都是2k的约数，这种情况下只有两种可能i=\frac{1}{2}k,j=\frac{2}{3}k或者i=\frac{2}{5}k,j=\frac{2}{3}k，这都很好统计。接下来考虑lcm\left(i,j,k\right)=k那么只要满足ij是k的约数。预处理处每个数的约数，离线把询问按右端点排序，按顺序计算i<j<k\le r的三元组数量，回答询问时减去i<l的三元组，这可以用树状数组维护。 | ||
| - | CF1709E | + | |
| + | ===CF1709E=== | ||
| 题意：给定一棵树，有点权，每次操作可以把任意结点值改成任意正整数，问最少用多少次操作可以使树上不存在异或和为零的简单路径。 | 题意：给定一棵树，有点权，每次操作可以把任意结点值改成任意正整数，问最少用多少次操作可以使树上不存在异或和为零的简单路径。 | ||
| 可以证明，只要存在一条以u为最高点的路径就把u的结点值改变，然后子树中的其他结点就不需要考虑了，经典的维护到根结点路径的异或和，再用dsu on tree统计答案。 | 可以证明，只要存在一条以u为最高点的路径就把u的结点值改变，然后子树中的其他结点就不需要考虑了，经典的维护到根结点路径的异或和，再用dsu on tree统计答案。 | ||
| - | CF1696F | + | |
| + | ===CF1696F=== | ||
| 题解：给出一个n个结点的树上的所有三元组f(x,y,z)=dis(x,z)==dis(y,z)，要求构造一种可能的树，或者确定无解。n<=100 | 题解：给出一个n个结点的树上的所有三元组f(x,y,z)=dis(x,z)==dis(y,z)，要求构造一种可能的树，或者确定无解。n<=100 | ||
| 首先假定以1位根，按照到1的距离是否相等把剩下的结点分成若干组，假定一组是1的儿子，然后判断是否可行，和一个结点父亲距离相等的结点只能是他的儿子，我们按照这个规则可以把整棵树构造出来，然后判断是否满足所有的三元组要求，如果不满足则换下一组假定成1的儿子。如果所有都不满足则无解。 | 首先假定以1位根，按照到1的距离是否相等把剩下的结点分成若干组，假定一组是1的儿子，然后判断是否可行，和一个结点父亲距离相等的结点只能是他的儿子，我们按照这个规则可以把整棵树构造出来，然后判断是否满足所有的三元组要求，如果不满足则换下一组假定成1的儿子。如果所有都不满足则无解。 | ||
| - | CF1696G | + | |
| + | ===CF1696G=== | ||
| 题意：给定x,y，每次操作可以选择一个a_i,1\le i<n以及一个t，将a_i减少x*t，将a_{i+1}减少y*t或者a_i减少y*t，将a_{i+1}减少x*t，问将整个a都变成小于等于0，需要的最少的t的总和。 | 题意：给定x,y，每次操作可以选择一个a_i,1\le i<n以及一个t，将a_i减少x*t，将a_{i+1}减少y*t或者a_i减少y*t，将a_{i+1}减少x*t，问将整个a都变成小于等于0，需要的最少的t的总和。 | ||
| 容易将问题转化为一个线性规划问题 | 容易将问题转化为一个线性规划问题 | ||
| 行 84: | 行 98: | ||
| 转化成这种形式就美观多了，其中x_i的取值只有0，1Y，1X+Y 三种情况，（假设Y>=X） | 转化成这种形式就美观多了，其中x_i的取值只有0，1Y，1X+Y 三种情况，（假设Y>=X） | ||
| 然后对这三种取值进行DP，是可以用矩阵表达转移的，于是可以线段树维护。 | 然后对这三种取值进行DP，是可以用矩阵表达转移的，于是可以线段树维护。 | ||
| - | ARC149D | + | |
| + | ===ARC149D=== | ||
| 题意：一开始给定n个坐标轴上的一维坐标和m个操作，每个操作给定一个d，对于当前为正的坐标，这些坐标-d，对于当前坐标为负的坐标，这些坐标+d，如果有坐标到达了原点就会永久消失。问每个坐标在第几次操作时到达原点，或者无法到达原点则给出最后一次操作结束后的位置。X<=1000000,m,n<=300000 | 题意：一开始给定n个坐标轴上的一维坐标和m个操作，每个操作给定一个d，对于当前为正的坐标，这些坐标-d，对于当前坐标为负的坐标，这些坐标+d，如果有坐标到达了原点就会永久消失。问每个坐标在第几次操作时到达原点，或者无法到达原点则给出最后一次操作结束后的位置。X<=1000000,m,n<=300000 | ||
| 一个观察是，对于两个关于对称的坐标，在以后所有的操作中都会关于原点对称。然后又由于坐标范围不是很大，我们可以对1~1000000都求出答案，我们按照顺序完成操作，如果有关于原点对称的点出现，那么就把他们链接在一起，容易发现这样是线性的。 | 一个观察是，对于两个关于对称的坐标，在以后所有的操作中都会关于原点对称。然后又由于坐标范围不是很大，我们可以对1~1000000都求出答案，我们按照顺序完成操作，如果有关于原点对称的点出现，那么就把他们链接在一起，容易发现这样是线性的。 | ||
| - | ARC149E | + | |
| + | ===ARC149E=== | ||
| 题意：一个长度为n的循环数组a，从第一个开始，每次把m个连续的数排序，再给定一个1到n的排列b，问有多少a满足经过k次连续的操作后可以变成b。n,m<=300000,k<=1e9 | 题意：一个长度为n的循环数组a，从第一个开始，每次把m个连续的数排序，再给定一个1到n的排列b，问有多少a满足经过k次连续的操作后可以变成b。n,m<=300000,k<=1e9 | ||
| 考虑操作了n-m+1次之后，这时整个a中最大的m-1个数都已经被按顺序排在了最后，后续操作就是把这m-1个数向后移动一个位置，因此k的大小其实是没有意义的。考虑什么情况下可以变成b，我们把b复原到最大的m-1个数都按顺序排在最后的情况。此时，寻找以b1开头的最长不下降子序列（不考虑最后m-1个数）。在不下降序列中的数字每次有m种排法，其余数字的位置则是固定的，因为否则的话一定会被排序提前排到前面去。最后m-1个数的顺序不影响最后的结果，因此有(m-1)!种方案。 | 考虑操作了n-m+1次之后，这时整个a中最大的m-1个数都已经被按顺序排在了最后，后续操作就是把这m-1个数向后移动一个位置，因此k的大小其实是没有意义的。考虑什么情况下可以变成b，我们把b复原到最大的m-1个数都按顺序排在最后的情况。此时，寻找以b1开头的最长不下降子序列（不考虑最后m-1个数）。在不下降序列中的数字每次有m种排法，其余数字的位置则是固定的，因为否则的话一定会被排序提前排到前面去。最后m-1个数的顺序不影响最后的结果，因此有(m-1)!种方案。 | ||
| - | ARC149F | + | |
| + | ===ARC149F=== | ||
| 题意：给定一个有理数\frac{p}{q}\geq1.01，p,q=1，容易证明，对于任意正整数n，都存在唯一的序列a_1\ldotsa_k，a1≠0，0≤ai≤p-1，i=1kai·pqk-i。求1~N中表示法按字典序排在第L~R位的数是哪些，N<=1e18，R-L+1<=300000。 | 题意：给定一个有理数\frac{p}{q}\geq1.01，p,q=1，容易证明，对于任意正整数n，都存在唯一的序列a_1\ldotsa_k，a1≠0，0≤ai≤p-1，i=1kai·pqk-i。求1~N中表示法按字典序排在第L~R位的数是哪些，N<=1e18，R-L+1<=300000。 | ||
| 首先1~p-1的表示法很简单，p的倍数的表示法也容易想到，对于其他的数，我们找到离n最近的能被p整除的数m，m·qp·pq+n-m就得到了一种新的表示法。我们发现所有数的表示法构成了一棵字典树的结构，而且1~N按照树的bfs序排列，而字典序大小按照dfs序排列。所以我们一旦确定排名第L的数，就可以O(1)计算下一个数。因此问题转化为求字典序排名L的数。注意到还有\frac{p}{q}\geq1.01的条件，因此字典树的深度不超过log_{1.01}N，也就是不会超过4000。我们从字典树第一层开始往下走，可以通过二分来确定需要从哪个位置向下走。 | 首先1~p-1的表示法很简单，p的倍数的表示法也容易想到，对于其他的数，我们找到离n最近的能被p整除的数m，m·qp·pq+n-m就得到了一种新的表示法。我们发现所有数的表示法构成了一棵字典树的结构，而且1~N按照树的bfs序排列，而字典序大小按照dfs序排列。所以我们一旦确定排名第L的数，就可以O(1)计算下一个数。因此问题转化为求字典序排名L的数。注意到还有\frac{p}{q}\geq1.01的条件，因此字典树的深度不超过log_{1.01}N，也就是不会超过4000。我们从字典树第一层开始往下走，可以通过二分来确定需要从哪个位置向下走。 | ||
| - | ABC271G | + | |
| + | ===ABC271G=== | ||
| 题意：有一串无限长的01序列，循环节长度为24，给出循环节，按序列顺序执行操作，若序列当前位置上为0，则A操作，有X%的概率成功，为1，则B操作，有Y%的概率成功。问第N次成功是由B完成的概率。 | 题意：有一串无限长的01序列，循环节长度为24，给出循环节，按序列顺序执行操作，若序列当前位置上为0，则A操作，有X%的概率成功，为1，则B操作，有Y%的概率成功。问第N次成功是由B完成的概率。 | ||
| f_i表示前i次成功是由B完成的概率，p_i表示一个循环节当中成功i次的概率。有f_n=\sum_{i=0}^{24}{p_i*f_{n-i}}这个式子明显可以用矩阵快速幂优化，细节就不赘述了。 | f_i表示前i次成功是由B完成的概率，p_i表示一个循环节当中成功i次的概率。有f_n=\sum_{i=0}^{24}{p_i*f_{n-i}}这个式子明显可以用矩阵快速幂优化，细节就不赘述了。 | ||
| + | |||
| ===ARC148E=== | ===ARC148E=== | ||
| 题意：求长度为n的序列的重排列满足任意两个相邻的元素的和都大于等于k的数量。 | 题意：求长度为n的序列的重排列满足任意两个相邻的元素的和都大于等于k的数量。 | ||
2022-2023/teams/fire_and_blood/week_summary_1.1665679173.txt.gz · 最后更改: 2022/10/14 00:39 由 clap
