2019-2020 ICPC Asia Hong Kong Regional Contest 補題（部分）

codeforces原題連結
 大佬題解

B - Binary Tree

每個人每次一定拿走奇數（ $2^k-1$ ）個節點，如果先手必勝不難發現兩人輪流拿最終一定拿奇數次（每次奇數個節點）說明一共有奇數個節點，如果先手必敗說明最終兩人共拿偶數次說明有偶數個節點，因此可以根據奇偶性判斷輸贏。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=50010;
const ll mod=998244353;
int n;
int main()
{
    IO;
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
        }
        if(n&1) cout<<"Alice\n";
        else cout<<"Bob\n";
    }
    
    return 0;
    
}

D - Defining Labels

模擬一下就即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=50010;
const ll mod=998244353;
int main()
{
    IO;
    int T=1;
    cin>>T;
    while(T--)
    {
        int k;ll x;
        cin>>k>>x;
        ll base=1,s=0;
        while(s<x)
        {
            base=base*k;
            s+=base;
        }
        
        x-=s-base;
        base/=k;
        vector<int> ans;
        while(x>0&&base)
        {
            
            int r=(x+base-1)/base;
            ans.push_back(r+9-k);
            x-=(r-1)*base;   
            base/=k;
        }
        for(auto t:ans) cout<<t;
        cout<<'\n';
        
    }
    
    return 0;
    
}

G - Game Design

本來想著構造一條鏈，不過發現 $k$ 有點大搞不了，於是。。就沒有於是了
參考上述題解發現自己還是對遞迴不熟練。

如果當前節點的方案數為偶數，那麼我們構造兩個方案數分別為 $2,\frac n 2$ 的子節點；如果是奇數就構造兩個方案數分別為
$2,\frac n 2$ 的子節點，並且根節點單獨作為一種方案，遞迴終點是 $k \leq 2$ 的時候，我們只需要建一條鏈即可。

當父節點的權值等於孩子節點的權值和的時候，父節點即可單獨稱為一種方案，如果大於就不能單獨稱為一種方案。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=50010;
const ll mod=998244353;
int k,cnt;
int fa[N],c[N];
int dfs(int k,int p)
{
    int now=++cnt;
    fa[now]=p;
    if(k<=2)
    {
        fa[++cnt]=now;
        c[cnt]=1;
        c[now]=3-k;
        return 1;
    }
    c[now]=dfs(k/2,now)+dfs(2,now)+(k%2==0);
    return c[now]-(k%2==0);
    
}
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>k;
        dfs(k,0);
        cout<<cnt<<'\n';
        for(int i=2;i<=cnt;i++) cout<<fa[i]<<' ';
        cout<<'\n';
        for(int i=1;i<=cnt;i++) cout<<c[i]<<' ';
        cout<<'\n';
    }
    
    return 0;
    
}

E - Erasing Numbers

大佬題解
直接貼貼大佬題解的圖片吧真的非常妙
在這裡插入圖片描述

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5010;
const ll mod=998244353;
int a[N],n;
bool check(int x)
{
    int cnt0=0,cnt1=0;
    for(int i=1;i<=n;i++) cnt0+=a[i]<x,cnt1+=a[i]>x;

    if(cnt0==cnt1) return 1;
    else if(cnt0<cnt1)
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>x) cnt++;
            else if(a[i]==x) cnt=0;//最後消x
            else cnt=max(cnt-1,0);
            if(cnt==3)
            {
                cnt1-=2,cnt=1;
                if(cnt0==cnt1) return 1;
            }
        }
    }
    else 
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]<x) cnt++;
            else if(a[i]==x) cnt=0;//最後消x
            else cnt=max(cnt-1,0);
            if(cnt==3) 
            {
                cnt0-=2,cnt=1;
                if(cnt0==cnt1) return 1;
            }
        }
    }
    return 0;
    
}
int main()
{
    IO;
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            if(check(a[i])) cout<<1;
            else cout<<0;
        }
        cout<<'\n';
    }
    
    return 0;
    
}

J - Junior Mathematician

竟然還有點卡常，少了幾個%就A了。
為了補這個題重學數位dp，然後發現基本的數位dp

// 2652 ms
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=5010;
const ll mod=1e9+7;
int a[N];
char l[N],r[N];
int m;
int f[N][65][65][2];
int ten[N];
int dfs(int pos,int s,int cur,bool limit)
{
    if(!pos) return cur==0;
    if(f[pos][s][cur][limit]!=-1) return f[pos][s][cur][limit];
    int v=limit?a[pos]:9;
    ll res=0;
    for(int i=0;i<=v;i++)
        res+=dfs(pos-1,(s+i)%m,((cur+s*i-i*ten[pos-1])%m+m)%m,limit&&i==v);
    
    res=(res%mod+mod)%mod;
    return f[pos][s][cur][limit]=res;
}
int solve(char s[])
{
    
    int cnt=strlen(s);
    // 初始化記憶化陣列
    for(int i=1;i<=cnt;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                f[i][j][k][0]=f[i][j][k][1]=-1;
                
    for(int i=1;i<=cnt;i++) a[i]=s[cnt-i]-'0';
  
    return dfs(cnt,0,0,1);
}
int main()
{
    IO;
    int T=1;
    cin>>T;
    
    while(T--)
    {
        cin>>l+1>>r+1;
        cin>>m;
        ten[0]=1;
        for(int i=1;i<=5000;i++) ten[i]=ten[i-1]*10%m;
        // [l,r] 差分-> [0,r]-[0,l-1] 首先讓l-1
        for(int i=strlen(l+1);i;i--)
        {
            if(l[i]>'0') 
            {
                l[i]--;
                break;
            }
            else l[i]='9';
        }
        cout<<((solve(r+1)-solve(l+1))%mod+mod)%mod<<'\n';
    }
    return 0;
    
}

最近作業巨難，訊號+數電，~~感覺老師上課瘋狂划水~~，真就自學???
而且最近題解品質真的差，沒時間打markdown~~不想打~~
要加油哦~