當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

topcoder SRM712 Div1 LR

發(fā)布時間：2023/12/10 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 topcoder SRM712 Div1 LR 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

題目：

Problem Statement

????

We have a cyclic array A of length n. For each valid i, element i-1 the left neighbor of element i. Additionally, element n-1 is the left neighbor of element 0.?

You are given two vector<long long>s?s?and?t, each with n elements. Currently, we have A[i] =?s[i] for each valid i. Our goal is to have A[i] =?t[i] for each valid i.?

We can use two operations that modify the contents of A:

Operation L: Each element is increased by the value of its left neighbor.
Operation R: Each element is increased by the value of its right neighbor.

Note that all changes happen simultaneously. For example, if you use the operation L, the new value of A[7] is computed as the sum of the old value of A[7] and the old value of A[6].?

If there is no way to reach the desired goal state, return "No solution". Otherwise return any valid way of doing so by using at most 100 operations. More precisely, return one valid sequence of operations encoded as a string of 'L's and 'R's.?

If there are multiple valid solutions, you may return any of them. In particular, you are not required to find the shortest valid solution. Any valid solution will be accepted as long as its length does not exceed 100. We can prove that if there is an valid solution then there must exist one with length at most 100.

Definition

????

Class:	LR
Method:	construct
Parameters:	vector<long long>, vector<long long>
Returns:	string
Method signature:	string construct(vector<long long> s, vector<long long> t)
(be sure your method is public)

Limits

????

Time limit (s):	2.000
Memory limit (MB):	256
Stack limit (MB):	256

Constraints

s?will contain between 2 and 50 elements, inclusive.

s?and?t?will contain the same number of elements.

Each element in?s?will be between 0 and 1,000,000,000,000,000 (10^15) inclusive.

Each element in?t?will be between 0 and 1,000,000,000,000,000 (10^15) inclusive.

Examples

????

{0,1,0,0,0}

{0,1,2,1,0}

Returns: "LL"

The first operation L will change A into {0,1,1,0,0} and then the second operation L will produce the array we wanted.

????

{0,0,0,1}

{0,1,0,0}

Returns: "No solution"

Even though A is cyclic, the precise indices matter. Here,?s?and?t?are two different configurations, and there is no valid way to change this?s?into this?t.

????

{1,2,3,4,5,6,7,8,9,10}

{12,24,56,95,12,78,0,100,54,88}

Returns: "No solution"

Regardless of the type and order of operations all elements of A will always remain positive. However,?t?contains a zero. Therefore,?t?cannot be reached.

????

{1,0,0}

{11,11,10}

Returns: "RRRRR"

The sequence of five operations R will change the array A as follows: {1,0,0} -> {1,0,1} -> {1,1,2} -> {2,3,3} -> {5,6,5} -> {11,11,10}.

????

{1,1}

{562949953421312,562949953421312}

Returns: "RLLLRRRLLRRRLRLRRLLLLRLLRRLRRRLRRLRRLLRRRLLRRRLLL"

We start with A[0] = A[1] = 1, and we want A[0] = A[1] = 2^49. We can easily verify that in this case each operation changes A from {x, x} into {2x, 2x}. Therefore, any string of exactly 49 'L's and 'R's is a valid answer.

????

{0,0,0,0,0}

{0,0,0,1,0}

Returns: "No solution"

????

{123,456}

Returns: ""

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

思路：因為這是一個圓形數(shù)列，所以L和R所得的數(shù)列是差不多的，只是左移右移一次的區(qū)別。

　　所以先判斷進行sum次操作（通過數(shù)列值的和判斷）。

　　然后先進行sum次L操作，再判斷把進行sum次操作后的數(shù)列k次右平移后能否得到t數(shù)列。

　　能到得到的話則是進行了k次R，sum-k次L操作，LR的先后順序沒有關(guān)系。

1 // BEGIN CUT HERE 2 3 #include <conio.h> 4 #include <sstream> 5 /* 6 */ 7 #define debuging 8 #ifdef debuging 9 #define FIN {freopen("new.in" , "r" , stdin) ;} 10 #define FOUT {freopen("new.out" , "w" , stdout) ;} 11 #define OUT(x) {cout<< #x << " : " << x <<endl ;} 12 #define ERR(x) {cout<<"#error: "<< x ; while(1) ;} 13 #endif 14 // END CUT HERE 15 #include <bits/stdc++.h> 16 17 using namespace std; 18 19 #define MP make_pair 20 #define PB push_back 21 typedef long long LL; 22 typedef pair<int,int> PII; 23 const double eps=1e-8; 24 const double pi=acos(-1.0); 25 const int K=1e6+7; 26 const int mod=1e9+7; 27 28 29 class LR 30 { 31 public: 32 string construct(vector<long long> s, vector<long long> t) 33 { 34 int cnt=101; 35 LL suma=0,sumb=0,sum=1; 36 string ans; 37 for(int i=0; i<s.size(); i++) 38 suma+=s[i],sumb+=t[i]; 39 if(suma==sumb) sum=0; 40 for(int i=1; i<=100&∑ i++) 41 if((suma*=2) == sumb) 42 { 43 sum=i; 44 break; 45 } 46 if(suma!=sumb) 47 return "No solution"; 48 for(LL i=0,n=s.size(); i<sum; i++) 49 for(LL j=0,ls=s[n-1],tmp; j<n; j++) 50 tmp=s[j],s[j]+=ls,ls=tmp; 51 for(int i=0; i<=sum; i++) 52 { 53 if(s==t) 54 { 55 cnt=i;break; 56 } 57 s.insert(s.begin(),s[s.size()-1]); 58 s.erase(--s.end()); 59 } 60 if(cnt>sum) 61 return "No solution"; 62 if(sum==0) 63 return ""; 64 for(int i=0; i<cnt; i++) 65 ans+="R"; 66 for(int i=cnt; i<sum; i++) 67 ans+="L"; 68 return ans; 69 } 70 71 72 // BEGIN CUT HERE 73 public: 74 void run_test(int Case) 75 { 76 if ((Case == -1) || (Case == 0)) test_case_0(); 77 if ((Case == -1) || (Case == 1)) test_case_1(); 78 if ((Case == -1) || (Case == 2)) test_case_2(); 79 if ((Case == -1) || (Case == 3)) test_case_3(); 80 if ((Case == -1) || (Case == 4)) test_case_4(); 81 if ((Case == -1) || (Case == 5)) test_case_5(); 82 if ((Case == -1) || (Case == 6)) test_case_6(); 83 } 84 private: 85 template <typename T> string print_array(const vector<T> &V) 86 { 87 ostringstream os; 88 os << "{ "; 89 for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; 90 os << " }"; 91 return os.str(); 92 } 93 void verify_case(int Case, const string &Expected, const string &Received) 94 { 95 cerr << "Test Case #" << Case << "..."; 96 if (Expected == Received) cerr << "PASSED" << endl; 97 else 98 { 99 cerr << "FAILED" << endl; 100 cerr << "\tExpected: \"" << Expected << '\"' << endl; 101 cerr << "\tReceived: \"" << Received << '\"' << endl; 102 } 103 } 104 void test_case_0() 105 { 106 LL Arr0[] = {0,1,0,0,0}; 107 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 108 LL Arr1[] = {0,1,2,1,0}; 109 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 110 string Arg2 = "LL"; 111 verify_case(0, Arg2, construct(Arg0, Arg1)); 112 } 113 void test_case_1() 114 { 115 LL Arr0[] = {0,0,0,1}; 116 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 117 LL Arr1[] = {0,1,0,0}; 118 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 119 string Arg2 = "No solution"; 120 verify_case(1, Arg2, construct(Arg0, Arg1)); 121 } 122 void test_case_2() 123 { 124 LL Arr0[] = {1,2,3,4,5,6,7,8,9,10}; 125 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 126 LL Arr1[] = {12,24,56,95,12,78,0,100,54,88}; 127 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 128 string Arg2 = "No solution"; 129 verify_case(2, Arg2, construct(Arg0, Arg1)); 130 } 131 void test_case_3() 132 { 133 LL Arr0[] = {1,0,0}; 134 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 135 LL Arr1[] = {11,11,10}; 136 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 137 string Arg2 = "RRRRR"; 138 verify_case(3, Arg2, construct(Arg0, Arg1)); 139 } 140 void test_case_4() 141 { 142 LL Arr0[] = {1,1}; 143 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 144 LL Arr1[] = {562949953421312,562949953421312}; 145 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 146 string Arg2 = "RLLLRRRLLRRRLRLRRLLLLRLLRRLRRRLRRLRRLLRRRLLRRRLLL"; 147 verify_case(4, Arg2, construct(Arg0, Arg1)); 148 } 149 void test_case_5() 150 { 151 LL Arr0[] = {0,0,0,0,0}; 152 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 153 LL Arr1[] = {0,0,0,1,0}; 154 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 155 string Arg2 = "No solution"; 156 verify_case(5, Arg2, construct(Arg0, Arg1)); 157 } 158 void test_case_6() 159 { 160 LL Arr0[] = {123,456}; 161 vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 162 LL Arr1[] = {123,456}; 163 vector<long long> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 164 string Arg2 = ""; 165 verify_case(6, Arg2, construct(Arg0, Arg1)); 166 } 167 168 // END CUT HERE 169 170 }; 171 // BEGIN CUT HERE 172 int main() 173 { 174 LR ___test; 175 ___test.run_test(3); 176 getch() ; 177 return 0; 178 } 179 // END CUT HERE

轉(zhuǎn)載于:https://www.cnblogs.com/weeping/p/6739263.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎