2022 China Collegiate Programming Contest (CCPC) Weihai Site

VP概況

這場我一年之前做過，然后就沒有去補題，今年重新和新隊友們做做這場，開局還算順利地過了兩個簽到，然后就是三道銅牌題，曾經一度卡題一個半小時，然后我做出了J，隊友做出了數學和計算幾何，在正賽算是可以拼手速拿到銅，但還不夠，還要多多補題，其實VP的時候C可以寫出來的，下蛋就真的不會了

E - Python Will be Faster than C++

模擬，存在 \(a_{n - 1} \geq a_n\) 無解，其余模擬即可

const int N = 1e7 + 20;
 
int a[N];
void solve()
{       
    int n, k;   cin>>n>>k;
    int i;
    for(i = 1; i <= n; i++)
        cin>>a[i];
    int cnt = 0;
    i = n;
    while(++cnt <= 1e7 && a[n - 1] >= a[n])
    {
        i++;
        a[i] = max(0, 2 * a[i - 1] - a[i - 2]);
        if(a[i] < k)
        {
            cout<<"Python 3."<<i<<" will be faster than C++\n";
            return;            
        }
    }
    cout<<"Python will never be faster than C++\n";
    return;
}

A - Dunai

記錄每個位置有多少人，然后算出能組成多少支隊伍，再和冠軍選手取個min即可，賽時畫了柱狀圖去理解

int n, m, c[10], b[10];
void solve()
{       
    cin>>n;
    set<string> S;
    for(int i = 1; i <= n * 5; i++)
    {
        string s;    cin>>s;
        S.insert(s);
    }
    cin>>m;
    for(int i = 1; i <= m; i++)
    {
        string s;    cin>>s;
        int a;  cin>>a;
        if(S.count(s))
            c[a]++;
        b[a]++;
    }
    int miv = min({b[1], b[2], b[3], b[4], b[5]});
    miv = min({miv, c[1] + c[2] + c[3] + c[4] + c[5]});
    cout<<miv<<'\n';
 
    return;
}

J - Eat, Sleep, Repeat

博弈，但是答案是求最多的操作次數的奇偶性相關

我的做法是對限制為0進行分段，這樣就可以確定 \(a_i\) 最終會出現在哪一段內，對 a 排序，雙指針去模擬這個過程

const int N = 3e5 + 20;
 
int a[N];
int n, k;
map<int, int> mp;
vector<int> vx;
set<int> S;
void solve()
{       
    mp.clear();
    vx.clear();
    S.clear();
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
 
    mp[-1] = 0;
    vx.push_back(-1);
    S.insert(-1);
 
    mp[1000000002] = 0;
    vx.push_back(1000000002);
    S.insert(1000000002);    
    for(int i = 1; i <= k; i++)
    {
        int x, y;   cin>>x>>y;
        mp[x] = y;
        if(y == 0)  
        {
            S.insert(x);
            vx.push_back(x);
        }
    }
    sort(a + 1, a + 1 + n);
    sort(vx.begin(), vx.end());
    int m = vx.size();
    queue<int> q[m + 2];
    for(auto it : vx)
    {
        int p = it + 1;
        for(int l = p; ; l++)
        {
            if(S.count(l))  break;
            if(mp.count(l) == 0)    
            {
                mp[l] = n;
                break;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        int pos = lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() - 1;
        q[pos].push(a[i]);
    }  
    ll res = 0;
    for(int i = 0; i < m; i++)
    {
        int p = vx[i] + 1;
        for(int l = p; ; l++)
        {
            while(mp[l] != 0 && !q[i].empty() && q[i].front() >= l)
            {
                mp[l]--;
                res += (q[i].front() - l);
                q[i].pop();
            }
            if(q[i].empty())
                break;
        }
    } 
    if(res % 2 == 1)
    {
        cout<<"Pico\n";
    }
    else
        cout<<"FuuFuu\n";
    return;
}

G - Grade 2

打表可以知道答案有循環節，求出這個循環節區間

typedef long long ll;
 
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
 
ll mi = 1, s[N];
 
void init()
{
    ll x;   cin>>x;
    for(; mi <= x; mi *= 2);
    for(int i = 1; i <= mi; i++)
        s[i] = s[i - 1] + (__gcd(i * x ^ x, x) == 1);
}
 
void solve()
{       
    ll l, r;    cin>>l>>r;
    l--;
    ll res = r / mi * s[mi] + s[r % mi] - l / mi * s[mi] - s[l % mi];
    cout<<res<<'\n';
 
    return;
}
 
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    init();
    cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }
    return 0;
}

C - Grass

手玩數據可以知道，只要 5 個點不在一條直線上，那么答案一定存在，枚舉這 5 個點誰做A點即可

證明看 官方題解

int n;
void solve()
{           
 
    cin>>n;
    vector<array<int, 2>> d; 
    for(int i = 1; i <= min(n, 4); i++)
    {
        int x, y;   cin>>x>>y;
        d.push_back({x, y});
    }
    bool ok = false;
    if(n > 4)
    {
        for(int i = 5; i <= n; i++)
        {
            int x, y;   cin>>x>>y;
            d.push_back({x, y});
            for(int j = 0; j < 5; j++)
            {
                set<array<int, 2>> S, a;
                for(int k = 0; k < 5; k++)
                {
                    if(j == k)  continue;
                    int tx = d[k][0] - d[j][0];
                    int ty = d[k][1] - d[j][1];
                    int g = __gcd(abs(tx), abs(ty));
                    tx /= g, ty /= g;
                    S.insert({tx, ty});
                }
                if(S.size() == 4 && ok == false)
                {
                    cout<<"YES\n";
                    cout<<d[j][0]<<" "<<d[j][1]<<'\n';
                    for(int k = 0; k < 5; k++)
                        if(j != k)
                            cout<<d[k][0]<<" "<<d[k][1]<<'\n';
                    ok = true;
                }
            }
            d.pop_back();
        }
    }
    if(!ok)
        cout<<"NO\n";
    return;
}

I - Dragon Bloodline

VP時沒思路，認為是dp或者貪心，看了題解發現是貪心，也明白了貪心的正確性，對于每次貪心需要最多的元素，放生產效率最高的工具龍去生產

const int N = 2e5 + 10;
 
int n, k;
ll a[N], b[N], c[N], sb[N];
 
bool check(ll mid)
{
    priority_queue<ll, vector<ll>, less<ll>> q;
    for(int i = 1; i <= n; i++)
        q.push(a[i] * mid);
    for(int i = 0; i < k; i++)
        c[i] = b[i];
    int i = k - 1;
    while(q.size() >= 1)
    {
        ll t = q.top(); q.pop();
        if(i == -1) return false;
        ll need = max({1ll, t / (1 << i)});
        need = min(c[i], need);      
        t = t - need * (1 << i);
        c[i] = c[i] - need;
        if(t >= 1)
            q.push(t);
        if(c[i] == 0)
            i--;
    }
    return true;
}
void solve()
{       
    cin>>n>>k;
    ll l = 0, r = 0, t = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        t += a[i];
    }
 
    for(int i = 0; i < k; i++)
    {
        cin>>b[i];
        sb[i] = b[i] * (1 << i);
        r += sb[i];
    }
    r /= t;
    while(l < r)
    {
        ll mid = (l + r + 1) >> 1;
        if(check(mid))    l = mid;
        else r = mid - 1;
    }
    cout<<l<<'\n';
    return;
}