XVIII Open Cup named after E.V. Pankratiev. GP of Urals

A. Nutella’s Life

斜率優化DP顯然，CDQ分治后按$a$排序建線段樹，每層維護凸包，查詢時不斷將隊首彈出即可。

時間復雜度$O(n\log^2n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int N=100010,M=262150;
int n,i,a[N],cb;ll f[N],g[N],w[N],ans;
int st[M],en[M],tot,q[4000000];
int H;
P b[N];
inline void up(ll&a,ll b){a<b?(a=b):0;}
inline double pos(int x,int y){return 1.0*(g[x]-g[y])/(y-x);}
inline void push(int x){
	while(H<tot&&pos(q[tot-1],q[tot])>pos(q[tot],x))tot--;
	q[++tot]=x;
}
void build(int x,int l,int r){
	if(l==r){
		st[x]=en[x]=++tot;
		q[tot]=b[l].second;
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	int i=st[x<<1],j=st[x<<1|1];
	H=st[x]=tot+1;
	while(i<=en[x<<1]&&j<=en[x<<1|1]){
		if(q[i]<q[j]){
			push(q[i++]);
		}else{
			push(q[j++]);
		}
	}
	while(i<=en[x<<1])push(q[i++]);
	while(j<=en[x<<1|1])push(q[j++]);
	en[x]=tot;
}
inline ll cal(int x,int y){return g[y]+2LL*x*y;}
void ask(int x,int a,int b,int d,int p){
	if(b<=d){
		while(st[x]<en[x]&&cal(p,q[st[x]])<cal(p,q[st[x]+1]))st[x]++;
		if(st[x]<=en[x])up(f[p],cal(p,q[st[x]])+w[p]);
		return;
	}
	int mid=(a+b)>>1;
	ask(x<<1,a,mid,d,p);
	if(d>mid)ask(x<<1|1,mid+1,b,d,p);
}
void solve(int l,int r){
	if(l==r){
		g[l]=f[l]-l-1LL*l*l;
		up(ans,f[l]-1LL*(n-l)*(n-l+1));
		return;
	}
	int mid=(l+r)>>1,i;
	solve(l,mid);
	cb=0;
	for(i=l;i<=mid;i++)b[++cb]=P(a[i],i);
	sort(b+1,b+cb+1);
	tot=0;
	build(1,1,cb);
	for(i=mid+1;i<=r;i++){
		if(a[i]<b[1].first)continue;
		int t=lower_bound(b+1,b+cb+1,P(a[i],i))-b-1;
		ask(1,1,cb,t,i);
	}
	solve(mid+1,r);
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]*=2;
	ans=-1LL*n*(n+1);
	for(i=1;i<=n;i++){
		f[i]=-1LL*(i-1)*i+a[i];
		w[i]=-1LL*i*i+i+a[i];
	}
	solve(1,n);
	printf("%lld",ans/2);
}

B. Oleg and Data Science

若$R<Q$，那么顯然$\bmod Q$操作無效，故答案為無窮。

否則若$\lfloor\frac{L}{Q}\rfloor=\lfloor\frac{R}{Q}\rfloor$，則答案為$Q\lfloor\frac{L}{Q}\rfloor$的因子個數。

否則答案為$Q$的因子個數。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
LL L, R, Q;
LL check(LL n)
{
	LL rtn = 1;
	for(LL x = 2; x * x <= n; ++x)if(n % x == 0)
	{
		int cnt = 0;
		while(n % x == 0)
		{
			n /= x;
			++cnt;
		}
		rtn *= cnt + 1;
	}
	if(n >= 2)rtn *= 2;
	return rtn;
}
LL bf(bool out)
{
	int rtn = 0;
	for(int X = 1; X <= 40; ++X)
	{	
		bool flag = 1;
		for(int S = L; S <= R; ++S)
		{
			if(S % Q % X != S % X)
			{
				flag = 0;
				break;
			}
		}
		if(flag)
		{
			if(out)printf("%d ", X);
		}
		rtn += flag;
	}
	if(out)puts("END");
	return rtn;
}
int main()
{
	while(~scanf("%lld%lld%lld",&L,&R,&Q))
	//while(R = rand() % 30 + 1, L = rand() % R + 1, Q = rand() % 30 + 1, true)
	{
		if(R<Q)
		{
			puts("infinity");
		}
		else
		{
			//LL ans = check(max(Q, L / Q * Q));
			LL ans;
			if(L / Q == R / Q)ans = check(L / Q * Q);
			else ans = check(Q);
			printf("%lld\n", ans);
			/*
			if(ans != bf(0))
			{
				printf("%lld %lld %lld: %lld %lld\n", L, R, Q, ans, bf(1));
				getchar();
				//while(1);
			}
			*/
		}
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

C. Christmas Garland

首先將相鄰同色塊合并，建立一張圖，每個點表示一種顏色的燈，兩點間的邊表示這兩種顏色相鄰的有多少個，那么答案為亮著的燈數減去同時亮著的邊數。

將點按照度數大小以$\sqrt{m}$為界分成小點和大點，對于每個點維護$w_x$表示周圍有多少個小點亮著。

那么若操作小點，則枚舉它所有相連的邊，修改其$w$，同時對于相鄰的大點計算對答案的貢獻。

若操作大點，則枚舉它所有與大點相連的邊，計算貢獻。

時間復雜度$O(n\sqrt{n})$。

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
const int N=200010;
int n,ce,_,m,Q,i,j,x,y,have[N],tot,ans,lim;
int d[N],a[N],f[N],w[N];
vector<P>g[N],gg[N];
vector<P>::iterator it;
struct E{int x,y;}e[N];
inline bool cmp(const E&a,const E&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline void add(int x,int y,int z){
	d[x]++;
	lim++;
	g[x].push_back(P(y,z));
}
inline void addd(int x,int y,int z){
	if(d[x]>=lim&&d[y]>=lim)gg[x].push_back(P(y,z));
}
int main(){
	scanf("%d%d%d",&_,&m,&Q);
	while(_--){
		scanf("%d",&x);
		if(x!=a[n])a[++n]=x;
	}
	for(i=1;i<=n;i++)have[a[i]]++;
	for(i=1;i<n;i++){
		x=a[i],y=a[i+1];
		if(x>y)swap(x,y);
		e[++ce].x=x;
		e[ce].y=y;
	}
	sort(e+1,e+ce+1,cmp);
	for(i=1;i<=ce;i=j){
		for(j=i;j<=ce&&e[i].x==e[j].x&&e[i].y==e[j].y;j++);
		add(e[i].x,e[i].y,j-i);
		add(e[i].y,e[i].x,j-i);
	}
	lim=sqrt(lim);
	for(i=1;i<=ce;i=j){
		for(j=i;j<=ce&&e[i].x==e[j].x&&e[i].y==e[j].y;j++);
		addd(e[i].x,e[i].y,j-i);
		addd(e[i].y,e[i].x,j-i);
	}
	while(Q--){
		scanf("%d",&x);
		if(d[x]<lim){
			if(f[x]==0){
				tot+=have[x];
				ans+=w[x];
				for(it=g[x].begin();it!=g[x].end();it++){
					w[it->first]+=it->second;
					if(d[it->first]>=lim&&f[it->first])ans+=it->second;
				}
			}else{
				tot-=have[x];
				ans-=w[x];
				for(it=g[x].begin();it!=g[x].end();it++){
					w[it->first]-=it->second;
					if(d[it->first]>=lim&&f[it->first])ans-=it->second;
				}
			}
		}else{
			if(f[x]==0){
				tot+=have[x];
				ans+=w[x];
				for(it=gg[x].begin();it!=gg[x].end();it++)if(f[it->first])ans+=it->second;
			}else{
				tot-=have[x];
				ans-=w[x];
				for(it=gg[x].begin();it!=gg[x].end();it++)if(f[it->first])ans-=it->second;
			}
		}
		f[x]^=1;
		printf("%d\n",tot-ans);
	}
}

D. Anna and Lucky Tickets

問題即統計有多少長度為$n$的回文十進制數字串滿足奇數位數位和等于偶數位數位和。

若$n$是偶數，那么因為回文的性質，左半部分在右半部分奇偶性反轉，故奇數位和必定等于偶數位和，故$ans=10^{\frac{n}{2}}$。

若$n$是奇數，那么奇數位要填$[0,9]$，偶數位要填$[-9,0]$，將所有偶數位都加上$9$，再枚舉中間的數，則問題轉化為統計$\sum_{i=1}^n x_i=m,0\leq x_i\leq 9$的解數。

考慮容斥，枚舉有$k$個$x_i$必定突破了上限，剩下的不管，將上限從$m$中減掉后用隔板法計算，則$ans=\sum_{k=0}^n (-1)^kC(n,k)C(m-10k+n-1,n-1)$。

時間復雜度$O(n)$。

#include<cstdio>
const int N=10000010,P=1000000007;
int n,i,ans,even,odd,all,fac[N],inv[N];
inline int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}
inline int C(int n,int m){
  if(n<m)return 0;
  if(n==m)return 1;
  return 1LL*fac[n]*inv[m]%P*inv[n-m]%P;
}
int cal(int sum,int n){
  int ret=0;
  for(int i=0;i<=n;i++){
    int t=1LL*C(sum-i*10+n-1,n-1)*C(n,i)%P;
    if(i&1)ret=(ret-t+P)%P;else ret=(ret+t)%P;
  }
  return ret;
}
int main(){
  scanf("%d",&n);
  if(n%2==0)return printf("%d",po(10,n/2)),0;
  for(fac[0]=i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%P;
  for(inv[0]=inv[1]=1,i=2;i<N;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;
  for(i=2;i<N;i++)inv[i]=1LL*inv[i-1]*inv[i]%P;
  even=n/2;
  odd=n-even;
  all=even*9;
  if((n+1)/2%2)odd--;else even--;
  odd/=2;
  even/=2;
  for(i=0;i<10;i++){
    int t=all-i;
    if(t<0||t%2)continue;
    ans=(cal(t/2,odd+even)+ans)%P;
  }
  printf("%d",ans);
}

E. Octopus

分類大討論。

F. Secret Permutation

首先進行一輪迭代$Q(zero,i,zero)$即可找到$0$的位置。

將剩下$n-1$個數放入集合$S$，每次從$S$中隨機選擇兩個$x,y$，詢問$Q(x,y,zero)$，即可有很大概率排除掉$x$和$y$，期望$\frac{n}{2}$次可以得到$1$的位置。

那么知道$1$之后，不斷詢問$Q(i,one,one)$即可得到所有數的位置。

詢問次數期望為$2.5n\leq 12512$。

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int N=5010;
int n,i,A,B,x,m,q[N],f[N],one,zero;
inline int ask(int a,int b,int c){
  printf("? %d %d %d\n",a,b,c);
  fflush(stdout);
  int t;
  scanf("%d",&t);
  return t;
}
int main(){
  srand(time(NULL));
  scanf("%d",&n);
  if(n==1){
    puts("! 0");
    fflush(stdout);
    return 0;
  }
  for(i=0;i<n;i++)zero=ask(zero,i,zero);
  for(i=0;i<n;i++)if(i!=zero)q[m++]=i;
  while(m>1){
    A=q[x=rand()%m];
    swap(q[x],q[--m]);
    B=q[x=rand()%m];
    swap(q[x],q[--m]);
    x=ask(A,B,zero);
    if(x==A)q[m++]=B;
    if(x==B)q[m++]=A;
  }
  f[A=one=q[0]]=1;
  for(i=2;i<n;i++)f[A=ask(A,one,one)]=i;
  printf("!");
  for(i=0;i<n;i++)printf(" %d",f[i]);
  fflush(stdout);
}

G. Polygon Rotation

留坑。

H. Mikhail’s Problem

論文題。回文樹求出每個回文等差數列消失的位置，樹狀數組維護，時間復雜度$O(n\log n)$。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010;
int sz,last,go[N][26],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
  while(s[i]!=s[i-len[v]-1])v=link[v];
  return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
  last=go_until_pal(i,last);
  int&v=go[last][s[i]-'a'];
  if(v==-1){
    v=sz++;
    len[v]=len[last]+2;
    if(!last)link[v]=1;
    else{
      last=go_until_pal(i,link[last]);
      link[v]=go[last][s[i]-'a'];
    }
    diff[v]=len[v]-len[link[v]];
    if(diff[v]==diff[link[v]]){
      baby[v]=baby[link[v]];
      series_link[v]=series_link[link[v]];
    }else{
      baby[v]=v;
      series_link[v]=link[v];
    }
  }
  last=v;
  pair<vector<int>,vector<int> >ans;
  for(int u=v;u!=1;u=series_link[u]){
    int B=baby[u];
    vector<pair<int,int> >&vec=poses[B];
    int left=i-len[u]+1;
    if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
    else vec.push_back(make_pair(left,len[u]));
    ans.first.push_back(i-len[B]+1);
    if(vec.size()!=1){
      int L=vec[vec.size()-2].first,
          len_=vec[vec.size()-2].second,
          R=L+len_-1,
          L_=R-len[u]+1;
      ans.second.push_back(L_);
    }
    if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){
      vec[vec.size()-2]=vec[vec.size()-1];
      vec.pop_back();
    }
  }
  return ans;
}
inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  sz=2,last=0,len[0]=-1;
  for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i]));
  for(i=0;i<m;i++){
    read(x),read(y);
    que[y].push_back(make_pair(x,i));
  }
  for(i=1;i<=n;i++){
    pair<vector<int>,vector<int> >vec=add_char(i);
    vector<int>adding=vec.first,deleting=vec.second; 
    for(j=0;j<deleting.size();j++){
      if(!f[k=deleting[j]])continue;
      add(k,-1);
    }
    for(j=0;j<adding.size();j++){
      if(f[k=adding[j]]==1)continue;
      add(k,1);
    }
    for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
  }
  for(i=0;i<m;i++)printf("%d\n",ans[i]);
}

I. Rat-O-Matic

若$A$包含$B$，則$B$的半徑不超過$A$的一半，故掃描線將包含關系建樹后，樹高不超過$O(\log R)$。

對于每個字符串，枚舉所有后綴，將長度$O(\log R)$的前綴插入字典樹，即可完成詢問。

J. Readability

貪心，求出每個數的活動區間，掃描線的時候將最優的那個數填下來即可。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
int a[N], b[N], c[N];
int v[2];
int w[2][N];
int P(int o, int id)
{
	return id * 2 - o;
}
struct A
{
	int pos, val;
};
bool gorgt(A a, A b)
{
	if(a.pos != b.pos)return a.pos < b.pos;
	return a.val > b.val;
}
bool golft(A a, A b)
{
	if(a.pos != b.pos)return a.pos > b.pos;
	return a.val > b.val;
}
void GORGT(int st, int ed, int val, int o, int aimo, int b[])
{
	vector<A>vt;
	for(int i = st; ; i += val)
	{
		vt.push_back({w[o][i], 1});
		vt.push_back({P(aimo,i), -1});
		if(i == ed)break;
	}
	sort(vt.begin(), vt.end(), gorgt);
	multiset<int>sot;
	for(auto it : vt)
	{
		if(it.val == 1)
		{
			sot.insert(a[it.pos]);
		}
		else
		{
			b[it.pos] = *sot.begin();
			sot.erase(sot.begin());
		}
	}
}
void GOLFT(int st, int ed, int val, int o, int aimo, int b[])
{
	vector<A>vt;
	for(int i = st; ; i += val)
	{
		vt.push_back({w[o][i], 1});
		vt.push_back({P(aimo,i), -1});
		if(i == ed)break;
	}
	sort(vt.begin(), vt.end(), golft);
	multiset<int>sot;
	for(auto it : vt)
	{
		if(it.val == 1)
		{
			sot.insert(a[it.pos]);
		}
		else
		{
			b[it.pos] = *--sot.end();
			sot.erase(--sot.end());
		}
	}
}
LL solve(int o, int aimo, int b[])
{
	LL rtn = 0;
	//try to check every num
	for(int i = 1; i <= v[o]; ++i)
	{
		int l = w[o][i];	//start pos
		int r = P(aimo, i);	//end pos
		rtn += abs(l - r);
		if(l == r)
		{
			b[r] = a[l];
		}
		else if(l < r)
		{
			int p = i;
			while(p < v[o])
			{
				int ll = w[o][p + 1];
				int rr = P(aimo, p + 1);
				if(ll <= r)
				{
					r = rr;
					++p;
					rtn += abs(ll - rr);
				}
				else break;
			}
			GORGT(i, p, 1, o, aimo, b);
			i = p;
		}
		else
		{
            swap(l, r);
			int p = i;
			while(p < v[o])
			{
				int ll = w[o][p + 1];
				int rr = P(aimo, p + 1);
				swap(ll, rr);
				if(ll <= r)
				{
					r = rr;
					++p;
					rtn += abs(ll - rr);
				}
				else break;
			}
			GOLFT(i, p, 1, o, aimo, b);
			i = p;
		}
	}
	return rtn;
}
void print(int b[])
{
	for(int i = 1; i <= n; ++i)
	{
		printf("%d%c", b[i], i == n ? '\n' : ' ');
	}
}
bool small(int b[], int c[])
{
    for(int i = 1; i <= n; ++i)
    {
        if(b[i] > c[i])return 0;
        if(b[i] < c[i])return 1;
    }
    return 0;
}
int p[N];
int d[N], ansd[N];
LL bf()
{
    int ans = 1e9;
    for(int i = 1; i <= n; ++i)p[i] = i;
    do
    {
        int tmp = 0;
        bool flag = 1;
        for(int i = 1; i <= n; ++i)
        {
            tmp += abs(p[i] - i);
            d[i] = a[p[i]];
            if(i >= 2 && d[i] % 2 == d[i - 1] % 2)flag = 0;
        }
        if(flag)
        {
            if(tmp < ans || tmp == ans && small(d, ansd))
            {
                ans = tmp;
                for(int i = 1; i <= n; ++i)ansd[i] = d[i];
            }
        }
    }while(next_permutation(p + 1, p + n + 1));
}
int main()
{
	while(~scanf("%d",&n))
	//while(n = rand() % 9 + 1, true)
	{
	    //for(int i = 1; i <= n; ++i)a[i] = i; random_shuffle(a + 1, a + n + 1);
	    //printf("A: ");print(a);
		v[0] = v[1] = 0;
		for(int i = 1; i <= n; ++i)
		{
			scanf("%d", &a[i]);
			if(a[i] & 1)
			{
				w[1][++v[1]] = i;
			}
			else
			{
				w[0][++v[0]] = i;
			}
		}
	    //bf();
		if(n & 1)
		{
			//puts("n & 1");

			//偶 奇 偶
			if(v[0] > v[1])
			{
				solve(0, 1, b);
				solve(1, 0, b);
			}
			//奇 偶 奇
			else
			{
				solve(1, 1, b);
				solve(0, 0, b);
			}
			print(b);
			/*
            if(small(ansd, b))
            {
                puts("NO");
                print(ansd);
                getchar();
            }
            */
		}
		else
		{
            //ans1 偶 奇
            LL ans1 = solve(0, 1, b) + solve(1, 0, b);
            //ans2 ji ou
            LL ans2 = solve(1, 1, c) + solve(0, 0, c);
            if(ans1 < ans2)
            {
                print(b);
                /*
                if(small(ansd, b))
                {
                    puts("NO");
                    print(ansd);
                    getchar();
                }
                */
            }
            else if(ans1 > ans2)
            {
                print(c);
                /*
                if(small(ansd, c))
                {
                    puts("NO");
                    print(ansd);
                    getchar();
                }
                */
            }
            else
            {
                if(small(b, c))
                {
                    print(b);
                    /*
                    if(small(ansd, b))
                    {
                        puts("NO");
                        print(ansd);
                        getchar();
                    }
                    */
                }
                else
                {
                    print(c);
                    /*
                    if(small(ansd, c))
                    {
                        puts("NO");
                        print(ansd);
                        getchar();
                    }
                    */
                }
            }
		}
	}
	return 0;
}

/*
【trick&&吐槽】
4
1 3 2 4

4
3 1 4 2

【題意】


【分析】


【時間復雜度&&優化】


*/

K. Robotobor

BFS出$d[i][j][x][y]$表示從$(i,j)$到$(x,y)$的最短回文路線。

第二次BFS出$f[i][j]$表示從$(i,j)$到終點最少需要多少條長度不超過$100$的回文路線。

時間復雜度$O(n^4)$。

#include<cstdio>
const int N=55;
int n,m,i,j,x,y;
char a[N][N];
int d[N][N][N][N],f[N][N];
char q[N*N*N*N][4];
int h,t;
inline void ext(int A,int B,int C,int D,int w){
	if(A<1||A>n||B<1||B>m)return;
	if(a[A][B]=='#')return;
	if(C<1||C>n||D<1||D>m)return;
	if(a[C][D]=='#')return;
	if(~d[A][B][C][D])return;
	q[++t][0]=A;
	q[t][1]=B;
	q[t][2]=C;
	q[t][3]=D;
	d[A][B][C][D]=w;
}
inline void up(int x,int y,int w){
	if(~f[x][y])return;
	q[++t][0]=x;
	q[t][1]=y;
	f[x][y]=w;
}
inline int abs(int x){return x>0?x:-x;}
void print(int A,int B,int C,int D){
	if(A==C&&B==D)return;
	if(abs(A-C)+abs(B-D)==1){
		if(A+1==C)putchar('D');
		if(A-1==C)putchar('U');
		if(B+1==D)putchar('R');
		if(B-1==D)putchar('L');
		return;
	}
	if(~d[A][B-1][C][D+1]&&d[A][B-1][C][D+1]+2==d[A][B][C][D]){
		putchar('L');
		print(A,B-1,C,D+1);
		putchar('L');
		return;
	}
	if(~d[A][B+1][C][D-1]&&d[A][B+1][C][D-1]+2==d[A][B][C][D]){
		putchar('R');
		print(A,B+1,C,D-1);
		putchar('R');
		return;
	}
	if(~d[A-1][B][C+1][D]&&d[A-1][B][C+1][D]+2==d[A][B][C][D]){
		putchar('U');
		print(A-1,B,C+1,D);
		putchar('U');
		return;
	}
	if(~d[A+1][B][C-1][D]&&d[A+1][B][C-1][D]+2==d[A][B][C][D]){
		putchar('D');
		print(A+1,B,C-1,D);
		putchar('D');
		return;
	}
	puts("Error");
	while(1);
}
void show(int x,int y){
	while(f[x][y]){
		bool flag=0;
		for(i=1;i<=n;i++)for(j=1;j<=m;j++){
			if(flag)break;
			if(~d[x][y][i][j]&&d[x][y][i][j]<=100&&f[i][j]+1==f[x][y]){
				print(x,y,i,j);
				puts("");
				x=i,y=j;
				flag=1;
				break;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%s",a[i]+1);
	for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)for(x=0;x<=n+1;x++)for(y=0;y<=m+1;y++){
		d[i][j][x][y]=-1;
	}
	h=1,t=0;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)ext(i,j,i,j,0);
	for(i=1;i<=n;i++)for(j=1;j<=m;j++){
		ext(i,j,i+1,j,1);
		ext(i,j,i-1,j,1);
		ext(i,j,i,j-1,1);
		ext(i,j,i,j+1,1);
	}
	while(h<=t){
		int A=q[h][0],B=q[h][1],C=q[h][2],D=q[h][3];
		h++;
		int w=d[A][B][C][D]+2;
		//D
		ext(A-1,B,C+1,D,w);
		//U
		ext(A+1,B,C-1,D,w);
		//L
		ext(A,B+1,C,D-1,w);
		//R
		ext(A,B-1,C,D+1,w);
	}
	h=1,t=0;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]=-1;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]=='F')up(i,j,0);
	while(h<=t){
		int A=q[h][0],B=q[h][1];
		h++;
		int w=f[A][B]+1;
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(~d[i][j][A][B]&&d[i][j][A][B]<=100)up(i,j,w);
	}
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]=='S'){
		if(f[i][j]<0)return puts("-1"),0;
		printf("%d\n",f[i][j]);
		show(i,j);
		return 0;
	}
}

posted @ 2018-03-29 00:53 Claris 閱讀(1183) 評論(0) 收藏舉報

刷新頁面返回頂部

Claris' Blog

XVIII Open Cup named after E.V. Pankratiev. GP of Urals

公告