背景 靠队友带飞，我是演员（雾
题解 思路 类似有序数组合并的思路，可以用在这个题上面。
假设说，我们有$n$个数组，每个数组里面有$m$个元素，如$n=3, m=2$时：
然后，由于我们要求第$K$大的数，可以把每个数组最后面的元素都压到一个优先队列里，并以最后相乘得到的结果来规定优先队列的优先级。
其中，为了方便后续操作，我们可以规定这样的一个三元组$(n, nowm, g)$。
更详细的说：
$n$代表当前元素是第几个数组里的
$nowm$代表当前元素是第$n$个数组里的第几个元素
$g$是相乘的结果（$|x| * |y|$）。
然后，压入优先队列，由上文，在最开始的时候，我们压入的是$(1, 2, 2), (2, 2, 4), (3, 2, 6)$。
我们找到这个优先队列里$g$最大的元素，即$(3, 2, 6)$，弹出。
然后，压入第$3$个数组里面，第$2-1$个元素，即压入三元组$(3, 1, 3)$。这样每次弹出的元素都是最大的。
类似的，重复$K$次，时间复杂度为$O(KlogN)$，可以通过本题。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <bits/stdc++.h> #define int long long #define maxn 1000005 using namespace std ;int n, m, K;struct Node { int n, nowm; int g; }; bool operator < (const Node &A, const Node &B){ return A.g < B.g; } priority_queue<Node> q1; signed main (void ) scanf ("%lld %lld %lld" , &n, &m, &K); for (int i = 1 ; i <= n; i++) q1.push((Node){i, m, i * m}); int cnt = 0 , now = -1 ; while (cnt < K) { cnt++; Node tmp = q1.top(); q1.pop(); now = tmp.g; q1.push((Node){tmp.n, tmp.nowm - 1 , tmp.n * (tmp.nowm - 1 )}); } printf ("%lld\n" , now); return 0 ; }
思路 一个很关键的地方是，胜利后，每次这个元素都会翻倍 。
另一个关键的地方是，如果当前元素胜利后，翻倍后$\geq$最大值，则一定可以把剩下的元素吃掉。
因此，我们暴力枚举每一个点，并不断往左右拓展，由于翻倍的影响，最多只会拓展$30$次左右，就能大于等于最大值，即可以实现最后的胜利。
时间复杂度为$O(N)$。
本题有点类似花神游历各国 （暴力开方就可以，因为一段数不会被开方很多次就会变成$0/1$）。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> #define maxn 500005 using namespace std ;int n, maxx, a[maxn];bool check (int pos) int l = pos - 1 , r = pos + 1 , val = a[pos]; while (1 ) { if (val >= maxx) return true ; if (l && val >= a[l]) val *= 2 , l--; else if (r <= n && val >= a[r]) val *= 2 , r++; else return false ; } } int cnt, ans[maxn];int main (void ) scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d" , &a[i]), maxx = max (maxx, a[i]); for (int i = 1 ; i <= n; i++) if (check(i)) ans[++cnt] = i; printf ("%d\n" , cnt); for (int i = 1 ; i <= cnt; i++) printf (i == cnt ? "%d\n" : "%d " , ans[i]); return 0 ; }
思路 考虑数组内全为$2$的情况为边界情况。
若数组全为$2$时，为$Alice$的回合，则$Bob$获胜。
否则，$Alice$必胜。
那么，讨论如何从最开始的状态达到这个边界情况。
假设，$Alice$在到达这种情况下能够执行$cnt1$步，$Bob$能执行$cnt2$步。
我们发现，$Alice$和$Bob$能够操作的数是互相独立的。
$Alice$为了使自己获胜，每次选择把一个奇数$k$分解为$k - 2$和$k$是最优的。
由此，某一奇数$k$能够为$Alice$提供$k/2 + 1$步操作（$+1$是把最后的$1$给消去了，只剩下全为$2$的情况）。
而$Bob$为了使自己获胜，自然不会选择把一个偶数分解为两个奇数给对面，而是会选择分为两个偶数。
对于一个偶数$k$，在分解为边界情况前，可以为$Bob$提供$k/2-1$步操作。
最后，只要统计两人的总操作数，即$cnt1$和$cnt2$，就可以判断全$2$的局面是落在了谁的回合，即可以判断输赢。
记得开long long
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> #define maxn 1000005 #define int long long using namespace std ;int t, n, a[maxn];signed main (void ) scanf ("%lld" , &t); while (t--) { scanf ("%lld" , &n); int cnt1 = 0 , cnt2 = 0 ; for (int i = 1 ; i <= n; i++) { scanf ("%lld" , &a[i]); if (a[i] == 1 ) cnt1++; else if (a[i] == 2 ) cnt2 += 0 ; else if (a[i] & 1 ) cnt1 += a[i] / 2 + 1 ; else cnt2 += a[i] / 2 - 1 ; } if (cnt1 > cnt2) printf ("Alice\n" ); else printf ("Bob\n" ); } }
思路 拿到这题时，发现这一题有$+ i i$的操作，也有$- i i$的操作，不太方便进行$dp$。
然后，写了个暴力打表程序，打了小的表后发现，貌似这些数都可以被$1,2,3$个完全平方数通过运算得到。
因此，提前计算出所有的完全平方数，大约有$300$个，可以写个$n^2+n^3$的枚举，计算最少需要多少个数才能凑出来。（结论的正确性我也不知道咋证明，但是在$1e5$内测试过没有不能表达出来的数字）。
赛后发现，实际上预处理所有的完全平方数，直接$bfs$就能通过该题了（
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include <bits/stdc++.h> #define maxn 200005 #define int long long using namespace std ;int dp[maxn], bas[maxn], cnt;void solve2 () for (int i = 1 ; i <= cnt; i++) for (int j = 1 ; j <= cnt; j++) { int val; val = bas[i] + bas[j]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 2L L); val = bas[i] - bas[j]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 2L L); } } void solve3 () for (int i = 1 ; i <= cnt; i++) for (int j = 1 ; j <= cnt; j++) for (int k = 1 ; k <= cnt; k++) { int val; val = bas[i] + bas[j] + bas[k]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 3L L); val = bas[i] + bas[j] - bas[k]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 3L L); val = bas[i] - bas[j] + bas[k]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 3L L); val = bas[i] - bas[j] - bas[k]; if (val >= 0 && val <= 100000 ) dp[val] = min (dp[val], 3L L); } } int q, n;signed main (void ) memset (dp, 0x3f , sizeof (dp)); for (int i = 1 ; i * i <= 100000 ; i++) { bas[++cnt] = i * i; dp[i * i] = 1 ; } solve2(); solve3(); scanf ("%lld" , &q); while (q--) { scanf ("%lld" , &n); printf ("%lld\n" , dp[n]); } return 0 ; }
思路 一个期望题，签到，求最小的回合数。
设$(a, b, c)$分别为$a, b, c$三个人的落败数。
第一轮，任意一个人获胜，得到的结果都可以等效为$(0, 0\ | \ 1)$，落败的暂时出局。
然后，第二轮，剩下两个人战斗，得到结果可以等效为$(1, 0 \ | \ 1)$。
那么，其实最终的轮数只取决于第三轮，若落败过的选手再次落败，则结束回合，即变为$(2, 0 \ | \ 1)$。
否则，则继续第四局，且在第四局一定会有一个选手落败到两轮。
即第三轮过后变为$(1, 1 \ | \ 1)$，第四轮一定会结束。因此，期望应该是$3 0.5 + 4 0.5 = 3.5$。
思路 一个判断点位置的问题。
$todo$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> #define int long long #define maxn 1000005 using namespace std ;int inX (int x, int y, int z) if (y * y + z * z <= 1000 * abs (x)) { if (x > 0 ) return 1 ; else return 2 ; } return 0 ; } int inY (int x, int y, int z) if (z * z + x * x <= 1000 * abs (y)) { if (y > 0 ) return 3 ; else return 4 ; } return 0 ; } int inZ (int x, int y, int z) if (y * y + x * x <= 1000 * abs (z)) { if (z > 0 ) return 5 ; else return 6 ; } return 0 ; } void judge (int x, int y, int z) printf ("%lld\n" , inX(x, y, z)); printf ("%lld\n" , inY(x, y, z)); printf ("%lld\n" , inZ(x, y, z)); } int t, x_1, y_1, z_1, x_2, y_2, z_2;signed main (void ) scanf ("%lld" , &t); while (t--) { scanf ("%lld %lld %lld" , &x_1, &y_1, &z_1); scanf ("%lld %lld %lld" , &x_2, &y_2, &z_2); if (inX(x_1, y_1, z_1) == inX(x_2, y_2, z_2) && inY(x_1, y_1, z_1) == inY(x_2, y_2, z_2) && inZ(x_1, y_1, z_1) == inZ(x_2, y_2, z_2)) { printf ("Yes\n" ); } else { printf ("No\n" ); } } }
