【牛客】几何糕手、国际裁判带师、数位dp?、灵异背包、矩阵快速幂签到、第一次放学

《几何糕手》

题目链接

题目描述

“芝士肾么？”

地上有一根木桩，在木桩上栓有一根长度为 a 的木绳，木绳的末端还栓有一根长度为 b 的木棍，现在小沙想要知道，木棍可能扫过的位置在地面上的投影面积有多大。

输入描述
第一行输入两个正整数 a，b，代表木绳以及木棍的长度。
保证有1≤a,b≤100。

输出描述
输出一个数字代表答案，答案保留10位小数。

示例1：
输入：

1 1

输出：

12.5663706144

思路

把木棍和绳子的长度加起来作为圆的半径，然后直接求圆的面积即可，这里想要使用圆周率Π的话可以使用acos(-1)来表示

代码

#include<bits/stdc++.h>
using namespace std;int main()
{double a,b;cin>>a>>b;printf("%.10lf",acos(-1)*pow(a+b,2));return 0;
}

《国际裁判带师》

题目链接

题目描述

“蒸馍？你不福气？”

在很多比赛中，会有如下图所示的计分表，每次得分之后会翻动来表示得分。

先给定如上图所示记分表，并给定一个长度为n 的比赛获胜记录，小沙需要记录整场比赛中，每次计分表变化之后，数字 0 出现了多少次。
小沙：“ACMer，帮帮我”。

输出描述
链接：
第一行，输入一个长度不超过 n 的字符串，保证字符串中仅包含 a 和 b。
其中 a 代表红方获胜得一分，b 代表蓝方获胜得一分。
保证有1≤n≤99。

示例1：
输入：

aab

输出：

8

说明：

第一次红方得分，计分表变成 0001，出现了3 个 0。 第二次红方得分，计分表变成 0002，出现了3 个 0。
第一次蓝方得分，计分表变成 0102，出现了 2 个 0。 总计出现了 8 次数字 0。

思路

遍历题目给出的字符串，记录每一个环节a和b对应的分数然后对每一个和环节a和b的分数计算有多少个0。

代码

#include<bits/stdc++.h>
using namespace std;int solve(int n)
{int ans=0;while(n>0){if(n%10==0)ans++;}return ans;
}int main()
{string s;cin>>s;int a=0,b=0;int ans=0;for(int i=0;i<s.size();++i){if(s[i]=='a')a++;else b++;if(a/10==0)ans++;if(a%10==0)ans++;if(b/10==0)ans++;if(b%10==0)ans++;}cout<<ans;return 0;
}

《数位dp?》

[题目链接](https://ac.n
owcoder.com/acm/contest/66877/A)

题目描述

给定一个数字n，你可以对它进行接下来的操作——

• 选择数字中任意一个数位删除

例如对1024选择操作百位，数字则变成了124；对1024选择操作千位，数字则变成了024

我们称一个数字是干净的，当且仅当数字满足以下任意一种情况：

• 这个数字是偶数且不含前导零
• 这个数字为空

请问最少需要进行多少次操作，使得数字n变成干净的

输入描述
第一行包含一个整数 n (1≤n≤10⁹)，表示这个数字的大小
输入的数字保证不含前导零

输出描述
输出最少需要的操作次数。
注意，因为一定能使得数字删成空，所以当前数字一定能变成干净的

示例1：
输入：

1024

输出：

0

说明：

当前数字无需操作便满足条件

示例2：
输入：

3

输出：

1

说明：

最少只需要删除一次即可把数字删成空
‘3’⇒’’
​

示例3：
输入：

233

输出：

2

说明：

最少只需要删除两次即可把数字删成偶数
233⇒23⇒2

思路

简单模拟，把这个数从后面往前面一直删除一直到遇到偶数就停止

代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;int ans=0;while(n){if(n%2==0)break;n/=10;ans++;}cout<<ans;return 0;
}

《灵异背包》

题目链接

题目描述

有n个正整数，现在，你可以选择将其中一些数放进灵异背包中，使得背包里面所有数的总和为偶数且最大，求能得到的最大值是多少？

注意：如果你不将任何数放进灵异背包，此时背包总和为0

输出描述
第一行包含一个正整数n (1≤n≤10⁵ )，表示数字的数量
接下来n行包含n个正整数 a1 ,a2…,an (1≤ai ≤2×10⁴)，表示数字的大小

示例1：
输入：

3
2
5
6

输出：

8

说明：
当灵异背包里面有(2,5,6)，此时总和为2+5+6=13，为奇数，不满足条件
当灵异背包里面有(2,6)，此时总和为2+6=8，为偶数，且为最大值

示例2：
输入：

1
3

输出：

0

说明：

选择的灵异背包为空，总和为0

思路

偶数全部都可以加进来，奇数需要分类讨论，如果奇数个数是偶数个也可以全部加入，如果是奇数个就去掉最小的奇数

代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n;bool pd=0;long long minzhi=INT_MAX;long long ans=0;cin>>n;long long input;while(n--){cin>>input;ans+=input;if(input&1){pd^=1;minzhi=min(minzhi,input);}}if(pd)ans-=minzhi;cout<<ans;return 0;
}

《矩阵快速幂签到》

题目链接

题目描述

输入描述
一个正整数 （1≤n≤998244351）

输出描述
一个整数，对应答案。

示例1：
输入：

1

输出：

2

示例2：
输入：

2

输出：

3

思路

这道题就是诈骗题，无脑输出一下最前面的那几项找找规律就会发现直接输出n+1就可以了

代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;cout<<(n+1)%998244353;return 0;
}

《第一次放学》

题目链接

题目描述

输入描述

输出描述
一个整数，表示目前学校里最多有多少同学是属于同一个班级的。

示例1：
输入：

6 3 3
3 1 2 3 3 2

输出：

3

思路

题目询问最多多少个同学是同一个班级，那我们直接找最大的那个班级进行对比，如果那个班级的人数更多那么剩下的n-k个人都是这个班级的，否则就是这个班级的人加上其他的班级的人，此时输出人数最大的班级的人数

代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n,m,k;int a[(int)1e5+10];cin>>n>>m>>k;int input;int maxzhi=0;for(int i=0;i<n;++i){cin>>input;a[--input]++;maxzhi=max(maxzhi,a[input]);}if(maxzhi>n-k)cout<<n-k;else cout<<maxzhi;return 0;
}