DDJ Regular Contest Round#5 Tutorial

a626: A. 簽到

tags: geometry

結論: 三個有向面積

$\overrightarrow{PA}\times \overrightarrow{PB},\overrightarrow{PB}\times \overrightarrow{PC},\overrightarrow{PC}\times \overrightarrow{PA}$同號等價於

$P$在三角形內

自己畫幾張圖觀察一下三個面積的方向就會發現這很顯然
這裡簡單證明一下，不管

$P$在哪裡

$\mathrm{△}ABC$的面積都可以寫成

$$\frac{1}{2}|\overrightarrow{PA}\times \overrightarrow{PB}+\overrightarrow{PB}\times \overrightarrow{PC}+\overrightarrow{PC}\times \overrightarrow{PA}|$$
如果

$P$在

$\mathrm{△}ABC$內面積可以寫成

$$\frac{1}{2}|\overrightarrow{PA}\times \overrightarrow{PB}|+\frac{1}{2}|\overrightarrow{PB}\times \overrightarrow{PC}|+\frac{1}{2}|\overrightarrow{PC}\times \overrightarrow{PA}|$$
如果

$P$在

$\mathrm{△}ABC$外，則上式會大於

$\mathrm{△}ABC$的面積
這足以證明

$P$在

$\mathrm{△}ABC$內是三個有向面積同號的充分必要條件

Solution

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;
using pll = pair<long long, long long>;

inline pll operator-(const pll &a, const pll &b) { return {a.ff - b.ff, a.ss - b.ss}; }
inline long long operator^(pll a, pll b) { return a.ff * b.ss - a.ss * b.ff; }
inline int sig(long long x) { return (x > 0) - (x < 0); }

void solve() {
    pll p, a, b, c;
    cin >> p.ff >> p.ss;
    cin >> a.ff >> a.ss >> b.ff >> b.ss >> c.ff >> c.ss;
    int t = sig((a-p)^(b-p)) + sig((b-p)^(c-p)) + sig((c-p)^(a-p));
    if (t == 3 || t == -3) cout << "YES\n";
    else cout << "NO\n";
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

---

a622: B. 關燈遊戲

tags: greedy, number theory

結論: 一直操作編號最大的亮燈直到全滅

兩個顯然的性質

1. 操作順序不影響結果
2. 操作兩次等於不操作，所以規定每盞燈最多操作一次

假設目前編號最大的亮燈是

$p$，根據

$1.$我們可以先來考慮如何把

$p$滅掉，想要把

$p$滅掉可以對

$p$的任意一個倍數操作，將

$p$的倍數分成

$p$和

$kp(k\ge 2)$討論，如果選擇操作

$kp$，則最大的亮燈變為

$kp$，現在討論如何滅掉

$kp$，但根據

$2.$我們不能再對

$kp$操作，只能在選擇一個更大的倍數操作，最大的亮燈編號將會不斷變大永遠無法全滅，因此只能選擇操作

$p$使最大的亮燈編號不斷變小直到全滅

實作的部分可以從大到小暴力枚舉因數操作，時間複雜度

$O(n\sqrt{n})$
也可以枚舉每個數的倍數求出哪些數的因數包含自己並記錄起來，時間和空間複雜度都是

$O(n\log n)$

註: 調和級數的複雜度是

$O(\log n)$

一個比較乾淨的作法是從大到小枚舉每個數

$i$的倍數去計算

$i$改變了幾次，在處理到

$i$之前，

$sta[i]$的定義是亮/暗(0/1)，處理完

$i$後

$sta[i]$的定義變成操作/不操作(0/1)，時間複雜度

$O(n\log n)$

Solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

bool sta[maxn];

void solve() {
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> sta[i];
    for (int i = n; i; i--) {
        for (int j = i+i; j <= n; j += i)
            sta[i] ^= sta[j];
        ans += sta[i];
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

---

a625: C. 括號序列

tags: data structures

如果把(當

$+1$)當

$-1$，一個合法的序列要滿足

1. 和為
   $0$，(的數量要等於)的數量
2. 任何一個前綴和都要
   $\ge 0$，(的數量要大於等於)的數量

於是維護前綴和
對於詢問

$[l,r]$需要判斷是否有

$sum[r]-sum[l-1]=0$和

$min(sum[l],sum[l+1],...,sum[r])-sum[l-1]\ge 0$
對於修改

$i$需要將

$sum[i]\sim sum[n]$

$+2$或

$-2$

Subtask 1 (30%)

暴力

Subtask 2 (70%)

維護一個區間最小區間加值線段樹

Solution

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 5;

int sum[maxn];
string str;

struct segment_tree {
    static const int maxn = 16e5 + 5;
    int mi[maxn] = {}, tag[maxn] = {};
    inline void updata(int p, int v) { mi[p] += v, tag[p] += v; }
    inline void pull(int p) { mi[p] = min(mi[p<<1], mi[p<<1|1]) + tag[p]; }
    inline void push(int p) {
        if (tag[p]) updata(p<<1, tag[p]), updata(p<<1|1, tag[p]);
        tag[p] = 0;
    }
    void build(int l, int r, int p) {
        if (l == r) { mi[p] = sum[l]; return; }
        int mid = (l+r)>>1;
        build(l, mid, p<<1), build(mid+1, r, p<<1|1);
        pull(p);
    }
    int query(int l, int r, int ql, int qr, int p) {
        if (ql == 0) return 0;
        if (ql == l && qr == r) return mi[p];
        push(p);
        int mid = (l+r)>>1;
        if (qr <= mid) return query(l, mid, ql, qr, p<<1);
        else if (mid < ql) return query(mid+1, r, ql, qr, p<<1|1);
        else return min(query(l, mid, ql, mid, p<<1), query(mid+1, r, mid+1, qr, p<<1|1));   
    }
    void modify(int l, int r, int ml, int mr, int v, int p) {
        if (ml == l && mr == r) { updata(p, v); return; }
        int mid = (l+r)>>1;
        push(p);
        if (mr <= mid) modify(l, mid, ml, mr, v, p<<1);
        else if (mid < ml) modify(mid+1, r, ml, mr, v, p<<1|1);
        else modify(l, mid, ml, mid, v, p<<1), modify(mid+1, r, mid+1, mr, v, p<<1|1);
        pull(p);
    }
} seg;

void solve() {
    int n, m;
    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i-1] + 1 - 2*(str[i-1] == ')');
    seg.build(1, n, 1);
    int opt, l, r;
    while (m--) {
        cin >> opt;
        if (opt == 1) {
            cin >> l >> r;
            if ((r-l+1)&1) cout << "NO\n";
            else if (seg.query(1, n, r, r, 1) != seg.query(1, n, l-1, l-1, 1))
                cout << "NO\n";
            else if (seg.query(1, n, l, r, 1) - seg.query(1, n, l-1, l-1, 1) >= 0)
                cout << "YES\n";
            else cout << "NO\n";
        }
        else if (opt == 2) {
            cin >> l;
            if (str[l-1] == '(') {
                str[l-1] = ')';
                seg.modify(1, n, l, n, -2, 1);
            }
            else {
                str[l-1] = '(';
                seg.modify(1, n, l, n, 2, 1);
            }
        }
    }
}

signed main() {
    solve();
    return 0;
}

---

a621: D. 樹的分數

tags: trees, combinatorics, math

考慮直接算出原樹的分數，用

$cn{t}_u$表示包含節點

$u$的路徑個數，則節點

$u$對分數的貢獻就是

$u\times cn{t}_u$，根據排序不等式，只要將小的編號配小的權重，大的編號配大的權重就可以有最大分數

Subtask 1 (15%)

顯然越靠近重心

$cnt$越大，越靠近葉子

$cnt$越小，且從一邊數來第

$k$個節點和從另一邊數來第

$k$個節點的

$cnt$一樣，也就是這兩個節點的編號交換不影響分數，因此答案就是

$2^{\lfloor \frac{n}{2}\rfloor }$

Subtask 2 (25%)

現在必須算出每個

$cnt$的值，以

$u$為根包含

$u$的路徑有兩種，起點或終點為

$u$，和起點在

$u$的某個子數上終點在

$u$的另一個子樹上，所以有

$$cn{t}_u=(n-1)+\sum _{i=1}^{d_u-1}\sum _{j=i+1}^{d_u}siz[v_i]\times siz[v_j]$$
其中

$d_u$表示點

$u$的度數，

$v_i$表示

$u$的第

$i$個鄰居，

$siz[v_i]$表示子樹的大小，若同樣的

$cnt$值有

$k$個，則這

$k$個節點的編號可以互換，對答案貢獻

$k!$，暴力計算

$cnt$的複雜度為

$O(\sum d_i^2)=O(n^2)$

Subtask 3 (60%)

只要將Subtask2的求法優化一下即可，注意到

$$2\sum _{i=1}^{d-1}\sum _{j=i+1}^{d}siz[v_i]\times siz[v_j]=(\sum _{i=1}^{d}siz[v_i]{)}^2-\sum _{i=1}^{d}siz[v_i{]}^2=(n-1{)}^2-\sum _{i=1}^{d}siz[v_i{]}^2$$
或者換一種計算方法，全部路徑扣掉起點終點都在同一個子樹的路徑

$$cn{t}_u=C_2^n-\sum _{i=1}^{d_u}{C}_2^{siz[v_i]}$$
這樣複雜度變為

$O(\sum d)=O(n)$

Solution

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;
const int maxn = 2e5 + 5;

map<long long, int> cnt;
long long fac[maxn];
vector<int> G[maxn];
int n;

long long dfs(int u, int f) {
    long long ret = 1, t;
    long long s = 1ll * n * (n-1) / 2;
    for (int v : G[u]) {
        if (v == f) continue;
        t = dfs(v, u);
        s -= t * (t-1) / 2;
        ret += t;
    }
    s -= (n-ret) * (n-ret-1) / 2;
    cnt[s]++;
    return ret;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i-1] * i % mod;
    long long ans = 1;
    for (pair<long long, int> p : cnt)
        ans = ans * fac[p.second] % mod;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

---

a614: E. 數列貼貼

tags: dp, math, matrices

Subtask 1 (20%)

暴力遞推

Subtask 2 (80%)

將

$a_{i+1}{a}_i$展開

$$a_{i+1}{a}_i=(x{a}_i+y{a}_{i-1})(x{a}_{i-1}+y{a}_{i-2})=x^2{a}_i{a}_{i-1}+xy{a}_i{a}_{i-2}+xy{a}_{i-1}{a}_{i-1}+y^2{a}_{i-1}{a}_{i-2}$$現在嘗試湊出從

${\overrightarrow{v}}_i=(a_i{a}_{i-1},a_i{a}_{i-2},a_{i-1}{a}_{i-1},a_{i-1}{a}_{i-2})$到

${\overrightarrow{v}}_{i+1}=(a_{i+1}{a}_i,a_{i+1}{a}_{i-1},a_i{a}_i,a_i{a}_{i-1})$
的線性轉移

$a_{i+1}{a}_i=(x^2,xy,xy,y^2)\cdot {\overrightarrow{v}}_i$

$a_{i+1}{a}_{i-1}=(x{a}_i+y{a}_{i-1})a_{i-1}=x{a}_i{a}_{i-1}+y{a}_{i-1}{a}_{i-1}=(x,0,y,0)\cdot {\overrightarrow{v}}_i$

$a_i{a}_i=a_i(x{a}_{i-1}+y{a}_{i-2})=x{a}_i{a}_{i-1}+y{a}_i{a}_{i-2}=(x,y,0,0)\cdot {\overrightarrow{v}}_i$

$a_i{a}_{i-1}=(1,0,0,0)\cdot {\overrightarrow{v}}_i$

所以轉移方程為

$$\left[\begin{array}{cccc}{x}^2& xy& xy& y^2\\ x& 0& y& 0\\ x& y& 0& 0\\ 1& 0& 0& 0\end{array}\right]\left[\begin{array}{c}{a}_i{a}_{i-1}\\ a_i{a}_{i-2}\\ a_{i-1}{a}_{i-1}\\ a_{i-1}{a}_{i-2}\end{array}\right]=\left[\begin{array}{c}{a}_{i+1}{a}_i\\ a_{i+1}{a}_{i-1}\\ a_i{a}_i\\ a_i{a}_{i-1}\end{array}\right]$$再設

$S_i=a_1{a}_2+a_2{a}_3+...+a_{i-2}{a}_{i-1}$加入轉移式

$$\left[\begin{array}{ccccc}{x}^2& xy& xy& y^2& 0\\ x& 0& y& 0& 0\\ x& y& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}{a}_i{a}_{i-1}\\ a_i{a}_{i-2}\\ a_{i-1}{a}_{i-1}\\ a_{i-1}{a}_{i-2}\\ S_i\end{array}\right]=\left[\begin{array}{c}{a}_{i+1}{a}_i\\ a_{i+1}{a}_{i-1}\\ a_i{a}_i\\ a_i{a}_{i-1}\\ S_{i+1}\end{array}\right]$$用矩陣快速冪求

${\overrightarrow{v}}_{n+1}$，時間複雜度

$O(5^3\log n)$

Solution

#include <bits/stdc++.h>

using namespace std;

const long long mod = 998244353;

struct matrix {
    static const int N = 5;
    long long a[N][N] = {}, n = 0, m = 0;
    matrix(int _n, int _m) : n(_n), m(_m) {}
    long long* operator[](const int &x) { return a[x]; }
};

matrix operator*(matrix A, matrix B) {
    int n = A.n, m = B.m, h = A.m;
    matrix ret(n, m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < h; k++)
                ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % mod;
    return ret;
}

matrix ksm(matrix A, long long b) {
    matrix ret(A.n, A.m);
    for (int i = 0; i < A.n; i++) ret[i][i] = 1;
    while (b) {
        if (b&1) ret = ret * A;
        A = A * A;
        b >>= 1;
    }
    return ret;
}

void solve() {
    long long a1, a2, a3, x, y, n;
    cin >> a1 >> a2 >> x >> y >> n;
    matrix T(5, 5), v(5, 1);
    T[0][0] = x*x % mod, T[0][1] = T[0][2] = x*y % mod, T[0][3] = y*y % mod;
    T[1][0] = T[2][0] = x, T[1][2] = T[2][1] = y;
    T[3][0] = T[4][0] = T[4][4] = 1;
    a3 = (x*a2 + y*a1) % mod;
    v[0][0] = a3*a2 % mod, v[1][0] = a3*a1 % mod;
    v[2][0] = a2*a2 % mod, v[3][0] = a2*a1 % mod;
    v[4][0] = a1*a2 % mod;
    cout << (ksm(T, n-2) * v)[4][0] << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}