ACM / ICPC 2018亚洲区预选赛北京赛站网络赛 3题签到

#include <bits/stdc++.h>
using namespace std;

int dir[4][2]= {{0,1}, {0,-1}, {1,0}, {-1,0} };
int n,m;
int sx,sy,tx,ty;
int mp[105][105];
int book[105][105][6];
struct node {
	int x,y;
	int b;
	int step;
	bool operator < (const node &c)const {
		return step>c.step;
	}
};


int ans=999999;
void bfs(int x,int y,int step) {

	memset(book,0,sizeof(book));

	priority_queue<node> q;

	node tp;
	tp.x=x;
	tp.y=y;
	tp.b=0;
	tp.step = 0 ;
	q.push(tp);
	while(!q.empty()) {
		node tm = q.top();
		q.pop();
		for(int i=0; i<4; i++) {

			node r =tm;
			r.step++;

			r.x += dir[i][0];
			r.y += dir[i][1];

			if(r.x==tx&&r.y==ty) {
				ans=r.step;
				return ;
			}
			if (r.b == 0 && mp[r.x][r.y] == 4)
				continue;

			if(r.x>=0&&r.y>=0&&r.x<n&&r.y<m) {


				if(mp[r.x][r.y]==2) { //B

					if(r.b<5)
						r.b++;

				} else if(mp[r.x][r.y]==3) { //P

					r.step--;

				} else if(mp[r.x][r.y]==4) { //#
					if(r.b>0) {
						r.b--;
						r.step++;

					}
				}

				if(book[r.x][r.y][r.b])
					continue;

				book[r.x][r.y][r.b]=1;
				q.push(r);
			}
		}

	}
}
int main() {
	while(scanf("%d %d",&n,&m)&&(n||m)) {
		char tu[105];
		for(int i=0; i<n; i++) {
			getchar();
			scanf("%s",tu);
			for(int j=0; j<m; j++) {
				if(tu[j]=='S')
					mp[i][j]=1,sx=i,sy=j;
				else if(tu[j]=='B')
					mp[i][j]=2;
				else if(tu[j]=='P')
					mp[i][j]=3;
				else if(tu[j]=='#')
					mp[i][j]=4;
				else if(tu[j]=='T')
					mp[i][j]=5,tx=i,ty=j;
				else if(tu[j]=='.')
					mp[i][j]=6;

			}
		}

		ans=9999999;
		bfs(sx,sy,0);
		if(ans==9999999)
			printf("-1\n");
		else printf("%d\n",ans);

	}
	return 0;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;
typedef long long llong;
const int MAXN = 100 + 10;

int main()
{
	int n, len[20];
	int i, j, k, x, y, m, sl, sgn, maxl;
	char str[20][100], s1[100], s[100], ans[100];
	
	while(scanf("%d", &n) != EOF)
	{
		getchar();
		for(i = 0; i < n; i++)
		{
			gets(str[i]);
			len[i] = strlen(str[i]);
		}
		for(i = 0; i < n; i++)
		{
			strcpy(s, str[i]);
			strcpy(str[i] + len[i], s);
		}
		if(n == 1)
		{
			strcpy(ans, str[0]);
			for(i = 0; i < len[0]; i++)
			{
				memcpy(s1, str[0] + i, len[0] * sizeof(char));
				s1[len[0]] = '\0';
				if(strcmp(ans, s1) > 0)
				{
					strcpy(ans, s1);
				}
			}
			printf("%s\n", ans);
			continue;
		}
		m = 1 << len[0];
		maxl = 0;
		for(int p = 0; p < len[0]; p++)
		{
			memcpy(s1, str[0] + p, len[0] * sizeof(char));
			s1[len[0]] = '\0';
			for(x = 1; x < m; x++)
			{
				k = x;
				for(i = 0, j = 0; k > 0; k = k >> 1, i++)
				{
					if(k & 1)
					{
						s[j] = s1[i];
						j++;
					}
				}
				s[j] = '\0';
				sl = j;
				sgn = 1;
				for(i = 1; i < n; i++)
				{
					int pm = 0;
					for(j = 0; j < len[i]; j++)
					{
						y = 0;
						for(k = j; k - j < len[i]; k++)
						{
							if(s[y] == str[i][k])
							{
								y++;
							}
						}
						if(y > pm)
						{
							pm = y;
						}
					}
					if(pm < sl)
					{
						sgn = 0;
						break;
					}
				}
				if(sgn == 1)
				{
					if(maxl < sl)
					{
						maxl = sl;
						strcpy(ans, s);
					}
					else if(maxl == sl && strcmp(ans, s) > 0)
					{
						strcpy(ans, s);
					}
				}
			}
		}
		if(maxl == 0)
		{
			printf("0\n");
		}
		else
		{
			printf("%s\n", ans);
		}
	}
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll a[1000005],b[1000005],d[1000005];
ll ls[1000005],dex[1000005];
int cnt;
vector<pair<int,ll> > q;
int n;

void solve()
{
	
	memset(ls,-1,sizeof(ls));
	memset(dex,-1,sizeof(dex));	
	 cnt=0;
	for(int i=0;i<n;i++)
	{
		int tp=0;
		int j=i;
		int f=0; 
		while(i<n&&tp+d[i]>=0)
		{
			tp+=d[i];
			i++;
			f=1;
		}
		
		if(f)i--;
		
		if(j==i)ls[cnt]=d[i],dex[cnt++]=j+1;//,q.push_back(make_pair(j+1,d[i]));
		else ls[cnt]=tp,dex[cnt++]=j+1;//,q.push_back(make_pair(j+1,tp));
	}
    //for(vector<pair<int,ll> >::iterator it=q.begin();it!=q.end();it++)
    //cout<<it->first<<" "<<it->second<<"\n";
}
int main()
{
	int t;
	ll c;
	scanf("%d",&t);
	while(t--)
	{
		
		ll suma=0,sumb=0;
		scanf("%d %lld",&n,&c);
		
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&a[i]);
			suma+=a[i];
		}
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&b[i]);
			sumb+=b[i];
			d[i]=a[i]-b[i];
		}
		
		if(suma-sumb+c<0)
		printf("-1\n");
		else
		{
		   solve();
	      int ans = -1;
	      for(int i=0; i<cnt; i++)
	      {
	      	 int st= dex[i];
	      	 int m=c+ls[i];
	      	 int tp=0;
	      	 if(m>=0)
	      	 {
	      	 	tp = m;
	      	 	for(int j=1;j<cnt;j++)
			{
				tp+=ls[(i+j)%(cnt)];
				if(tp<0)break;
			}
			if(tp>=0)
			 {
			 	ans=st;
			 	break;
			 }
		 }
			 
		  }
		  printf("%d\n",ans);
	    }
	}
	return 0;	
}