Codeforces Round #682 (Div. 2)

目录

A. Specific Tastes of Andre

题意:

构造一个长度为n数组,使得数组的和能被n整除

思路:

输出数组全为1即可

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int t, n;
int main(){
    cin>>t;
    while(t--){
        cin >> n;
        for (int i = 1; i <= n;i++)
            cout << 1 << ' ';
        cout << endl;
    }
    return 0;
}

B. Valerii Against Everyone

大意:

给出 \(b_i 以及 a_i = 2^{b_i}\) ,问是否存在两个不交叉区间,使得两个区间 \(a_i\)的和相等。

思路:

需要考虑\(a_i\)的性质,因为\(a_i\)为2的幂次方,所以如果任意\(a_i\)相加的话,如果不是两个数直接相等,这两个区间和是不可能相等的,所以只需要找相等的\(a_i\)即可,也就是找相等的\(b_i\)

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int t, n,x,flag;
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        flag = 0;
        map<int,int> mp;
        for (int i = 0; i < n;i++){
            cin >> x;
            if(mp[x]==0){
                mp[x] = 1;
            }
            else{
                flag = 1;
            }
        }
        if(flag){
            cout << "YES" << endl;
        }
        else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

C. Engineer Artem

题意
对于一个矩阵,你可以对矩阵的每个元素选择是否加一,最后使得这个矩阵每个元素相邻不能有相同元素。
思路
对每一个元素,如果横坐标加纵坐标为偶数,就让这个元素变为偶数,如果横坐标加纵坐标为奇数,就让这个元素变为奇数,这样每个相邻元素都是奇数和偶数的关系,就不会出现相同的元素。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int t, n, m, a[105][105],cnt;

int main(){
    cin>>t;
    while(t--){
        cin >> n >> m;
        for (int i = 1; i <= n;i++){
            for (int j = 1; j<= m;j++){
                cin>>a[i][j];
                if((i+j)%2!=a[i][j]%2){
                    a[i][j]++;
                }
            }
        }
        for (int i = 1; i <= n;i++){
            for (int j = 1; j<= m;j++){
                cout << a[i][j] << ' ';
                }
                cout << endl;
            }
            
        }
    return 0;
}

D. Powerful Ksenia

大意:

给出一个数组,每次可以选取三个不同位置的元素,将他们赋值为这三个元素的异或和,问能否在n-1步之内将这个数组全部修改为相同的数字

思路:

考虑到当三个数分别为\(x,x,y\)时,相当于将y赋值给x的位置,所以我们可以先获得一些相同的元素,然后两两与另一个元素异或,最终使得整个数组赋值为相同的值。

当数组长度为奇数时,以上操作是始终可以实现的,选取的方式为:

首先选取1,2,3 然后选取3,4,5,然后选取5,6,7......得到形如:

\(xxyyzzz\)

的数组,然后选择1,2,n 然后选取3,4,n...... 最终将数组全部转化为z

可以发现需要操作的次数正好为n-1次

而对于偶数长度的数组,可以首先判断整个数组的异或和是否为0,如果为0则不能实现,因为仔细观察可以发现以上操作并不改变数组的异或和。如果可以实现,直接按照奇数的情况来实现即可。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n,a[N],sum;
int main(){
    cin >> n;
    for (int i = 1; i <= n;i++){
        cin >> a[i];
        sum ^= a[i];
    }
    if(n&1){
        cout << "YES" << endl;
        cout << n - 1 << endl;
        for (int i = 1; i <= (n - 1) / 2;i++){
            cout << 2 * (i - 1) + 1 << ' ' << 2 * (i - 1) + 2 << ' ' << 2 * (i - 1) + 3 << endl;
        }
        for (int i = 1; i <= (n - 1) / 2;i++){
            cout << 2 * (i - 1) + 1 << ' ' << 2 * (i - 1) + 2 << ' ' << n << endl;
        }
    }
    else{
        if(sum){
            cout << "NO" << endl;
        }
        else{
            cout << "YES" << endl;
            cout << n - 2 << endl;
            for (int i = 1; i <= (n - 2) / 2;i++){
            cout << 2 * (i - 1) + 1 << ' ' << 2 * (i - 1) + 2 << ' ' << 2 * (i - 1) + 3 << endl;
            }
            for (int i = 1; i <= (n - 2) / 2;i++){
                cout << 2 * (i - 1) + 1 << ' ' << 2 * (i - 1) + 2 << ' ' << n << endl;
            }
        }
    }
        return 0;
}

E. Yurii Can Do Everything

大意:

给出一个数组,对于对于一个子区间,定义满足如下条件的子区间为“好”区间:

1.子区间长度至少为3

2.子区间两端的异或和 等于 子区间除了两个端点以外所有元素的和

问该数组有多少“好”区间?

思路:

出题人说是暴力题....这是我没想到的,虽然\(n=2e5\),但是符合条件的区间很少,符合什么条件呢?

假设区间\([l,r]\)两侧元素\(a_l\)和\(a_r\)的二进制表示,其最高位分别是\(b_l\)和\(b_r\),那么区间内的元素相加,其和必然小于\(2^{max(b_l,b_r)+1}\),所以可以根据这个约束进行两遍暴力即可,先是从左往右暴力一遍,然后是从右往左暴力一遍,这样可以保证所有符合条件的区间都会被收录,另外在暴力的时候注意去重

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int n,a[N],res;
map<pair<int, int>, int> mp;
void solve1(){
    for (int i = 0; i < n-2;i++){
        int k;
        for (int j = 29; j >= 0;j--){
            if((1<<j)&a[i]){
                k = j;
                break;
            }
        }
        k++;
        long long sum = a[i+1];
        for (int j = i + 2; j < n;j++){
            if(sum==(a[i]^a[j])){
                res++;
                mp[{i, j}] = 1;
                //cout << i+1 << ' ' << j+1 << endl;
            }
            else
                sum += a[j];
            if(sum>=(1<<k)){
                break;
            }
        }
    }
}

void solve2(){
    for (int i = n; i >= 2;i--){
        int k;
        for (int j = 29; j >= 0;j--){
            if((1<<j)&a[i]){
                k = j;
                break;
            }
        }
        k++;
        long long sum = a[i-1];
        for (int j = i - 2; j >= 0;j--){
            if(sum==(a[i]^a[j])&&(mp[{j,i}]==0)){
                res++;
                //cout << j+1 << ' ' << i+1 << endl;
            }
            else
                sum += a[j];
            if(sum>=(1<<k)){
                break;
            }
        }
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n;i++){
        cin>>a[i];
    }
    solve1();
    solve2();
    cout << res << endl;
    return 0;
}

F. Olha and Igor

交互题,先鸽了~

上一篇:682. 棒球比赛


下一篇:Codeforces Round #682 (Div. 2)