比赛链接 / 官方题解链接
A. Dreamoon and Ranking Collection Solution 挨个枚举，有空就填，直到走不动且用光填补次数为止。
Code >folded 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 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;const int N = 1005 ;int T, n, x, a[N];bool b[N];int main () read (T); while (T--){ memset (b, 0 , sizeof b); read (n, x); for (int i = 1 ; i <= n; i++){ read (a[i]); b[a[i]] = 1 ; } int ans = 0 ; while (x){ while (b[ans+1 ]) ans++; x--; ans++; } while (b[ans+1 ]) ans++; printf ("%d\n" , ans); } return 0 ; }
B. Dreamoon Likes Permutations Solution 分别从前往后和从后往前遍历，不断统计累和。以从前往后为例，如果前 $i$ 个点没有重复数字且累和为 $\frac{i(i+1)}{2}$，则这 $i$ 个数必是 $1\sim i$ 的一个排列，在 $i$ 处打上标记；从后往前同理。如果连续两个点，前者有从前往后的标记，后者有从后往前的标记，则是一个解。
Code >folded 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 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const int N = 200005 ;int T, n, a[N];bool p[N], q[N], e[N];int main () read (T); while (T--){ read (n); for (int i = 1 ; i <= n; i++) p[i] = q[i] = e[i] = 0 ; LL sum = 0 ; for (int i = 1 ; i <= n; i++) read (a[i]); bool rep = false ; for (int i = 1 ; i <= n; i++){ sum += a[i]; if (e[a[i]]) rep = true ; e[a[i]] = true ; if (!rep && sum == 1ll * i * (i + 1 ) / 2 ) p[i] = true ; } rep = false ; sum = 0 ; for (int i = 1 ; i <= n; i++) e[i] = 0 ; for (int i = n; i >= 1 ; i--){ sum += a[i]; if (e[a[i]]) rep = true ; e[a[i]] = true ; if (!rep && sum == 1ll * (n - i + 1 ) * (n - i + 2 ) / 2 ) q[i] = true ; } vector<pii> ans; for (int i = 1 ; i < n; i++) if (p[i] && q[i+1 ]) ans.pb (mp (i, n-i)); printf ("%d\n" , (int )ans.size ()); for (auto k: ans) printf ("%d %d\n" , k.first, k.second); } return 0 ; }
C. Dreamoon Likes Coloring Solution 我们可以先排除一些无解的情况：
如果所有区间长度之和小于 $n$，那肯定涂不完；
如果第 $i$ 个区间的长度大于 $n-i+1$，那么它一定会覆盖掉前 $i-1$ 个颜色中的某些颜色使颜色不全。
然后我们可以构造一种涂色方法：对于 $1\leq i\leq m$，把第 $i$ 个区间的起始点放在 $i$ 处。如此放完后第 $m$ 个区间到 $n$ 之间可能会有空隙，我们倒序依次往后移动区间把空隙填满即可。
Code >folded 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 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const int N = 100005 ;int n, m, a[N];LL sum[N], mx[N], pos[N]; int main () read (n, m); for (int i = 1 ; i <= m; i++){ read (a[i]); sum[i] = a[i]; } for (int i = m; i >= 1 ; i--) sum[i] += sum[i+1 ]; if (sum[1 ] < n) return puts ("-1" ), 0 ; for (int i = 1 ; i <= m; i++) if (i + a[i] - 1 > n) return puts ("-1" ), 0 ; for (int i = 1 ; i <= m; i++){ mx[i] = max (mx[i-1 ], 1ll * i + a[i] - 1 ); pos[i] = i; } int boun = n, now = m; while (now && mx[now] < boun){ pos[now] += boun - (pos[now] + a[now] - 1 ); boun = pos[now] - 1 ; now--; } if (pos[1 ] > 1 ) return puts ("-1" ); for (int i = 1 ; i <= m; i++) printf ("%lld " , pos[i]); return 0 ; }
D. Dreamoon Likes Sequences Solution 假设 $a_i$ 的最高位 $1$ 是第 $k$ 位，我们有结论：$a_1,a_2,\cdots,a_{i-1}$ 的最高位 $1$ 的位置一定小于 $k$，且 $a_{i+1},a_{i+2},\cdots,a_n$ 的最高位 $1$ 的位置一定大于 $k$.
证明：由于 $a$ 递增，所以 $a_1,a_2,\cdots,a_{i-1}$ 的最高位 $1$ 的位置最高等于 $k$，设 $a_j,a_r(jb_r$，不符合题意，所以 $a_i$ 是第一个最高位 $1$ 在 $k$ 的数，也就是 $a_1,a_2,\cdots,a_{i-1}$ 的最高位 $1$ 的位置一定小于 $k$；类似的容易知道 $a_{i+1},a_{i+2},\cdots,a_n$ 的最高位 $1$ 的位置一定大于 $k$.
换句话说，假设 $x$ 的第 $k$ 位为 $1$（ $2^k\leq x\leq 2^{k+1}-1$ ），在这个范围 $[2^k,2^{k+1}-1]$ 内的数只能不选或者选一个，一共 $1+2^k$ 种选法。
设 $lg=\lfloor\log_2d\rfloor$，则对于 $0\leq k<lg$，每个 $k$ 有 $1+2^k$ 种选法；对于 $k=lg$，有 $d-2^{lg}+2$ 种选法。所以答案就是 $\prod\limits_{k=0}^{lg-1}(1+2^k)\cdot(d-2^{lg}+2)-1$，减 $1$ 是因为全都不选（ $n=0$ ）的情况要删去。
Code >folded 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> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;int T;LL d, m; int main () read (T); while (T--){ read (d, m); LL lg = (int )log2 (d); LL ans = 1 , p = 1 ; for (LL i = 1 ; i <= lg; i++, p <<= 1 ){ (ans *= (1 + p)) %= m; } (ans *= (1 + d - p + 1 )) %= m; ans--; ((ans %= m) += m) %= m; printf ("%lld\n" , ans); } return 0 ; }
E. Drazil Liks Heap Solution 贪心策略比较显然：能够选根节点则选择根节点，否则递归选择其左右子节点。所谓能够选的意思是，如果选了之后存在高度小于 $g$ 的点，则不能选。采用递归的方式写较为简便。
Code >folded 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 66 67 68 69 70 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;const int N = 3000005 ;int T, h, g;LL a[N]; vector<int > ans; #define lid id<<1 #define rid id<<1|1 int dis (int id) if (a[lid] == 0 && a[rid] == 0 ) return 1 ; if (a[lid] > a[rid]) return dis (lid) + 1 ; else return dis (rid) + 1 ; } void f (int id) if (a[lid] == 0 && a[rid] == 0 ){ a[id] = 0 ; return ; } if (a[lid] > a[rid]){ a[id] = a[lid]; f (lid); } else { a[id] = a[rid]; f (rid); } } void solve (int id, int dep) if (a[id] == 0 ) return ; while (dis (id) + dep - 1 > g){ ans.emplace_back (id); f (id); } solve (lid, dep + 1 ); solve (rid, dep + 1 ); } int main () read (T); while (T--){ read (h, g); LL sum = 0 ; ans.clear (); for (int i = 1 ; i <= (1 << (h+1 )); i++) a[i] = 0 ; for (int i = 1 ; i < (1 << h); i++) read (a[i]); solve (1 , 1 ); for (int i = 1 ; i < (1 << g); i++) sum += a[i]; printf ("%lld\n" , sum); for (auto k: ans) printf ("%d " , k); puts ("" ); } return 0 ; }