1 条题解
-
1
前言
大家好我是大常数选手 myee,我的 Dijkstra 开 O2 还跑不过不开 O2 的 SPFA,勇夺最劣解!
我说这不好。
思路
前置知识:同余最短路。
好,我假设你们都知道这大概是什么了。
我们考虑如何建图。
题目保证 递增。
我们不妨取 作为同余长度。(其实任意一个都是可以的)
注意到若 可达,则 可达,其中 可为任意自然数。
于是我们把问题转化成了:
对每个自然数 ,求最小的 满足 使得其可达。
首先 时 显然。
其余的 的 可以通过最短路跑出来。
建图方法具体上就是说,你考虑连边 ,权值为 。
然后跑出来的结果就是 。
询问时比较一下就好了。
Code
#include <algorithm> #include <queue> #include <stdio.h> #include <vector> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;} template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;} template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;} template<typename T>T lowbit(T n){return n&-n;} template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;} template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;} template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;} uint A[5005]; uint Dist[50005]; bol Gone[50005]; int main(){ uint n;scanf("%u",&n); for(uint i=0;i<n;i++)scanf("%u",A+i); for(uint i=1;i<A[n-1];i++)Dist[i]=-1; typedef std::pair<ullt,uint>Pair; std::priority_queue<Pair,std::vector<Pair>,std::greater<Pair> >Q; Q.push(Pair(0,0)); while(!Q.empty()) { uint p=Q.top().second;Q.pop(); if(Gone[p])continue; Gone[p]=true; for(uint i=0;i+1<n;i++)if(_min(Dist[(A[i]+p)%A[n-1]],A[i]+Dist[p]))Q.push(Pair(Dist[(A[i]+p)%A[n-1]],(A[i]+p)%A[n-1])); } uint k,v; scanf("%u",&k); while(k--) { scanf("%u",&v); puts(v<Dist[v%A[n-1]]?"NIE":"TAK"); } return 0; }
- 1
信息
- ID
- 2612
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 9
- 已通过
- 3
- 上传者