欢乐赛#33题解
2024-11-10 22:00:05
发布于：广东
T1:
第一道题，不简单就不是欢乐赛，但是还是有很多新手这一题做不出来。如果直接
cout << "\n";
只会输出一个换行，正确做法如下：
print("\\n")//（别问我为什么用python，因为懒~~~~）
T2:
这题也十分简单，用斐波那契公式求和公式：
n * (n + 1) / 2;
但是要注意，因为n最大是INT_MAX,所以记得开long long。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t --){
long long x;
cin >> x;
cout << x * (x + 1) / 2 << endl;//求和公式
}
return 0;
}
T3:
这题的一个高精度符号’∑‘让新手们知难而退，太好了，但是其实说白了就是用每个韵母相对应的出现次数 * W[i]，理清思路即可。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long a,e,ii,o,u;
int main(){
string s;
cin >> s;
for(int i = 0;i < s.size();i ++){
if(s[i] == 'a'){
a ++;
} else if(s[i] == 'e'){
e ++;
} else if(s[i] == 'i'){
ii ++;//为了防止重名用ii代替i
} else if(s[i] == 'o'){
o ++;
} else if(s[i] == 'u'){
u ++;
}
}
long long ans = 0;
long long wa,we,wi,wo,wu;
cin >> wa >> we >> wi >> wo >> wu;
cout << a * wa + e * we + ii * wi + o * wo + u * wu;//计算答案
return 0;
}
T4:
我认为这一题是本赛出最后一题以外最难的题。对我来说还是小菜一碟，对于没有接触过查找因数的新手来说容易time limit error。这题用的贪心算法可能对于新手来说也会有一定难度。我来介绍两个版本。
版本一：
#include<bits/stdc++.h>
using namespace std;
int d[100005];
int f(int x){
int sum = 0;
for(int i = 1;i <= x;i ++){
if(x % i == 0){
sum ++;
}
}
return sum;
}
bool cmp(int a,int b){
return a > b;
}
int main(){
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i ++){
int x;
cin >> x;
d[i] = f(x);
}
sort(d,d + n,cmp);
int sum = 0;
for(int i = 1;i <= n;i ++){
sum += d[i - 1];
if(sum >= m){
cout << i;
break;
}
}
return 0;
}
根据我用一条命来换的测量，这样做的话会有几个TLE，其实可以优化f函数，把找因数的函数时间复杂度从O(N) 降到O(log N)。
最终AC代码如下：
#include<bits/stdc++.h>
using namespace std;
int d[100005];
int f(int x){
int sum = 0;
for(int i = 1;i * i <= x;i ++){//因为因数总会成双成对出现，所以搜到sqrt（n）就行了
if(x % i == 0){
if(i * i != x){
sum += 2;
} else {
sum ++;//如果是完全平方数就只+1
}
}
}
return sum;
}
bool cmp(int a,int b){
return a > b;
}
int main(){
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i ++){
int x;
cin >> x;
d[i] = f(x);
}
sort(d,d + n,cmp);//排序
int sum = 0;
for(int i = 1;i <= n;i ++){//贪心算法
sum += d[i - 1];
if(sum >= m){
cout << i;
break;
}
}
return 0;
}
T5:
这题不难，顺着题目的意思来就行了。记得下标不要弄混。
题目代码：
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
int t;
cin >> t;
while(t --){
int n;
cin >> n;
for(int i = 0;i < n;i ++){
cin >> a[i];
}
bool flag = 1;
for(int i = 0;i < n / 2;i ++){
if(a[i] != a[n - i - 1]){//是否回文
flag = 0;
break;
}
}
if(flag == 1){
cout << "No\n";
continue;
}
long long sum1 = 0,sum2 = 0;
for(int i = 0;i < n;i ++){//是否奇数偶数为的和相等
if(i % 2 == 0){//我的下标是从0开始的，所以是==0
sum1 += a[i];
} else {
sum2 += a[i];
}
}
if(sum1 != sum2){
cout << "No\n";
continue;
}
cout << "Yes\n";
}
return 0;
}
T6:
这题我的做法是拼命打补丁（所以死了很多次）。
要注意的有四项:
1.当数字形如xxxx......(x < 9)时，最优解是这个数字的位数-1个9，这是最显而易见的规律。
e.g : n = 53423,ans = 9999。
2.当数字的每一位都是九时，答案就是它本身。
e.g : n = 999,ans = 999。
3.当数字除了最后一位其他都是9时，答案也是它本身。
e.g : n = 9998,ans = 9998。
4.当数字的大部分位都是9，中间的几位<9时，答案是这个数字的位数-1个9。
e.g : n = 9899,ans = 999。
衣衫褴褛的代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
string n;
char c;
int flag = 0;
while(cin >> c){
if(c != '9') flag ++;
n += c;
}
if(n[n.size() - 1] != '9' and flag == 1 or n.size() == 1 or flag == 0){//直接输出n的情况
cout << n;
} else {
for(int i = 0;i < n.size() - 1;i ++) cout << 9;//全部输出9的情况
}
return 0;
}
如果这个题解对你有用，希望能点个赞支持一下！
这里空空如也
有帮助，赞一个