AcWing第155场周赛题解

type

status

date

slug

summary

📝 主旨内容

更大数的二倍(模拟)

给定一个整数区间 [l,r] 和一个整数 x。

请你判断整数 x 是否在区间 [l,r] 内。

注意： 当 x=l 或 x=r 时，也算在区间内。

给定两个正整数 a,b，请你输出 2×max(a,b) 的结果。

输入格式

共一行，两个正整数 a,b。

输出格式

一个整数，表示答案。

数据范围

前 3 个测试点满足 1≤a,b≤10。

所有测试点满足 1≤a,b≤100。

输入样例：

输出样例：

题解：

💡

签到题，直接模拟

模方程(质因数分解)

给定两个非负整数 a,b，请你计算一共有多少个正整数 x 满足 a mod x = b。

输入格式

共一行，包含两个非负整数 a,b。

输出格式

如果满足条件的正整数 x 有无限多个，则输出 infinity。

否则，输出一个整数，表示满足条件的正整数 x 的数量。

数据范围

前 5 个测试点满足 0≤a,b≤100。

所有测试点满足 0≤a,b≤10^9。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

💡

首先需要明确，取模只会使得结果小于等于之前的数，也就是说a<b时是不存任何的x使得a%x=b，同理当a=b时只需要x是大于a的即可，所以答案有无穷多个

💡

最后是a>b这种情况，可以转化成a = kx + b也就是(a - b)是x的倍数，x是(a - b)的一个因子，并且需要保证x是大于b的，因为a%x=b，b是余数

连续子序列(Tire树)

给定一个长度为 n 的非负整数序列 a1,a2,…,an。

请你计算，一共有多少个该序列的连续子序列满足：子序列内的所有元素的按位异或和不小于 k。

输入格式

第一行包含两个整数 n,k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示满足条件的连续子序列的数量。

数据范围

前 4 个测试点满足 1≤n≤3。

所有测试点满足 1≤n≤10^6，1≤k≤10^9，0≤ai≤10^9。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

💡

需要求一段连续子数组的异或和不小于k的数量，很容易想到前缀和，就是只需要知道区间的左右端点就能知道这一段连续区间的异或和，但是n的范围是10^5双重循环枚举端点会超时

💡

也就是说一个一个枚举会超时，能不能一次枚举得到一段的值呢？我们可以固定区间的右端点，查询出符合要求的左端点即可，可以用字典树来去实现这个操作

💡

重点在于query的实现，当k的某一位为0时，当前位为1之后的全部数都满足要求

🤗 总结归纳

秒完第一题，第二题有点懵

然后第三题已经知道要用字典树优化了，不知道怎么实现

Python是真的卡常啊

📝 主旨内容

更大数的二倍(模拟)

输入格式

输出格式

数据范围

输入样例：

输出样例：

题解：

模方程(质因数分解)

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

连续子序列(Tire树)

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

🤗 总结归纳

📎 参考文章