10.14 一中模拟高中2
qdl66666666
·
·
个人记录
T1
给定 n,m，表示有 n 个数，每个数可以为 [1,m] 中的数，最大化
注意到这个式子的本质是将两两数字进行匹配，求出异或和。
对每一位进行考虑，也就是算出每一位的贡献。
注意到异或的性质，当一位的异或值是 1 时，一定是 0\oplus1=1，所以每一位的贡献就是一的个数乘零的个数乘当前位置 p 的权值 cnt_{1} \times cnt_{0} \times 2 ^ p。
所以我们将每个数字二进制分解，统计每一位 1 的个数（0的个数可以用 n-cnt_{0} 计算），乘以权值即可，异或和就等于每一位的贡献之和。
这样我们将复杂度从 O(n^2) 降到了 O(n\times\log{V})。
再来看到这道题，答案很显然，逐位考虑。要使和最大我们要让 cnt_{0} 和 cnt_{1} 的差值尽可能小（和为定值，差值越小乘积越大）。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
template<typename TY>
inline void read(TY &s){
ll x = 0,f = 1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
s = x * f;
}
ll n,m;
ll count(ll m){
ll cnt = 0;
while(m){
m/=2;
cnt++;
}
return cnt;
}
int main(){
freopen("testdata.in","r",stdin);
freopen("testdata.out","w",stdout);
int T;
read(T);
while(T--){
read(m); read(n);
if(m == 1){
cout << "0\n";
continue;
}
ll k = count(m);
k = 1ll << k;
k = (k - 1 + MOD) % MOD;
cout << ((n * n) / 4ll) % MOD * k % MOD << "\n";
}
return 0;
}
```
而异或还有许多美妙的性质，像可以进行前缀和运算。
计算区间异或和的和是要用这两种方法相结合，不同的是此时有 $(n+1)$ 个数（前缀）。
[例题](https://www.luogu.com.cn/problem/P9236)
# T2
有 $n$ 台密码机，需要破解 $k$ 台,每台有两个值 $a_{i},b_{i}$。如果破译时间达到 $a_{i}$ 就破译成功，然后可以选择继续破译到 $b_{i}$ 获得一个机械人偶，机械人偶拥有和你一样的效率，你们可以同时破译也可分开破译。特别地，如果一个密码机被破译后没有机械人偶则 $b_{i}=-1$，否则 $b_{i}>=a_{i}$，问破译 $k$ 台密码机的最小时间。
第一步转化：发现人和机械人偶同时破译优于分开破译。
设破译速度为 $x$，破译 $a,b$ 时间的密码机，显然 $\frac{a+b}{2} <= \max(a,b)$，或者说这样操作至少不劣。所以人偶问题我们转化为每多一个人偶，破译的效率增加一倍。
第二步转化：如果我们已经定下来选几个密码机破译到 $a_{i}$，选几个密码机破译到 $b_{i}$，我们一定是先破译所有的 $b$，再破译所有的 $a$，且破译 $b$ 的时候排序去做，因为破译 $b$ 可以看作获得一样多的效率，把更多的效率攒到需要更长时间的时候去用，不能获得效率的 $a$ 自然放在效率攒够后再做最优，问题转化为贪心问题。
策略有了，如何统计答案？
可以枚举破译了几个 $b$（这样可以知道破译 $a$ 时的效率），然后考虑到当 $b_{i} < b_{j}$ 的时候，$b_{i}$ 太长的操作时间可能会影响到后续 $a_{j}$ 的最小破译时间，比如[这样](https://cdn.luogu.com.cn/upload/image_hosting/70z20gdp.png)。所以不是贪心的选最前面的几个 $b$，而是进行 $dp$ 记录前面破译了几个 $a$，几个 $b$，所用的最小时间。
复杂度 $O(n^4)$，考虑优化。
第三步转化：注意到关键信息，如果破译了最后一个 $b$，则前面没有啥都不破译的密码机，因为如果有，交换他们显然会让后面的破译效率更高。
所以我们不用记录前面破译了几个 $a$，当破译好了 $x$ 个 $b$ 后，后面几个 $a$ 的贡献也可以用后缀的前缀和 $O(1)$ 计算，总复杂度 $O(n^3)$。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 510;
template<typename TY>
inline void read(TY &s){
ll x = 0,f = 1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
s = x * f;
}
int n,k;
struct node{
double a,b;
}z[N];
bool cmp1(node a,node b){
return a.a < b.a;
}
bool cmp2(node x,node y){
return x.b < y.b;
}
bool is_A,is_B;
void solve_is_A(){
sort(z+1,z+n+1,cmp1);
double res = 0;
for(int i=1;i<=k;i++){
res += z[i].a;
}
printf("%.10lf",res);
}
double c[N],s[N][N],f[N][N],ans;
void chkmin(double &x,double y){
if(x > y) x = y;
}
int main(){
// freopen("mechanic.in","r",stdin);
// freopen("mechanic.out","w",stdout);
read(n); read(k);
for(int i=1;i<=n;i++){
cin >> z[i].a >> z[i].b;
if(z[i].b != -1) is_A = true;
if(z[i].b != -1 && z[i].b != z[i].a) is_B = true;
}
if(!is_A){
solve_is_A();
return 0;
}
for(int i=1;i<=n;i++){
if(z[i].b == -1) z[i].b = 1e9;
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
c[j] = z[j].a;
}
sort(c+i,c+n+1);
for(int j=i;j<=n;j++){
s[i][j-i+1] = s[i][j-i] + c[j];
}
}
ans = s[1][k];
for(int u=0;u<=k;u++){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j] = 1e18;
}
}
f[0][0] = 0;
for(int i=1;i<=k;i++){
for(int j=0;j<i;j++){
chkmin(f[i][j],f[i-1][j] + z[i].a / (u + 1));
if(z[i].b < 1e9) chkmin(f[i][j+1],f[i-1][j] + z[i].b / (j + 1));
}
chkmin(ans,f[i][u] + s[i+1][k-i] / (u + 1));
// cerr << "dp: " << f[i][u] + s[i+1][k-i]/(u+1) <<"\n";
}
}
printf("%.10lf",ans);
return 0;
}
```