题解 | #2023牛客寒假算法基础集训营1#
World Final? World Cup! (I)
https://ac.nowcoder.com/acm/contest/46800/A
温馨提示：如有遇到交题解内代码运行超时的情况，可以手动加上读入优化或参考提交记录
首先，感谢一下出题人——炸只因块哥哥！
其次，感谢一下可爱的波奇酱！
最后，安利一下《孤独摇滚》，大家一起波门！
A World Final? World Cup! (I)
签到题
考虑如下：
1.本球踢完，对手剩余所有球都踢进，本方所有球都踢不进是否已经胜利
2.本球踢完，对手剩余所有球都踢不进，本方所有球都踢进是否已经失败
3.注意事项：先手方球踢完时，剩余球比后手方少一个！
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
cin>>T;
while(T--){
int n = 10;
string s;
cin>>s;
s = " " + s;
int a = 0 , b = 0 , ans = -1;
for(int i=1;i<=n;i++){
if(i&1){
a += s[i] - '0';
if(a-b>(n-i+1)/2){
ans = i;
break;
}
if(b-a>(n-i)/2){
ans = i;
break;
}
}
else{
b += s[i] - '0';
if(a-b>(n-i)/2){
ans = i;
break;
}
if(b-a>(n-i)/2){
ans = i;
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60265893
B World Final? World Cup! (II)
hard题
思考过程：考虑四维DP，发现转移复杂度过大，二维DP，无法转移，不会做，摆烂——
C 现在是，学术时间 (I)
签到题
根据H指数式子可以发现，一篇论文可以提供的贡献最多为1（为什么呢？我也不会证，只能说显然了）
那么，每个教授发表其本人写的论文即可，只要至少有一个人引用，那么这篇论文就有贡献，否则没有，所以用论文总数直接减去的引用量为0的数量即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin>>T;
while(T--){
int n;
cin>>n;
int ans = n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(!x) ans--;
}
cout<<ans<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/46800/C
D 现在是，学术时间 (II)
简单题
分类讨论
假设粉色是原矩形，讨论P点位置，共有四种情况：
1.在原矩形内（波奇），那么，最优策略就是以P点和原矩形其中一个点作为对角线的新矩形中，面积最大的那一个
2.在原矩形右上方（归去来兮），那么，最优策略就是以P点和原矩形左下角点作为对角线的新矩形
3.在原矩形上方（大天使），那么，最优策略就是以P点和原矩形左下角点或右下角点作为对角线的新矩形中，面积大的那一个。
4.在原矩形右方（屑贝斯），那么，最优策略就是以P点和原矩形左下角点或左上角点作为对角线的新矩形中，面积大的那一个。
接下来就是计算交与并的面积，需要较好的代码基础快速求出。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LD = long double;
int main(){
int T = 1;
while(T--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x,y,xp,yp;
cin>>x>>y>>xp>>yp;
LD ans = 0;
if(xp>=x && yp>=y)
ans = x*y*1.0/(xp*yp);
else if(xp>=x && yp<=y)
ans = max(x*yp , x*(y-yp)) * 1.0/((xp-x) * max(yp , y-yp) + x*y);
else if(xp<=x && yp>=y)
ans = max(xp*y , (x-xp)*y) * 1.0/((yp-y) * max(xp , x-xp) + x*y);
else if(xp<=x && yp<=y)
ans = max({xp*yp , xp*(y-yp) , (x-xp)*yp , (x-xp)*(y-yp)}) * 1.0/(x*y);
printf("%.10Lf\n", ans);
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60330772
E 鸡算几何
中等题
不太会几何，想到一个非常散兵的做法，然后直接套板子。（讲的比较不清楚）
前提：如果L型两边长度相等，那么一定无法判断是否需要操作三，所以直接特判。
首先把初始状态和最终状态的中点（B）平移至原点，然后将其中初始状态和最终状态的同一条边旋转至同一条坐标轴的同一个方向上，我选的（应该）是y轴正方向（由于边长不同，需要把边进行对应，也就是交换初始状态或最终状态的A、C点，体现在vector上就是翻转），最后考虑两种状态下的剩下一个点是否在y轴同侧，是就说明不一定需要操作三，否则必须使用操作三。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using point_t=long double; //全局数据类型，可修改为 long long 等
constexpr point_t eps=1e-8;
constexpr long double PI=3.1415926535897932384l;
// 点与向量
template<typename T> struct point{
T x,y;
bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const point &a) const {return !(*this<a || *this==a);}
point operator+(const point &a) const {return {x+a.x,y+a.y};}
point operator-(const point &a) const {return {x-a.x,y-a.y};}
point operator-() const {return {-x,-y};}
point operator*(const T k) const {return {k*x,k*y};}
point operator/(const T k) const {return {x/k,y/k};}
T operator*(const point &a) const {return x*a.x+y*a.y;} // 点积
T operator^(const point &a) const {return x*a.y-y*a.x;} // 叉积，注意优先级
int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 测试
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const point &a) const {return (a-(*this)).len2();} // 两点距离的平方
// 涉及浮点数
long double len() const {return sqrtl(len2());} // 向量长度
long double dis(const point &a) const {return sqrtl(dis2(a));} // 两点距离
long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 向量夹角
point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转（给定角度）
point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转（给定角度的正弦与余弦）
};
using Point=point<point_t>;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
cin>>T;
while(T--){
vector<Point> s(3),t(3);
for(auto &[x,y] : s){
cin>>x>>y;
}
for(auto &[x,y] : t){
cin>>x>>y;
}
if(abs(s[1].dis2(s[0]) - s[1].dis2(s[2])) <= eps) goto no;
if(abs(s[1].dis2(s[0]) - t[1].dis2(t[0])) > eps) reverse(t.begin(), t.end());
{
auto [dx,dy] = s[1];
for(auto &[x,y] : s){
x -= dx;
y -= dy;
}
auto d = s[1].dis(s[0]);
auto si = s[0].x/d , co = s[0].y/d;
for(auto &x : s){
x = x.rot(co,si);
}
}
{
auto [dx,dy] = t[1];
for(auto &[x,y] : t){
x -= dx;
y -= dy;
}
auto d = t[1].dis(t[0]);
auto si = t[0].x/d , co = t[0].y/d;
for(auto &x : t){
x = x.rot(co,si);
}
}
if(t[2].x*s[2].x<0 || t[2].y*s[2].y<0) goto yes;
else goto no;
if(0) yes: cout<<"YES"<<endl;
if(0) no: cout<<"NO"<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60377745
F 鸡玩炸蛋人
中等题
并查集，这题比较诈骗，需要一定的思维。
首先读题需要发现，鸡可以在一个点连续下蛋，那么对于蛋只需要考虑有和没有，不需要考虑数量。然后要发现，一个联通块内的点，无论一个联通块内下蛋的情况是什么样的，在连通块内任取两个点都可以满足。由于S、T有顺序关系，并且可以重复，所以点对数量就是连通块大小的平方，记得开long long。
出题人的证明：在一棵连通块的生成树中，首先从S走到T，然后从T进行DFS，每次往回走时下蛋即可。
之后就是讨论有几个连通块内有蛋：
1.为0，那么S、T只要取自同一连通块即可，把所有连通块的贡献求和即可。
2.为1，那么S、T只能取自一个连通块，计算次连通块的贡献即可。
3.大于1，无解，因为鸡无法跨越连通块。
代码如下：
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
vector<int> s(n+1),num=s;
for(int i=1;i<=n;i++){
s[i] = i;
num[i] = 1;
}
function<int(int)> find = [&](int x){
if(s[x]!=x) return s[x] = find(s[x]);
return s[x];
};
auto add = [&](int x,int y){
if(x>y) swap(x,y);
s[y] = s[x];
num[x] += num[y];
};
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
u = find(u);
v = find(v);
if(u!=v) add(u,v);
}
map<int,int> mp;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x) mp[find(i)]++;
}
if(mp.size()>1) cout<<0<<endl;
else if(!mp.size()){
LL ans = 0;
for(int i=1;i<=n;i++){
if(find(i)==i) ans += 1ll*num[i]*num[i];
}
cout<<ans<<endl;
}
else{
int x = mp.begin()->x;
LL ans = num[x];
ans *= num[x];
cout<<ans<<endl;
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60386142
G 鸡格线
中等题
STL战神，有各种数据结构解法，由于数据比较水，一些奇怪的做法也可以通过。
观察式子，需要有一个会收敛的直觉，最直观的就是收敛至100。实际打表一下，可以发现，小于100的正整数，会收敛至99，大于等于100的正整数会收敛至100，而0会收敛为0。并且收敛所需的次数不多
那么，一操作可以转化成直接对区间内每一个元素进行暴力，某一元素已经收敛时，这个元素在后续操作之后可以就不再访问。
因此，我们需要一个数据结构去排除这些不需要访问的元素，可以使用并查集、线段树、树状数组二分等做法。
当然，也可以当STL战神！想到删除操作，最容易想到的是map，将第i个元素存在map[i]中，map[i]收敛时，直接删除map[i]。对每一个操作，使用lower_bound操作可以快速找到第一个需要修改的元素，从此处开始遍历。
注意：map的迭代器需要正确使用，否则容易段错误!
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
LL sum = 0;
map<int,int> a;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[i] = x;
sum += x;
}
a[n+1] = 1;
a[-1] = 1;
while(m--){
int t;
cin>>t;
if(t==2) cout<<sum<<endl;
else{
int l,r,k;
cin>>l>>r>>k;
for(auto it=a.lower_bound(l);it->first<=r;it++){
auto &[i,y] = *it;
for(int j=1;j<=k;j++){
int x = round(sqrt(y)*10);
sum -= y;
sum += x;
if(x==y){
it = a.erase(it);
it--;
break;
}
y = x;
}
}
}
}
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60362566
H 本题主要考察了DFS
签到题
诈骗题，仔细读题可以发现，只需要计算面积，总面积是 ，那么把每一个拼图面积和计算出来，再用总面积一减即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
cin>>T;
while(T--){
int n,m;
cin>>n;
int sum = 0;
for(int i=1;i<=n*n-1;i++){
string s;
cin>>s;
sum += 10 - count(s.begin(),s.end(),'1') + count(s.begin(),s.end(),'2');
}
cout<<n*n*10-sum<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60308439
I 本题也主要考察了DFS
hard题
构造题，看完后没想到（没想），听了讲题发现很简单，待会打原神深渊了，明天再写（发出咕咕咕的声音），开摆！
J 本题竟也主要考察了DFS
hard题
居然真是DFS！不会，讲题听不懂，开摆！
K 本题主要考察了dp
简单题
居然真的是DP，据说有 做法、贪心做法，但我没有脑子。
考虑前 个数字，共有 个1，最后两个数字是什么，也就是 ，然后考虑最后加入的是1还是0时的转移：
dp[i][j][0][0] = min(dp[i-1][j][0][0] , dp[i-1][j][1][0]);
dp[i][j][0][1] = min(dp[i-1][j-1][0][0] , dp[i-1][j-1][1][0] + 1);
dp[i][j][1][0] = min(dp[i-1][j][0][1] , dp[i-1][j][1][1] + 1);
dp[i][j][1][1] = min(dp[i-1][j-1][0][1] + 1 , dp[i-1][j-1][1][1] + 1);
最后在dp[n][m][x][y]中找到最小的即可。
注意事项：特判 为1的情况
代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
if(n<3){
cout<<0<<endl;
break;
}
vector dp(n+1,vector(n+1,vector(2,vector<int>(2,1e9))));
dp[2][0][0][0] = 0;
dp[2][1][0][1] = 0;
dp[2][1][1][0] = 0;
dp[2][2][1][1] = 0;
for(int i=3;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j][0][0] = min(dp[i-1][j][0][0] , dp[i-1][j][1][0]);
if(j>0) dp[i][j][0][1] = min(dp[i-1][j-1][0][0] , dp[i-1][j-1][1][0] + 1);
dp[i][j][1][0] = min(dp[i-1][j][0][1] , dp[i-1][j][1][1] + 1);
if(j>0) dp[i][j][1][1] = min(dp[i-1][j-1][0][1] + 1 , dp[i-1][j-1][1][1] + 1);
}
}
cout<<min({dp[n][m][0][0] , dp[n][m][0][1] , dp[n][m][1][0] , dp[n][m][1][1]})<<endl;
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60289436
L 本题主要考察了运气
签到题
看不懂题，我很抱歉，直接从1开始一个个交或者直接rand！
M 本题主要考察了找规律
波门题
暴力DP，出题人说：本题没有规律，就把用来打表的DP当作std了。
数据范围只有500，考虑二维DP，已经把仙贝分给了 个朋友（屑贝斯手），剩余 个仙贝。
转移时考虑给最后一个朋友分了几个仙贝，贡献为 ，转移就是（有点怪的转移，但是能过）：
dp[i+1][j-k] = max(dp[i+1][j-k] , dp[i][j] + k*1.0/j);
最后剩余的仙贝一定是0，因为把剩余所有仙贝都分给最后一个朋友肯定比只分一部分更优（显然），答案就是 。
代码如下：
#include <bits/stdc++.h>
using namespace std;
using LD = long double;
int main(){
int T = 1;
while(T--){
int n,m;
cin>>n>>m;
vector dp(n+1,vector<LD>(m+1));
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=j;k++){
dp[i+1][j-k] = max(dp[i+1][j-k] , dp[i][j] + k*1.0/j);
}
}
}
printf("%.10Lf",dp[n][0]);
}
return 0;
}
提交记录：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60303868
一定要看《孤独摇滚》！
一定要看《孤独摇滚》！！
一定要看《孤独摇滚》！！！
一定要看《孤独摇滚》！！！！
一定要看《孤独摇滚》！！！！！
一定要看《孤独摇滚》！！！！！！
一定要看《孤独摇滚》！！！！！！！
一定要看《孤独摇滚》！！！！！！！！
一定要看《孤独摇滚》！！！！！！！！！
一定要看《孤独摇滚》！！！！！！！！！！
一定要看《孤独摇滚》！！！！！！！！！！！
一定要看《孤独摇滚》！！！！！！！！！！！！
华为工作强度 806人发布
