526互联

2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite GCHMAD

发布时间 2023-09-28 11:10:12作者: magicat

2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite

目录

VP 情况

队友告诉我题意很顺利过了两签到，对着C虚空写法，搞了一个if(n=3)while(1)的样例发现构造假了，然后马上过了，但是罚时很多然后队友过了石头剪刀布，读了A，很快想到了dp和转移方程，但不知道怎么转移好，最后结束比赛了，看了大家用记忆化搜索竟然这么好些，然后补了DM，这个D我想了很久，一直不懂怎么枚举和三分这个赔率，写了好几个版本，直到今天终于想明白了。
image

G - Let Them Eat Cake

每轮操作删掉一半的数，已得知操作次数最多只有 \(\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

对于1的儿子，其答案是以其儿子为根子树的深度

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...

构造方式见代码

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

观察出有单调栈的特点，根据特点直接去模拟单调栈

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

轮流操作，我可以选择选一个我方能力值最大的英雄，也可以禁掉对方能力值最大的英雄

\(f_{pos,i,j}\)状态就是第 \(pos\) 轮，A选了 \(i\) 个英雄，\(B\) 选了 \(j\) 个英雄，而双方禁用的英雄数量是可以确定的，用记忆化搜索写就行

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 个, B 选了 p 个
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

选择枚举一个队的赔率，三分另一个队的赔率

  1. 将两队预测胜率从小到大排序
  2. 前缀和处理
  3. 枚举A队赔率
  4. 三分另一队赔率

这个我很快想到了解法，但是一直不知道怎么处理1,2操作，写了好多个版本一直过不了样例，过了1周再写就过了

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;
}