C++笔试强训day3

目录

1.简写单词

2.dd爱框框

3.除2！

1.简写单词

链接

我的思路超级简单，就是将输入的每个string存入vector，然后遍历每个string的第一个元素，如果为小写字母，就-32存入，若为大写，则直接存入。

详细代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 110;
vector<string> vs(N);
int main() {
    int sum = 0;
    int i = 0;
    while (cin >> vs[i]) {
        i++;
        sum++;
    }
    string ret;
    for (int i = 0; i < sum; ++i) {
        if (vs[i][0] >= 'a' && vs[i][0] <= 'z') {
            ret += vs[i][0] - 32;
        } else {
            ret += vs[i][0];
        }
    }
    cout << ret << endl;
}

2.dd爱框框

链接

我一开始的想法是暴力枚举，然后再用滑动窗口优化暴力，将每个符合条件的l和r下标存入一个tmp结构体中，最后遍历这个结构体完成解题。

详细代码：

#include <iostream>
#include <vector>

using namespace std;
const int N = 1e7 + 10;

struct tmp
{
    int l;
    int r;
    int dist;
}tmp[N];

int main()
{
    int n, target;
    cin >> n >> target;

    vector<int> a(N);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    if (n == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    int ans = 0x3f3f3f3f;
    int l = 0;
    int r = 0;
    int k = 0;
    int sum = a[0];

    while (r < n)
    {
        if (sum >= target)
        {
            tmp[k].l = l + 1;
            tmp[k].r = r + 1;
            tmp[k].dist = r - l + 1;
            k++;

            ans = min(ans, r - l + 1);
            l++;
            sum -= a[l - 1];
        }
        else
        {
            r++;
            sum += a[r];
        }
    }

    int prevl;
    int prevr;
    for (int i = 0; i < k; ++i)
    {
        if (tmp[i].dist == ans)
        {
            prevl = tmp[i].l;
            prevr = tmp[i].r;
            break;
        }
    }

    for (int i = 0; i < k; ++i)
    {
        if (tmp[i].dist == ans)
        {
            if (tmp[i].l <= prevl)
            {
                l = tmp[i].l;
                r = tmp[i].r;
            }
            prevl = tmp[i].l;
            prevr = tmp[i].r;
        }
    }

    cout << l << ' ' << r << endl;

    return 0;
}

虽然这段代码通过全部用例，但是几乎是卡时间通过，而且占用内存也大：

于是参考的一下正解代码，虽然也是滑动窗口优化，但是在处理数据方面没有我的这么繁琐：

#include <iostream>
using namespace std;

const int N = 1e7 + 10;
int arr[N];
int n, x;
int main()
{
	cin >> n >> x;
	for (int i = 1; i <= n; i++) cin >> arr[i];

	int left = 0, right = 0, sum = 0;
	int retLen = N, retLeft = -1, retRight = -1;

	while (right <= n)
	{
		sum += arr[right];
		while (sum >= x)
		{
			if (right - left + 1 < retLen)
			{
				retLeft = left;
				retRight = right;
				retLen = right - left + 1;
			}
			sum -= arr[left++];
		}
		right++;
	}

	cout << retLeft << " " << retRight << endl;

	return 0;
}

时间都差不多，毕竟都是一个算法，但内存大大优化了。

就是这段代码我唯一不理解的是为什么不用判断当有两个区间长度一致是l的大小。

3.除2！

链接

看到题目描述中最小的和，那就是每次都找最大的偶数除以2。

这时就很容易想到优先队列（也就是堆）。

堆创建时默认为大根堆。

详细代码：

#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

int n,k;

int main()
{
    cin >> n >> k;
    int ai = 0;
    ll sum = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < n; ++i)
    {
        cin >> ai;
        sum += ai;
        if(ai % 2 == 0)
            pq.push(ai);
    } 
    
    while (pq.size() && k--)
    {
        int t = pq.top();
        pq.pop();
        
        sum -= t / 2;
        if(t / 2 % 2 == 0)
            pq.push(t / 2);
    }
    
    cout << sum << endl;
    return 0;
}

while循环中的pq.size()一定不要忘记判断。不然只能过50%。