首页 > 代码库 > topcoder srm 712 div1 -23
topcoder srm 712 div1 -23
1、给定两个长度为$n$的数组$A,B$。有两种操作可以作用于数组$A$。第一种，将每个元素左侧的相邻数字加到其上；第二种，将每个元素右侧的相邻数字加到其上。0的左侧是$n-1$，$n-1$的右侧是0。比如1,2,3,4执行第一种操作后是5,3,5,7。给出一个不超过100的操作序列使得$A$变成$B$。$n \leq 50$.
思路：将$a_{0},a_{1},...,a_{n-1}$看做$a_{0}x^{0}+a_{1}x^{1}+...+a_{n-1}x^{n-1}$。那么第一种操作相当于乘以$1+x$模$x^{n}-1$，第二种操作相当于乘以$1+x^{n-1}$模$x^{n}-1$。所以操作的顺序无关。所以只需要枚举两种操作各用了多少次即可。
#include <string.h>#include <stdio.h>#include <vector>#include <string>#include <set>using namespace std;void print(vector<long long> a) { for(int i=0;i<a.size();++i) printf("%lld ",a[i]); puts("");}vector<long long> cal(vector<long long> s,int x,int y) { int n=(int)s.size(); while(x--) { vector<long long> tmp=s; for(int i=1;i<n;++i) tmp[i]+=s[i-1]; tmp[0]+=s[n-1]; s=tmp; } while(y--) { vector<long long> tmp=s; for(int i=n-2;i>=0;--i) tmp[i]+=s[i+1]; tmp[n-1]+=s[0]; s=tmp; } return s;}class LR{public: string construct(vector<long long> s,vector<long long> t) { if(s==t) return ""; long long x0=0,x1=0; int n=(int)s.size(); for(int i=0;i<n;++i) { x0+=s[i]; x1+=t[i]; } if(x0==0) return "No solution"; int k=0; while(x0<x1) ++k,x0<<=1; if(x0!=x1) return "No solution"; for(int i=0;i<=k;++i) { if(cal(s,i,k-i)==t) { string ans=""; for(int j=0;j<i;++j) ans+="L"; for(int j=0;j<k-i;++j) ans+="R"; return ans; } } return "No solution"; }};
topcoder srm 712 div1 -23
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。