【TopCoder SRM712】LR

相关链接

题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=14569&rd=16881

解题报告

我们经过观察发现，操作顺序不影响结果
于是我们就可以暴力枚举多少个$L$多少个$R$然后暴力判断
时间复杂度：$O(n \log^2 10^{17})$

Code

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

class LR {
    public:
    	string construct(vector<long long> s, vector<long long> t) {
    	    int n=s.size(),SPJ=1; LL s1=0,s2=0,pp,cnt=0;
    	    for (int i=0;i<n;i++) s1 += s[i], s2 += t[i], SPJ = (t[i]!=s[i]?0:SPJ);
    	    if (SPJ) return ""; pp = s1;
    	    if (s2-s1 <= 0 || (!s1 && s2)) return "No solution";
    	    while (pp<s2) pp<<=1,++cnt; 
			if (pp != s2) return "No solution";
			for (int i=0;i<=cnt;i++) {
				if (judge(s, t, i, cnt-i)) {
					string ret="";
					for (int j=1;j<=i;j++) ret += "L";
					for (int j=i+1;j<=cnt;j++) ret += "R";
					return ret;
				}
			}
			return "No solution";
   		}
   	private:
   		inline bool judge(vector<LL> s, vector<LL> t, int L, int R) {
			LL tmp[55],a[55],b[55],n=s.size();
			for (int i=1;i<=n;i++) a[i] = s[i-1], b[i] = t[i-1];
			for (int k=1;k<=L;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[0] = a[n];
				for (int i=1;i<=n;i++) a[i] = tmp[i-1] + tmp[i];
			}
			for (int k=1;k<=R;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[n+1] = a[1];
				for (int i=1;i<=n;i++) a[i] = tmp[i] + tmp[i+1];
			}
			for (int i=1;i<=n;i++) if (a[i] != b[i]) return 0;
			return 1;
		} 
};