Codeforces Round #827 (Div. 4) 复盘＋题解

原比赛链接

复盘：

ABC签到，手速太慢了。

D捣鼓了好久才想起来从更小的值域出发去做。

E简单二分答案。

然后就time out了。D题搞错方向浪费太久时间了。

F思维题，考虑到初值、字符集，然后是$\text{rearranged}$的，情况就很简单。

G简单位性质，拐一个弯就能想到了。

题解

D.Coprime

题意简述

给定正整数数组$a$，长度$2e5$，值域$1\le a_i \le 1000$，求最大的$i+j$满足$a_i$和$a_j$互质。

分析做法

①预处理得到$1000$以内的$gcd[i][j]$和$coprime[i][j]$。

②读入数组，对于每个$a_i$，尝试用$i$对$id[a_i]$求$\max$并更新。

③枚举$x$和$y$（$1\sim1000$），如果$id[x]$和$id[y]$有值，且$x$和$y$互质，那么尝试用$id[x]+id[y]$对$ans$求$\max$并更新。

注：枚举$i+j$和$i$会$T$掉。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int N = 2e5;

const int M = 1000;

    int gcd[M + 3][M + 3];

    int n, a[N + 3];

    int id[M + 3];

int fgcd(int a, int b){

    if(a >= b)

        return gcd[a][b];

    return gcd[b][a];

}

bool cop(int a, int b){

    return fgcd(a, b) == 1;

}

void sol(){

    scanf("%d", &n);

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

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

    memset(id, 0, sizeof id);

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

        id[a[i]] = max(id[a[i]], i);

    int ans = -1;

    for(int x = 1; x <= M; x++)

        for(int y = 1; y <= M; y++){

            if(id[x] > 0 && id[y] > 0 && fgcd(x, y) == 1)

                ans = max(ans, id[x] + id[y]);

        }

    printf("%d\n", ans);

}

int main(){

    int a, b, r;

    for(int i = 1; i <= M; i++)

        for(int j = 1; j <= i; j++){

            a = i;

            b = j;

            r = a % b;

            while(r > 0){

                a = b;

                b = r;

                r = a % b;

            }

            gcd[i][j] = b;

        }

    int T;

    scanf("%d", &T);

    while(T--)

        sol();

    return 0;

}

E.Scuza

题意简述

给定每个台阶之间的高度差（台阶数量$2e5$，台阶高度$1e9$）。多次询问，给出腿长$k$，从头开始登台阶，问最多上到多高？（$k\ge a_i$才能登上这个台阶）

分析做法

记得开$\mathrm{long\,long}$存数值。

设$premax_i=\mathop{\max}\limits_{1\le j \le i}\{a_j\}$，则$f(i)=[k\ge premax_i]$在$i\in [1,n]$上是单调的，可以二分得到能上几个台阶，预处理前缀最大值和前缀和就行。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 2e5;

    int n, q;

    LL pmax[N + 3], sum[N + 3];

void sol(){

    scanf("%d%d", &n, &q);

    LL k;

    pmax[0] = sum[0] = 0;

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

        scanf("%lld", &k);

        pmax[i] = max(pmax[i - 1], k);

        sum[i] = sum[i - 1] + k;

    }

    pmax[n + 1] = 1e9 + 1;

//

//    while(q--){

//        scanf("%lld", &k);

//

//

//        for(int i = 1; i <= n + 1; i++)

//            if(k < pmax[i]){

//                printf("%lld ", sum[i - 1]);

//                break;

//

//            }

//

//    }

    int l, r, mid, ans;

    while(q--){

        scanf("%lld", &k);

        l = 1;

        r = n + 1;

        ans = 0;

        while(l <= r){

            mid = (l + r) >> 1;

            if(pmax[mid] <= k){

                l = mid + 1;

                ans = mid;

            }

            else

                r = mid - 1;

        }

        printf("%lld ", sum[ans]);

    }

    putchar('\n');

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--)

        sol();

    return 0;

}

F.Smaller

题意简述

初始两个字符串$s=t=\mathtt{a}$，然后$q$次操作，分别给$s$或$t$末尾加上$k$遍字符串$x$。

每次操作后，问能否重排$s$和$t$，使得$s$的字典序小于$t$。注意，操作影响会累积。

分析做法

因为$s$和$t$初始有一个$\mathtt{a}$，所以

①如果$t$中出现了非$\mathtt{a}$的字符，则重排时将其排在第一位，就能使得$s<t$，输出$\mathbf{YES}$

②保证$t$全部为$\mathtt{a}$，如果$s$中含有非$\mathtt{a}$的字符……

$\mathrm{i.}$要么$s$中$\mathtt{a}$个数少于$t$，情况形如$\mathtt{aab}>\mathtt{aaa}$

$\mathrm{ii.}$要么$s$中$\mathtt{a}$个数等于$t$，情况形如$\mathtt{aaab}>\mathtt{aaa}$

$\mathrm{iii.}$要么$s$中$\mathtt{a}$个数多于$t$，情况形如$\mathtt{aaaab}>\mathtt{aaa}$

所以一定输出$\mathbf{NO}$

③保证$s$和$t$全部为$\mathtt{a}$，那么如果$s$中$\mathtt{a}$个数少于$t$结果为$\mathbf{YES}$，否则为$\mathbf{NO}$。

所以实际上只需要维护$f[1]$和$f[2]$分别表示$s$和$t$是否只含$\mathtt{a}$，$c[1]$和$c[2]$分别表示$s$和$t$含有$\mathtt{a}$的个数即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5;

    char s[N + 3];

void sol(){

    int q, k, d;

    bool f[3];            //only a?

    LL c[3];            //cnt of a

    f[1] = f[2] = true;

    c[1] = c[2] = 1LL;

    scanf("%d\n", &q);

    while(q--){

        scanf("%d %d %s", &d, &k, s);

        if(f[d])

            for(int i = 0; s[i]; i++)

                if(s[i] != 'a'){

                    f[d] = false;

                    break;

                }

                else

                    c[d] += 1LL * k;

        if(!f[2])

            printf("YES\n");

        else

            if(f[1] && c[1] < c[2])

                printf("YES\n");

            else

                printf("NO\n");

    }

}

int main(){

    int T;

    scanf("%d\n", &T);

    while(T--)

        sol();

    return 0;

}

G.Orray

题意简述

给非负整数数列$a$，重排$a$，字典序地最大化其前缀按位$\mathrm{OR}$数列。

分析做法

首先把最大值排到第一位，这样就“点亮”了一些二进制位。

接下来每步，把“已点亮”的位屏蔽之后，还没用上的元素之中找出最大值，又“点亮”了一些二进制位。

简单实现：使用$\mathrm{unsigned\,int}$类存储$a$，和“掩码”$mask$；$visit[]$数组。

每轮循环找个最大值填到下一个位置，如果没找到新的，说明没有新的二进制位可以点亮，直接把剩下的元素随便填上。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef unsigned int UI;

const int N = 2e5;

const int inf = 1e9 + 1;

    int n;

    UI a[N + 3], b[N + 3];                    //b save id

    bool vis[N + 3];

void sol(){

    scanf("%d", &n);

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

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

    int bpos = 0, pic;

    UI mask = 0;

    memset(vis, 0, sizeof vis);

    while(bpos <= n){

        pic = -1;

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

            if(!vis[i] && (a[i] & ~mask) > 0)

                if(pic == -1 || (a[i] & ~mask) > (a[pic] & ~mask))

                    pic = i;

        if(pic == -1)

            break;

        vis[pic] = true;

        b[++bpos] = pic;

        mask |= a[pic];

    }

    for(int i = 1; i <= n && bpos < n; i++)

        if(!vis[i])

            b[++bpos] = i;

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

        printf("%d ", a[b[i]]);

    printf("\n");

}

int main(){

    int T;

    scanf("%d\n", &T);

    while(T--)

        sol();

    return 0;

}

巴特西

Codeforces Round #827 (Div. 4) 复盘＋题解

最新文章

热门文章