我好失败啊,Div2只能做3、4题,还天天掉rating,丢人

10-6 Codeforces Round #439 (Div. 2)

A. The Artful Expedient

意思是给出两个数组,让你判断
xor
xor 的对数
本来想着打的算法来着,结果后面发现
将式子变化一下
那么就有 xor
xor
那么就说明每一个合法的对,能够贡献的就是2对
所以一定是偶数

B - The Eternal Immortality

就是求的个位数字
可以发现如果有因子10末位就一定是0那么判断一下间距是否大于10即可,否则就模拟一下

C - The Intriguing Obsession

计数题天天爆炸啊……
给你三种颜色的岛,实际是问有多少种边的组成方式
总共就有3种边
之间建条边的方案数

算出每种边的方案全部乘起来即可

10-15 Codeforces Round #440 (Div. 2)

A. Search for Pretty Integers

题意不好描述
判有没有重复,如果有,输出最小的重复的数否则输出AB数组中最小值组成的最小整数

B. Maximum of Maximums of Minimums

给出个整数,问将其划分成段,使每一段最小值中的最大值最大
分类讨论
如果输出最小值
如果输出
如果输出最大值
貌似挺显然的……

C. Maximum splitting

给出一个,使这个分解成最多的合数的和,求最多的数量是多少
观察样例可得,尽可能拆成4的组合,如果只能取6那就取6,如果是奇数就取9,这样是最优的,剩下的情况就是-1了

10-16 Codeforces Round #441 (Div. 2)

暂时先放着,等到时候做完了再来写

11-17 Codeforces Round #446 (Div. 2)

A.Greed

问有n个水桶,每一个有的水量,能装
问最终能否将所有的水装入两个桶
考虑是液体,那么只需求出,然后将排成降序只要比较的大小即可

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 100000 + 5;
int n;
int Max_1,Max_2;
LL A[maxn];
LL B[maxn];
LL Sum;
int main(int argc, char const *argv[]) {
    cin >> n;
    if(n == 2){ cout << "YES\n"; return 0;}
    for(int i = 1;i <= n; i++) cin >> A[i] , Sum += A[i];
    for(int i = 1;i <= n; i++) {
        cin >> B[i];
        if(B[i] > Max_1){
            Max_2 = Max_1;
            Max_1 = B[i];
            continue;
        }
        if(B[i] > Max_2)
            Max_2 = B[i];
    }
    if(Sum <= Max_2 + Max_1) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

B.Wrath

给出n个人,每一个能杀死他前面的标号大于等于的人,问最后有多少人存活
大概就是差分一下,给左端点-1,右端点+1,在最后的区间统计0的个数

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 5;
#define LL long long
LL n,ans;
LL A[maxn];
LL cnt[maxn];
int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1;i <= n; i++){
        cin >> A[i];
        cnt[max(1ll,i - A[i])] --;
        cnt[i] ++;
    }
    for(int i = 1;i <= n; i++){
        cnt[i] = cnt[i - 1] + cnt[i];
        if(cnt[i] >= 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

C.Pride

给出n个数,每次操作可以将相邻的两个数之中的一个变成他们的gcd,问最小步数变成全1
考虑找1,如果已经有个1,那答案就是
然后再考虑在区间gcd里找一,枚举左端点,和右端点,维护区间gcd,找到最小的区间长度使得gcd为1,然后答案就是

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000 + 5;
int n,cnt;
int Min = maxn;
int A[maxn];
int gcd(int m , int n){ return n == 0 ? m : gcd(n , m % n); }

int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> A[i];
        if(A[i] == 1) cnt ++;
    }
    if(cnt > 0){ cout << n - cnt << endl; return 0; }
    for (int i = 1 ; i <= n ; i++) {
        int G = A[i];
        for(int j = i + 1;j <= n; j++){
            G = gcd(G , A[j]);
            if(G == 1){
                if(j - i < Min){
                    Min = j - i;
                    break;
                }
            }
        }
    }
    if(Min == maxn) cout << "-1\n" << endl;
    else cout << n + Min - 1 << endl;
    return 0;
}

D.Gluttony

给出n个数,问是否有一种排列能满足

可以将原数组排序后,把每一个位置都换上rank比他高一位的,这样就可以满足条件,具体证明见官方证明

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20 + 5;
int n;
int A[maxn],B[maxn],Ans[maxn];
int comp(const int &x,const int &y){ return A[x] < A[y];}
int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1 ; i <= n ; i++) cin >> A[i] , B[i] = i;
    sort(B + 1, B + 1 + n , comp);
    for (int i = 1 ; i <= n ; i++) Ans[ B[i] ] = A[ B[i % n + 1] ];
    for (int i = 1 ; i <= n ; i++) cout << Ans[i] << ' '; cout << endl;
    return 0;
}

12-3 GoodBye 2017

A.New Year and Counting Cards

给出一个字符串,数其中元音和奇数个数

B.New Year and Buggy Bot

给出一张地图和一个操作序列,有多少0,1,2,3映射方向的方式使机器人不出界不碰到障碍物并到达目的地,发现0,1,2,3的全排列个数只有24,直接dfs就好了

C.New Year and Curling

给出n个圆的x坐标,然后圆会从最高点掉下来,直到与坐标轴或另外的圆相接触为止,求每一个圆的y坐标
发现两个圆直接互相影响只会出现在时,然后根据相切条件勾股一下就可以得出记录下就好了

1 对 “Codeforces Div2 总结”的想法;

发表评论

电子邮件地址不会被公开。 必填项已用*标注