百度暑期前端 笔试

第一题：

没有用map，直接把字符串sort以后比较是否相等

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

int t;
string s;

int main () {
    cin >> t;
    string tar = "Baidu";
    sort(tar.begin(), tar.end());
    while(t--) {
        cin >> s;
        sort(s.begin(), s.end());
        if(s == tar)
            puts("Yes");
        else
            puts("No");
    }
    
    return 0;
}

第二题：

题目看了半天才看懂，解法用的滑动窗口

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

int t, k, n;
int a[10100];
unordered_map<int, int> mp;

int main () {
    cin >> t;
    while(t--) {
        mp.clear();
        cin >> n >> k;
        set<int> st;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
            st.insert(a[i]);
            mp[a[i]]++;            
        }
        vector<int> v;
        sort(a, a + n);
        n = st.size();
        for(int i = 0; i < n; ++i) {
            a[i] = *st.begin();   
            st.erase(a[i]);
        }
        for(int i = 0; i < n; ++i) {
            v.push_back(mp[a[i]]);
        }
        int flag = false, sum = 0;
        int l = 0, r = 0;
        while(r < v.size()) {
            sum += v[r];
            if(sum > k) {
                sum -= v[l];
                l++;
                if(l > r) {
                    r = l;
				}
            } else if(sum < k) {
                r++;
            } else {
                cout << a[l] << ' ' << a[r] << endl;
                flag = true;
                break;
            }
        }
        if(!flag) {
            if(sum == k)
                cout << a[l] << ' ' << a[r] << endl;
            else
                puts("-1");
        }
    }
    
    return 0;
}

第三题（65%测试点）

一开始想先看看能骗多少分，不断拼接 red 循环直到 x，但是长度会超过限制的 1e5，好像过了65%。然后想太复杂了，越做分数越低，结束后写了一版不知道能对多少。

65%版本：

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

int x;
int main () {
    cin >> x;
    string s = "", base = "red";
    while(s.length() + 3 < x) {
        s += base;
    }
    if(s.length() == x)
        cout << s << endl;
    else {
        s += base.substr(0, x - s.length());
        cout << s << endl;
    }
    return 0;
}

复盘版本：

思路：一个单字符循环的字符串，含有 n(n-1)/2+n 个回文子串，于是想先尽可能用 rrrrr循环和 eeeee循环填充（比如尝试用rrrrr循环凑 x/2 个回文串，填不满的部分后面再说），剩下的先填一个d（因为如果再填一个r，会多一个回文），如果还有剩就继续填 red 循环。

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

int x;

int main () {
    cin >> x;
    string s = "", base = "red";
    int n = 1;
    while(n * (n - 1) / 2 + n <= x / 2) {
        n++;
    }
    n--;
    //  先填 n 个 r 和 n 个 e 
    int len = (n * (n - 1) / 2 + n) * 2;
    s += string(n, 'r') + string(n, 'e');
    if(len == x) {
        cout << s << endl;
        return 0;
	}
	//  有剩下的，再填个 d 
    s += 'd';
    len += 1;
    //	还有剩，就填 red 循环 
    while(len + 3 < x) {
        s += base;
        len += 3;
    }
    if(len == x) {
        cout << s << endl;
	}
    else {
        s += base.substr(0, x - len);
        cout << s << endl;
    }
    
    return 0;
}