2022年蓝桥杯省赛 C/C++ A组题解

前言： NewOJ最新推出2022蓝桥杯省赛题目，数据均为管理员自行构造，仅供参考。

传送门：http://oj.ecustacm.cn/viewnews.php?id=1021。

题目总览

注：本次$C++A$组的题目题目质量很好，但是难度过大，线段树考点重复（也可能存在其他做法）。

试题A: 裁纸刀

题意： 一张纸上打印了$20$行$22$列共$440$个二维码，至少需要裁多少次可以全部裁出。如下图，$2$行$3$列共需要裁$9$次。

Tag： 模拟

难度： ☆

思路： 根据题意，首先需要额外裁剪$4$次去除边界。每裁$1$刀，可以使得纸张数目增加$1$。 最终要变成$440$个二维码，只需要裁剪$439$次。总计$439+4=443$次。

试题B: 灭鼠先锋

题意： 在$2$行$4$列的棋盘中，两人轮流操作，每次可选择在空位上放置$1$个棋子，或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在$4$种初始局面如下所示，$O$表示空，$X$表示已放置。每人均以最优策略放棋子。判断先手胜利（输出$V$）还是后手胜利（输出$L$）。

XOOO XXOO OXOO OXXOOOOO OOOO OOOO OOOO

Tag： 博弈

难度： ☆☆☆

思路： 博弈题核心：

只能转移到必胜态的，均为必败态。

可以转移到必败态的，均为必胜态。

1. 首先确定最终的必败态：只剩下1个棋子的时候肯定是必败的。

   OXXXXOXXXXXXXXXX

2. 利用上述提到的核心，倒推出其他情况属于必败态还是必胜态。

3. 注意，给定的$4$个局面为先手第一步的四种局面，对于此时局面为必胜态，表示的是后手胜。

#includeusing namespace std;///判断是否仅存在一个空格bool check(string s){int tot = 0;for(auto x : s)if(x == 'O')tot++;return tot == 1;}map<string, bool>SG;bool dfs(string s){if(SG.count(s))return SG[s];if(check(s))return SG[s] = false;///模拟放1个棋子for(int i = 0; i < s.size(); i++)if(s[i] == 'O'){string tmp = s;tmp[i] = 'X';if(dfs(tmp) == false)///可以到达必败态均为必胜态return SG[s] = true;}///模拟放2个棋子for(int i = 0; i < s.size() - 1; i++)if(s[i] == 'O' && s[i + 1] == 'O' && i != 3){string tmp = s;tmp[i] = tmp[i + 1] = 'X';if(dfs(tmp) == false)///可以到达必败态均为必胜态return SG[s] = true;}///运行到此，说明只能转移到必胜态，此时为必败态return SG[s] = false;}int main(){string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};for(int i = 0; i < 4; i++){if(dfs(s[i]))cout<<"L";///此时为必胜态，说明后手面临的局面必胜，输出Lelse cout<<"V";}return 0;}

试题C: 求和

题意： 给定数组$a$，求 ∑ i = 1n∑ j = i + 1naiaj \sum_{i=1}^n\sum_{j=i+1}^n a_ia_j∑i=1n​∑j=i+1n​ai​aj​。

Tag： 前缀和

难度： ☆☆

思路： 可以进行如下转换：
∑ i=1n ∑ j=i+1n a i a j= ∑ i=1n [ ai∑ j = i + 1naj]\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j =\sum_{i=1}^n\left[a_i\sum_{j=i+1}^na_j\right] i=1∑n​j=i+1∑n​ai​aj​=i=1∑n​[ai​j=i+1∑n​aj​]
对于里面的求和，直接用前缀和优化：
∑ i=1n ∑ j=i+1n a i a j= ∑ i=1n [ ai∑ j = i + 1naj]= ∑ i=1n a i(sum[n]−sum[i])\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j =\sum_{i=1}^n\left[a_i\sum_{j=i+1}^na_j\right] =\sum_{i=1}^n a_i(sum[n]-sum[i]) i=1∑n​j=i+1∑n​ai​aj​=i=1∑n​[ai​j=i+1∑n​aj​]=i=1∑n​ai​(sum[n]−sum[i])
预处理前缀和即可，时间复杂度$O(n)$。

#includeusing namespace std;typedef long long ll;const int maxn = 2e5 + 10;ll a[maxn], sum[maxn];int main(){int n;ll ans = 0;cin >> n;for(int i = 1; i <= n; i++) ///预处理前缀和cin >> a[i], sum[i] = sum[i - 1] + a[i];for(int i = 1; i <= n; i++) ///求和即可ans += a[i] * (sum[n] - sum[i]);cout<<ans<<endl;return 0;}

试题D: 选数异或

题意： 给定数组$a$和整数$x$，$m$次询问，每次询问区间$[l,r]$是否存在两个数字使得异或值等于$x$。

Tag： 线段树、$ST$表

难度： ☆☆☆

思路： 由于给定$x$，对于区间$[l,r]$中的每个数字$a[i]$而言，只需要判断区间$[l,r]$中是否存在$a[i]\oplus x$。

暴力判断会超时，如何快速判断区间$[l,r]$而不是一个一个$a[i]$来判断？

对每个数字$a[i]$，找到它左边最近的$a[j]$，满足$a[i]\oplus a[j]=x$，则$<j,i>$二元组是一个合法解，其中$j<i$。

为什么一定是左边最近合法位置而不是右边最近？

二者是一样的，因为i找到的左边最近合法位置是$j$，$j$找到的右边最近是$i$。

对于每个$i$，都找到左边最近合法的$j$，记为$Left[i]=j$，满足$j<i,a[i]\oplus a[j]=x$。

那么对于询问$[l,r]$中是否存在两个数字异或值等于$x$，等价于询问$[l,r]$中是否存在一个$i$满足：$l\le i\le r,l\le Left[i]$。

存在一个$i$即可满足条件，相当于最大的$Left[i]$大于$l$即可，即$l\le Max\{Left[i]|l\le i\le r\}$。

问题转换成：求区间最大值问题，使用线段树或者$ST$表即可。

那如何快速得到$Left$数组？从左往右遍历时，利用$pos[x]$记录数字$x$上一次出现的位置，那么$Left[i]=pos[a[i]\oplus x]$。

注：本题也可使用莫队算法维护区间异或等于$x$的次数来求解。

#includeusing namespace std;const int maxn = 100000 + 10;int tree[maxn << 2];int Left[maxn], pos[(1 << 20) + 10];int a[maxn], n, m, x;//线段树模板void build(int o, int l, int r){if(l == r){tree[o] = Left[l];return;}int mid = (l + r) >> 1;build(o << 1, l, mid);build(o << 1 | 1, mid + 1, r);tree[o] = max(tree[o << 1], tree[o << 1 | 1]);}int query(int o, int l, int r, int L, int R){if(L <= l && r <= R)return tree[o];int mid = (l + r) >> 1;int ans = 0;if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));return ans;}int main(){scanf("%d%d%d", &n, &m, &x);for(int i = 1; i <= n; i++) //预处理Left数组{scanf("%d", &a[i]);Left[i] = pos[a[i] ^ x];pos[a[i]] = i;}build(1, 1, n);//线段树建树while(m--){int l, r;scanf("%d%d", &l, &r);if(query(1, 1, n, l, r) >= l)//查询区间最值printf("yes\n");elseprintf("no\n");}return 0;}

试题E: 爬树的甲壳虫

题意： 甲壳虫想要爬上高度为$n$的树，开始位于树根，高度为0，当它尝试从高度$i-1$爬到高度为$i$的位置时有 Pi P_iPi​的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

Tag： 期望$DP$、逆元

难度： ☆☆☆☆

思路： $dp[i-1]$表示从高度$i-1$出发到顶部花费的期望时间。根据题意可以得到如下的状态转移方程：
dp[i−1] = P i∗dp[0]+(1− P i)dp[i]+1dp[n] =0\begin{aligned} dp[i-1]&=P_i*dp[0]+(1-P_i)dp[i] + 1 \\ dp[n]&=0 \end{aligned} dp[i−1]dp[n]​=Pi​∗dp[0]+(1−Pi​)dp[i]+1=0​
利用递推式展开：
dp[n] =0∗dp[0]+0=a∗dp[0]+bdp[n−1] = P n∗dp[0]+(1− P n)dp[n]+1dp[n−2] = P n−1 ∗dp[0]+(1− P n−1 )dp[n−1]+1…dp[0] = P 1dp[0]+(1− P 1)dp[1]+1\begin{aligned} dp[n]&=0*dp[0]+0=a*dp[0]+b \\ dp[n-1]&=P_n * dp[0] + (1-P_n)dp[n] + 1 \\ dp[n-2]&=P_{n-1} * dp[0] + (1-P_{n-1})dp[n-1] + 1 \\ … \\ dp[0]&=P_1dp[0]+(1-P_1)dp[1]+1 \end{aligned} dp[n]dp[n−1]dp[n−2]…dp[0]​=0∗dp[0]+0=a∗dp[0]+b=Pn​∗dp[0]+(1−Pn​)dp[n]+1=Pn−1​∗dp[0]+(1−Pn−1​)dp[n−1]+1=P1​dp[0]+(1−P1​)dp[1]+1​
维护两个变量$a,b$，分别表示$dp[0]$的系数和常数，初始均为0。

将$dp[n]$代入$dp[n-1]$中，得到新的$a,b$：
a= P n+(1− P n)∗ab=1+(1− P n)∗b\begin{aligned} a&=P_n+(1-P_n)*a \\ b&=1+(1-P_n)*b \end{aligned} ab​=Pn​+(1−Pn​)∗a=1+(1−Pn​)∗b​
最终可以得到：
$$dp[0]=a\ast dp[0]+b$$
遍历中全部使用模意义下的数字，求解$dp[0]$的时候相当于求解：
$$(a-1)dp[0]+b\equiv 0\%MOD$$
利用扩展欧几里得求解$dp[0]$即可。

注意：存在更优的做法，递推过程更复杂，但是不需要最后的扩展欧几里得。

#includeusing namespace std;typedef long long ll;const int maxn = 1e5 + 10;const int MOD = 998244353;ll x[maxn], y[maxn];ll ksm(ll a, ll b, ll m){ll ans = 1;while(b){if(b & 1)ans = ans * a % m;b >>= 1;a = a * a % m;}return ans;}ll inv(ll x){return ksm(x, MOD - 2, MOD);}ll extgcd(ll a, ll b, ll&x, ll&y)//ax+by = gcd(a, b)的解。返回值为gcd{ll d = a;if(b){ d = extgcd(b, a % b, y, x); y -= (a / b) * x;}else x = 1, y = 0;return d;}int main(){int n;cin >> n;for(int i = 1; i <= n; i++){cin >> x[i] >> y[i];ll g = __gcd(x[i], y[i]);x[i] = x[i] / g;y[i] = y[i] / g;}ll a = 0, b = 0;for(int i = n; i >= 1; i--){ll p = x[i] * inv(y[i]) % MOD, p_1 = (y[i] - x[i]) * inv(y[i]) % MOD;a = (p + p_1 * a) % MOD;b = (1 + p_1 * b) % MOD;}///cout<<x[1]<<" "<<y[1]<<" "<<inv(y[1])<<endl;///dp[0] = a * dp[0] + b///(a-1)dp[0]+k * MOD = MOD - b///(a - 1)x + MOD * y = MOD - b///cout<ll c = a - 1, d = MOD, x, y;ll g = extgcd(c, d, x, y);///cout<<x<<" "<<y<<endl;ll x1 = x * (MOD - b) / g;ll y1 = y * (MOD - b) / g;cout<<(x1 % MOD + MOD ) % MOD<<endl;return 0;}

试题F: 青蛙过河

题意： 小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到0 是允许的）。

小青蛙一共需要去学校上$x$天课，所以它需要往返$2x$次。当小青蛙具有一个跳跃能力$y$时，它能跳不超过$y$的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完$x$次课。

Tag： 二分答案、贪心

难度： ☆☆☆☆

思路： 往返累计$2x$次相当于单向走$2x$次。跳跃能力越大，越能保证可以通过$2x$次。因此可以使用二分答案，找到一个最小的满足条件的跳跃能力。

假设跳跃能力为$mid$，一种思想是每次能跳多远跳多远，然后去模拟判断$mid$是否合法，做法比较复杂，暂不展开。

另一种想法是判断每个长度为$mid$的区间之和是否大于等于$2x$，如果每个区间和都大于$2x$，肯定可以保证构造出一组解通过$2x$次。反过来是否成立可以自行思考一下。

参考：https://www.zhihu.com/question/525176453/answer/2433729894。

#includeusing namespace std;const int maxn = 1e5 + 10;template <typename T>inline T read(T& x) {x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;}int h[maxn], sum[maxn];int n, x;//判断所有长度为mid的区间之和是否大于等于2xbool check(int mid){for(int i = 1; i + mid - 1 <= n; i++)if(sum[i + mid - 1] - sum[i - 1] < 2 * x)return false;return true;}int main(){read(n); read(x);for(int i = 1; i <= n - 1; i++)//预处理前缀和read(h[i]), sum[i] = sum[i - 1] + h[i];sum[n] = 1e9 + 7;int left = 1, right = n, ans = n;while(left <= right)//二分答案{int mid = (left + right) >> 1;if(check(mid))ans = mid, right = mid - 1;//求最小合法解elseleft = mid + 1;}cout<<ans<<endl;return 0;}

试题G: 最长不下降子序列

题意： 给定数组$a$，可以修改连续的$K$个数字变成一个相同值。请计算修改后的最长不下降子序列长度。

Tag： 动态规划、线段树

难度： ☆☆☆☆☆

思路： 最长不下降子序列是经典的动态规划问题。本题只和数字大小有关，与数值无关，因此，先对数组进行离散化。

记$dp[i]$表示以$a[i]$结尾的最长不下降子序列长度，对于修改连续的$K$个数字变成同一值，最好修改成与前面一样的数字，即：

修改$a[i-k+1],\dots ,a[i]$均修改成$a[i-k]$，此时的最长上升子序列可以看成3段：

1. $[1,i-k]$：长度为$dp[i-k]$
2. $[i-k+1,\dots ,i-1]$：长度为$k-1$
3. $[i,i+1\dots n]$：$a[i],a[i+1],\dots ,a[n]$中，以$a[i]$开头的最长上升子序列，注意此时的$a[i]$的值应该等于$a[i-k]$

为了求出$dp[i]$，利用权值线段树求出$dp[1],\dots ,dp[i-1]$中最大的数字$dp[j]$，同时保证$a[j]\le a[i]$。

具体做法为：对$a$数组离散化后，从左往右遍历$a$数组，将$a[i]$看作线段树的第$a[i]$位，$dp[i]$为线段树维护的值（线段树维护最大值），查询线段树区间$[1,a[i]]$的最大值即可。

类似的，反向遍历，每次查询$[a[i],n]$的最大值，就可以维护以$x$开头的最长上升子序列，这样，最后暴力枚举每一段$K$即可。

#includeusing namespace std;const int maxn = 1e5 + 10;template <typename T>inline T read(T& x) {x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;}int a[maxn], b[maxn];int dp[maxn];///dp[i]表示以i结尾的最长上升子序列///权值线段树，维护dp数组int tree[maxn << 2];void build(int o, int l, int r){tree[o] = 0;if(l == r)return;int mid = (l + r) >> 1;build(o << 1, l, mid);build(o << 1 | 1, mid + 1, r);}void update(int o, int l, int r, int x, int val){if(l == r){tree[o] = max(tree[o], val);return;}int mid = (l + r) >> 1;if(x <= mid)update(o << 1, l, mid, x, val);else update(o << 1 | 1, mid + 1, r, x, val);tree[o] = max(tree[o << 1], tree[o << 1 | 1]);}int query(int o, int l, int r, int L, int R){if(L <= l && r <= R)return tree[o];int mid = (l + r) >> 1;int ans = 0;if(L <= mid)ans = max(ans, query(o << 1, l, mid, L, R));if(R > mid)ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R));return ans;}int main(){int n, k, tot = 0;read(n); read(k);for(int i = 1; i <= n; i++)read(a[i]), b[++tot] = a[i];if(n == k){cout<<n<<endl;return 0;}///离散化sort(b + 1, b + 1 + tot);tot = unique(b + 1, b + 1 + tot) - (b + 1);for(int i = 1; i <= n; i++)a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;build(1, 1, tot);int ans = 0;for(int i = 1; i <= n; i++)///从前往后遍历a，放入权值线段树中{///dp[i] = max(dp[j]) 满足j=1...i-1 && a[j] <= a[i]dp[i] = query(1, 1, tot, 1, a[i]) + 1;update(1, 1, tot, a[i], dp[i]);}///重新清空build(1, 1, tot);for(int i = n; i > k; i--)///从后往前遍历a，放入权值线段树中{///a[i-k+1] ... a[i]相等 均等于a[i-k]///最后一段要注意：查询的是[a[i-k],tot]中的最大值ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1);int tmp = query(1, 1, tot, a[i], tot) + 1; ///以a[i]开始的最长上升子序列长度ans = max(ans, tmp + k);///插入的是a[i]update(1, 1, tot, a[i], tmp);}cout<<ans<<endl;return 0;}

试题H: 扫描游戏

题意： 有一根围绕原点$O$顺时针旋转的棒$OA$，初始时指向正上方（$Y$ 轴正向）。在平面中有若干物件，第$i$个物件的坐标为$(xi,yi)$ ，价值为$zi$。当棒扫到某个物件时，棒的长度会瞬间增长$zi$，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到），如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。

如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出$-1$。

Tag： 计算几何、线段树

难度： ☆☆☆☆☆

思路： 首先进行极角排序，按照顺时针排序。具体可以利用象限+叉积来排序。

初始时棒长度为$L$，每次需要找到顺时针第一个小于等于$L$的点即可。

可以利用线段树维护每个点到原点的距离 xi2+ yi2 x_i^2+y_i^2xi2​+yi2​，要找的是下一个小于等于 L2 L^2L2的点，因此维护最小值。

假设之前位置为$last$（初始为0），每次利用线段树查找区间$[last+1,n]$中从左往右第一个小于等于 L2 L^2L2的数字，如果没有找到则查找区间$[1,last-1]$中从左往右第一个小于等于 L2 L^2L2的数字（顺时针一圈）。

如果没找到则终止。

如果找到了，下标记为$idx$。棒长$L$增加 z i d x z_{idx}zidx​，记录一下当前第$idx$个点的答案。注意特判一下，如果当前点和先前点夹角为0，则排名是一样的。

代码中由于$L$不断增加， L2 L^2L2会超过$longlong$，可以在代码中维护距离而不是距离的平方，也可以使用$\_\_int128$来维护变量 L2 L^2L2。

#includeusing namespace std;typedef long long ll;const int INF = 1e9 + 7;const int maxn = 2e5 + 10;template <typename T>inline T read(T& x) {x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x = x * w;}struct point{ll x, y, z;int id;}a[maxn];ll n;__int128 L;int Quadrant(point a){if(a.x >= 0 && a.y > 0)return 1;///y的正半轴放到第一象限if(a.x > 0 && a.y <= 0)return 2;///x的正半轴放到第二象限if(a.x <= 0 && a.y < 0)return 3;return 4;}ll cross(point a, point b){return a.x * b.y - a.y * b.x;}bool cmp(point a, point b){if(Quadrant(a) == Quadrant(b)){if(cross(a, b) == 0)return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;else return cross(a, b) < 0;}elsereturn Quadrant(a) < Quadrant(b);}__int128 mi[maxn << 2];void push_up(int o){mi[o] = min(mi[o << 1], mi[o << 1 | 1]);}void build(int o, int l, int r){if(l == r){mi[o] = a[l].x * a[l].x + a[l].y * a[l].y;return ;}int mid = (l + r) >> 1;build(o << 1, l, mid);build(o << 1 | 1, mid + 1, r);push_up(o);}void update(int o, int l, int r, int x, __int128 val){if(l == r){mi[o] = val;return;}int mid = (l + r) >> 1;if(x <= mid)update(o << 1, l, mid, x, val);else update(o << 1 | 1, mid + 1, r, x, val);push_up(o);}///找右边第一个小于等于z^2的数字ll idx;bool query(int o, int l, int r, int L, int R, __int128 z){if(L > R)return false;if(l == r){idx = l;return mi[o] <= z;}int mid = (l + r) >> 1;if(L <= mid){if((mi[o << 1] <= z) && query(o << 1, l, mid, L, R, z))return true;}if(R > mid){if((mi[o << 1 | 1] <= z) && query(o << 1 | 1, mid + 1, r, L, R, z))return true;}return false;}int ans[maxn];int main(){read(n);read(L);for(int i = 1; i <= n; i++){read(a[i].x);read(a[i].y);read(a[i].z);a[i].id = i;ans[i] = -1;}sort(a + 1, a + 1 + n, cmp);build(1, 1, n);int cnt = 0;int lastcnt = 0;int last = 0;///上一个位置while(true){bool ok = query(1, 1, n, last + 1, n, L * L);if(ok)L = L + a[idx].z;else{ok = query(1, 1, n, 1, last - 1, L * L);if(ok)L = L + a[idx].z;else break;}update(1, 1, n, idx, 1e32);if(last){if(Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0)ans[a[idx].id] = lastcnt, ++cnt;elseans[a[idx].id] = ++cnt, lastcnt = cnt;}elseans[a[idx].id] = ++cnt, lastcnt = cnt;last = idx;}for(int i = 1; i <= n; i++){cout<<ans[i];if(i != n)cout<<" ";}return 0;}

试题I: 数的拆分

题意： 判断数字 a ≤ 1 018 a \le 10^{18}a≤1018能否表示成 x1 y 1×2 y 2 x_1^{y_1}x_2^{y_2}x1y1​​x2y2​​的形式，其中 x1, x2 x_1,x_2x1​,x2​为正整数， y1, y2 y_1,y_2y1​,y2​为大于等于$2$的正整数。$T\le 100000$次询问。

Tag： 数论

难度： ☆☆☆☆☆

思路： 首先考虑将$a$进行素因子分解 p1 q 1p2 q 2⋅ . . . ⋅ pk q k p_1^{q_1}p_2^{q_2}\cdot …\cdot p_k^{q_k}p1q1​​p2q2​​⋅…⋅pkqk​​，首先要满足 qi≥ 2q_i\ge 2qi​≥2。

∀ qi≥ 2\forall q_i \ge 2∀qi​≥2，要拆分成 k1∗ y1+ k2∗ y2= qi k_1*y_1+k_2*y_2=q_ik1​∗y1​+k2​∗y2​=qi​， k1, k2≥ 0 , y1, y2≥ 2k_1,k_2 \ge 0,y_1,y_2\ge 2k1​,k2​≥0,y1​,y2​≥2。

y1= 2 , y2= 3y_1=2,y_2=3y1​=2,y2​=3可以保证所有的 qi≥ 2q_i \ge 2qi​≥2均有非负整数解。

2 k 1+3 k 2=k2k_1+3k_2=k 2k1​+3k2​=k对于$\forall k>1$均有非负整数解：

1、$k\%3==0$： k 1=0, k 2= k 3k_1=0,k_2=\frac{k}{3} k1​=0,k2​=3k​

2、$k\%3==1$： k 1=2, k 2= k−43k_1=2,k_2=\frac{k-4}{3} k1​=2,k2​=3k−4​

3、$k\%3==2$： k 1=1, k 2= k−23k_1=1,k_2=\frac{k-2}{3} k1​=1,k2​=3k−2​

所以问题变成数字$a$能否变成 x12x23 x_1^2x_2^3x12​x23​。

对于 a = p1 q 1p2 q 2⋅ . . . ⋅ pk q k a=p_1^{q_1}p_2^{q_2}\cdot …\cdot p_k^{q_k}a=p1q1​​p2q2​​⋅…⋅pkqk​​，只需要检测每个 qi q_iqi​是否大于等于$2$即可，只要大于等于$2$就可以按照对应的 k1, k2 k_1,k_2k1​,k2​分配到 x1, x2 x_1,x_2x1​,x2​里面。

由于 a ≤ 1 018 a\le 10^{18}a≤1018，所以 x12x23≤ 1 018 x_1^2x_2^3\le 10^{18}x12​x23​≤1018。如果素因子$p>4000$，则 p5≥ 1 018 p^5\ge 10^{18}p5≥1018。所以只需要暴力判断$4000$以内的素因子，对于大于$4000$的$p$，指数只可能是$2,3,4$，即判断一下是否为平方数或者立方数即可。

时间复杂度$O(T\ast 550)$，$550$为$4000$以内素数数量。

#includeusing namespace std;typedef long long ll;const int MOD = 1e9 + 7;template <typename T>inline T read(T& x) {x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x * w;}bool not_prime[4010];int prime[4010], tot;void init(int n){for(int i = 2; i <= n; i++)if(!not_prime[i]){prime[++tot] = i;for(int j = i + i; j <= n; j += i)not_prime[j] = 1;}}inline bool check(ll x){///检查平方数ll y = pow(x, 0.5);if(y * y == x || (y + 1) * (y + 1) == x)return true;///检查立方数y = pow(x, 1.0 / 3);if(y * y * y == x || (y + 1) * (y + 1) * (y + 1) == x || (y + 2) * (y + 2) * (y + 2) == x)return true;return false;}int main(){init(4000);int T;read(T);while(T--){ll x;read(x);if(check(x)){puts("yes");continue;}bool flag = true;for(int i = 1; i <= tot; i++)if(x % prime[i] == 0){int now = 0;while(x % prime[i] == 0){now++;x /= prime[i] ;}///cout<<prime[i]<<" "<<now<<endl;if(now == 1){flag = false;break;}}if(flag & check(x)){puts("yes");continue;}else{puts("no");}}return 0;}

试题J: 推导部分和

题意： 对于数列$a$，已知部分区间和，询问若干次区间和。

Tag： 并查集、搜索

难度： ☆☆☆☆

思路： 对于已知的区间$[l,r]$的和为$s$，用前缀和$sum[r]-sum[l-1]=s$表示，根据差分约束建图准则，相当于点$l-1$到点$r$长度为$s$，$r$到$l-1$长度为$-s$。

建好图之后，每次询问一个区间$[ql,qr]$的和，相当于询问$sum[qr]-sum[ql-1]$的值。

首先要保证$ql-1$和$qr$在同一个连通块中，其次每个连通块只需要随便一个点初始化为$0$，然后按照边长扩展即可。这是由于等号，不管怎么走，相对差值是不变的。

代码中$dfs$和$bfs$均可以。

#includeusing namespace std;typedef long long ll;template <typename T>inline T read(T& x) {x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + (ch - '0');ch = getchar();}return x = x * w;}const int maxn = 1e5 + 10;const ll INF = -1e13;int n, m, q;struct edge{int v; ll w;edge(){}edge(int v, ll w):v(v), w(w){}};vector<edge>Map[maxn];ll sum[maxn];bool vis[maxn];void dfs(int u, ll d){vis[u] = 1;sum[u] = d;///cout<<u<<" "<<d<<endl;for(auto x : Map[u]){int v = x.v; ll w = x.w;if(vis[v])continue;dfs(v, d + w);}}queue<pair<int,ll> >Q;void bfs(int u, ll d){vis[u] = 1;sum[u] = d;Q.push(make_pair(u, d));while(!Q.empty()){auto now = Q.front();Q.pop();int u = now.first; ll d = now.second;for(auto x : Map[u]){int v = x.v; ll w = x.w;if(vis[v])continue;vis[v] = 1;sum[v] = d + w;Q.push(make_pair(v, d + w));}}}int f[maxn];int Find(int x){return x == f[x] " />: f[x] = Find(f[x]);}int main(){read(n);read(m);read(q);for(int i = 0; i <= n; i++)f[i] = i;for(int i = 1; i <= m; i++){int l, r; ll s;read(l);read(r);read(s);///cout<<l<<" "<<r<<" "<<s<<endl;///sum[r] - sum[l - 1] = sMap[l - 1].push_back(edge(r, s));Map[r].push_back(edge(l - 1, -s));f[Find(l - 1)] = Find(r);}for(int i = 0; i <= n; i++)if(!vis[i])bfs(i, 0);while(q--){int l, r;read(l), read(r);--l;if(Find(l) != Find(r))puts("UNKNOWN");else printf("%lld\n", sum[r] - sum[l]);}return 0;}