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("");
		}
	}
}