Codeforces Round #539 (Div. 2) 题解

Codeforces Round #539 (Div. 2)

题目链接：https://codeforces.com/contest/1113

A. Sasha and His Trip

题意：

n个城市，城市分布在一条直线上且按升序排序，现在有个人开车从一号城市出发，车的油箱容量为v。

在每个城市都可以买油，但价格不一样：第i个城市买1单位的油花费i元。问最终从1到n花费的最少为多少。

题解：

贪心即可，尽量在前面的城市买油，最后一鼓作气到n号城市。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+;

int n,v;

int main(){

    cin>>n>>v;

    int fir=,las=n-v;

    int ans=v;

    if(n-<=v){

        cout<<n-;

        return ;

    }

    for(int i=;i<=las;i++){

        ans+=i;

    }

    cout<<ans;

    return ;

}

B. Sasha and Magnetic Machines

题意：

给出n个数，现在选定i,j，然后取x满足a_j%x==0，之后让a_j=a_j/x，a_i=a_i*x。这个操作最多一次，问最后所有数的和最小为多少。

题解：

由于这里a_i<=100，并且n也最多1e4，所以可以直接考虑暴力。但这里暴力的是，取到一个x的时候，应该始终就是让最小的那个a_i来乘x，这应该是显而易见的。

具体见代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+;

int a[N];

int n;

int main(){

    scanf("%d",&n);

    int sum = ;

    for(int i=;i<=n;i++){

        scanf("%d",&a[i]);

        sum+=a[i];

    }

    int ans = sum;

    int mn = *min_element(a+,a+n+);

    sum-=mn;

    for(int i=;i<=n;i++){

        for(int j=;j<=a[i];j++){

            if(a[i]%j!=) continue ;

            ans=min(ans,sum-a[i]+a[i]/j+mn*j);

        }

    }

    cout<<ans;

    return ;

}

C. Sasha and a Bit of Relax

题意：

给出n个数，然后让你找出满足条件的区间个数：区间长度为偶数且区间左部分的异或和等于右部分的异或和。

题解：

根据题中条件可以知道，那整个区间的异或和是为0的，然后根据异或前缀和进一步可知：假设那个区间为[l,r]，那么pre_l-1=pre_r，这里pre_i为1~i的异或前缀和。并且还可以观察到，这里的l-1以及r是同奇偶的。

然后做法也大致清晰了，找出在奇偶位置异或前缀和为x的个数，假设我们目前只看奇数位置，有n个，那么这时对答案的贡献为C(n,2)，也即是n*(n-1)/2；偶数也同样。

只是需要注意的是，当前缀异或和为0并且当前为偶数位置时，这也算一种情况。

具体代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int cnt[][<<];

int main(){

    int n;

    cin>>n;

    vector <ll> a(n+);

    for(int i=;i<=n;i++) scanf("%I64d",&a[i]);

    ll sum=,ans=;

    cnt[][]=;

    for(int i=;i<=n;i++){

        sum^=a[i];

        ans+=cnt[i%][sum];

        cnt[i%][sum]++;

    }

    cout<<ans;

    return ;

}

D. Sasha and One More Name

题意：

给出一个回文串，然后让你用最少的次数分割为几个部分，之后可以拼接出一个和原来不同的回文串。如果不能就输出"Impossible"，否则输出最少次数。

题解：

不能的情况很好判断。

在判断可行性过后，可以证明次数最多只需要两次，考虑从两边同时往中间走的切法就行了。

也就是说，我们只需要判断只切一次是否可行。由于字符串的长度只有5000,O(n^2)暴力即可。

代码如下:

#include <bits/stdc++.h>

using namespace std;

const int N = ;

string s;

int l;

bool is(string ss){

    int f=;

    for(int i=;i<l;i++){

        int j=l-i-;

        if(ss[i]!=ss[j]) f=;

    }

    return f&&ss!=s;

}

int main(){

    cin>>s;

    l=s.length();

    int f=;

    for(int i=;i<l;i++){

        if(l& && i==l/) continue ;

        if(s[i]!=s[]) f=;

    }

    if(f){

        puts("Impossible");

        return ;

    }

    f=;

    for(int i=;i<l;i++){

        string t1=s.substr(,i),t2=s.substr(i,l);

        t2+=t1;

        if(is(t2))f=;

    }

    if(f) cout<<<<endl;

    else cout<<<<endl;

    return ;

}

秒客网

Codeforces Round #539 (Div. 2) 题解

相关文章