ABC367

A - Shout Everyday ↗#

Problem Statement#

Takahashi goes to bed at B o’clock and wakes up at C o’clock. You need to check whether he is awake at A o’clock.

Solution#

if $b < c$, then you just have to check whether $b <= a <= c$

if $b > c$, you can just let $c += 24$, $a += 24$ (if $a < b$)

Code#

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(b <= c) {
        if(a >= b && a <= c) {
            printf("No");
            return 0;
        }
    } else {
        c += 24;
        if(a < b) a += 24;
        if(a >= b && a <= c) {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}

B - Cut .0 ↗#

Problem Statemen#

give you a number $X$, print $X$ under the following conditions

• The decimal part must not have trailing 0s
• There must not be an unnecessary trailing decimal point

Solution#

Due to the characteristics of C++, you can just cin >> x and then cout << x

Code#

#include<bits/stdc++.h>
using namespace std;
int main() {
    double a;
    cin >> a;
    cout << a;
    return 0;
}

C - Enumerate Sequences ↗#

Problem Statement#

Print all sequences of length N that satisfy the following conditions

• the $1\leq a[i]\leq R_i$
• $\sum a[i]$ is a multiple of $K$

Solution#

Since $N, K, R_i$ is very small, we can just use dfs

Code#

#include<bits/stdc++.h>
#define N 250
using namespace std;
int n, K, a[N], b[N];
void dfs(int gs, int o) {
    if(gs == n + 1) {
        if(!o) {
            for(int i = 1; i <= n; i ++) printf("%d ", b[i]); printf("\n");
        }
        return ;
    }
    for(int i = 1; i <= a[gs]; i ++) {
        b[gs] = i;
        dfs(gs + 1, (o + i) % K);
    }
}
int main() {
    scanf("%d%d", &n, &K);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    dfs(1, 0);
    return 0;
}

D - Pedometer ↗#

Problem Statement#

give you a circle with $N$ key point, numbered in clockwise order. From point $i$, one needs to walk $A_i$ clockwise to reach the next point in clockwise direction.

Given $m$, find the number of point pairs $(s,t)$ requires $s \neq t$, that satisfy the distance from $s$ to $t$ in clockwise direction is a multiple of $m$

Solution#

Consider breaking the ring into a $2n$ chain

Use a bucket with range of $[0, m)$ to count the remainders. Each time the end point moves to the right, add the remainder of its current position to the bucket and delete the remainder of its position before it when around the circle.Add up all the number of remainders in the bucket that are the same as current number to get the answer.

Code#

#include<bits/stdc++.h>
#define N 2000050
using namespace std;
int n, m, a[N], b[N], s[N];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), a[n + i] = a[i];
    long long ans = 0;
    for(int i = 1; i < n + n; i ++) {
        if(i > n) b[s[i - n]] --;
        s[i] = (s[i - 1] + a[i]) % m;
        if(i >= n) ans += b[s[i]];
        b[s[i]] ++;
        // printf("%lld ", ans);
    }
    // for(int i = 1; i <= n + n; i ++) printf("%d ", s[i]); printf("\n");
    printf("%lld", ans);
    return 0;
}

E - Permute K times ↗#

Problem Statement#

given a sequnce $X$ of length $N$, ($1 \le X_i \le N$). Print the result of performing the following operation $K$ times on $A$

• replace $A$ with $B$ such that $B_i = A_{X_i}$

$1\leq N \leq 2\times 10^5, 0\le K \le 10^{18}$

Solution#

Consider $1 \sim n$ as nodes in a graph, with a directed edge from each $i$ to the corresponding $X_i$, and each node has exactly one outgoing edge(base-ring inward forest). And the problem can be transformed into a “k-level ancestor” problem.

This problem can be solved using the doubling algorithm.

Code#

#include<bits/stdc++.h>
#define N 200050
using namespace std;
int n, fa[N][66], a[N];
long long k;
int main() {
    scanf("%d%lld", &n, &k); 
    for(int i = 1; i <= n; i ++) scanf("%d", &fa[i][0]);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int j = 1; j <= 60; j ++) 
        for(int i = 1; i <= n; i ++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for(int i = 1; i <= n; i ++) {
        int x = i;
        for(int j = 60; j >= 0; j --)
            if((k >> j) & 1) x = fa[x][j];
        printf("%d ", a[x]);
    }
    return 0;
}

F - Rearrange Query ↗#

Problem Statement#

given two sequences $a_i, b_i$ of length $N$

Answer $q$ queries, for each query, you are given $l,r,L,R$, and need to determine whether the subsequence of $a$,($a_l,....,a_r$) can be rearranged to match the subsequence of $b$, ($b_L,....,b_R$).

Solution#

There is a very common trick.

Assign a random number $0\le z_i < L$ for each $i$ , where $L$ is a large number (often $2^{63} - 1$). Let $a_i = z_{a_i}$, and use prefix sums.

If the sums do not match, the answer is No, otherwise is probably Yes.

Code#

#include<bits/stdc++.h>
#include <random>
#define ull unsigned long long
#define N 2000050
using namespace std;
ull ha[N], sa[N], sb[N];
int n, m, a[N], b[N];
int main() {
    std::mt19937_64 rng;
    rng.seed(114514);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
    for(int i = 1; i <= n; i ++) ha[i] = rand();
    for(int i = 1; i <= n; i ++) {
        sa[i] = sa[i - 1] + ha[a[i]];
        sb[i] = sb[i - 1] + ha[b[i]];
    }
    while(m --) {
        int l, r, ll, rr;
        scanf("%d%d%d%d", &l, &r, &ll, &rr);
        if((sa[r] - sa[l - 1]) == (sb[rr] - sb[ll - 1])) 
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

G - Sum of (XOR^K or 0) ↗#

Problem Statement#

given $N,M,K$, and a sequenc $A$, $0 \le A_i < 2^{20}$ $B$ is a non-empty subsequnce of A,

Find the sum of all $B$, modulo $998244353$

$\large \sum\limits_{|B|\text{ is a multiple of M}} (\otimes B_i)^k$

Solution#

to be continued…