Java教程

题解 打表

本文主要是介绍题解 打表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

今日份题意杀已到帐，请注意查收

还是只会爆搜，枚举当前还没有选的位，当前这一轮的贡献是 \(\frac{minn+maxn}{2}\)
但考虑这样一个事情
如果当前情况下反打表CPU选第 \(i\) 位更优，那不管轮到哪个CPU都一定会选它，只不过填的数相反
而这一轮由每个CPU填数的概率是 \(\frac{1}{2}\)
也就是在说地址的每一位都是随机的
所以最后选中每个位置的概率相等
直接输出 \(\frac{\sum\limits_{i=0}^{2^k-1} |a_i-a_{ans}|}{2^k}\) 即可

Code: 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long 
#define fir first
#define sec second
#define make make_pair
#define reg register int
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int k, ans;
ll rom[1<<18];
const ll p=1e9+7, inv2=500000004;

namespace force{
	struct pair_hash{inline size_t operator () (pair<int, int> p) const {return hash<int>()(p.fir*p.sec);}};
	unordered_map<pair<int, int>, pair<double, ll>, pair_hash> mp{10000, pair_hash()};
	pair<double, ll> dfs(int s, int t) {
		//cout<<"dfs1 "<<s<<' '<<t<<endl;
		if (s==(1<<k)-1) return make(llabs(rom[ans]-rom[t]), llabs(rom[ans]-rom[t])%p);
		if (mp.find(make(s, t))!=mp.end()) return mp[make(s, t)];
		pair<double, ll> t1, t2, mx=make(0, 0), mn=make(1e18, 0);
		for (reg i=0; i<k; ++i) if (!(s&(1<<i))) {
			t1=dfs(s|(1<<i), t), t2=dfs(s|(1<<i), t|(1<<i));
			if (t1.fir>mx.fir) mx=t1;
			if (t1.fir<mn.fir) mn=t1;
			if (t2.fir>mx.fir) mx=t2;
			if (t2.fir<mn.fir) mn=t2;
		}
		pair<double, ll> tem=make(0.5*mx.fir+0.5*mn.fir, (inv2*mx.sec%p+inv2*mn.sec%p)%p);
		mp[make(s, t)]=tem;
		return tem;
	}
}

namespace task1{
	ll qpow(ll a, ll b) {
		ll ans=1;
		while (b) {
			if (b&1) ans=ans*a%p;
			a=a*a%p; b>>=1;
		}
		return ans;
	}
	void solve() {
		ll sum=0;
		for (int i=0; i<(1<<k); ++i) sum=(sum+llabs(rom[i]-rom[ans]))%p;
		sum=sum*qpow(1<<k, p-2)%p;
		printf("%lld\n", sum);
		exit(0);
	}
}

signed main()
{
	k=read(); ans=read();
	for (reg i=0,n=1<<k; i<n; ++i) rom[i]=read();
	//printf("%lld\n", dfs(0, 0).sec);
	task1::solve();
	
	return 0;
}
这篇关于题解 打表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航