codeforces 1829G. Hits Different 容斥原理+记忆化搜索

题目描述：

给定一个n，把n给打倒，然后递归的求出包含n在内的上面所有的会倒下的瓶子值的平方和。

这里使用二分先求出目前给定的n的行号i和列号j。观察可以发现，对于所有的列号j，j=1或者j=i时，是需要考虑往上单边的总和，其他情况都有两个分支。

再观察可以发现，两个分支在再上一行的重合部分，会被dfs多计算一遍，所以减去这一部分即可。

把计算结果用map保存，减少重复计算。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define int long long
 6 
 7 map<pair<int, int>, int> mp;
 8 
 9 int dfs(int i, int j)
10 {
11     if (mp.count({i, j})) {
12         return mp[{i, j}];
13     }
14     if (j > i || j <= 0) {
15         return mp[{i, j}] = 0;
16     }
17     int s = i * (i - 1) / 2 + j;
18     if (j == 1 || j == i) {
19         return mp[{i, j}] = s * s + dfs(i - 1, j) + dfs(i - 1, j - 1);
20     } else {
21         return mp[{i, j}] = s * s + dfs(i - 1, j) + dfs(i - 1, j - 1) - dfs(i - 2, j - 1);
22     }
23 }
24 
25 void solve()
26 {
27     int n;
28     cin >> n;
29     int l = 1, r = 2023;
30     while (l < r) {
31         int mid = (l + r) >> 1;
32         if ((1 + mid) * mid / 2 >= n) {
33             r = mid;
34         } else {
35             l = mid + 1;
36         }
37     }
38     int curRow = l;
39     int curPos = n - curRow * (curRow - 1) / 2;
40     mp[{1, 1}] = 1;
41     cout << dfs(curRow, curPos) << endl;
42 
43 }
44 
45 int32_t main()
46 {
47     ios_base::sync_with_stdio(false);
48     cin.tie(nullptr); cout.tie(nullptr);
49 
50     int t = 1;
51     cin >> t;
52     while (t--) {
53         solve();
54     }
55 
56     return 0;
57 }