题解 打表
2021/8/23 6:58:32
本文主要是介绍题解 打表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
今日份题意杀已到帐,请注意查收
还是只会爆搜,枚举当前还没有选的位,当前这一轮的贡献是 \(\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; }
这篇关于题解 打表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现