CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Saving Tang Monk II
按气罐数量分层建图跑最短路。
#include<bits/stdc++.h>
#define POS(i,j,k) ((k)*(n)*(m)+(i)*(m)+(j))
using namespace std;
typedef int ll;
const int INF=1e9;
struct Graph
{
struct Vertex
{
vector<int> a;
};
struct Edge
{
int from,to;
ll dist;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n):v(n) {}
void add(const Edge &ed)
{
v[ed.from].a.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));
}
}
}
};
char s[127][127];
int main()
{
for(int n,m,sx,sy,tx,ty; ~scanf("%d%d",&n,&m)&&n&&m;)
{
for(int i=0; i<n; ++i)scanf("%s",s[i]);
Dijkstra g(POS(n-1,m-1,5)+1);
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
{
for(int k=0,tk,dist=s[i][j]=='#'?2:s[i][j]!='P'; k<6; ++k)
if(tk=s[i][j]=='#'?k-1:s[i][j]=='B'?k+1:k,0<=tk&&tk<=5)
{
if(i)g.add({POS(i,j,k),POS(i-1,j,tk),dist});
if(j)g.add({POS(i,j,k),POS(i,j-1,tk),dist});
if(i+1<n)g.add({POS(i,j,k),POS(i+1,j,tk),dist});
if(j+1<m)g.add({POS(i,j,k),POS(i,j+1,tk),dist});
}
if(s[i][j]=='S')sx=i,sy=j;
if(s[i][j]=='T')tx=i,ty=j;
}
g.ask(POS(sx,sy,0));
ll ans=INF;
for(int k=0; k<6; ++k)
ans=min(ans,g.d[POS(tx,ty,k)]);
printf("%d\n",ans<INF?ans:-1);
}
}
Tomb Raider
#include<bits/stdc++.h>
using namespace std;
int n;
string s[15],lcs,ans;
bool check(string s)
{
for (int i=0; i<s.size(); ++i)
{
int h=i,j=0;
for (; h!=(i+s.size()-1)%s.size(); h=(h+1)%s.size())
{
if (s[h]==lcs[j]) ++j;
if (j==lcs.size()) return true;
}
if (j!=lcs.size() && s[h]==lcs[j]) ++j;
if (j==lcs.size()) return true;
}
return false;
}
void rep(string &s)
{
string st,ret=s;
for (int i=0; i<s.size(); ++i)
{
st=s.substr(i)+s.substr(0,i);
if (st<ret) ret=st;
}
s=ret;
}
int main()
{
while (cin >> n)
{
ans="";
for (int i=1; i<=n; ++i) cin >> s[i];
int l=s[1].size();
for (int i=1; i<(1<<l); ++i)
{
bool ok=true;
lcs="";
for (int j=0; j<l; ++j) if (i&(1<<j)) lcs+=s[1][j];
for (int i=2; i<=n; ++i)
{
if (!check(s[i]))
{
ok=false;
break;
}
}
if (!ok) continue;
rep(lcs);
if (lcs.size()>ans.size() || lcs.size()==ans.size() && lcs<ans) ans=lcs;
}
if (ans=="") cout << "0\n";
else cout << ans << endl;
}
}
80 Days
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000000+10;
int t,n,c,cnt,head;
long long a[maxn*2],b[maxn*2];
long long sum;
inline int read()
{
char c=getchar();
while (((c<'0')||(c>'9'))&&(c!='-')) c=getchar();
int x,t;
if (c=='-') t=-1,x=0;
else x=c-'0',t=1;
while (((c=getchar())>='0')&&(c<='9')) x=x*10+c-'0';
return x*t;
}
int main()
{
t=read();
while (t--)
{
n=read();
c=read();
sum=c;
for (int i=1; i<=n; i++) a[i+n]=a[i]=read(),sum+=a[i];
for (int i=1; i<=n; i++) b[i+n]=b[i]=read(),sum-=b[i];
if (sum<0)
{
printf("-1\n");
continue;
}
cnt=1;
head=1;
sum=c+a[1]-b[1];
while (cnt<n)
{
while (sum<0) sum=sum-a[head]+b[head],head++,cnt--;
sum+=a[head+cnt]-b[head+cnt];
cnt++;
}
printf("%d\n",head);
}
return 0;
}
K-Dimensional Foil II
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct P
{
int x,id;
double ans;
bool minus;
}a[200];
bool cmpx(const P& a,const P& b)
{
return a.x>b.x;
}
bool cmpid(const P& a,const P& b)
{
return a.id<b.id;
}
int T,n,k,r;
int c[200];
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&k);
scanf("%d",&r);
for (int i=1;i<=k;++i) scanf("%d",&c[i]);
for (int i=1;i<=n;++i)
{
memset(a,0,sizeof(a));
for (int j=1;j<=k;++j) {scanf("%d",&a[j].x);a[j].id=j;}
for (int j=1;j<=k;++j)
{
a[j].x=a[j].x-c[j];
if(a[j].x<0) {a[j].x=-a[j].x;a[j].minus=true;}
}
sort(a+1,a+k+1,cmpx);
int res=r;
for (int j=1;j<=k;++j)
{
if ((a[j].x-a[j+1].x)*j<=res)
{
res-=(a[j].x-a[j+1].x)*j;
}
else
{
for (int r=1;r<j;++r) a[r].ans=a[r].x-a[j].x;
for (int r=1;r<=j;++r) a[r].ans+=double(res)/j;
break;
}
}
sort(a+1,a+k+1,cmpid);
for (int j=1;j<=k;++j)
if (a[j].minus) printf("%.5lf ",-a[j].ans+c[j]);
else printf("%.5lf ",a[j].ans+c[j]);
puts("");
}
}
}