2022 PCCA Winter Camp div 1

1月 29, 2022

2022 PCCA Winter Camp div 1

這次跟 $\text{KenIsGenius}$ 組隊參加了 $\text{2022 PCCA Winter Camp div 1}$ 的比賽，以下是有解出來的部分。如果是我有解的我會附大意和想法。

題目：給一個字串 $S$ 每次可以選一個子字串 $t$，可以將 $S$ 中不重疊的區間，而且此區間等於 $t$，換成一字元，問最後可以為回文的最長長度。

解法：可以用 $\text{Greedy}$，就是從兩側慢慢往裡面看，用 $\text{Hash}$ 即可快速判斷。

$\text{Code by becaido：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;
const int base = 137;
const int MOD = 1e9 + 9;

string s;
int n;
int pro[SIZE], inv[SIZE], pre[SIZE];

int turn (int x) {
    x %= MOD;
    return (x < 0 ? x + MOD : x);
}

int hs (int l, int r) {
    return turn ( (pre[r] - pre[l - 1]) * inv[l - 1]);
}

int power (int d, int up) {
    int ans = 1;
    while (up) {
        if (up & 1)
            ans = ans * d % MOD;
        d = d * d % MOD;
        up >>= 1;
    }
    return ans;
}

int ans = 0;

void cal (int l, int r) {
    if (l > r)
        return;
    if (l == r) {
        ans++;
        return;
    }
    for (int i = 1; i <= (r - l + 1) / 2; i++) {
        if (hs (l, l + i - 1) == hs (r - i + 1, r)) {
            ans += 2;
            cal (l + i, r - i);
            return;
        }
    }
    ans++;
}

void solve() {
    getline (cin, s);
    n = s.size(), s = " " + s;
    pro[0] = inv[0] = 1;
    FOR (i, 1, n) {
        pro[i] = pro[i - 1] * base % MOD;
        inv[i] = power (pro[i], MOD - 2);
        pre[i] = (pre[i - 1] + 1ll * s[i] * pro[i]) % MOD;
    }
    cal (1, n);
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt = 1;
    //cin >> tt;
    while (tt--)
        solve();
}

$\text{pC.}$ Checkerboard Splitting

題目：給一個棋盤，有黑白灰色，灰色各有 $\frac{1}{2}$ 機率會變黑或白色。最後棋盤會有美麗值，如果 $color(x,y) = color(x+1,y-1)$，美麗值等於 $0$，否則美麗值等於用最少骨牌蓋滿整個棋盤，骨牌的定義是相鄰格子必須為異色。問最後美麗值期望值 $\frac{P}{Q}$，輸出 $P\times Q^{-1} \text{mod}\ 998244353$

解法：沿著斜線 $\text{DP}$，好難寫...

$\text{Code by becaido：}$

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;
const int MOD = 998244353;

int n, m;
string s[SIZE];

int power (int d, int up) {
    int ans = 1;
    while (up) {
        if (up & 1)
            ans = ans * d % MOD;
        d = d * d % MOD;
        up >>= 1;
    }
    return ans;
}

bool check (int sum) {
    int x = 0;
    for (int i = min (n, sum - 1), j = sum - i; i >= 1 && j <= m; i--, j++) {
        if (s[i][j] == 'W')
            x |= (i % 2 ? 2 : 1);
        if (s[i][j] == 'B')
            x |= (i % 2 ? 1 : 2);
        if (x == 3)
            return 0;
    }
    return 1;
}

int ty (int sum) {
    for (int i = min (n, sum - 1), j = sum - i; i >= 1 && j <= m; i--, j++) {
        if (s[i][j] == 'W')
            return (j % 2 ? 0 : 1);
        if (s[i][j] == 'B')
            return (j % 2 ? 1 : 0);
    }
    return 2;
}

int cnt (int sum) {
    int re = 0;
    for (int i = min (n, sum - 1), j = sum - i; i >= 1 && j <= m; i--, j++) {
        re += s[i][j] == '?';
    }
    return re;
}

int all = 1;
int dp[2][2];/// 0 : W 1 : B at i%2==1
int ok[2][2];

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) cin >> s[i], s[i] = " " + s[i];
    FOR (i, 2, n + m) {
        if (!check (i)) {
            cout << "0\n";
            return;
        }
    }
    if (s[1][1] == 'W')
        dp[0][0] = 1, ok[0][0] = 1;
    else if (s[1][1] == 'B')
        dp[0][1] = 1, ok[0][1] = 1;
    else {
        dp[0][0] = dp[0][1] = 1;
        ok[0][0] = ok[0][1] = 1;
        all=2;
    }
    FOR (i, 3, n + m) {
        int t = ty (i);
        dp[i & 1][0] = dp[i & 1][1] = 0;
        ok[i & 1][0] = ok[i & 1][1] = 0;
        if (t == 0 || t == 2) {
            ok[i & 1][0] = ok[! (i & 1)][0] + ok[! (i & 1)][1];
            dp[i & 1][0] += dp[! (i & 1)][0] + ok[! (i & 1)][0] * (i <= n + 1);
            dp[i & 1][0] += dp[! (i & 1)][1] + ok[! (i & 1)][1] * (i <= m + 1);
        }
        if (t == 1 || t == 2) {
            ok[i & 1][1] = ok[! (i & 1)][0] + ok[! (i & 1)][1];
            dp[i & 1][1] += dp[! (i & 1)][0] + ok[! (i & 1)][0] * (i <= m + 1);
            dp[i & 1][1] += dp[! (i & 1)][1] + ok[! (i & 1)][1] * (i <= n + 1);
        }
        dp[i & 1][0] %= MOD;
        dp[i & 1][1] %= MOD;
        ok[i & 1][0] %= MOD;
        ok[i & 1][1] %= MOD;
        all = all * power (2, cnt (i)) % MOD;
    }
    cout << (dp[ (n + m) & 1][0] + dp[ (n + m) & 1][1]) * power (all, MOD - 2) % MOD << '\n';
}

int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt = 1;
    //cin >> tt;
    while (tt--)
        solve();
}

$\text{pD.}$ DVD Player

題目：一個半徑為 $r$ 的 $\text{DVD}$ 在長寬為 $n,m$ 的電視移動，中心點起始座標在 $(x,y)$，$x$ 方向速率為 $V_x$，$y$ 方向速率為 $V_y$，碰到牆壁會反彈，問碰到角落最小時間 $t$，或是不可能。

解法：可以先將 $\text{DVD}$ 變成一個點，就是將 $n-2\times r, m-2\times r ,x-r, y-r$，令 $(x+V_xt, y+V_yt) = (k_1n, k_2m)$，$k_1,k_2$ 為非負整數。可得 $t = (k_1n - x) / V_x = (k_2m - y) / V_y$，將兩邊弄來弄去，可得 $Ak_1+Bk_2=C$，如果 $C$ 不能被 $gcd(A,B)$ 整除，就代表永遠碰不到，否則將 $A,B,C$ 同除 $gcd(A,B)$，兩邊對 $A$ 取 $\text{mod}$，得 $Bk_1 ≡ C (\text{mod}\ A)$，$k_1 ≡ C\times B^{-1}$，用 $\text{exgcd}$ 就可以了，之後再輸出 $t$。然後我用 $\text{__int128}$ 避免溢位。

$\text{Code by becaido：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

int turn (__int128 x, int mod) {
    x %= mod;
    return (x < 0 ? x + mod : x);
}

void exgcd (int a, int b, int &A, int &B, int mod) {
    if (b == 0)
        return;
    exgcd (b, a % b, A, B, mod);
    int t = A;
    A = B;
    B = turn (t - (__int128) a / b * B, mod);
}

void solve() {
    int n, m, r, x, y, vx, vy;
    cin >> n >> m >> r >> x >> y >> vx >> vy;
    n -= 2 * r, m -= 2 * r;
    x -= r, y -= r;
    int A = vy * n, B = vx * m, C = -vy * x + vx * y;
    int gcd = __gcd (A, B);
    if (C % gcd) {
        cout << "-1\n";
        return;
    }
    A /= gcd, B /= gcd, C /= gcd;
    C = turn (C, A);
    int aa = 0, bb = 1;
    exgcd (B, A, bb, aa, A);
    int k = turn ( (__int128) C * bb, A);
    cout << fixed << setprecision (10) << ( (double) k * m - y) / vy << '\n';
}

int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt = 1;
    //cin >> tt;
    while (tt--)
        solve();
}

$\text{pE.}$ Elise Loves Drinks

$\text{Code by KenIsGenius：}$

#include <bits/stdc++.h>
#define V vector
#define F first
#define S second
#define vi V<int>
#define vvi V<vi>
#define pii pair<int,int>
#define vpii V<pii>
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sqr(x) ((x)*(x))
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz(x) (int)((x).size())
#define ld long double
#define StarBurst ios_base::sync_with_stdio(0),cin.tie(0);
#define inf INT64_MAX
#define eps (1e-9)
#define int long long
using namespace std;

signed main(){
    StarBurst
    int n,m;
    cin>>n>>m;
    vi dp(n+1,0);
    vi t(n),a(n);
    int sum=0,s2=0;
    for(int i=0;i<n;i++){
        cin>>t[i]>>a[i];
        if(t[i]==0)dp[i+1]=dp[i]+10-a[i]/10;
        else dp[i+1]=dp[i]-a[i]/10,s2+=a[i];
        sum+=a[i];
    }
    if(sum>m*100){
        cout<<"-1\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(dp[i]<0){
            cout<<"-1\n";
            return 0;    
        }
    }
    cout<<(m*100-sum)/100<<'\n';
}

$\text{pH.}$ Hex Activation Key

題目：有 $16$ 個 $16$ 進制的字元，給一些限制，有 $c_1, c_2$ 不能相鄰，還有 $c_1$ 不能被 $c_2, c_3$ 夾，問要造一個長度為 $n$ 的字串有幾種方法。

解法：可以用 $dp$，$n = 1$ 時特判，否則 $O(16^3\times n)$。

$\text{Code by becaido & KenIsGenius：}$

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int mod = 998244353;
const int MOD = mod;

int dp[2][16][16];/// (pos&1) c[pos-1] c[pos] ways
bool ok[16][16][16];/// c[pos-2] c[pos-1] c[pos] can?
bool o[16][16];

int turn (char c) {
    if (c >= '0' && c <= '9')
        return c - '0';
    return c - 'a' + 10;
}

void solve() {
    int n, m;
    cin >> n >> m;
    if (n == 1) {
        cout << "16\n";
        return;
    }
    while (m--) {
        char c;
        cin >> c;
        if (c == '-') {
            char s[2];
            FOR (i, 0, 1) cin >> s[i], s[i] = turn (s[i]);
            FOR (i, 0, 15) ok[i][s[0]][s[1]] = ok[i][s[1]][s[0]] = 1;
            FOR (i, 0, 15) ok[s[0]][s[1]][i] = ok[s[1]][s[0]][i] = 1;
            o[s[0]][s[1]] = o[s[1]][s[0]] = 1;
        } else {
            char s[3];
            FOR (i, 0, 2) cin >> s[i], s[i] = turn (s[i]);
            ok[s[1]][s[0]][s[2]] = ok[s[2]][s[0]][s[1]] = 1;
        }
    }
    FOR (i, 0, 15) FOR (j, 0, 15) {
        o[i][j] ^= 1;
        dp[0][i][j] += o[i][j];
        FOR (k, 0, 15) ok[i][j][k] ^= 1;
    }
    FOR (t, 3, n) FOR (i, 0, 15) FOR (j, 0, 15) {
        dp[t & 1][j][i] = 0;
        FOR (k, 0, 15) dp[t & 1][j][i] += dp[! (t & 1)][k][j] * ok[k][j][i];
        dp[t & 1][j][i] %= MOD;
    }
    int ans = 0;
    FOR (i, 0, 15) FOR (j, 0, 15) ans += dp[n & 1][j][i];
    cout << ans % MOD << '\n';
}

int32_t main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt = 1;
    //cin >> tt;
    while (tt--)
        solve();
}

$\text{pK.}$ Kore wa FFT desu ka?

$\text{Code by KenIsGenius：}$

#include <bits/stdc++.h>
#define V vector
#define F first
#define S second
#define vi V<int>
#define vvi V<vi>
#define pii pair<int,int>
#define vpii V<pii>
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sqr(x) ((x)*(x))
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz(x) (int)((x).size())
#define ld long double
#define StarBurst ios_base::sync_with_stdio(0),cin.tie(0);
#define inf INT64_MAX
#define eps (1e-9)
#define int long long
using namespace std;

signed main(){
    StarBurst
    int t;
    cin>>t;
    while(t--){
        int n,p;
        cin>>n>>p;
        int f=0;
        for(int i=0;i<31;i++){
            if((1<<i)>n and (p-1)%(1<<i)==0){
                f=1;
            }
        }
        cout<<(f?"YES\n":"NO\n");
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！

搜尋此網誌

Caido Coding Blog

2022 PCCA Winter Camp div 1

留言

張貼留言

熱門文章

110年建中科學班心得

2022 全國賽心得