CodeForces1732 | Crystal’s Blog

type

Post

status

Published

date

Oct 25, 2022

slug

codeforces1732

summary

CF Contest 1732 A-D1 solution and code Code Forces 1732 比赛 A题-D1 题题目思路以及代码

A题 Bestie

给出长度为的数组，可以对任意一个数进行一种操作：使得,该操作的花费是,请问：最少需要多少花费能使得整个数组的GCD等于1？

💡

思路：可以证明，只需要操作第个元素和第个元素就能满足题意。所以总共有三种方案：操作第个元素、操作第个元素、同时操作第个元素和第个元素。对于第三种方案：因为对进行操作后得到的值一定会是的约数，而和一定互质，也就是=1，分别对二者进行操作后的值也一定互质，因此解释了第三种方案的合理性。

A题代码


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void solve()
{
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        v.push_back(x);
    }
    int d = v[0];
    for (int i = 1; i < n; i++)
    {
        d = gcd(d, v[i]);
    }
    int ans = 3;
    for (int i = n - 1; i >= 0; i--)
    {
        int x = gcd(v[i], i + 1);
        if (gcd(x, d) == 1)
        {
            ans = n - i;
            break;
        }
    }
    ans = min(ans, 3);
    if (d == 1)
        ans = 0;
    cout << ans << endl;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

B题 Ugu

给定一个字符串，能对第个元素进行如下操作：对所有的，将的值取反，请问最少要进行几次操作使得整个字符串非严格递增？

💡

计算反转次数（），如果第一个反转是，则结果减

B题代码


#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
void solve()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int i = 0;
    s += s[n - 1];
    while (i < n && s[i] <= s[i + 1])
    {
        i++;
    }
    int ans = 0;
    while (i < n)
    {
        if (s[i] != s[i + 1])
            ans++;
        i++;
    }
    cout << ans << endl;
}
int main()
{
    // freopen("in.txt","r",stdin);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

C1题 Sheikh (Easy version)

给定一个长度为的数组，定义，给出一个查询，请问在区间，使得最大且最短的区间分别是多少？

💡

首先都具有类似前缀后和差分的性质，也就是说：在中枚举,对于每一个,在二分枚举，对于每一种组合通过前缀和的性质的复杂度求出，总复杂度为。

C1题代码


#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>
#include <map>
typedef long long ll;
using namespace std;
const int N = 2e5 + 50;
ll sum[N], xr[N];
ll get(ll a,ll b){
    return sum[b] - sum[a - 1] - (xr[b] ^ xr[a - 1]);
}
void solve()
{
    ll n, q;
    cin >> n >> q;
    vector<ll> v;
    v.push_back(0);
    for (int i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        v.push_back(x);
    }
    memset(sum, 0, sizeof sum);
    memset(xr, 0, sizeof xr);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + v[i];
        xr[i] = xr[i - 1] ^ v[i];
    }
    ll L, R;
    cin >> L >> R;
    ll ans = get(L,R);
    ll minn = 2e9, l, r;
    for (int i = L; i <= R; i++)
    {
        ll l1=i,r1=R;
        while(l1<r1){
            ll mid=(l1+r1)/2;
            if(get(i,mid)==ans){
                r1=mid;
            }else{
                l1=mid+1;
            }
        }
        if(l1==r1&&get(i,l1)==ans&&(l1-i+1)<minn){
            minn=l1-i+1;
            l=i;
            r=l1;
        }
    }
    cout<<l<<" "<<r<<endl;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    return 0;
}

C2题 Sheikh (Hard Version)

在C1题的基础上，将只有1个查询改成个查询，也就是要求我们对每个查询只能运用的复杂度。

💡

主要优化在于不从区间内枚举，而是从前33个不为0的元素中枚举,总复杂度为。考虑什么情况下增加却减少？答案是所有为1的位都变为0。假设，减少了，是因为最后两位由变为。那最后两位是怎么变为0的呢？对于最后一位，在区间内一定有个数最后一位为1。因为数组中的最大值，A的位数，所以答案的左边界一定存在在前33个不为0的元素中。

C2题代码


togg#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>
#include <map>
typedef long long ll;
using namespace std;
const int N = 2e5 + 50;
ll sum[N], xr[N];
ll get(ll a, ll b)
{
    return sum[b] - sum[a - 1] - (xr[b] ^ xr[a - 1]);
}
ll m_min(ll a, ll b)
{
    return a > b ? b : a;
}
void solve()
{
    ll n, q;
    cin >> n >> q;
    vector<ll> v, v1;
    v.push_back(0);
    for (int i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        v.push_back(x);
        if (x != 0)
            v1.push_back(i + 1); //存放不为0的数的下标
    }
    memset(sum, 0, sizeof sum);
    memset(xr, 0, sizeof xr);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + v[i];
        xr[i] = xr[i - 1] ^ v[i];
    }
    while (q--)
    {
        ll L, R;
        cin >> L >> R;
        ll ans = get(L, R);
        ll minn = 2e9, l = L, r = L;
        ll id = lower_bound(v1.begin(), v1.end(), L) - v1.begin(); //找到第一个下标>=l且不为0的元素

        for (int i = id; i < m_min(33 + id, v1.size()); i++)
        {
            ll l1 = v1[i], r1 = R;
            while (l1 < r1)
            {
                ll mid = (l1 + r1) / 2;
                if (get(v1[i], mid) == ans)
                {
                    r1 = mid;
                }
                else
                {
                    l1 = mid + 1;
                }
            }
            if (l1 == r1 && get(v1[i], l1) == ans && (l1 - v1[i] + 1) < minn)
            {
                minn = l1 - v1[i] + 1;
                l = v1[i];
                r = l1;
            }
        }
        cout << l << " " << r << endl;
    }
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    return 0;
}

D1题 Balance (Easy version)

有个查询，查询分两种：，前者表示将数x添加到set中，后者表示查询最小的能整除k且不在set中的非负数。

💡

添加操作用map标记，查询操作直接枚举对于下面这个例子会超时：时间复杂度为，因为每次都会从0开始枚举,优化思路：对于相同的查询，记忆化上次操作的结果，这一次直接从上次的结果值开始枚举。

D1题代码


#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<map>
typedef long long ll;
using namespace std;
const ll Maxn=3e18;
map<ll,ll>mp,mp1;//mp标记是否在集合中，mp1存放已经查询过的值及对应结果
void solve(){
    char c;ll x;
    scanf("%s%lld",&c,&x);
    mp[0]=1;
    if(c=='+'){
        mp[x]=1;
    }else{
       
        for(ll i=mp1[x];i<=Maxn/x;i++){
            ll y=x*i;
            if(mp[y]!=0){
                continue;
            }else{
                mp1[x]=i;
                cout<<y<<endl;
                break;
            }
        }
    }
}
int main(){
    // freopen("in.txt","r",stdin);
    int T;
   scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}