比赛链接
Luke’s Score （贡献计算） 30 pts 暴力枚举以 $i$ 开头，以 $j$ 结尾的区间，并 $O(n)$ 求和，复杂度 $O(n^3)$。
60 pts 预处理出前缀和数组 $sum[i]$，同样还是枚举区间，求和的复杂度降到了 $O(1)$，总的复杂度为 $O(n^2)$
100 pts 考虑每一个数会被多少个区间包括。
例如：$3$ 个数 $[1,2,3]$。包括 $1$ 的区间有 $[1,1], [1,2], [1,3]$，包括 $2$ 的区间有 $[1,2],[1,3],[2,2],[2,3]$ 共四个。
对于每个位置 $i$，包含 $A[i]$ 的区间，左端点可以在 $[1, i]$ 里选，右端点可以在 $[i, n]$ 里选，共有 $i \times (n-i+1)$ 种选法，所以 $A[i]$ 被统计了 $i \times (n-i+1)$ 次。
答案即为
$$
用这个方法计算，时间复杂度为 $O(n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <bits/stdc++.h> #define ll long long using namespace std;ll n, x, ans; int main () scanf ("%lld" , &n); for (ll i = 1 ; i <= n; i++) { scanf ("%lld" , &x); ans += x * i * (n - i + 1 ); ans %= 1000000007 ; } printf ("%lld" , ans); return 0 ; }
Luke’s Game （数论、GCD 的性质、xor 的性质） 30 pts 枚举两个数并判断，$O(n^2\log{n})$
60 pts 根据 $xor$ 的性质，$a \operatorname{xor} b = c$ 等价于 $a \operatorname{xor} c = b$
那么有 $\operatorname{gcd}(a, b) = \operatorname{gcd}(a, a \operatorname{xor} c) = c$
而其中 $c$ 是 $a$ 的约数，因此我们可以枚举 $c$，再枚举 $a = i \times c$，由于 $\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \ldots + \frac{n}{n} = O(n \log n)$，再算上 $\operatorname{gcd}$ 的一只 $\log$，总复杂度 $O(n \log^2 n)$
100 pts 因为 $a = b$ 是肯定无解，所以不妨设 $a > b$。
根据 $\gcd$ 的性质，我们有 $\operatorname{gcd}(a,b) \le a - b$。
根据 $\operatorname{xor}$ 的性质，我们有 $a - b \le a \operatorname{xor} b$
因此 $c = \operatorname{gcd}(a,b) \le a - b \le a \operatorname{xor} b = c$
所以我们可以推出 $c = a - b$
那么我们在 60 pts 的算法基础上，有 $\operatorname{gcd}(a, a - c) = c$，所以我们只需判断 $a \operatorname{xor} c = a - c$即可，复杂度 $O(n \log{n})$
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 #include <bits/stdc++.h> void solve () int n; std::cin >> n; int ans = 0 ; for (int i = 3 ; i <= n; i += 2 ) { int k = n / i; for (int j = 1 ; j <= k; j++) { int t = i * j; if ((t ^ (t - j)) == j) { ans++; } } } std::cout << ans; } signed main () solve (); return 0 ; }
速算大师小 R （数学、高精度） 根据题意，易得需要计算的数为${2^P}-1$向下取整，求$1 + log_{10} ({2^P}-1)$，以及${2^P}-1$的后500位。
对于前$30%$的数据，开$long long$累乘求位数，随后用前导零补齐空缺即可。
前$70%$的数据可以采用高精度计算累乘解决，时间复杂度为$O(n^2)$。
对于最后$30%$的数据：
如果$log_{10} x$是整数，易得$x$的最后一位一定是$0$，$x-1$的最后一位一定是$9$（若$x$不为1）。
由于$log_{10}({2^P}-1)$最后一位不可能为$9$，因此$log_{10}({2^P}-1)$ 向下取整就相当于 $log_{10}({2^P})$ 向下取整。
而$log_{10}({2^P}) = P·log_{10}{2}$。
因此第一行的答案就是
用高精快速幂可以在$O(log_2 P)$的时间复杂度里求出后500位。
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> using namespace std;void out (vector<int > a) a[0 ] -= 1 ; for (int i = 499 ; i >= 0 ; i--) { printf ("%d" , a[i]); if (i % 50 == 0 ) putchar ('\n' ); } return ; } vector<int > muti (vector<int > a, vector<int > b) vector<int > rt; for (int i = 0 ; i < 500 ; i++) rt.push_back (0 ); for (int i = 0 ; i < 500 ; i++) { for (int j = 0 ; j < 500 ; j++) { if (i + j >= 500 ) continue ; rt[i + j] += a[i] * b[j]; } } for (int i = 0 ; i < 500 - 1 ; i++) { rt[i + 1 ] += rt[i] / 10 ; rt[i] %= 10 ; } rt[499 ] %= 10 ; return rt; } vector<int > fpow2 (int p) vector<int > rt; if (p == 0 ) { rt.push_back (1 ); for (int i = 1 ; i < 500 ; i++) rt.push_back (0 ); return rt; } rt = fpow2 (p / 2 ); rt = muti (rt, rt); vector<int > mutiv; mutiv.push_back (2 ); for (int i = 1 ; i < 500 ; i++) mutiv.push_back (0 ); if (p % 2 ) rt = muti (rt, mutiv); return rt; } signed main () int p; scanf ("%d" , &p); cout << int (log10 (2 ) * p + 1 ) << endl; out (fpow2 (p)); return 0 ; }
傻鹿尖塔（反悔贪心） 对于前20分，暴力枚举使用药水的时机即可。
考虑使用反悔贪心，当遇到新的怪物时，尽可能使用药水，如果没有药水可以用，则检查之前用过药水的怪物造成伤害的最小值，若比当前怪物造成的伤害少则改为对当前怪物使用药水，血量减去被反悔的怪物的攻击力。暴力枚举时间复杂度为$O(n^2)$。
使用优先队列维护使用过药水的怪物的攻击力可以将时间复杂度压缩至$O(n log_2 n)$。
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 #include <bits/stdc++.h> using namespace std;void solve () long long n, x, k; scanf ("%lld%lld%lld" , &n, &x, &k); priority_queue<long long , vector<long long >, greater<long long >> pq; int ans = -1 ; for (int i = 1 ; i <= n; i++) { long long in; scanf ("%lld" , &in); if (k) { k--; pq.push (in); } else if (pq.size () && pq.top () < in) { x -= pq.top (); pq.pop (); pq.push (in); } else { x -= in; } if (x <= 0 && ans == -1 ) ans = i - 1 ; } if (ans == -1 ) ans = n; printf ("%d\n" , ans); } int main () int t; scanf ("%d" , &t); while (t--) solve (); return 0 ; }
树联网（树、DFS） 对于前$50%$的数据，可以对每条边两边的点分别进行一次搜索来统计点数，时间复杂度为$O(n^2)$。
随意选一个点作为根，再以这个点出发构造有根树。在进行dfs时，每搜索完一条边，可以通过树的总节点数和子树的节点数快速计算出这条边两边节点个数的差异。时间复杂度为$O(n)$。
1 ans+=abs (n-2 *size[to])*val;
完整代码 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 64 65 #include <bits/stdc++.h> using namespace std;struct edge { int to; long long val; }; int n;long long ans = 0 ;bool used[1000005 ];int siz[1000005 ];vector<edge> begraph[1000005 ]; vector<edge> aftgraph[1000005 ]; void maketree () queue<int > deal; deal.push (1 ); while (deal.size ()) { int indx = deal.front (); used[1 ] = 1 ; deal.pop (); for (int i = 0 ; i < begraph[indx].size (); i++) if (!used[begraph[indx][i].to]) { aftgraph[indx].push_back (begraph[indx][i]); used[begraph[indx][i].to] = 1 ; deal.push (begraph[indx][i].to); } } } int dfs (int lo) if (!aftgraph[lo].size ()) { siz[lo] = 1 ; return siz[lo]; } for (int i = 0 ; i < aftgraph[lo].size (); i++) { siz[lo] += dfs (aftgraph[lo][i].to); ans += abs (n - 2 * siz[aftgraph[lo][i].to]) * aftgraph[lo][i].val; } siz[lo]++; return siz[lo]; } int main () cin >> n; for (int i = 1 ; i <= n - 1 ; i++) { int a, b, c; scanf ("%d%d%d" , &a, &b, &c); edge indx; indx.to = a; indx.val = c; begraph[b].push_back (indx); indx.to = b; begraph[a].push_back (indx); } maketree (); dfs (1 ); cout << ans; return 0 ; }
山路（思维、差分） $20pts$ 枚举最终道路的高度，对于每个高度进行多次遍历，每次遍历统计出不连续的最低和最高段数，将这些高度$+1$/$-1$并计数。
$60pts$ 枚举最终道路的高度，对于每次枚举，统计相对于高度的连续高峰/低谷，每个高度只需一次遍历即可求出答案。
$100pts$ 考虑把初始道路的高度转化成差分数组，操作在差分数组中会变成将$0∼n+1$的任意一位$+1$，另一位$-1$。最终要让第$2∼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 #include <bits/stdc++.h> using namespace std;long long num[10000005 ];long long cf[10000005 ];int main () int n; scanf ("%d" , &n); long long cntz = 0 , cntf = 0 ; for (int i = 1 ; i <= n; i++) { scanf ("%lld" , &num[i]); cf[i] = num[i] - num[i - 1 ]; if (i != 1 ) { if (cf[i] > 0 ) cntz += cf[i]; if (cf[i] < 0 ) cntf -= cf[i]; } } cout << max (cntz, cntf) << endl << abs (cntz - cntf) + 1 ; return 0 ; }