CVBB ACM Team

=====  A.LCM Problem =====

[[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即可。

<hidden> 
<code cpp>
#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;
    }
 
</code>
</hidden>  

=====  B.Array Walk =====  


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

贪心。对于1-x范围内的路径，三种情况可能为最优值： 
 
找到相邻两项和的最大值，在这相邻两项间重复走min(p, k-p/2)次。  

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

1->x->x-1

<hidden> 

<code cpp> 

#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;
    }
 
}
</code>
</hidden>

=====  C.Good String =====



题意：长度为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 =====


题意：给定2种区间，每种区间有n个，2种不同区间为一组。每次操作可以将区间向左/右扩展一个单位。求使各组区间重叠长度达到k的最小步数。  

最优情况下，扩展时有3个过程：不相邻->相邻->区间完全重叠->继续扩展  

三个过程的重叠数收入分别为0，扩展数、扩展数/2  

记录每个过程的扩展长度，枚举选i组区间扩展到重叠k次需要的扩展数，取最小值。
  
需要注意已经重叠的情况

<hidden> 

<code cpp>
#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
 
int main() {
    int t = 0;
    cin >> t;
    while (t--) {
        LL n, k;
        cin>>n>>k;
        int l1, r1, l2, r2;
        cin>>l1>>r1>>l2>>r2;
        LL pre = max(0, max(l1, l2) - min(r1, r2));
        LL most = max(r1, r2) - min(l1, l2);
        LL ist = max(0, min(r1, r2) - max(l1, l2) )* (LL)n ;
        k -= ist;
        if(k <= 0){
            cout<<0<<endl;
            continue;
        }
        LL ans = INT32_MAX;
        for (int i = 1; i <= n; ++i) {
            LL cur = pre * i;
            cur += min((LL)k, most * i);
            if(k > most * i){
                cur += 2 * (k - most * i);
            }
            ans = min(ans, cur);
        }
        cout<<ans<<endl;
    }
 
}
</code>
</hidden>
CVBB ACM Team

用户工具

站点工具

页面工具
