2021牛客OI赛前集训营-J组-3 解析

前言

这次的题目比较偏向数学。只需要把题意分析透彻，代码写出来只不过是时间的问题。

A 反码

题干：

鸡尾酒今天学习了原码反码补码的概念，现在他想要设计一个程序，能够自动把原码转换成反码。
原码转换成反码的规则：原码的第一位为符号位，若符号位为 0，则反码与原码相同。若符号位为 1，则符号位不变，将其他位全部取反。
但是写代码太累了，于是鸡尾酒将这个任务交给了你。

解析：

基础题

答案1：字符串写法

/*
 * @Link: https://ac.nowcoder.com/acm/contest/20102/A
 * @Date: 2021-10-09 18:37:57
 * @LastEditTime: 2021-10-09 18:44:11
 * @FilePath: \牛客\2021牛客OI赛前集训营-J\第三场\A 反码\anti_code.cpp
 * @Method: 
 */
#include <iostream>
using namespace std;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> s;
    if (s[0] == '0')
        cout << s;
    else
    {
        putchar('1');
        for (int i = 1; s[i]; i++)
            putchar(s[i] == '0' ? '1' : '0');
    }
    return 0;
}

答案1：简洁写法

/*
 * @Link: https://ac.nowcoder.com/acm/contest/20102/A
 * @Date: 2021-10-09 18:37:57
 * @LastEditTime: 2021-10-10 21:10:34
 * @FilePath: \牛客\2021牛客OI赛前集训营-J\第三场\A 反码\anti_code_easiest.cpp
 * @Method: 
 */
#include <iostream>
int o, x;
int main()
{
    scanf("%1d", &o);
    printf("%d", o);
    while (~scanf("%1d", &x))
        printf("%d", o ? !x : x);
    return 0;
}

B 异或

题干：

鸡尾酒获得了一个数组，他定义数组的价值为每个相邻元素异或之和。例如数组 [3,5,9] 的价值为 (3^5)+(5^9)=18 ，其中 ^ 为二进制中的异或运算。
现在他将数组向右进行 $mm$m 次向右循环移动，每次移动 $b_{i}b\_i$bi​ 位，循环移动都建立在上一次移动的基础上进行。现在他想考考你，每次循环移动过后，这个数组的价值为多少？
向右循环移动的定义：向右循环移动一位，数组中最右边的元素变成最左边的元素，其余元素全部向右移动一位。
例如数组 [1,2,3,4,5] 向右循环移动两位的结果是 [4,5,1,2,3]

解析：

这道题较简单，很多人给这道题打上前缀和的标签，其实前缀和都不需要。
这道题唯一的坑：
不开long long见祖宗
不开long long见祖宗
不开long long见祖宗

答案1(前缀和)：

#include <iostream>
#include <deque>
const int N = 1e5 + 9;
long long n, m, sum, a[N], b[N], ans[N];
std::deque <long long> deq; // 麻烦了点，这用不着deque
int main()
{
    scanf("%lld%lld", &n, &m);
    for (long long i = 1; i <= n; i++)
    {
        scanf("%lld", a + i);
        if (i > 1)
            deq.push_back(a[i-1] ^ a[i]), sum += (a[i-1] ^ a[i]);
    }
    deq.push_back(a[n] ^ a[1]), sum += (a[n] ^ a[1]);
    for (long long i = 1; i <= n; i++)
    {
        long long temp = *deq.rbegin();
        ans[i] = sum - temp; 
        deq.pop_back(); deq.push_front(temp);
    }
    printf("%lld ", ans[1]);
    for (long long i = 1; i <= m; i++)
    {
        scanf("%lld", b + i);
        b[i] += b[i-1]; b[i] %= n; // 求前缀和
        printf("%lld ", ans[b[i]+1]);
    }
    return 0;
}

答案2 简洁写法(某巨佬写的)：

/*
 * @Link: https://ac.nowcoder.com/acm/contest/20102/B
 * @Date: 2021-10-10 21:19:35
 * @LastEditTime: 2021-10-10 21:25:00
 * @FilePath: \牛客\2021牛客OI赛前集训营-J\第三场\B 异或\xor_easiest.cpp
 * @Method: 
 */
#include <iostream>
const int N = 1e5 + 9;
typedef long long LL;
LL a[N], sum[N], tot;
int main()
{
    int n, m, k;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%lld", a + i);
    for (int i = 0; i < n-1; i++)
        sum[i] = a[i] ^ a[i+1], tot += sum[i];
    sum[n-1] = a[n-1] ^ a[0], tot += sum[n-1];
    LL s = n - 1;
    printf("%lld ", tot - sum[s]);
    while (m--)
    {
        scanf("%d", &k);
        s = (s - k) % n;
        if (s < 0)
            s += n;
        printf("%lld ", tot - sum[s]);
    }
    return 0;
}

C 最大公约数

题干：

鸡尾酒的数学很差，他学了很长时间的最大公约数，终于有一天他会求最大公约数了。
于是他迫不及待地向你提问——给定数轴上的区间 [l,r]，你可以从中任选两个不相同的整数，求它们的最大公约数。请问它们的最大公约数最大为多少？

解析：

undefinded

答案：

D 划分

题干：

在 DOTA2 第八届国际邀请赛（TI8）中，选手 AME 操刀的水人在关键时刻释放了一个波浪的技能，扭转局势，帮助 OG 战队获得冠军。
为了纪念这一技能，我们引出一个“波浪数组”的概念，其定义如下：
对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大。
例如 [1,3,2,5,3,4] 就是一个波浪数组，而 [2,3,4,1,2] 则不是，因为第二个位置 3 比左边的数字 2 大，比右边的数字 4 小。
注意：根据定义，长度小于等于 2 的数组一定是波浪数组。
现在有一个长度为 n 的数组，你每次操作可以将任意一个位置的数字修改成任意一个新数字。我们想要将其变成一个波浪数组，请问最小的修改次数是几次？

解析：

undefinded

答案：

明天继续整理