2019华工校赛 B - 修仙时在做什么?有没有空?可以来炼丹吗?
2024-09-06 04:33:51
题目链接:https://ac.nowcoder.com/acm/contest/625/B
解法:这题其实就是求2^18个点内最近的两个点的距离。我们可以容易想到朴素解法:把每个点作为源点跑最短路取最小值。也很容易想到这个做法严重超时。
对于这种构图,这里有一个比较套路的方法:枚举2进制位数k,按二进制k位的0/1分成两组跑最短路。为什么是正确的,因为一旦两个数不等,那么这两个数必定在至少一个二进制位上不同,我们枚举了所有的二进制位,那么任意两个数都会被至少一次分到不同组中,亦即所有情况的最短路都考虑到了,那么当然是正确的。
这道题能得到一个启发:像这种对于一个很大很大的图,但是其实只有很少点是我们要计算的,我们可以考虑想出一种分组方式能使得任两个数都至少一次分到不同组,这就能减少时间而且不遗漏。
细节详见代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long P=;
const long long INF=(long long)<<;
typedef long long LL;
const int N=2e5+;
const int M=;
typedef pair<int,int> pii;
int n,ans,a[N],cost[(<<M)+][M],d[(<<M)+],mark[(<<M)+];
bool vis[(<<M)+]; inline LL PowMod(LL a, LL b) { LL r=; while(b) { if(b&) r=r*a%P; a=a*a%P, b>>=; } return r; } void prework() {
for (int s = ; s < (<<); ++s) {
for(int i = ; i < ; ++i) {
cost[s][i] = PowMod( max(s,s^(<<i))%P, <<i ) % P + ;
}
}
} priority_queue<pii> q;
void Dijkstra(int k) {
while (!q.empty()) q.pop();
memset(d,0x3f,sizeof(d));
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++)
if (a[i]>>k & ) { //把n个数字 分成2组 跑最短路
q.push(make_pair(,a[i]));
d[a[i]]=;
}
while (!q.empty()) {
pii x=q.top(); q.pop();
if (mark[x.second] && x.first!=) ans=min(ans,-x.first);
if (-x.first>=ans) return; //当前最短路都比答案大,后面的不用看
if (vis[x.second]) continue;
vis[x.second]=; for (int i=;i<;i++) {
int y=x.second^(<<i);
if (d[y]>d[x.second]+cost[x.second][i]) {
d[y]=d[x.second]+cost[x.second][i];
q.push(make_pair(-d[y],y));
}
}
}
} signed main()
{
prework(); scanf("%lld",&n);
for (int i=;i<=n;i++) scanf("%lld",&a[i]),mark[a[i]]=;
sort(a+,a+n+);
for (int i=;i<=n;i++)
if (a[i]==a[i-]) { puts(""); return ; } ans=INF;
for (int i=;i<;i++) Dijkstra(i);
cout<<ans<<endl;
return ;
}
最新文章
- Linux学习日记-WCF RestFul的部署(三)
- appledoc 使用brew命令安装使用
- jQuery.queue源码分析
- 【poj1091】 跳蚤
- 为什么高手离不了Linux系统?这就是我的理由
- Python基础(6)--条件、循环
- hdu 4901 The Romantic Hero (dp)
- ant 安装过程中问题记录
- 考研路之C语言
- Nginx重要结构request_t解析之http请求的获取
- Machine Learning - Lecture 16
- Angular CLI 安装和使用
- 序列化 反序列化 MessagePack for C#
- 一、Redis-NoSQL数据库
- JS Array.reduce 对象属性累加
- Vue.js——快速入门Vuex
- 表单数据转javabean对象
- 安装yii2 需要token 记录
- SaaS应用十大关键NFR - 第2部分
- oracle中sql优化