贪心+模拟大法好！
思路：简单模拟。不难发现，通过f函数运算下去的步骤数量不会很多，所以暴力模拟，只要有一个数字第二次出现break即可。
AC代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <iomanip> 8 #include <complex> 9 #include <string> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #include <list> 14 #include <deque> 15 #include <queue> 16 #include <stack> 17 #include <bitset> 18 using namespace std; 19 typedef long long LL; 20 typedef unsigned long long ULL; 21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向 23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 24 const double eps = 1e-6; 25 const double PI = acos(-1.0); 26 const int maxn = 1e5+5; 27 const int inf = 0x3f3f3f3f; 28 29 LL n; 30 set<LL> st; 31 32 int main() { 33 while(cin >> n) { 34 st.clear(); 35 st.insert(n); 36 while(1) { 37 ++n; 38 while(n % 10 == 0) n /= 10; 39 if(st.count(n)) break; 40 st.insert(n); 41 } 42 cout << st.size() << endl; 43 } 44 return 0; 45 }
思路：简单贪心+模拟。为了使得替换得到的数字最大，并且替换的数字必须是连续的，我们只需找到第一个替换的数字满足 $c_i > b_i$ 作为贪心的起点，并且让$ b_i > c_i$ 作为贪心的终点，然后简单模拟一下即可。
AC代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <iomanip> 8 #include <complex> 9 #include <string> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #include <list> 14 #include <deque> 15 #include <queue> 16 #include <stack> 17 #include <bitset> 18 using namespace std; 19 typedef long long LL; 20 typedef unsigned long long ULL; 21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向 23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 24 const double eps = 1e-6; 25 const double PI = acos(-1.0); 26 const int maxn = 2e5+5; 27 const int inf = 0x3f3f3f3f; 28 29 int n, f[10], b[maxn], c[maxn]; 30 string str, ans; 31 bool flag; 32 33 34 int main() { 35 while(cin >> n) { 36 cin >> str; 37 ans = ""; 38 flag = false; 39 for(int i = 0; i < n; ++i) b[i] = str[i] - ‘0‘; 40 for(int i = 1; i <= 9; ++i) cin >> f[i]; 41 for(int i = 0; i < n; ++i) c[i] = f[b[i]]; 42 for(int i = 0; i < n; ++i) { 43 if(!flag) { 44 if(b[i] < c[i]) flag = true, ans += c[i] + ‘0‘; // 贪心起点 45 else ans += str[i]; 46 }else { 47 if(b[i] > c[i]) { // 贪心终点 48 for(int j = i; j < n; ++j) ans += str[j]; 49 break; 50 } 51 else ans += c[i] + ‘0‘; 52 } 53 } 54 cout << ans << endl; 55 } 56 return 0; 57 }
思路：简单模拟即可。
AC代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <iomanip> 8 #include <complex> 9 #include <string> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #include <list> 14 #include <deque> 15 #include <queue> 16 #include <stack> 17 #include <bitset> 18 using namespace std; 19 typedef long long LL; 20 typedef unsigned long long ULL; 21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向 23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 24 const double eps = 1e-6; 25 const double PI = acos(-1.0); 26 const int maxn = 2e5+5; 27 const int inf = 0x3f3f3f3f; 28 29 int n, lt, rt, cnt, per, a[maxn]; 30 string str; 31 32 int main() { 33 while(cin >> n) { 34 cnt = 0, per = 0; 35 str = ""; 36 for(int i = 0; i < n; ++i) cin >> a[i]; 37 int i, j; 38 for(i = 0, j = n - 1; i < j;) { 39 if(a[i] > a[j]) { 40 if(a[j] > per) str += ‘R‘, ++cnt, per = a[j], --j; 41 else if(a[i] > per) str += ‘L‘, ++cnt, per = a[i], ++i; 42 else break; 43 }else { 44 if(a[i] > per) str += ‘L‘, ++cnt, per = a[i], ++i; 45 else if(a[j] > per) str += ‘R‘, ++cnt, per = a[j], --j; 46 else break; 47 } 48 } 49 if(i == j && a[j] > per) { 50 if(2 * j >= n - 1) str += ‘R‘, ++cnt; 51 else str += ‘L‘, ++cnt; 52 } 53 cout << cnt << endl; 54 cout << str << endl; 55 } 56 return 0; 57 }
思路：贪心+简单模拟。①若当前两边i，j指向的数字不同，则直接贪心处理；②若当前两边i，j指向的数字相同，如何选择左边或右边呢？我们只需另外设置2个变量来比较i和j分别能延伸的长度，哪边长就贪心选哪边即可。
AC代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <iomanip> 8 #include <complex> 9 #include <string> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #include <list> 14 #include <deque> 15 #include <queue> 16 #include <stack> 17 #include <bitset> 18 using namespace std; 19 typedef long long LL; 20 typedef unsigned long long ULL; 21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向 23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 24 const double eps = 1e-6; 25 const double PI = acos(-1.0); 26 const int maxn = 2e5+5; 27 const int inf = 0x3f3f3f3f; 28 29 int n, res1, res2, cnt, per, a[maxn]; 30 string str; 31 bool flag; 32 33 int main() { 34 while(cin >> n) { 35 cnt = 0, per = 0; 36 str = ""; 37 for(int i = 0; i < n; ++i) cin >> a[i]; 38 int i, j; 39 for(i = 0, j = n - 1; i < j;) { 40 if(a[i] > a[j]) { 41 flag = false; 42 if(a[j] > per) str += ‘R‘, ++cnt, per = a[j], --j, flag = true; 43 if(flag) continue; 44 if(a[i] > per) str += ‘L‘, ++cnt, per = a[i], ++i, flag = true; 45 if(!flag) break; 46 }else if(a[j] > a[i]){ 47 flag = false; 48 if(a[i] > per) str += ‘L‘, ++cnt, per = a[i], ++i, flag = true; 49 if(flag) continue; 50 if(a[j] > per) str += ‘R‘, ++cnt, per = a[j], --j, flag = true; 51 if(!flag) break; 52 } 53 else { // equal 54 if(a[i] <= per) break; 55 res1 = res2 = 0; 56 for(int lt = i; lt + 1 < j && a[lt] < a[lt + 1]; ++lt, ++res1); 57 for(int rt = j; rt - 1 > i && a[rt - 1] > a[rt]; --rt, ++res2); 58 if(res1 > res2) str += ‘L‘, ++cnt, per = a[i], ++i; 59 else str += ‘R‘, ++cnt, per = a[j], --j; 60 } 61 } 62 if(i == j && a[j] > per) { 63 if(2 * j >= n - 1) str += ‘R‘, ++cnt; 64 else str += ‘L‘, ++cnt; 65 } 66 cout << cnt << endl; 67 cout << str << endl; 68 } 69 return 0; 70 }
思路：
AC代码：
思路：简单贪心。这个题用vector容器会T到飞qwq，题解是用关联式容器multiset（自动排序），其增删查的时间复杂度均为 $O(log^n) $，用起来非常简单，容易上手！注意到a数组、b数组中所有元素都小于n，那么问题求解就变得简单了：为了使得每个 $a_i$ 各自能匹配到的 $b_j$ 使得 $(a_i + b_j) \% n $ 最小，只需贪心找不小于 $ (n - a_i) $ 的最小值，因为以 $ (n - a_i) $ 为起点的$ b_j$ 和 $ a_i$ 的和取模n的余数为0，往后逐渐增加，循环一圈到 $ (n - a_i - 1) $ 达到最大；若找不到，则取容器中首个元素进行匹配，即离 $ (n-a_i) $ 左边最远的一个，不难证明此时的 $(a_i+b_j) % n $ 是最小的。
AC代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <algorithm> 7 #include <iomanip> 8 #include <complex> 9 #include <string> 10 #include <vector> 11 #include <set> 12 #include <map> 13 #include <list> 14 #include <deque> 15 #include <queue> 16 #include <stack> 17 #include <bitset> 18 using namespace std; 19 typedef long long LL; 20 typedef unsigned long long ULL; 21 const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左 22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向 23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 24 const double eps = 1e-6; 25 const double PI = acos(-1.0); 26 const int maxn = 2e5+5; 27 const int inf = 0x3f3f3f3f; 28 29 30 int n, a[maxn], b, pos, siz; 31 multiset<int> st; 32 multiset<int>::iterator it; 33 34 35 int main() { 36 while(~scanf("%d", &n)) { 37 st.clear(); 38 for(int i = 0; i < n; ++i) scanf("%d", &a[i]); 39 for(int i = 0; i < n; ++i) scanf("%d", &b), st.insert(b); 40 for(int i = 0; i < n; ++i) { 41 it = st.lower_bound(n - a[i]); 42 if(it == st.end()) it = st.begin(); 43 printf("%d%c", (a[i] + *it) % n, " \n"[i == n - 1]); 44 st.erase(it); 45 } 46 } 47 return 0; 48 }
Codeforces Round #555 (Div. 3)
原文：https://www.cnblogs.com/acgoto/p/10782071.html
