今天的题目整体上来说对我这种蒟蒻来说体验感比较好，有思维题但是思维量不大，题目比较迷惑选手，每道题解题思路也比较多。
A:World Final? World Cup! (I)
题意：两队轮流点球，已知十个球的进球状态，求最快第几个点球之后能知道比赛结果
解题思路：当出现一个队伍落后的点球数小于后面剩余的点球机会的时候，就能够看出比赛结果（都是前面一段时间世界杯的经验），例如说：A队伍与B队伍各踢了3球，此时比分为3：0，B球队剩余两次点球机会，此时B球队的最好结果是自己进两球，A球队丢两球，比赛结果为3：2，仍然是输了比赛。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include<iostream> using namespace std; int main() { int t; //一共t个样例 cin>>t; while(t--) { int a=0,b=0; string s; cin>>s; for(int i=0;i<10;++i) { if(s[i]=='1') { if(i&1)b++; else a++; } if((i+1)%2==1) //当此时是A球队点球完毕时 { if(a+(9-i)/2<b) //A球队的最优情况仍然是输 { //cout<<'*'; cout<<i+1<<endl; break; } if(a>b+(9-i)/2+1) //B球队的最优情况仍然是输 { cout<<i+1<<endl; break; } } else{ //当此时是B球队点球完毕时 if(a+(9-i)/2<b) //A球队的最优情况仍然是输 { cout<<i+1<<endl; break; } if(a>b+(9-i)/2) //B球队的最优情况仍然是输 { cout<<i+1<<endl; break; } } } if(a==b)cout<<-1<<endl; //最后双方打平 } return 0; }
代码比较繁杂，主要是怕简化之后有些东西没有考虑清楚。
C:现在是，学术时间 (I)
题意：一共有n个老师每人一篇论文，每一篇论文有一个对应的值（题目中的“引用量”），每一个老师有一个指标H，H的值是该老师手中至少H篇论文的引用量大于等于H"这一命题成立的最大的H，现在求所有老师的指标H和的最大值。
解题思路：对于一篇论文a来说，如果在单独在一个老师手里且这篇论文a的值不为0，则这个老师的指标为1，此时这个论文a的贡献值为1：如果这个论文a是和其他论文一起在一个老师的手里，则此时这个老师的指标最大值为论文的数量（最理想的情况下，也就是全部的论文值都要超过论文数量），此时论文a的贡献值还是1，所以我们不需要刻意把论文集中放在一颗老师的身上，直接对原来的数据进行是否为0的判断累加即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#include <iostream> #include <algorithm> using namespace std; int arr[100005]; int main() { int t; cin>>t; while(t--) { int n,sum=0; cin>>n; for(int i=0;i<n;++i) { cin>>arr[i]; if(arr[i]>0)sum++; } cout<<sum<<endl; } return 0; }
D:现在是，学术时间 (II)
题意：给你三个坐标点，其中两个ab点确定一个矩形，还有一个点c作为另外一个矩形的一点，你需要找到另外一个能够确定矩形的顶点d，使得两个矩形的交集面积除并集面积的值最大。
解题思路：需要证明，但是当时没想这么多，直接默认从矩形ab的四个顶点里面选择一个最远离点c的，证明的过程比较多，后面再补，今天小摆一下。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include<iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int x,y,x1,y1; cin>>x>>y>>x1>>y1; int ansx,ansy; if(x1>x/2)ansx=0; else ansx=x; if(y1>y/2)ansy=0; else ansy=y; double ans,arr; double chang,kuang; if((double)abs(x1-ansx)<x)chang=abs(x1-ansx); else chang=x; if((double)abs(y1-ansy)<y)kuang=abs(y1-ansy); else kuang=y; ans=abs((ansx-x1)*(ansy-y1))+abs(x*y)-abs(chang*kuang); printf("%.9fn",chang*kuang*1.0/ans); } return 0; }
H:本题主要考察了DFS
题意：有一个n*n的拼图，缺了一块，求缺的这一块的造价
思路1：这个是我一开始的做题思路，每一个凸出来的拼图都要有一个对应的凹进去的拼图对应，一块拼图有上下左右，对应题目给的字符串的顺序就是上右下左，右边有一个2的话，就要有一个拼图的左边是1，也就是说右边2的数量和应该和左边1的数量和一样，如果没有缺少的话，通过这个方式就可以定位到缺了什么样的拼图，然后直接计算成本就行。
代码1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; string s; int arr[4][3]{0}; for(int i=0;i<n*n-1;i++) { cin>>s; for(int j=0;j<4;++j) arr[j][s[j]-'0']++; //cout<<"**"<<s<<endl; } int x=0,y=0; for(int i=0;i<4;++i) { if(arr[i][1]<arr[(i+2)%4][2])x++; if(arr[i][1]>arr[(i+2)%4][2])y++; //cout<<i<<'*'<<arr[i][1]<<'*'<<arr[(i+2)%4][2]<<endl; } cout<<10-x+y<<endl; //cout<<endl<<x<<'*'<<y; } return 0; }
思路2：造价与面积有关，而且和面积呈正比，最后总的面积已知，每一个小拼图也知道，只需要求总的造价减去每一个小拼图的造价即可，最后化简式子直接求凸和凹的个数即可
代码2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17#include <iostream> using namespace std; char c[100005]; int main(){ int t;cin>>t; while(t--){ int n,x=0,y=0; cin>>n; for(int i=0;i<n*n*4-4;i++){ cin>>c[i]; if(c[i]=='1')x++; if(c[i]=='2')y++; } cout<<10+x-y<<endl; } }
L:本题主要考察了运气
题意：一共有五个队伍，每个队伍按顺序排列四个人，每一次你可以在下面的两个类型问题中选一个询问，一直问到你100%确定目标的人，求期望的询问次数。
1、这个人是否属于队伍（1~5）
2、这个人时候是队伍（1~5）中间第（1~4）的那个人
每次得到回答是或否
思路：首先要确定是哪一个队伍，然后在确定是第几个人，确认队伍的询问次数分别为：1、2、3、4、4（假设从队伍一按顺序询问，这里对应目标在队伍12345顺序），在队伍五的时候，我们经过前面四次询问就能够确定这个目标就是在队伍五，同样的方法确定目标在队伍中的顺序，列出询问表格：
最后将5.05转化为题目中的选项即可。
代码：
1
2
3
4
5
6
7
8#include<iostream> using namespace std; int main() { cout<<32; return 0; }
M:本题主要考察了找规律
题意：把n个物品分给m个人（可以不分完物品也可以有人没分到物品），当你有y个物品然后你分给一个人x个，则好感度提升x/y，每个人只能分一次，分了若干次之后好感度提升的和最大是多少。
解题思路：这道题和找规律一点关系没有，后面直接打表做的，直接dp，设数组dp[i][j]表示已经给i个人分了物品，分出去了共j个的最大提升好感度之和。
dp[i][j]=max(dp[i][j],k*1.0/j+dp[i-1][j-k])
答案为dp[n][m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#include<iostream> using namespace std; double dp[505][505]; int main() { for(int i{1};i<501;++i) { for(int j{1};j<501;++j) { for(int k{0};k<=j;++k) dp[i][j]=max(dp[i][j],k*1.0/j+dp[i-1][j-k]); } } int n,m; cin>>n>>m; printf("%.15f",dp[n][m]); return 0; }
最后
以上就是小巧面包最近收集整理的关于牛客2023牛客寒假算法基础集训营1题解（ACDHLM题解）的全部内容，更多相关牛客2023牛客寒假算法基础集训营1题解（ACDHLM题解）内容请搜索靠谱客的其他文章。
发表评论 取消回复