Educational Codeforces Round 60 (Rated for Div. 2) 解题报告

A. Best Subsegment

给定一串数列, 求区间最大平均值

显然,最大的区间平均值可以就是数列中最大的那个,然后基于最大的点想两边枚举区间长度

#include <cstdio>
#include <algorithm>
inline int Max(int a, int b){return a > b? a: b;}
const int N = 1e5 + 1e4;
int n, max, max_id, len, rig, max_len;
int a[N];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        if(a[i] > max)
            max = a[i];
    }
    for(int i = 1; i <= n; i++){
        if(a[i] == max && ( a[i - 1] != max || i == 1 ) ){
            rig = i; len = 0;
            while( a[rig] == a[i] && rig <= n ){
                rig++; len++;
            }
            max_len = Max(len, max_len);
        }
    }
    printf("%d", max_len);
}

B. Emotes

总共 $n$ 个表情, 你需要输出一个长度为 $m$ 的长度序列,但是同一个表情不能连续出现 $k$ 次

排个序,每个周期按,最大的出现 $k$ 次,然后出现一次第二大的,枚举周期即可

#include <cstdio>
#include <algorithm>
const int N = 2e5 + 1e4;
int n, m, k, tmp;
long long ans;
int a[N];
bool cmp(int a, int b){
    return a > b;
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1, cmp);
    if( m <= k ){
        printf("%lld", 1LL * a[1] * m);
        return 0;
    }
    else {
        ans = 1LL * a[1] * k + (long long) a[2];
        ans *= (m / (k + 1) );
        m %= (k + 1);
        ans += 1LL * a[1] * m;
        printf("%lld", ans);
    }
}

C. Magic Ship

本来是到直接两点坐标差的绝对值之和就可以的

然后有洋流

我们设每一轮洋流为一个周期,然后二分最少需要多少周期

然后 $O(n)$ 判断不在整数周期内部的就可以

#include <cstdio>
inline long long Aabs(long long a){return a < 0? (0 - a): a;}
const long long N = 1e5 + 1e4;
long long x1, y1, x2, y2, dx, dy, n, tmp, ans, mid;
char str[N];
int main(){
    scanf("%lld%lld", &x1, &y1);
    scanf("%lld%lld", &x2, &y2);
    scanf("%lld", &n);
    scanf("%s", str + 1);
    for(long long i = 1; i <= n; i++){
        if(str[i] == 'U') dy++;
        if(str[i] == 'D') dy--;
        if(str[i] == 'L') dx--;
        if(str[i] == 'R') dx++;
    }
    long long left = 0, rig = (int)2e9;
    while(left <= rig){
        mid = (left + rig) >> 1;
        if( Aabs(x1 + dx * mid - x2) + Aabs(y1 + dy * mid - y2) <= n * mid ) rig = mid - 1;
        else left = mid + 1;
    }
    x1 += dx * rig;
    y1 += dy * rig;
    ans = n * rig;
    if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans){
        printf("%lld", ans);
        return 0;
    }
    for(long long i = 1; i <= n; i++){
        if(str[i] == 'U') y1++;
        if(str[i] == 'D') y1--;
        if(str[i] == 'L') x1--;
        if(str[i] == 'R') x1++;
        ans++;
        if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans ){
            printf("%lld", ans);
            return 0;
        }
    }
    printf("-1");
}


]]>

Codeforces Round #538 (Div. 2) 解题报告

A Got Any Grapes?

顺序判断即

比赛的时候忘记写 else 既然 PP 了,然后就 FST

#include <cstdio>
int an,dm,mi;
int gr,pu,bl;
int main(){
    scanf("%d%d%d", &an, &dm, &mi);
    scanf("%d%d%d", &gr, &pu, &bl);
    if(an > gr) {
        printf("NO\n");
        return 0;
    }
    else gr -= an;
    if(pu + gr < dm){
        printf("NO\n");
        return 0;
    }
    else {
        if(pu <= dm) {dm -= pu; pu = 0;}
        else {pu -= dm; dm = 0;}
        if(gr < dm) {
            printf("NO\n");
            return 0;
        }
        else gr -= dm;
    }
    if(gr + pu + bl < mi) printf("NO\n");
    else printf("YES\n");
}

B Yet Another Array Partitioning Task

反正最后还是要前$ m \times k $ 个数字

直接离散化,然后见当前区间有$ m $ 个就收

#include <cstdio>
#include <algorithm>
const long long N = 2e5 + 1e4;
struct node{
    long long now, id;
}b[N];
long long n, m, k, cnt, time;
long long a[N];
bool vis[N];
bool cmp(node a, node b){
    return a.now > b.now;
}
int main(){
    scanf("%lld%lld%lld", &n, &m, &k);
    for(long long i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        b[i].now = a[i], b[i].id = i;
    }
    std::sort(b + 1, b + n + 1, cmp);
    long long tmp = m * k;
    for(long long i = 1; i <= tmp; i++) vis[ b[i].id ] = true, cnt += b[i].now;
    printf("%lld\n",cnt);
    cnt = 0;
    for(long long i = 1; i <= n; i++){
        cnt += vis[i];
        if(cnt == m){
            time++;
            time < k && printf("%lld ",i);
            cnt = 0;
        }
    }
}

C. Trailing Loves (or L’oeufs?)

求 $ b $ 进制下 $ n! $ 的末尾的 0 的个数

显然我们要求中间乘出来有多少个$b$

接下来就是分解质因数,然后枚举求最小值即可

#include <cstdio>
#include <cmath>
const long long INF = 1e18 + 1e17;
inline long long Min(long long a, long long b){return a < b? a: b;}
struct node{
    long long now, cnt;
}pri[(int)(1e6)];
int pcnt;
long long n, b, tmp, cnt, ans = INF;
inline void get_pri(long long b){
    tmp = std::sqrt(b);
    for(long long i = 2; i <= tmp; i++){
        if(b % i == 0){
            pri[ ++pcnt ] = (node){i, 0};
            while(b % i == 0){
                pri[pcnt].cnt++;
                b/=i;
            }
        }
    }
    if(b != 1) pri[ ++pcnt ] = (node){b, 1};
}
int main(){
    scanf("%lld%lld", &n, &b);
    get_pri(b);
    for(int i = 1; i <= pcnt; i++){
        tmp = 1; cnt = 0;
        while(tmp * pri[i].now <= n){
            tmp *= pri[i].now;
            if(tmp < 0 || tmp % pri[i].now != 0) break;
            cnt += n / tmp;
        }
        ans = Min(ans, cnt/pri[i].cnt);
    }
    printf("%lld\n", ans);
}

D. Flood Fil

有一个非常显然的地方,就是我们每次有两个状态,当前联通部分向左对其或者想右对其

然后我们先把数列中的联通部分预处理出来,然后区间 dp 即可

#include <cstdio>
#include <cstring>
inline int Min(int a, int b){return a < b? a: b;}
const int N = 5100;
int n;
int a[N], l[N], r[N], f[N][N];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    l[1] = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] == a[i - 1]) l[i] = l[i - 1];
        else l[i] = i;
    }
    r[n] = n;
    for(int i = n - 1; i >= 1; i--){
        if(a[i] == a[i + 1]) r[i] = r[i + 1];
        else r[i] = i;
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = 1; i<= n;i ++) f[ l[i] ][ r[i] ] = 0;
    for(int len = 0; len < n; len++){
        for(int i = 1,j; i + len <= n; i++){
            j = i + len;
            if(i > 1 && j < n && a[i - 1] == a[j + 1])
                f[ l[i - 1] ][ r[j + 1] ] = Min(f[ l[i - 1] ][ r[j + 1] ],f[i][j] + 1);
            if(i > 1)
                f[ l[i - 1] ][j] = Min(f[ l[i - 1] ][j], f[i][j] + 1);
            if(j < n)
                f[i][ r[j + 1] ] = Min(f[i][ r[j + 1] ], f[i][j] + 1);
        }
    }
    printf("%d", f[1][n]);
}

E. Arithmetic Progression

交互题目,60次询问内知道当前乱序等差数列的首项和公差

先二分找最大的,然后random_shuffle随机化询问,求与最大项差的 gcd 即为公差

#include <cstdio>
#include <algorithm>
int gcd(int a, int b){return b? gcd(b ,a%b): a;}
inline int Min(int a, int b){return a < b? a: b;}
inline int Aabs(int a){return a < 0? (0 - a): a;}
const int N = 1e6 + 1e5;
int n, global_tmp, d, max, chance_cnt = 60;
int a[N];
inline bool has_num(int now){
    printf("> %d\n",now);
    fflush(stdout);
    scanf("%d", &global_tmp);
    chance_cnt--;
    return global_tmp;
}
inline int binary_search_max(int max_limit){
    int left = 0, rig = max_limit, mid, res;
    while(left <= rig){
        mid = (left + rig) >> 1;
        if( has_num(mid) ) left = mid + 1;
        else rig = mid - 1, res = mid;
    }
    return res;
}
int main(){
    scanf("%d", &n);
    max = binary_search_max(1e9);
    for(int i = 1; i <= n; i++) a[i] = i;
    for(int i = 1; i <= 5; i++) std::random_shuffle(a + 1, a + n + 1);
    for(int i = 1; i <= Min(n ,chance_cnt); i++){
        printf("? %d\n", a[i]);
        fflush(stdout);
        scanf("%d", &global_tmp);
        if(global_tmp == max) continue;
        if(d == 0) d = Aabs(max-global_tmp);
        d = gcd(d , Aabs(max-global_tmp));
    }
    fflush(stdout);
    printf("! %d %d\n", max - (n - 1) * d, d);
}

F. Please, another Queries on Array?

这个题目首先得知道$\varphi(n)$的求法

然后就是乘积线段树和或线段树维护一下

就没有然后了

#include <cstdio>
const int N = 4e5 + 1e4;
const long long mod = 1e9 + 7;
int n, q, x, y, z, pcnt;
int a[N];
long long p[310], pri[N], inv[310];
char op[10];
inline long long ksm(long long a, long long p){
    long long res = 1;
    while(p){
        if(p & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        p >>= 1;
    }
    return res;
}
inline void prime(){
    for(int i = 2; i <= 300; i++){
        for(int j = 1; j <= pcnt; j++)
            if(i % p[j] == 0) pri[i] |= pri[ p[j] ];
        if(pri[i] == 0) {p[++pcnt] = i; pri[i] = (1LL << (pcnt - 1LL));}
    }
}
inline void get_inv(){
    for(int i = 1; i <= pcnt; i++)
        inv[i] = ksm(p[i], mod - 2);
}
// Segment Tree Start
struct node{
    long long val,pri;
    void operator+= (const node &b){
        this -> val = (this -> val * b.val) % mod;
        pri |= b.pri;
    }
}tree[N << 2], lazy[N << 2];
inline void pushup(int now){
    tree[now].val = (tree[now << 1].val * tree[now << 1 | 1].val) % mod;
    tree[now].pri = tree[now << 1].pri | tree[now << 1 | 1].pri;
}
inline void pushdown(int now, int lson, int rson){
    if(lazy[now].pri != 0){
        tree[now << 1].val  =  (1LL * tree[now << 1].val * ksm(lazy[now].val, lson)) % mod;
        tree[now << 1 | 1].val  =  (1LL * tree[now << 1 | 1].val * ksm(lazy[now].val, rson)) % mod;
        tree[now << 1].pri |= lazy[now].pri;
        tree[now << 1 | 1].pri |= lazy[now].pri;
        lazy[now << 1].val = (1LL * lazy[now << 1].val * lazy[now].val) % mod;
        lazy[now << 1 | 1].val = (1LL * lazy[now << 1 | 1].val * lazy[now].val) % mod;
        lazy[now << 1].pri |= lazy[now].pri;
        lazy[now << 1 | 1].pri |= lazy[now].pri;
        lazy[now].val = 1LL; lazy[now].pri = 0;
    }
}
inline void query_mut(int now, int left, int rig, int from, int to, int val){
    if(from <= left && rig <= to){
        tree[now].val = (1LL * tree[now].val * ksm(val, (rig - left + 1LL))) % mod;
        tree[now].pri |= pri[val];
        lazy[now].val = (lazy[now].val * val) % mod;
        lazy[now].pri |= pri[val];
        return ;
    }
    int mid = (left + rig) >> 1;
    pushdown(now, mid - left + 1LL, rig - mid);
    if(from <= mid) query_mut(now << 1, left, mid, from, to, val);
    if(to > mid) query_mut(now << 1 | 1, mid + 1, rig, from, to, val);
    pushup(now);
}
inline node query_sum(int now, int left, int rig, int from, int to){
    if(from <= left && rig <= to) return tree[now];
    int mid = (left + rig) >> 1;
    node res = (node){1, 0};
    pushdown(now, mid - left + 1LL, rig - mid);
    if(from <= mid) res += query_sum(now << 1, left, mid, from, to);
    if(to > mid) res += query_sum(now << 1 | 1, mid + 1, rig, from, to);
    pushup(now);
    return res;
}
inline void build_tree(int now, int left, int rig){
    lazy[now].val = 1; lazy[now].pri = 0;
    if(left == rig){
        scanf("%lld", &tree[now].val);
        tree[now].pri = pri[ tree[now].val ];
        return ;
    }
    int mid = (left + rig) >> 1;
    build_tree(now << 1, left, mid);
    build_tree(now << 1 | 1, mid + 1, rig);
    pushup(now);
}
// Segment Tree End
int main(){
    prime();
    get_inv();
    scanf("%d%d", &n, &q);
    build_tree(1, 1, n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while(q--){
        scanf("%s", op);
        if(op[0] == 'M'){
            scanf("%d%d%d", &x, &y, &z);
            query_mut(1, 1, n, x, y, z);
        }
        else {
            scanf("%d%d", &x, &y);
            node tmp = query_sum(1, 1, n, x, y);
            for(int i = 1; i <= pcnt; i++){
                if((tmp.pri >> (i - 1LL)) & 1LL)
                    tmp.val = (((tmp.val * (p[i] - 1) ) % mod) * inv[i]) % mod;
            }
            printf("%lld\n", tmp.val);
        }
    }
}


]]>