[title] Atcoder ExaWizards 2019 & KEYENCE 2019

ExaWizards 2019:

C.

Note that the operation of moving left and right will not change the relative position of the magic image, so if the magic image in position a will finally fall out from the left, all the magic images on the left of a will fall out from its left. Through two points, find the magic image falling from the left on the far right, the magic image falling from the right on the far left, and the magic image in the middle will be retained.

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000
int n, Q, d[maxn], ansl, ansr;
char s[maxn], c[maxn];

bool Checkl(int x) {
    for(int i = 1; i <= Q; i ++)
        if(c[i] == s[x]) {
            x += d[i];
            if(x <= 0) return 1;
            if(x >= n + 1) return 0;
        }
    return 0;
}

bool Checkr(int x) {
    for(int i = 1; i <= Q; i ++) 
        if(c[i] == s[x]) {
            x += d[i];
            if(x >= n + 1) return 1;
            if(x <= 0) return 0;
        }
    return 0;
}

int main() {
    cin >> n >> Q;
    scanf("%s", s + 1);
    for(int i = 1; i <= Q; i ++) {
        char t;
        scanf(" %c %c", &c[i], &t);
        if(t == 'L') d[i] = -1; else d[i] = 1;
    }
    int l = 1, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(mid + 1 <= r) mid += 1;
        if(Checkl(mid)) l = mid;
        else r = mid - 1;
    }
    if(Checkl(l)) ansl = l;
    else ansl = 0;
    l = 1, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(Checkr(mid)) r = mid;
        else l = mid + 1;
    }
    if(Checkr(l)) ansr = l;
    else ansr = n + 1;
    printf("%d", ansr - 1 - ansl);
    return 0;
}

D.

After sorting all elements from small to large, put them into the operation sequence from large. Then the current largest element will have an impact on the current x on the blackboard only if it is placed in the first empty position of the current operation sequence (otherwise, x will take the modulus of a smaller number before this number, and this large number will lose its meaning). Set dp[i][j] as the number of schemes with X as j on the blackboard after the first I number (in reverse order), and transfer it in two cases: whether the i - 1 number is placed in the first position or the back position.

#include <bits/stdc++.h>
using namespace std;
#define maxn 105000
#define mod 1000000007
int n, X, ans, a[maxn], f[2][maxn]; 

int read() {
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void Add(int &a, int b) {
    a += b; if(a >= mod) a -= mod;
}

int mul(int a, int b) {
    return 1ll * a * b % mod;
}

int main() {
    n = read(), X = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    sort(a + 1, a + 1 + n);
    int now = 1, nxt = 0;
    f[now][X] = 1;
    for(int i = n + 1; i > 1; i --) {
        for(int j = X; j >= 0; j --) f[nxt][j] = 0;
        for(int j = X; j >= 0; j --)
            if(f[now][j]) {
                Add(f[nxt][j % a[i - 1]], f[now][j]);
                Add(f[nxt][j], mul(f[now][j], (i - 2)));
            }
        swap(nxt, now);
    }
    for(int i = 0; i <= X; i ++)
        Add(ans, mul(f[now][i], i));
    printf("%d\n", ans);
}

E.

Enumerate the last continuous balls of the same color, and the probability of each ball in the front is one-half, and the probability of each ball in the back is one. Each ball in front is equivalent and each ball in the back is equivalent, so the total number of sequences * probability is the contribution to the probability of a position. Segment tree is used for interval addition.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 3000000
int B, W, inv2, ppow[maxn], tag[maxn], t[maxn], fac[maxn], finv[maxn];

int read() {
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

int add(int a, int b) {
    a += b; if(a >= mod) a -= mod;
    return a;
}

void Add(int &a, int b) {
    a += b; if(a >= mod) a -= mod;
}

int mul(int a, int b) {
    return 1ll * a * b % mod;
}

int Qpow(int x, int t) {
    int base = 1;
    for(; t; t >>= 1, x = mul(x, x))
        if(t & 1) base = mul(base, x);
    return base;
}

int C(int m, int n) {
    if(n < m) return 0;
    if(n < 0 || m < 0) return 0;
    return mul(fac[n], mul(finv[m], finv[n - m]));
}

void Push_down(int p, int l, int r) {
    if(!tag[p]) return;
    int mid = (l + r) >> 1;
    Add(tag[p << 1], tag[p]); Add(tag[p << 1 | 1], tag[p]);
    Add(t[p << 1], mul(tag[p], mid - l + 1));
    Add(t[p << 1 | 1], mul(tag[p], r - mid));
    tag[p] = 0;
    return;
}

void Mod(int p, int l, int r, int L, int R, int x) {
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        Add(t[p], mul(x, r - l + 1));
        Add(tag[p], x);    
        return;
    }
    Push_down(p, l, r);
    int mid = (l + r) >> 1;
    Mod(p << 1, l, mid, L, R, x);
    Mod(p << 1 | 1, mid + 1, r , L, R, x);
    t[p] = add(t[p << 1], t[p << 1 | 1]);
}

void Print(int p, int l, int r) {
    if(l == r) {
        printf("%d\n", t[p]);
        return;
    }
    int mid = (l + r) >> 1;
    Push_down(p, l, r);
    Print(p << 1, l, mid);
    Print(p << 1 | 1, mid + 1, r);
}

int main() {
    B = read(), W = read(); inv2 = Qpow(2, mod - 2); 
    fac[0] = finv[0] = ppow[0] = 1; int n = B + W;
    for(int i = 1; i <= n; i ++) ppow[i] = mul(ppow[i - 1], inv2);
    for(int i = 1; i <= n; i ++) fac[i] = mul(fac[i - 1], i);
    for(int i = 1; i <= n; i ++) finv[i] = Qpow(fac[i], mod - 2);
    for(int i = 1; i <= B; i ++) {
        int x = B - i, y = W;
        Mod(1, 1, n, n - i + 1, n, mul(C(x, x + y - 1), ppow[x + y]));
        if(x) Mod(1, 1, n, 1, n - i - 1, mul(C(y - 1, x + y - 2), ppow[x + y]));
    }
    for(int i = 1; i <= W; i ++) {
        int x = B, y = W - i;
        if(B) Mod(1, 1, n, 1, n - i - 1, mul(C(y, x + y - 2), ppow[x + y]));
        if(B) Mod(1, 1, n, n - i, n - i, mul(C(y, x + y - 1), ppow[x + y]));
    }
    Print(1, 1, n);
    return 0;
}

KEYENCE 2019:

D.

From big to small. If the maximum value of a row or column has been determined when x is processed, we call such a row or column determined row / determined column. If a number is the largest in both rows and columns, the position of the number has been determined. If a number is only the largest row, it indicates that it should appear in the determined column in the row. Each determined column is equivalent and can be placed at will. (the same is true only for the largest column). If a number is neither, it should appear at the junction of the determined row and the determined column (all positions are equivalent). Use the multiplication principle to calculate.

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define mod 1000000007
#define maxn 1200000
int n, m, markl[N], markr[N], L[maxn], R[maxn], cntl, cntr, ans = 1, tot;

int read() {
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

int mul(int x, int y) {
    return 1ll * x * y % mod;
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i ++) {
        int x = read();
        R[x] = i;
    }
    for(int i = 1; i <= m; i ++) {
        int x = read();
        L[x] = i;
    }
    for(int i = n * m; i >= 1; i --) {
        if(L[i] && R[i]) {
            if(markl[L[i]] || markr[R[i]]) {
                printf("0\n");
                exit(0);
            }
            markl[L[i]] = markr[R[i]] = 1;
            tot += cntl + cntr;
            cntl ++, cntr ++;
        }
        else if(L[i]) {
            if(markl[L[i]]) {
                printf("0\n");
                exit(0);
            }
            markl[L[i]] = 1; cntl ++;
            tot += cntr - 1;
            ans = mul(ans, cntr); 
        }
        else if(R[i]) {
            if(markr[R[i]]) {
                printf("0\n");
                exit(0);
            }
            markr[R[i]] = 1; cntr ++;
            tot += cntl - 1;
            ans = mul(ans, cntl);
        }
        else {
            ans = mul(ans, tot);
            tot -= 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

E

Analyze what kind of edge will not appear in the minimum spanning tree. If there are several edges that can connect I and j, and the weights of these edges are less than or equal to the edges between I and j, the edges between I and J will not appear in the minimum spanning tree. Considering divide and conquer, each time the current layer only considers the connection between the left point and the right point. Then let f[i] = a[i] - D * i, g[i] = a[i] + D * i, then the weight of an edge between I and J (I is the left point, j is the right point) is f[i]+g[j], let i1 be the point with the smallest f[i], and j1 be the point with the smallest g[j]. Then if I is not equal to i1 and j is not equal to j1, then f[i]+g[j1],f[i1]+g[j],f[i1]+g[j1] these three edges are less than or equal to f[i]+g[j]. So the edges between I and J can be ignored. Then each layer only needs to add i = i1 or j = j1 edges, a total of nlogn edges. Then sort to find the complexity of the minimum spanning tree, which is \ (nlog^{2}n \).

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 10000000
int n, D, cnt, fa[maxn], a[maxn]; 
LL ans, f[maxn], g[maxn];

struct edge {
    int u, v; LL w;
    edge(int _u, int _v, LL _w) {
        u = _u, v = _v, w = _w;
    }
    friend bool operator <(edge a, edge b) {
        return a.w < b.w;
    }
    friend bool operator >(edge a, edge b) {
        return a.w > b.w;
    }
}; priority_queue <edge, vector<edge>, greater<edge> > q;

int read() {
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;  
}

int find(int u) {
    if(fa[u] != u) return fa[u] = find(fa[u]);
    else return u;
}

void Div_Con(int l, int r) {
    if(l >= r) return;
    int mid = (l + r) >> 1;
    int i0 = 0, j0 = 0;
    for(int i = l; i <= mid; i ++) if((!i0) || (f[i] < f[i0])) i0 = i;
    for(int i = mid + 1; i <= r; i ++) if((!j0) || (g[i] < g[j0])) j0 = i;
    for(int i = l; i <= mid; i ++)
        if(i != i0) q.push(edge(i, j0, f[i] + g[j0]));
    for(int i = mid + 1; i <= r; i ++)
        q.push(edge(i0, i, f[i0] + g[i]));    
    Div_Con(l, mid); Div_Con(mid + 1, r);
}

signed main() {
    n = read(), D = read(); 
    for(int i = 1; i <= n; i ++) a[i] = read(), fa[i] = i;
    for(int i = 1; i <= n; i ++) f[i] = 1ll * a[i] - 1ll * i * D;
    for(int i = 1; i <= n; i ++) g[i] = 1ll * a[i] + 1ll * i * D;
    Div_Con(1, n);
    while(!q.empty() && (cnt < (n - 1))) {
        edge t = q.top(); q.pop();
        int fu = find(t.u), fv = find(t.v);
        if(fu != fv) ans += t.w, fa[fu] = fv, cnt ++;
    }
    printf("%lld\n", ans);
    return 0;
}

 

Posted by otterbield on Wed, 11 May 2022 16:15:17 +0300