20联赛集训day13 题解
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
这场ABC都是Div2 ABC种偏难的。。但是后面难度就上不去了（可能是我只会做一点点套路题的原因？）A这里的反转是 reverse，不是取反。。自闭了。。设这两个数是 $a,b$，其中 $a > b$，由于字典序最小，所以我们从低位向高位看，要求尽量是 $0$。我们找到 $b$ 的 $\text{lowbit}$ $p$，发现比 $p$ 低的位都是无法改变的（由 $a$ 决定），我...
A做法一：答案一定是相邻两个的差的最小值。考虑反证法：如果 $[l,r](l+1 < r)$ 是答案，那么中间一定能取到一段小于等于平均数的。做法二：二分答案。首先答案是 $\min_{i,j} \frac{a_i-a_j}{j-i}$，考虑二分最小值，那么相当于对于所有 $j>i$ 要有 $a_i-a_j \geq kj-ki$，也就是 $a_i+k_i \geq a_j+k_...
A设点 $i$ 有 $a_i$ 个糖果。对于每个起点 $s$ ，只需要能计算出对于每个点 $t$，完成所有任务所需要的最短时间，取 max 即可。而计算这个时间相当于是先转几圈，然后找一个距离它最近的当做最后一次的任务。可以加强到 $10^5$，观察一下 $s \to s+1$ 的变化即可。B这个程序相当于每次取这个点最前面的保证和是非负的一段区间。所以想让它掉进坑一定是前面一堆 $0$，然...
题目链接题目大意$n \times m$ 的网格图 这个网格图中不能往上走 要求支持如下操作：修改网格图上的一条边询问从第一行某个点到最后一行某个点的最短路径$n \leq 5000,m \leq 200,q \leq 2\times 10^5$ 修改次数 $d \leq 500$。题解看到这个行+单点修改可以考虑维护一个线段树：令 $A_{i,j}$ 表示当前块内上面第 $i$ 个点到下...