竞赛讨论区 > 题解| 2021牛客OI赛前集训营-普及组(第三场)

题解| 2021牛客OI赛前集训营-普及组(第三场)

头像
昴星团
发布于 2021-10-10 08:41:56 APP内打开
赞 1 | 收藏 0 | 回复0 | 浏览394

2021牛客OI赛前集训营-普及组(第三场)解析

P.S. 传送门:https://ac.nowcoder.com/acm/contest/20102#question

1. A-反码:https://ac.nowcoder.com/acm/contest/20102/A

解析:考察基本的字符串处理,题意明确。注意使用 getline 时,对于 string 类型的字符串s,格式为 getline(cin,s); 而对于长度为 N 的字符数组s,格式为 cin.getline(s,N); 记得下标从 0 开始。

代码:(好习惯:尽量用getline读入一行)

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
string s;
int main() {
    getline(cin,s);
    if(s[0]=='0') cout<<s;
    else for(int i=0; i<s.size(); ++i)
            if(i==0) cout<<s[i];
            else if(s[i]=='1') cout<<'0';
            else cout<<'1';
    return 0;
}

2.B-异或:https://ac.nowcoder.com/acm/contest/20102/B

解析:如果每次都移动,时间复杂度 O(n*m),一定会超时。那么可以思考到本题的特殊性质:第一个是异或和,可以考虑用前缀和维护区间异或和;第二个是循环移动,由定义可得每移动 n 格就会回到原地,因此移动 cnt 格可以变为移动 cnt%n 格,再者观察可得,向右循环移动 cnt 格后,其实是把原数列分成了两部分:以 a[n] 为界限,右边是原来的 a[1]~a[n-cnt],而左边是原来的 a[n-cnt+1]~a[n]。这样变成了静态区间合并的问题,就可以用前缀和维护啦。(注意特判,而且要加上中间的 a[n]^a[1] )。

代码:(别忘开long long)

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],b[N],sum[N],cnt;
int get_sum(int l,int r) {
    return l==r?0:l==1?sum[r]:sum[r]-sum[l];
}
void solve() {
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%lld",&a[i]);
        if(i==1) sum[i]=0;
        else if(i==2) sum[i]=a[i-1]^a[i];
        else sum[i]=sum[i-1]+(a[i-1]^a[i]);
    }
    printf("%lld ",sum[n]);
    for(int i=1; i<=m; ++i) {
        scanf("%lld",&b[i]);
        cnt=(cnt+b[i]%n)%n;
        if(cnt==0) printf("%lld ",sum[n]);
        else printf("%lld ",get_sum(1,n-cnt)+get_sum(n-cnt+1,n)+(a[1]^a[n]));
    }
}
signed main() {
    solve();
    return 0;
}

3.C-最大公约数:https://ac.nowcoder.com/acm/contest/20102/C

解析:小学奥数题。如果暴力枚举任意两个数,显然只有20分,那么可以考虑逆向思维--枚举所有可能的公因数,找到其中合法的最大的那一个;也就是从公因数出发,找到要选的两个数。显然不管如何选择这两个数,他们的最大公因数一定在 [1,r] 之间。设选择的最大公因数为 i ,要找到两个数为 a 和 b (a < b)。最大公因数的定义即为两者共同的因数,那么显然 a, b 都是 i 的倍数即可。为了保证其在区间[l,r]之内,可以考虑最小和最大的情况,也就是距离 l 最近且大于 l 的第一个 i 的倍数,和距离 r 最近且小于 r 的第一关 i 的倍数。数学表达即为:a = ceil(l/i) * i , b = floor(r/i) * i .如果 a, b 均在区间内且 a < b,就可以认为此 i 合法,选最大的即可。

代码:

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
const int N=1e7+3;
int l,r,ans;
void solve() {
    scanf("%d%d",&l,&r);
    for(int i=r; i>=1; --i) {
        int a=(l%i==0?l/i:l/i+1)*i,b=r/i*i;
        if(a<b&&a>=l&&a<=r&&b>=l&&b<=r) {
            ans=i;
            break;
        }
    }
    printf("%d",ans);
}
int main() {
    solve();
    return 0;
}

4.D-波浪:https://ac.nowcoder.com/acm/contest/20102#question

解析:所谓“波浪数组”,体现在图形上就是一“峰”一“谷”交替,“峰”高“谷”低。如何将一个图形改为“峰谷”形式?从前向后依次修改,首先要确定起始点到底是“峰”还是“谷”,这样才能决定下一步走向。由于两者并无交集,全集就是这两种情况分别讨论,看那个更优即可。那么什么时候需要修改呢?又怎样修改?显然,如果当前点是“谷”,那么它一定比上一个点低,所以如果大于等于就是不合法情况,重新把它按入谷底,送个最小值即可;同理,如果当前点是“峰”,那么它一定比上一个点高,所以如果小于等于就是不合法情况,重新把它抬入云霄,送个最大值即可。最后,如何判定当前是在“峰”还是“谷”呢?看起始点,分奇偶讨论(或者叫找规律)就完成了。

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5,MAX=0x3f3f3f3f,MIN=-MAX;
int n,a[N],a1[N],a2[N],ans1,ans2;
void solve() {
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]),a1[i]=a2[i]=a[i];
    if(n<=2) { //特判
        printf("0");
        return;
    }
    for(int i=2; i<=n; ++i) { //将起始点作为“峰”的情况,则第二个点为“谷”
        if(i%2==0&&a1[i]>=a1[i-1]) { //为“谷”时的不合法情况
            a1[i]=MIN;//修改为“谷”
            ++ans1;//统计这次修改
        }
        if(i%2==1&&a1[i]<=a1[i-1]) { //为“峰”时的不合法情况
            a1[i]=MAX;//修改为“峰”
            ++ans1;//统计这次修改
        }
    }
    for(int i=2; i<=n; ++i) { //将起始点作为“谷”的情况,则第二个点为“峰”
        if(i%2==1&&a2[i]>=a2[i-1]) { //为“谷”时的不合法情况
            a2[i]=MIN;//修改为“谷”
            ++ans2;//统计这次修改
        }
        if(i%2==0&&a2[i]<=a2[i-1]) { //为“峰”时的不合法情况
            a2[i]=MAX;//修改为“峰”
            ++ans2;//统计这次修改
        }
    }
    printf("%d",min(ans1,ans2));//两种情况无交集,取个最小值即可
}
int main() {
    solve();
    return 0;
}

咳咳,点个赞再走吧~

0条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐