A. Towers of Boxes
所有盒子都是一样的，我们可以算出一个盒子最多可以承受几个盒子，设为\(c\)，那么一摞最多有\(c+1\)个，那么答案就是\(\lceil \frac{n}{c+1} \rceil\)。
点击查看代码
//凝视深渊的人，深渊也在凝视你。
#include<bits/stdc++.h>using namespace std;int n,m,d;void qy(){cin >> n >> m >> d;int c = d/m+1;cout << (n+c-1)/c << '\n';}signed main(){int _;cin >> _;while(_--) qy();return 0;}
B - Beautiful Numbers
我们设\(y = f(x)\)，那么题目要求达到的条件就是\(f(y) = y\)，也就是\(y\)是一位数，就是\(f(x)\)是一位数。
把每一位拆出来，那么除了第一位只可以让\(f(x)\)减少\(a_1-1\)，其他的位都可以让\(f(x)\)减少\(a_i\)，我们记某一位的贡献为它可以让\(f(x)\)减少的数量。
那么我们贡献从大到小选每一位，知道\(f(x)\)是一位数，这时选了多少位就是最优的了，那么答案就是几。
点击查看代码
//凝视深渊的人，深渊也在凝视你。
#include<bits/stdc++.h>using namespace std;string c;
int a[25];bool cmp(int x,int y){return x > y;
}void qy(){cin >> c;int n = c.length();int ans = 0;for(int i = 1;i <= n;++ i)ans += c[i-1]-'0',a[i] = c[i-1]-'0';a[1]--;sort(a+1,a+1+n,cmp);int o = 1;while(ans > 9){ans -= a[o++];}cout << o-1 << '\n';}signed main(){int _;cin >> _;while(_--) qy();return 0;}
C - Test Generator
本题所有的“位”指的都是二进制位。
可以发现\(a_i\)&\(m=a_i\)这个条件说的就是\(a_i\)只能是在\(m\)为\(1\)的位中选一些加在一起，那么我们把所有\(m\)为\(1\)的哪些位上的数记为\(v_1、v_2、v_3 …… v_{vcnt}\)，也就是说我们只能用这些数去凑\(S\)。
解释一下$v$数组
比如说$m=149=(10010101)_2$，那么$v$数组就是$1、4、16、128$。
那么我们如果考虑\(S\)的每一位最少用几个\(v_i\)凑出来，那么肯定是用比它位要低且位最高的那个最合适，这样我们就可以十分轻易地算出在最优的情况下每一个\(v_i\)要用多少次，记为\(gs_i\)。
接下来呢？接下来我们考虑二分答案，二分一个数组长度，考虑判断这个数组长度能不能把所有的\(gs_i\)个\(v_i\)都放进去。（要注意这里某一个第\(x\)位不是只能放\(2^x\)，也可以放两个\(2^{x-1}\)，也就是两个第\(x-1\)位）
那么这样，我们\(check\)的时候从高位到低位扫一遍，如果某一位的个数大于了数组长度，那么就放不下了，我们就把放不下的那些移到更低的一位，那么这样就保证了每一位的个数都小于数组长度，最终判断第\(0\)位的个数是否小于要求的数组长度即可。（看代码理解一下吧）
点击查看代码
//凝视深渊的人，深渊也在凝视你。
#include<bits/stdc++.h>#define int long longusing namespace std;int s,m;
int v[65],vs[65];
int gs[65];
int vcnt,vscnt;
int bas[61];int get_abcd(int x,int y){if(x > y) swap(x,y);return bas[y-x];
}bool check(int x){int p = gs[vcnt],q = gs[vcnt-1];for(int i = vcnt;i >= 1;i--){if(p <= x){p = gs[i-1];if(i != 1) q = gs[i-2];continue;}int c = p-x;q += c*get_abcd(v[i],v[i-1]);p = q;if(i != 1) q = gs[i-2];}if(p > x) return 0;return 1;
}void xm(){memset(gs,0,sizeof(gs));vcnt = vscnt = -1;cin >> s >> m;int a = 0;while(m){if(m&1) v[++vcnt] = a;m >>= 1;a++;}a = 0;while(s){if(s&1) vs[++vscnt] = a;s >>= 1;a++;}if(v[0] > vs[0]){cout << "-1\n";return;}for(int i = 0;i <= vscnt;++ i){int x = upper_bound(v,v+1+vcnt,vs[i])-v-1;gs[x] += get_abcd(vs[i],v[x]);}int l = 1,r = 0;for(int i = 0;i <= vcnt;++ i)r = max(r,gs[i]);while(l < r){int mid = (l+r)/2;if(check(mid)) r = mid;else l = mid+1;}cout << r << '\n';}signed main(){bas[0] = 1;for(int i = 1;i <= 60;++ i)bas[i] = bas[i-1]*2;int _;cin >> _;while(_--) xm();return 0;}