2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite

VP 情況

隊(duì)友告訴我題意很順利過(guò)了兩簽到，對(duì)著C虛空寫法，搞了一個(gè)if(n=3)while(1)的樣例發(fā)現(xiàn)構(gòu)造假了，然后馬上過(guò)了，但是罰時(shí)很多然后隊(duì)友過(guò)了石頭剪刀布，讀了A，很快想到了dp和轉(zhuǎn)移方程，但不知道怎么轉(zhuǎn)移好，最后結(jié)束比賽了，看了大家用記憶化搜索竟然這么好些，然后補(bǔ)了DM，這個(gè)D我想了很久，一直不懂怎么枚舉和三分這個(gè)賠率，寫了好幾個(gè)版本，直到今天終于想明白了。

G - Let Them Eat Cake

每輪操作刪掉一半的數(shù)，已得知操作次數(shù)最多只有 \(\log n\) 輪，直接模擬

int n;
const int N = 1e5 + 10;
 
void solve()
{
	cin>>n;
	int res = 0;
	vector<int> a, b;
	for(int i = 1; i <= n; i++)
	{
		int x;	cin>>x;
		b.push_back(x);
	}
	int sz = n;
	while(sz != 1)
	{
		res++;
		a = b;
		b.clear();
		int m = a.size();
		for(int i = 0; i < m; i++)
		{
			// cout<<a[i]<<"  ";
			// if(i - 1 >= 0)
			// 	cout<<a[i - 1]<<" ";
			// if(i + 1 < m)
			// 	cout<<a[i + 1]<<" ";
			// cout<<'\n';
			bool ok = false;
			if(i - 1 >= 0 && a[i - 1] > a[i])
			{
				ok = true;
			}
 
			if(i + 1 < m && a[i + 1] > a[i])
				ok = true;
			if(!ok)
				b.push_back(a[i]);
		}
		sz = b.size();
	}
	cout<<res<<'\n';
}

C - Catch You Catch Me

對(duì)于1的兒子，其答案是以其兒子為根子樹(shù)的深度

int n;
const int N = 1e5 + 10;
 
int dep[N], f[N];
vector<int> e[N];
void dfs(int u, int from)
{
	dep[u] = dep[from] + 1;
	f[u] = dep[u];
	for(auto v : e[u])
	{
		if(v == from)	continue;
		dfs(v, u);
		f[u] = max(f[u], f[v]);
	}
}
void solve()
{
	cin>>n;
	for(int i = 1; i < n; i++)
	{
		int u, v;	cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	long long res = 0;
	for(auto v : e[1])
	{
		res = res + f[v] - 1;
	}
	cout<<res<<'\n';
}

H - Life is Hard and Undecidable, but...

構(gòu)造方式見(jiàn)代碼

ll k;
int dx[] = {1, 1};
int dy[] = {1, 0};
int res[310][310];
void solve()
{
	cin>>k;
	int x = 1, y = 1;
	for(int i = 1; i <= 2 * k; i++)
	{
		x = x + dx[0];
		y = y + dy[0];
		res[x][y] = 1;
	} 	
	int n = 0;
	for(int i = 1; i <= 300; i++)
		for(int j = 1; j <= 300; j++)
			n += res[i][j];
	cout<<n<<'\n';
	for(int i = 1; i <= 300; i++)
		for(int j = 1; j <= 300; j++)
			if(res[i][j] == 1)
				cout<<i<<" "<<j<<'\n';
}

M - Rock-Paper-Scissors Pyramid

觀察出有單調(diào)棧的特點(diǎn)，根據(jù)特點(diǎn)直接去模擬單調(diào)棧

const int N = 1e6 + 10;
typedef long long ll;
int n, a[N];
void solve()
{
    string s;   cin>>s;
    n = s.size();
    s = "?" + s;
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'S') 
            a[i] = 0;
        else if(s[i] == 'P')    
            a[i] = 1;
        else 
            a[i] = 2;
    }
    stack<int> stk; stk.push(a[1]);
    for(int i = 2; i <= n; i++)
    {
        while(!stk.empty() && a[i] == (stk.top() - 1 + 3) % 3)
            stk.pop();
        stk.push(a[i]);        
    }
    while(stk.size() > 1)
        stk.pop();
    if(stk.top() == 0)
        cout<<"S";
    else if(stk.top() == 1)
        cout<<"P";
    else 
        cout<<"R";
    cout<<'\n';
}

A - Ban or Pick, What's the Trick

輪流操作，我可以選擇選一個(gè)我方能力值最大的英雄，也可以禁掉對(duì)方能力值最大的英雄

\(f_{pos,i,j}\)狀態(tài)就是第 \(pos\) 輪，A選了 \(i\) 個(gè)英雄，\(B\) 選了 \(j\) 個(gè)英雄，而雙方禁用的英雄數(shù)量是可以確定的，用記憶化搜索寫就行

const int N = 2e5 + 10;
 
typedef long long ll;
 
ll n, k;
ll a[N], b[N];
ll f[2 * N][11][11], tmp;
//  第 pos 次操作, A 選了 j 個(gè), B 選了 p 個(gè)
ll dfs(int pos, int i, int j)
{
    if(pos == 2 * n) return 0;
    int dela = i + pos / 2 - j;
    int delb = j + (pos + 1) / 2 - i;
    if(f[pos][i][j] != tmp)
        return f[pos][i][j];
    ll res;
    if(pos % 2 == 0)
    {
        res = -1e18;
        if(dela + 1 <= n && i + 1 <= k)
            res = max(dfs(pos + 1, i + 1, j) + a[dela + 1], res);
        res = max(dfs(pos + 1, i, j), res);
    }
    else
    {
        res = 1e18;
        if(delb + 1 <= n && j + 1 <= k)
            res = min(dfs(pos + 1, i, j + 1) - b[delb + 1], res);
        res = min(dfs(pos + 1, i, j), res);
    }
    f[pos][i][j] = res;
    return res;
}
 
void solve()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= n; i++)
        cin>>b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + n);
    memset(f, 0x3f, sizeof f);
    tmp = f[0][0][0];
    cout<<dfs(0, 0, 0)<<'\n';
    // cout<<f[1][0][0]<<'\n';
}

D - Gambler's Ruin

選擇枚舉一個(gè)隊(duì)的賠率，三分另一個(gè)隊(duì)的賠率

1. 將兩隊(duì)預(yù)測(cè)勝率從小到大排序
2. 前綴和處理
3. 枚舉A隊(duì)賠率
4. 三分另一隊(duì)賠率

這個(gè)我很快想到了解法，但是一直不知道怎么處理1,2操作，寫了好多個(gè)版本一直過(guò)不了樣例，過(guò)了1周再寫就過(guò)了

typedef long long ll;
 
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
 
map<double, ll> mp;
int n, m;
vector<pair<double, ll>> a, b;
ll sx[N], sy[N];
double res;
double f(int idx, int idy)
{
    double s1 = 1.0 * a[idx].first * sx[idx];
    double s2 = 1.0 * b[idy].first * sy[idy];    
    return 1.0 * sx[idx] + sy[idy] - max(s1, s2); 
}
void work(int idx)
{
    int l = 0, r = m - 1;
    while(l < r)
    {
        int lmid = l + (r - l) / 3;
        int rmid = r - (r - l) / 3;
        double fl = f(lmid, idx), fr = f(rmid, idx);
        if(fl <= fr)
            l = lmid + 1;
        else r = rmid - 1;
        res = max({fl, fr, res});
        // cout<<l<<" "<<r<<'\n';
    }
}
void solve()
{       
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        double p;   ll c;   cin>>p>>c;
        mp[p] += c;
    }
    a.push_back({0, 0});
    b.push_back({0, 0});
    for(auto [x, y] : mp)
    {
        if(x != 0.0)
            a.push_back({1.0 / x, y});
        if(x != 1.0)
            b.push_back({1.0 / (1.0 - x), y});
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    n = a.size(), m = b.size();
    for(int i = 0; i < n; i++)
    {
        sx[i] = a[i].second;
        if(i >= 1)  sx[i] += sx[i - 1];
    }
    for(int i = 0; i < m; i++)
    {
        sy[i] = b[i].second;
        if(i >= 1)  sy[i] += sy[i - 1];
    }
    for(int i = 0; i < n; i++)
        work(i);
    cout<<fixed<<setprecision(10)<<res<<'\n';
    return;
}