模考集训DAY4.py
题解
T1(数字存储)：
这道题很简单，就是需要了解一些数学常识，首先，二进制里的位数表示的数是几何形暴增的， 也就是说2进制的第一位表示2的0次方，第二位表示二进制的一次方，第三位表示二进制的二次方……
那么，事实上一个数在二进制中，以二为底的这个数二进制中的位数-1次方正好等于这个数，我们要是用数学表达式来写的话就是：
\log2{n}+1 = ans
在这里，n代表这个数，ans代表这个数的二进制位，所以代码思路也就很好想了，就是求1~n所有数的log之和。
代码也很简单
部分代码：
for(ll i=1;i<=n;i++){
dp[i]=dp[i-1]+log2(i)+1;
}
PS：这里我为了 装逼 让别人觉得我是个英俊潇洒风趣幽默器宇不凡人见人爱花见花开车见车爆胎的帅气男神所以用了一个非常简单的线性dp，其实也可以直接求和。
T2(异或最大值)：
这道题比较难想到，但是想到思路后也很容易AC，这道题看起来就像搜索，而且他给了一个限制条件，那就是：
\text{保证二项式系数 }\binom{N}{K}\leq10^6\text{。}
这样我们就可以直接暴力搜索就也不会超时，但是有的时候不一定，比如说 \binom{20000}{19999} 这个式子的答案其实是20000，可是我们的计算机会枚举 2^{20000} 次，这个数直接爆long long了，所以这里我们要引用一个超级niub的数学公式，那就是！！！：
\binom{n}{k} = \binom{n}{n-k}
这样就可以让 \binom{20000}{19999} 变成 \binom{20000}{1}
瞬间清爽有木有，那思路也就出来了，所以……
部分代码：
for(ll i=1;i<=n;i++){
cin >> a[i];
all^=a[i];
}
sort(a+1, a+n+1, cmp);
if(n-k<k){
k=n-k;
dfs1(1, all, 0);
}
else{
dfs1(1, 0, 0);
}
T3(小信爬树):
这道题很难，但是所有在 @2024秋季智灵基础 的人要说了，这道题多简单啊！不就拓扑排序吗？确实，这道题就是拓扑排序，在拓扑排序的同时对其进行处理，这样能保证每次调整不会影响到前面处理过的节点。
对每一个节点来说，要做以下处理：
- 若当前节点的数字小于左边界，将其父节点加上当前节点的右边界，并将操作次数+1。
- 若当前节点的数字大于等于右边界，将其父节点加上当前节点的右边界，但不对操作次数进行处理。
- 若是其他情况，便将当前节点的父节点加上当前节点的数字。
以上结论是在一堆老师我精准精确精妙的数学推理中产生的，所以，请不要怀疑这些结论，怀疑这些结论就是在怀疑老师我！！我问你，你敢怀疑老师我吗，你敢吗！！LOOKING MY EYES!!!
部分代码：
while(!q.empty()){
ll now=q.front();
q.pop();
if(a[now]<l[now]){
ans++;
a[p[now]]+=r[now];
}
else if(a[now]>=r[now]){
a[p[now]]+=r[now];
}
else{
a[p[now]]+=a[now];
}
d[p[now]]--;
if(d[p[now]]==0){
q.push(p[now]);
}
}
T4(小信的最大最小值)：
这道题更难，但是所有在 @2024秋季智灵基础 的人要说了，这道题多简单啊！不就二分模拟吗？对的没错，这道题是用了一个二分加二重循环，如果纯暴力的解法的话时间复杂度是 O(n^k)，也就是 3000^{3000}，你猜这个数有多大？？
Overflow
相当于无限了，所以我们需要尝试枚举别的东西，比如枚举最大值或最小值，最小值的范围是 \frac{a_1}{k}\leq i \leq a_1 ，最大值的范围是 \frac{a_n}{k}\leq i \leq a_n，二者选其一就行，这里以最小值作为例子。
枚举完最小值后，我们需要验证这个最小值是否正确，同时求出最大值，我们用二分求出所有的 p_i，然后打擂台确定最大值和最小值，在最后验证最小值是否正确，然后打擂台求出所有可能答案中的最小代价就可以了：
部分代码：
for(ll a1=a[1]/k;a1<=a[1];a1++){
ll maxn=-1, minn=1e10;
for(ll i=1;i<=n;i++){
ll l=0, r=k+1;
while(l+1<r){
ll m=l+r>>1;
if(a[i]/m>=a1){
l=m;
}
else r=m;
}
maxn=max(maxn, a[i]/l);
minn=min(minn, a[i]/l);
}
// cout <<"_"<< a1<<" "<<ans-a1 << endl;
if(minn==a1) vans=min(maxn-minn, vans);
}
做题情况
T1：这道题很简单，15分钟AC，不留遗憾。
AC 100pt
T2：最开始想到折半搜索，但是发现时间复杂度不够，又去想别的可能，然后突然老师解释了一句话，就是：
\binom{x}{y} = C_x^y 这瞬间让我茅厕茅塞顿开，既然这样，那暴力搜索也肯定不会超时，于是我就放心的写了一个折半搜索，样例过了就直接提交，不拖泥带水。\Huge BUT 我忘了个事，那就是 C_x^y = C_x^{x-y} ，因为这样导致 C_{20000}^{19999} 的结果依然是小于等于 10^6 的， 但是我的程序会枚举 20000^{19999} 次！！！，这就直接爆炸了，所以这一点没考虑到，导致我TLE了
TLE 0pt
T3：这道题很难，但是架不住我做过呀！！，根据我的模糊 清晰的记忆，我记得和最值有关，但是我却忘了遍历方式，于是根据我的记忆，加上我的现场推理，我搞了一个树形dp+窜天猴的思路，样例也是直接过了，我同桌羡慕的不得了，但是我忘了一个事，那就是时间复杂度！！要是是dfs的话直接爆炸，所以还是TLE了
TLE 20pt
T4：这道题我也做过！！但是就是想不起来咋做的，反正琢磨了半天不如打一个简单的暴力，也是成功骗到10分
TLE 10pt
总结
预期得分：310pt
实际得分：130pt
ber，这差距有点高啊！！我实在是太菜了，要是第二题肯在思考思考，第三题在琢磨琢磨，这不就都A了吗！！，ε=(´ο｀*)))唉，也就只能祝我最后一次模考
\Huge AK!!!!