CVBB ACM Team

https://codeforces.com/contest/1389/problem/A

题意： 找到[l, r]范围内的两个数x < y使得其最小公倍数也在[l, r]范围内。

设x = p * gcd(x, y) ，y = q * gcd(x, y) ，pq互质。lcm(x, y) = pq*gcd(x, y)。 x确定时y = 2x 时lcm(x, y) = y取到最小值

x = l时存在解有= 2*l。判断r是否小于2*l即可。

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

题意：给定一个数组，起始位置在下标1处，可以选择向左走与向右走，不可重复向左走，向左走总次数不得超过p，总共走k次，求经过路径上数组元素值和的最大值。

贪心。对于1-x范围内的路径，三种情况可能为最优值：

找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次。

找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次, 再在结尾向左走1次。

1→x→x-1

 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
 
LL a[100005];
LL maxA2[100005];
LL tot[100005];
int main() {
    int t = 0;
    cin >> t;
    while (t--) {
        int n, k, z;
        LL ans = 0;
        cin>>n>>k>>z;
        LL tt = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", a+i);
            if(i)tt += a[i];
            tot[i] = tt;
        }
        LL a2 = 0;
        for (int i = 0; i < n - 1; ++i) {
            a2 = max(a2, a[i] + a[i+1]);
            maxA2[i] = a2;
        }
        ans = tot[k];
        for (int i = 1; i <= k; ++i) {
            int rep = min(z, (k - i) / 2);
            if(k == i + rep * 2) ans = max(ans, maxA2[i - 1] * rep + tot[i]);
            if(k == i + 1 && z) ans = max(ans, tot[i] + a[i-1]);
            if(k == i + 1 + rep * 2 && z >= rep + 1) ans = max(ans, maxA2[i - 1] * rep + tot[i] + a[i-1]);
        }
        cout<<ans + a[0]<<endl;
    }
 
}

题意：长度为n的good string是s[i] = s[(i+2) % n] 的字符串 给定一个0-9构成的字符串，求使其变为good string需要删除的最少字符数 直接暴力枚举，在0-9中选2个数字构成good string，计算每次选择需要删除的字符数，找到最小的答案。 <hidden> <code cpp> #include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int t = 0; cin » t; while (t–) { string s; cin»s; int l = s.length(); int ans = INT32_MAX; for (int i = '0'; i ⇐ '9'; ++i) { for (int j = '0'; j ⇐ '9'; ++j) { int e = 0; bool rev = 0; for (int k = 0; k < l && e < ans; ++k) { char c = rev ? j : i; if(s[k] != c) e++; else if(k == l - 1 && i != j && (l & 1))e++; else rev = !rev; } if(rev && (i != j))e++; ans = min(ans, e); } } cout«ans«endl; } } </code> </hidden> ===== D.Segment Intersections ===== https://codeforces.com/contest/1389/problem/A 题意：找到[l, r]范围内的两个数x, y使得其最小公倍数也在[l, r]范围内。 <hidden> <code cpp> </code> </hidden> ===== E.Segment Intersections =====