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}

的差值尽可能小（和为定值，差值越小乘积越大）。

cnt_{0}

取

\lfloor\frac{n}{2}\rfloor

时差值最小。而每一位都可以达到最大值，令

\lfloor\frac{n}{2}\rfloor

的数最高位是

1

，其余为是

0

，另一半数最高位是

0

，其余位是

1

，此时的答案为

\lfloor\frac{n}{2}\rfloor\times (n-\lfloor\frac{n}{2}\rfloor)\times(2^{p+1}-1) = \lfloor\frac{n^2}{4}\rfloor\times(2^{p+1}-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)

个数（前缀）。例题

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}

的最小破译时间，比如这样。所以不是贪心的选最前面的几个

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;
}

10.14 一中模拟高中2

文章操作

T1

T2

相关推荐

评论

10.14 一中模拟高中2