社区首页 >专栏 >48days强训——day3

48days强训——day3

秋邱

发布于 2025-03-26 06:04:37

2500

代码可运行

文章被收录于专栏：笔记笔记

运行总次数：0

代码可运行

第一题：简写单词

链接：简写单词_牛客题霸_牛客网

描述规定一种对于复合词的简写方式为只保留每个组成单词的首字母，并将首字母大写后再连接在一起比如 “College English Test”可以简写成“CET”，“Computer Science”可以简写为“CS”，“I am Bob”简写为“IAB” 输入一个长复合词（组成单词数 sum,sum≥1且sum≤100sum,sum≥1且sum≤100,每个单词长度len,len≥1且len≤50len,len≥1且len≤50），请你输出它的简写 输入描述： 输入一个复合词 输出描述： 输出一行，表示复合词的简写 示例1 输入： College English Test 输出： CET

思路：这题可以用string的成员函数getlin，也可以直接操作。其核心算法是移动窗口

//直接
#include <bits/stdc++.h>
using namespace std;

int main() 
{
   string s;
   while(cin >>s )
   {
        if(s[0] <= 'z'  && s[0]>='a') cout << (char)(s[0]-32);
        else cout << s[0];
   }
   return 0;
}


//getline
#include <bits/stdc++.h>
using namespace std;

int main() 
{
    string s;
    getline(cin, s);
    
    cout << (char)toupper(s[0]);

    for (int i = 1; i < s.size(); i++)
     {
        if (s[i - 1] == ' ') 
        {  
            if (s[i] >= 'a' && s[i] <= 'z') cout << (char)(s[i] - 32); 
            else cout << s[i];  
        }
    }

    return 0;
}

第二题：除2！

链接：除2！

题目描述 给一个数组，一共有 n n\ n 个数。你能进行最多 k k\ k 次操作。每次操作可以进行以下步骤：

选择数组中的一个偶数 ai，将其变成 ai/2 。

现在你进行不超过 k k\ k 次操作后，让数组中所有数之和尽可能小。请输出这个最小的和。 输入描述: 第一行输入两个正整数 n n\ n 和 k k\ k ，用空格隔开第二行输入n n\ n 个正整数 aia_iai 数据范围： 1≤n≤100000，1≤k≤1091 ≤ n≤100000，1≤k≤10^91≤n≤100000，1≤k≤109 1≤ai≤1091≤a_i≤10^91≤ai≤109 输出描述: 一个正整数，代表和的最小值。 示例1 输入 5 3 2 4 8 10 11 5 3 2 4 8 10 11 输出 24 24 说明对8操作2次，对10操作1次，最后的数组是2 4 2 5 11。可以证明这样的操作是最优的。

思路：将所有的偶数放入一个大根堆里，每次对最大的数进行减半，减半之后，判断是否为偶数。

偶数，入堆。这里是相加，数据有点大，需要采用long long来存储。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,k;
    long long sum = 0,x;
    cin >> n >> k;
    priority_queue<long long> q;
    while(n--)
    {
        cin >> x;
        sum += x;
        if(x % 2==0)q.push(x);
    }
    while(k-- && q.size())
    {
        auto a = q.top() / 2;
        q.pop();
        sum -= a;
        if(a %2==0)q.push(a);
    }
        
    cout << sum << endl;
    return 0;
}

第三题：Fibonacci数列

链接：Fibonacci数列_牛客题霸_牛客网

描述 Fibonacci数列是这样定义的： F[0] = 0 F[1] = 1 for each i ≥ 2: F[i] = F[i-1] + F[i-2] 因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。 输入描述： 输入为一个正整数N(1 ≤ N ≤ 1,000,000) 输出描述： 输出一个最小的步数变为Fibonacci数" 示例1 输入： 15 输出： 2

思路：找到离输入数目标数x 最近的两个相邻斐波那契数 b 和 c（b ≤ x < c），然后计算 x 到它们的较小距离并输出

代码：

#include <bits/stdc++.h>
using namespace std;

int main() 
{
   int a = 1,b = 1,c = 2,x = 0;
   cin >> x;
   while(c < x)
   {
        a = b;
        b = c;
        c = a + b;
   }
   cout << min(c-x,x -b);
}

总结：

字符处理：toupper和tolower

数字转字符串：to_string

字符串转数字：stoi

int main()
{
	char ch ;
	cout << (char)toupper('a') << endl; // 'A'
	cout << (char)tolower('B') << endl;  // 'b'

	int num = 123;
	string str = to_string(num);  // "123"

	string str = "123";
	int num = stoi(str);  // 123

	return 0;
}