1389A. LCM Problem

题意：给定一个范围 [l,r]。要在这个范围内找到两个整数 x，y，并且l<=LCM(x,y)<=r。

思路：因为x,y不能相等。那么在这范围内的最小的lcm应该就是l的两倍。既只要l*2<=r。就可以

#include<bits/stdc++.h> using namespace std; int main() {  ios::sync_with_stdio(false); int t;  cin >> t; while (t--) { long long l, r;   cin >> l >> r; if (l *2 > r) {    cout << -1 << ' ' << -1 << endl; } else {    cout << l << ' ' << l *2 << endl; } } return 0; } 

1389B. Array Walk

题意：给你一个数组，有n个数。初始位置在下标为1的a1处，你可以在数组上进行移动k次。移动到某个位置时，你可以得到相对应的分数。但有两个限制。不能连续两次向左移动，并且向左移动的次数不能超过z次。问最后最高可以得到多少分。

思路：可以枚举 2—n 的位置上，左右移动1-z次。选择得分最高的情况。 具体实现看代码中的注释。

#include<bits/stdc++.h> using namespace std; int main() {  ios::sync_with_stdio(false); int t;  cin >> t; while (t--) { int n, k, z;   cin >> n >> k >> z;   vector<long long> v(n); for (auto& val : v) {    cin >> val; } int i, j; int idx = 0; long long ans = 0; bool can = false;   vector<long long> sum(n);   sum[0] = v[0]; for (i = 1; i < n; i++) {    sum[i] = sum[i - 1] + v[i]; }   ans = sum[k]; for (i = 1; i < n; i++) { for (j = 1; j <= z && j <= k - i; j++) { // sum为前缀和  // k-i 为 移动到i这个位置时，还剩下的移动次数 // 如果剩余的移动次数够来回移动j次。 i->i-1 ,i-1>i  这样算完整的一次来回移动 if (j * 2 <= k - i) // sum[i + k - 2 * j - i]  i表示当前的位置 k-2*j-i 表示到达当前位置 // i并且来回移动j次后剩余的移动次数。所以i + k - 2 * j - i表示最后可以达到的位置的前缀和      ans = max(ans, (v[i] + v[i - 1]) * j + sum[i + k - 2 * j - i]); // 如果不够来回移动j次。 既最后一次向左移动后，不能回到i这个位置。 else if (j * 2 - 1 <= k - i)      ans = max(ans, (v[i] + v[i - 1]) * (j - 1) + v[i - 1] + sum[i]); } }   cout << ans << endl; } return 0; } 

1389C. Good String

题意：字符串有做循环位移和右循环位移两种操作。例如字符串“123456”，如果进行左循环位置后得“234561”，如果进行右循环位移后得“612345”。我们称一个字符串为好的，当且仅当它进行左循环位移和右循环位移后相等。现在给定一个字符串只包含0-9，可以删除字符串中某些字符，要求最少删除多少个字符串可以让字符串边好。

思路：要满足左右循环位移一位后字符串完全相等，那么字符串要么全由一个字符串组成，例如，’111111‘，或者只有两个字符循环出现，例如样例中的“2525252525”。那么我们就可以去构造字符串，然后去判断。只有一个字符的时候只要记录一下每个字符出现的次数即可。如果是两个字符循环出现的话，可以枚举剩下的两个字符，然后去和原字符串匹配。复杂度为10*10*n。

#include<bits/stdc++.h> using namespace std; int match(string str, char ch1,char ch2) { int flag = 0; int i; int cnt = 0; for (i = 0; i < str.size(); i++) { if (flag == 0) { if (str[i] == ch1) {     flag = 1;     cnt++; } } else { if (str[i] == ch2) {     flag = 0;     cnt++; } } } return cnt%2==0?cnt:0; } int main() {  ios::sync_with_stdio(false); int t;  cin >> t; while (t--) {   string str;   cin >> str;   unordered_map<char, int> mmid; int i, j; for (i = 0; i < str.size();i++) {    mmid[str[i]]++; } int ans = str.size(); int len = str.size(); for (auto& [a, b] : mmid) {    ans = min(ans, len - b); } for (i = 0; i < 10; i++) { for (j = 0; j < 10; j++) { if (j == i)continue; int tmp = len - match(str, i + '0', j + '0');     ans = min(ans, tmp); } }   cout << ans << endl; } return 0; }