2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite
C. Catch You Catch Me
解题思路:
站在距离出口最近的点等深度深的蝴蝶飞上来即可。
时间复杂度:\(O(n)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
scanf("%d",&n);
vector<vector<int>> adj(n + 1);
for(int i = 1;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> p(n + 1),ans(n + 1);
auto dfs = [&](auto self,int u,int fa) -> int
{
p[u] = fa;
ans[u] = 1;
for(auto v : adj[u])
{
if(v == fa)
{
continue;
}
ans[u] = max(ans[u],self(self,v,u) + 1);
}
return ans[u];
};
dfs(dfs,1,-1);
ll res = 0;
for(int i = 1;i<=n;i++)
{
if(p[i] == 1)
{
res += ans[i];
}
}
printf("%lld\n",res);
}
int main()
{
int t = 1;
while(t --)
{
solve();
}
return 0;
}
G. Let Them Eat Cake
解题思路:
由于每个数互不相同，所以对于每个数来说，我们和右边一位比较，例如\(i-1,i,i+1\)。
若\(a[i-1] < a[i]<a[i+1]\)，则删\(a[i-1],a[i]\).
若\(a[i-1] > a[i] > a[i + 1]\)，则删\(a[i],a[i+1]\)。
若\(a[i-1] > a[i] < a[i+1]\)，则删\(a[i]\)。
若\(a[i-1] < a[i] > a[i+1]\)，则删\(a[i-1],a[i+1]\)。
如上举例，在看4个的情况。
每三个中最少删1个，没四个中最少要删两个。因为三个中有两对，四个中有三对。最多两对答案相同。
所以直接暴力枚举即可
时间复杂度:\(O(nlogn)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
void solve()
{
int n;
scanf("%d",&n);
vector<int> a(n);
for(int i = 0;i<n;i++)
{
scanf("%d",&a[i]);
}
int cnt = 0;
while(a.size() != 1)
{
vector<int> b;
for(int i = 0;i<n;i++)
{
if(i == 0)
{
if(a[0] > a[1])
{
b.push_back(a[0]);
}
}
else if(i == n - 1)
{
if(a[n - 1] > a[n - 2])
{
b.push_back(a[n - 1]);
}
}
else
{
if(a[i] > a[i-1] && a[i] > a[i+1])
{
b.push_back(a[i]);
}
}
}
cnt ++;
a = b;
n = a.size();
}
cout<<cnt;
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
}
H. Life is Hard and Undecidable, but...
解题思路:
题目看似很长，其实构造简单。
斜着构造一条长度为\(2k - 1\)的链即可。
注意：图中没有活细胞的位置上默认存在死细胞，这也是不能横竖构建链的原因。
时间复杂度:\(O(k)\)
代码:
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int k;
scanf("%d",&k);
int n = 2 * k - 1;
printf("%d\n",n);
for(int i= 1;i<=n;i++)
{
printf("%d %d\n",i,i);
}
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
}
A. Ban or Pick, What's the Trick
解题思路:
首先，每次选最大的，如果时自己的就\(pick\)，如果是对面的就\(ban\)的贪心是错的。
如果我选择\(pick\)，那么选自己中当时可选的最大的。如果我选择\(ban\)，那么选对面可\(ban\)的种最大的。这个贪心是对的。
\(f[i][k1][k2]\)：在第\(i\)论\(bp\),\(A\)方\(pick\)了\(k1\)位英雄,\(B\)方\(pick\)了\(k2\)位英雄，此时\(A\)方的最大领先分数。
注意，轮数的就看判断是哪方进行\(bp\)。本题要求选的是两方按照对自身最优的策略进行\(bp\)。所以从自身角度看对面的正收益对于自身都是负收益。
那么我们可以分为进行\(pick\)和进行\(ban\)两个子集进行转移。
\(r1 = \lfloor\frac {1}{i}\rfloor\),表示\(A\)队已经\(bp\)过的总次数。
\(ban2 = r1 - k1\),表示\(A\)队已经\(ban\)了\(B\)队多少人。
\(p2 = k2 + ban2 + 1\),表示如果从\(B\)队的池子中选人，选第几个。
本题直接转移搜索会\(TLE\)，所以使用记忆化搜索来优化时间。
对于当前能否选择记得进行合法性判断。
单纯地\(ban\)对面不会带来直接性收益，只有确实\(pick\)到了，才会有正收益。
时间复杂度:\(O(n * k^2)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = -1e18;
bool cmp(int a,int b)
{
return a > b;
}
void solve()
{
int n,k;
scanf("%d %d",&n,&k);
vector<int> a(n + 1),b(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i = 1;i<=n;i++)
{
scanf("%d",&b[i]);
}
vector<vector<vector<ll>>> f(n + n + 10,vector<vector<ll>>(k + 1,vector<ll>(k + 1,-INF)));
vector<vector<vector<bool>>> st(2 *n + 10,vector<vector<bool>>(k + 1,vector<bool>(k + 1)));
sort(a.begin() + 1,a.end(),cmp);
sort(b.begin() + 1, b.end(),cmp);
auto dfs = [&](auto self,int i,int k1,int k2) -> ll
{
if(i > 2 * n)
{
return 0;
}
if(st[i][k1][k2])
{
return f[i][k1][k2];
}
ll &ans = f[i][k1][k2];
st[i][k1][k2] = true;
ll r1 = i / 2;
ll r2 = (i - 1) / 2;
ll ban1 = r2 - k2;
ll ban2 = r1 - k1;
ll p1 = k1 + ban1 + 1;
ll p2 = k2 + ban2 + 1;
if((i & 1))
{
if(k1 < k && p1 <= n)
{
if(p2 <= n)
{
ans = max(-self(self,i + 1,k1 + 1,k2) + a[p1],-self(self,i + 1,k1,k2));
}
else
{
ans = -self(self,i + 1,k1 + 1,k2) + a[p1];
}
}
else
{
ans = -self(self,i + 1,k1,k2);
}
}
else
{
if(k2 < k && p2 <= n)
{
if(p1 <= n)
{
ans = max(-self(self,i + 1,k1,k2 + 1) + b[p2],-self(self,i + 1,k1,k2));
}
else
{
ans = -self(self,i + 1,k1,k2 + 1) + b[p2];
}
}
else
{
ans = -self(self,i + 1,k1,k2);
}
}
// cout<<i<<' '<<k1<<' '<<k2<<' '<<ans<<endl;
return ans;
};
printf("%lld",dfs(dfs,1,0,0));
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
}
M. Rock-Paper-Scissors Pyramid
解题思路:
举例：
\(SPR\)最终答案是\(S\)。
虽然\(S\)打不过\(R\),但如果\(S和R\)之间有一个\(P\),那么，\(P\)后面的所有\(R\)一定碰不到\(S\).
所以，从左往右扫，遇到打不过的就不断出栈知道空或者打得过。
打得过了就入栈。
最终栈底就是胜者。
时间复杂度:\(O(n)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
string s;
cin>>s;
auto battle = [&](char a,char b)
{
if(a == 'S' && b == 'P')
{
return true;
}
if(a == 'P' && b == 'R')
{
return true;
}
if(a == 'R' && b == 'S')
{
return true;
}
return false;
};
stack<int> q;
int n = s.size();
for(int i = 0;i<n;i++)
{
while(!q.empty() && !battle(s[q.top()],s[i]))
{
q.pop();
}
q.push(i);
}
char ans;
while(q.size())
{
ans = s[q.top()];
q.pop();
}
printf("%c\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
D.Gambler's Ruin
解题思路:
我们先对\(p\)进行降序排序。
根据题意不难得知,若\(p_i \cdot x\geq 1\),那么\(p_k \cdot x \geq 1,(k \leq i)\)。对于\(y\)则是反序。
也就是说，对于\(i\)的前缀都会投\(BU\),对于\(j\)的后缀都会投\(BC\).
对应的边界\(x\)即为\(\frac{1}{p_i}\),毕竟如果超出这个边界但又不满足\(p_{i + 1} \cdot x \geq 1\),多出的赔率不就是白送钱吗。
对于\(j\)自然就是\(\frac{1}{1 - p_j}\)。
那么答案就是
\[pre_i +suf_j - max(\frac{pre_i}{p_i},\frac{suf_j}{1-p_j}) \]我们固定\(i\)。
如果我们将\(j\)向后移，\(p_j\)减小，\(1-p_j\)增大，\(suf_j\)减小，所以\(\frac{suf_j}{1-p_j}\)减小。
如果此时\(\frac{suf_j}{1-p_j}\geq \frac{pre_i}{p_i}\)，那么
\[pre_i +suf_j - max(\frac{pre_i}{p_i},\frac{suf_j}{1-p_j}) = pre_i - \frac{p_j}{1 - p_j}suf_j \]其中，\(\frac{p_j}{1 - p_j}suf_j\)，随着\(j\)不断右移而减小。答案就不断增大，直到\(\frac{suf_j}{1-p_j}\leq \frac{pre_i}{p_i}\)。假设这个大小翻转的边界为\(k\)，那么答案就在\(j =k和j = k - 1\)之中。根据上面的式子可知，此时\(\frac{p_j}{1 - p_j}suf_j\)来到最小，答案达到最大。
对于\(i\)的右移，\(p_i\)减小,\(pre_i\)增大,\(\frac{pre_i}{p_i}\)增大。所以对应的\(j\)的边界值\(k\)下标也只会往后移。
如果此时\(\frac{suf_j}{1-p_j}\leq \frac{pre_i}{p_i}\)，那么
\[pre_i +suf_j - max(\frac{pre_i}{p_i},\frac{suf_j}{1-p_j}) = suf_j - \frac{p_i - 1}{p_i}pre_i \]若\(j\)不变，答案随\(i\)增大而减小。
这样\(i\)和\(j\)之间就具有单调性了，即随着\(i\)变大，\(j\)的边界也会变大。
双指针求解。
时间复杂度:\(O(n)\)
代码:
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
#define fi first
#define se second
const double eps = 1e-10;
bool cmp(pdd a,pdd b)
{
return a.fi > b.fi;
}
void solve()
{
int n;
scanf("%d",&n);
vector<pdd> v(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%lf %lf",&v[i].fi,&v[i].se);
}
sort(v.begin() + 1,v.end(),cmp);
vector<double> pre(n + 10),suf(n + 10);
int cnt = 0;
for(int i = 1;i <= n;i++)
{
if(i == 1 || fabs(v[i].fi - v[i-1].fi) > eps)
{
v[++cnt] = v[i];
}
else
{
v[cnt].se += v[i].se;
}
}
n = cnt;
for(int i = 1;i <= n;i ++)
{
pre[i] = pre[i-1] + v[i].se;
}
for(int i = n;i; i --)
{
suf[i] = suf[i+1] + v[i].se;
}
auto get = [&](int i,int j) -> double
{
return pre[i] + suf[j] - max(pre[i] / v[i].fi,suf[j] / (1.0 - v[j].fi));
};
int j = n;
double ans = 0;
for(int i = 1;i<=n;i ++)
{
if(i == n || fabs(v[i].fi - v[i + 1].fi) > eps)
{
while(j > i && pre[i] / v[i].fi > suf[j] / (1.0 - v[j].fi))
{
j --;
}
ans = max(ans,get(i,j + 1));
if(j <= i)
{
break;
}
ans = max(ans,get(i,j));
}
}
printf("%.12lf",ans);
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
}