如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
Made In Heaven
Astar 求 K 短路。
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
typedef int ll;
const ll INF=1e9;
struct Graph
{
struct Vertex
{
vector<int> a,b;//相关出边和入边编号
//int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int from,to;
ll dist/*,cap*/;//边长、容量，图论算法使用
};
vector<Vertex> v;//点集
vector<Edge> e;//边集
Graph(int n):v(n) {}
void add(const Edge &ed)
{
//if(ed.from==ed.to)return;//如果有需要请拆点
v[ed.from].a.push_back(e.size());
v[ed.to].b.push_back(e.size());
e.push_back(ed);
}
};
struct Dijkstra:Graph
{
vector<ll> d;
Dijkstra(int n):Graph(n) {}
void ask(int s)
{
d.assign(v.size(),INF);
priority_queue<pair<ll,int> > q;
for(q.push(make_pair(d[s]=0,s)); !q.empty();)
{
ll dis=-q.top().first;
int u=q.top().second;
if(q.pop(),d[u]<dis)continue;
for(int i=0,k,to; i!=v[u].a.size(); ++i)
if(k=v[u].a[i],to=e[k].to,
d[to]>d[u]+e[k].dist)
{
d[to]=d[u]+e[k].dist;
q.push(make_pair(-d[to],to));
}
}
}
};
struct Astar:Dijkstra
{
vector<ll> ans;
Astar(int n):Dijkstra(n) {}
void ask(int s,int t,int k,int T)
{
Dijkstra::ask(s);
ans.assign(k,INF);
if(d[t]==INF)return;
vector<int> cnt(v.size(),0);
priority_queue<pair<ll,int> > q;
for(q.push(make_pair(-d[t],t)); cnt[s]<k&&!q.empty();)
{
ll dis=-q.top().first;
int u=q.top().second;
if(u==s)ans[cnt[s]]=dis;
if(dis>T)return;
if(q.pop(),++cnt[u]>k)continue;
for(int i=0,k; i<v[u].b.size(); ++i)
k=v[u].b[i],q.push(make_pair(d[u]-d[e[k].from]-e[k].dist-dis,e[k].from));
}
}
};
int main()
{
for(int n,m,s,e,k,t; ~scanf("%d%d%d%d%d%d",&n,&m,&s,&e,&k,&t);)
{
Astar g(n+1);
for(int u,v,w; m--;)
{
scanf("%d%d%d",&u,&v,&w);
g.add({u,v,w});
}
g.ask(s,e,k,t);
printf(g.ans[k-1]>t?"Whitesnake!\n":"yareyaredawa\n");
}
}
Fantastic Graph
转换一下变成一个有源汇上下界网络流模型。
#include<cstdio>
#include<vector>
using namespace std;
typedef int ll;
const ll INF=1e9;
struct Graph
{
struct Vertex
{
vector<int> a/*,b*/;//相关出边和入边编号
//int siz,dep,top,dfn;//树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge
{
int from,to;
ll /*dist,*/cap;//边长、容量，图论算法使用
};
vector<Vertex> v;//点集
vector<Edge> e;//边集
Graph(int n):v(n) {}
void add(const Edge &ed)
{
//if(ed.from==ed.to)return;//如果有需要请拆点
v[ed.from].a.push_back(e.size());
//v[ed.to].b.push_back(e.size());
e.push_back(ed);
}
};
struct ISAP:Graph
{
ll flow;
vector<ll> f;
vector<int> h,cur,gap;
ISAP(int n):Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.from,ed.to),ed.cap=0;
Graph::add(ed);
}
ll dfs(int s,int u,int t,ll r)
{
if(r==0||u==t)return r;
ll _f,_r=0;
for(int &i=cur[u],k; i<v[u].a.size(); ++i)
if(k=v[u].a[i],h[u]==h[e[k].to]+1)
{
_f=dfs(s,e[k].to,t,min(r-_r,e[k].cap-f[k]));
f[k]+=_f,f[k^1]-=_f,_r+=_f;
if(_r==r||h[s]>=v.size())return _r;
}
if(!--gap[h[u]])h[s]=v.size();
return ++gap[++h[u]],cur[u]=0,_r;
}
void ask(int s,int t)
{
h.assign(v.size(),0);
cur.assign(v.size(),0);
gap.assign(v.size()+2,0);
/*for(deque<int> q(h[t]=gap[t]=1,t); !q.empty(); q.pop_front())//可选预处理
for(int i=0,u=q.front(),k,to; i<v[u].a.size(); ++i)
if(to=e[v[u].a[i]].to,!h[to])
++gap[h[to]=h[u]+1],q.push_back(to);*/
for(f.assign(e.size(),flow=0); h[s]<v.size();)
flow+=dfs(s,s,t,INF);
}
};
int main()
{
for(int n,m,k,l,r,kase=0; ~scanf("%d%d%d",&n,&m,&k);)
{
ISAP g((n+m)*2+9);
scanf("%d%d",&l,&r);
for(int i=0,u,v; i<k; ++i)
{
scanf("%d%d",&u,&v);
v+=n;
g.add({2*u+1,2*v,1});
}
int s=2*(n+m+1),t=s+1,ss=t+1,tt=ss+1;
g.add({t,s,INF});
for(int i=1; i<=n; ++i)
g.add({s,2*i,INF});
for(int i=n+1; i<=n+m; ++i)
g.add({2*i+1,t,INF});
for(int i=1; i<=n+m; ++i)
{
g.add({2*i,2*i+1,r-l});
g.add({ss,2*i+1,l});
g.add({2*i,tt,l});
}
g.ask(ss,tt);
printf("Case %d: %s\n",++kase,g.flow==(n+m)*l?"Yes":"No");
}
}
Spare Tire
#include<cstdio>
#include<vector>
#define mul(a,b,m) ((a)*(b)%(m))
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll n,m,ans1,ans2,INV[9];
vector<ll> fac;
void getfac(ll n)
{
fac.clear();
for(ll i=2; i*i<=n; ++i)
if(n%i==0)
for(fac.push_back(i); n%i==0;)n/=i;
if(n>1)fac.push_back(n);
}
ll pow(ll a,ll b,ll m)
{
ll r=1;
for(a%=m; b; b>>=1,a=mul(a,a,m))
if(b&1)r=mul(r,a,m);
return r;
}
void dfs(ll cur,ll num,ll val)
{
if(cur==fac.size())
{
if(val!=1)
{
ll t=n/val,k=mul(mul(t*(t+1)/2%M,num%2?M-1:1,M),val,M);
if(ans1+=k,ans1>=M)ans1-=M;
if(ans2+=mul(mul(mul(k,(t*2+1),M),INV[3],M),val,M),ans2>=M)ans2-=M;
}
return;
}
dfs(cur+1,num,val),dfs(cur+1,num+1,val*fac[cur]);
}
int main()
{
for(ll i=0; i<9; ++i)INV[i]=pow(i,M-2,M);
while(~scanf("%lld%lld",&n,&m))
{
ans1=n*(n+1)/2%M;
ans2=ans1*(2*n+1)%M*INV[3]%M;
getfac(m);
dfs(0,0,1);
printf("%lld\n",(ans1+ans2)%M);
}
}
Lattice’s basics in digital electronics
做了一遍就不想再做一遍的沙雕大模拟…为了模拟而模拟。字典树跑掉。
#include<cstdio>
using namespace std;
const int NPOS=-1,N=200009<<2;
struct AhoCorasick
{
struct Node
{
int ch[2],val;
int &to(char c)
{
return ch[c-'0'];
}
Node():val(NPOS)
{
ch[0]=ch[1]=0;
}
} v[N];
int siz;
AhoCorasick():siz(1) {}
void add(char s[],int val)
{
int u=0;
for(int i=0; s[i]; u=v[u].to(s[i++]))
if(!v[u].to(s[i]))
{
v[u].to(s[i])=siz;
v[siz++]=Node();
}
v[u].val=val;
}
};
char stak[N],data[N];
int t,kase=0,m,n;
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%d%d",&m,&n);
AhoCorasick ac;
for(int i=0,c; i<n; ++i)
{
scanf("%d%s",&c,data);
ac.add(data,c);
}
scanf("%s",stak);
int len=0,siz=0;
for(int i=0; stak[i]; ++i)
{
stak[i]='0'<=stak[i]&&stak[i]<='9'?stak[i]-'0':
'a'<=stak[i]&&stak[i]<='z'?stak[i]-'a'+10:
stak[i]-'A'+10;
len+=4;
for(int j=1; j<=4; ++j)data[len-j]='0'+stak[i]%2,stak[i]/=2;
}
for(int i=0,cnt; i+8<len; i+=9)
{
for(int j=cnt=0; j<8; ++j)if(data[i+j]=='1')++cnt;
if(cnt%2!=(data[i+8]=='0'?1:0))continue;
for(int j=0; j<8; ++j)stak[siz++]=data[i+j];
}
for(int i=0,u=0,cnt=0; i<siz; ++i)
if(ac.v[u=ac.v[u].to(stak[i])].val!=NPOS)
{
printf("%c",ac.v[u].val);
u=0;
if(++cnt==m)break;
}
printf("\n");
}
}
Supreme Number
#include<stdio.h>
#include<string.h>
char s[127];
int t,n,kase,a[]=
{
1,2,3,5,7,
11,13,17,23,31,
37,53,71,73,113,
131,137,173,311,317
};
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%s",s);
if(strlen(s)>3)n=318;
else sscanf(s,"%d",&n);
for(int i=19; ~i; --i)
if(a[i]<=n)
{
printf("Case #%d: %d\n",++kase,a[i]);
break;
}
}
}