C - Quả Cam Mandarina

Đề xuất một phương pháp khác với độ phức tạp \(\mathcal{O}(n \log n)\).

Đặt cho vị trí thứ \(i\), vị trí đầu tiên bên trái lớn hơn nó là \(L_i\), và vị trí đầu tiên bên phải lớn hơn nó là \(R_i\).

Ta nhận thấy rằng giá trị tối ưu cho vị trí \(i\) khi làm \(x\) chính là \((R_i-L_i-1)\times val_i\).

Có thể sử dụng danh sách liên kết đôi để xử lý, chi tiết xem trong code.

int n, arr[N], id[N], Nxt[N], Pre[N];
inline bool cmp(int A, int B) {return arr[A] == arr[B] ? A < B : arr[A] > arr[B];}
int main() {
    scanf("%d", &n);
    forn(i,1,n) scanf("%d", arr+i), Pre[i] = i-1, Nxt[i] = i+1, id[i] = i;
    int Ans = 0;
    sort(id+1, id+n+1, cmp);
    forn(i,1,n) {
        int l = Pre[id[i]], r = Nxt[id[i]];
        Nxt[l] = r,Pre[r] = l;
        Ans = Max(Ans, (r-l-1) * arr[id[i]]);
    }
    printf("%d\n", Ans);
    return 0;
}

D - Biểu thức Logic

Bài toán đệ quy đơn giản.

Đặt \(T_i\) và \(F_i\) lần lượt là số lượng kết quả là \(\text{True}\) hoặc \(\text{False}\) của \(i\) phép toán đầu tiên.

Nếu phép toán thứ \(i\) là AND, thì có:

[T_i = T_{i-1} ][F_i = F_{i-1}\times 2 + T_{i-1} ] Ngược lại:

[F_i = F_{i-1} ][T_i = T_{i-1}\times 2 + F_{i-1} ] Kết quả chính là \(T_n\)

E - Xoay và Lật

Bài toán này có thể giải không cần ma trận, cũng không quá phức tạp.

Quan sát từng thao tác:

opt1 \((x,y) \rightarrow (y,-x)\)

opt2 \((x,y) \rightarrow (-y,x)\)

opt3 \((x,y) \rightarrow (2\times p-x,y)\)

opt4 \((x,y) \rightarrow (x,2\times p-y)\)

Ta thấy rằng với bất kỳ tổ hợp các thao tác nào, tọa độ ban đầu đều có thể biểu diễn dưới dạng:

\((sum_x\ \text{opt}_x\ x, sum_y \ \text{opt}_y\ y)\) hoặc \(( sum_y \ \text{opt}_y\ y,sum_x\ \text{opt}_x\ x)\).

\(sum\) là một giá trị, \(\text{opt}\) là dấu, \(x/y\) là giá trị tọa độ ban đầu.

Khi thực hiện, chỉ cần xử lý offline, duy trì 5 biến: \(sum_{x/y}\), \(\text{opt}_{x/y}\), và trạng thái lật tọa độ.

inline bool cmp(int NA, int NB) {return A[NA] < A[NB];}
int main() {
    scanf("%d", &n);
    forn(i,1,n) scanf("%d%d", X+i, Y+i);
    scanf("%d", &m);
    forn(i,1,m) {
        scanf("%d", opt+i);
        if(opt[i] > 2) scanf("%d", p+i);
    }
    scanf("%d", &q);
    forn(i,1,q) scanf("%d%d", A+i, B+i), id[i] = i;
    sort(id+1, id+q+1, cmp);
    LL trn = 0, Xopt = 1, Yopt = 1, Xsum = 0, Ysum = 0;
    int j = 1;
    forn(i,1,m+1) {
        while(A[id[j]] == i-1) {
            Xans[id[j]] = Xsum + Xopt*1ll*X[B[id[j]]];
            Yans[id[j]] = Ysum + Yopt*1ll*Y[B[id[j]]];
            if(trn) swap(Xans[id[j]], Yans[id[j]]);
            ++j;
        }
        if(opt[i] == 1) {
            if(trn) {
                Yopt = -Yopt;
                Ysum = -Ysum;
            } else {
                Xopt = -Xopt;
                Xsum = -Xsum;	
            }
            trn^=1;
        } else if(opt[i] == 2) {
            if(trn) {
                Xopt = -Xopt;
                Xsum = -Xsum;	
            } else {
                Yopt = -Yopt;
                Ysum = -Ysum;
            }
            trn^=1;
        } else if(opt[i] == 3) {
            if(trn) {
                Ysum = 2ll*p[i] - Ysum;
                Yopt = -Yopt;
            } else {
                Xsum = 2ll*p[i] - Xsum;
                Xopt = -Xopt;	
            }
        } else {
            if(trn) {
                Xsum = 2ll*p[i] - Xsum;
                Xopt = -Xopt;
            } else {
                Ysum = 2ll*p[i] - Ysum;
                Yopt = -Yopt;
            }
        }
    }
    forn(i,1,q) printf("%lld %lld\n", Xans[i], Yans[i]);
    return 0;
}

F - Sugoroku2

Đặt \(f_i\) là kỳ vọng số lần đi từ ô \(i\) đến đích, rõ ràng có:

\( \begin{cases} \ f_i = \displaystyle{0} & i\geq n\\ \ f_i = \displaystyle{f_0} & i\in A \\ \ f_i = \displaystyle{\frac{1}{m}\sum_{j=i+1}^{i+m} f_j}+1 & \text{ngược lại}\\ \end{cases} \)

Công thức này không thể tính trực tiếp, nhưng mỗi \(f_i\) có thể biểu diễn dưới dạng hàm tuyến tính của \(f_0\), cuối cùng thu được phương trình \(f_0 = k\times f_0+b\), giải phương trình trực tiếp.

Vì vậy có thể dùng DP tối ưu bằng tổng hậu tố để tìm ra mỗi hàm tuyến tính, độ phức tạp tổng thể chỉ là \(\mathcal{O}(n)\).

#include<bits/stdc++.h>
#define forn(i,s,t) for(register int i=(s);i<=(t);++i)
#define form(i,s,t) for(register int i=(s);i>=(t);--i)
using namespace std;
const int N = 2e5+3;
int n, m, k, a[N]; bool bck[N];
long double f1[N], f2[N], suf1[N], suf2[N];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    long double C = (long double)1.0/m;
    forn(i,1,k) scanf("%d", a+i), bck[a[i]] = 1;
    form(i,n-1,0) {
        if(bck[i]) {
            suf1[i] = suf1[i+1];
            suf2[i] = suf2[i+1] + 1.0;
            continue ;
        }
        f1[i] = C*(suf1[i+1] - suf1[i+m+1]) + 1;
        f2[i] = C*(suf2[i+1] - suf2[i+m+1]);
        suf1[i] = suf1[i+1] + f1[i];
        suf2[i] = suf2[i+1] + f2[i];
    }
    if(1-f2[0] < 1e-6) puts("-1");
    else printf("%.4Lf\n", f1[0]/(1-f2[0]));
    return 0;
}