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}\)。
那么答案就是
我们固定\(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}\)，那么
其中，\(\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}\)，那么
若\(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();
}
}
- Programming Collegiate Mianyang Contest Onsiteprogramming collegiate mianyang contest programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate contest harbin programming contest campus onsite programming collegiate codeforces contest