#携程笔试# 8.30

#携程笔试# 8.30
有一说一，不考基础知识太舒服了。
没有使用本地IDE所以没有代码。

重组偶数
选择一个偶数，假设第i为偶数，把第i位和最后一位互换swap(s[i], s[s.size()-1])。
循环后判断一下最后一位是不是偶数即可。
you
you = min(y, min(o, u))
oo = max(0, o - you - 1)
ans = you * 2 + oo
三色树
注意是无向图
直接深搜，dfs(u, fa)，划分为两个区域，u要和它的儿子们放一个区域进行计算，因为u和父亲断开，只是断一条边；如果u和儿子们断开，可能断开多条边。

补个代码，这个没有测试过，刚刚敲的，大概就是这么回事。

#include<bits/stdc++.h>
using namespace std;
vector<int> node[100000+5];
int res = 0;
int rgb[3];//0 r; 1 g; 2 b 
string str;
vector<int> dfs(int u, int fa){
    vector<int> ans(3);//  the numbers of rgb

    for(auto v : node[u]){
        vector<int> tmp;
        if(v == fa) continue; //father
        tmp = dfs(v, u);
        ans[0] += tmp[0];
        ans[1] += tmp[1];
        ans[2] += tmp[2];
    }
    // the color of u
    if(str[u] == 'r') ans[0]++;
    if(str[u] == 'g') ans[1]++;
    if(str[u] == 'b') ans[2]++;
    // check two parts
    // one part is u and its sons
    // another is remains node
    // just delete the edge betw u and u's fa 

    if(ans[0] && ans[1] && ans[2] 
    && rgb[0] - ans[0] 
    && rgb[1] - ans[1] 
    && rgb[2] - ans[2]){
        res++;
    }
    return ans;
}
int main(){
    // freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    cin>>str;
    for(auto c : str){
        if(c == 'r') rgb[0]++;
        if(c == 'g') rgb[1]++;
        if(c == 'b') rgb[2]++;

    }
    int u,v;

    for(int i = 0; i < n -1; i++){
        cin >> u >> v;
        u--;// the id of input data from 1 not 0
        v--;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    dfs(u,u);
    cout<<res<<endl;
}

平滑数列
最开始的平滑值最大值是maxValue
然后再遍历一下，如果当前num[i]和前面的num[i-1]的平滑值==maxValue，
我们进行这样的操作
令 num[i] = (num[i - 1] + num[i + 1]) / 2求一次maxValue（整个数组），还原num[i]
令 num[i - 1] = (num[i - 2] + num[i]) / 2求一次maxValue（整个数组），还原num[i - 1]
break，不用继续循环了。答案就是三次maxValue的最小值。

补个代码，没有测试过，思路是这样的。

#include<bits/stdc++.h>
using namespace std;
vector<int> num;
int get(int n){
    int maxValue = 0;
    for(int i = 1; i < n; i++){
        maxValue = max(maxValue, num[i] - num[i - 1]);
    }
    return maxValue;
}
int main(){
    // freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        num.push_back(x);
    }

    int maxValue = get(n);
    for(int i = 1; i < n; i++){
        if(num[i] - num[i - 1] == maxValue){
            int tmp;

            //num[i - 1] = (num[i - 2] + num[i]) / 2
            tmp = num[i - 1];
            if(i == 1){
                num[i - 1] = num[i];
            } else {
                num[i - 1] = (num[i - 2] + num[i]) / 2;
            }
            maxValue = min(maxValue, get(n));
            num[i - 1] = tmp;

            //num[i] = (num[i - 1] + num[i + 1]) / 2
            tmp = num[i];
            if(i == n - 1){
                num[i] = num[i - 1];
            } else {
                num[i] = (num[i - 1] + num[i + 1]) / 2;
            }
            maxValue = min(maxValue, get(n));
            num[i] = tmp;

            break;//if we dont deal this case, the biggest maxValue at least is maxValue.
        }
    }
    cout << maxValue << endl;
    return 0;
}
/*
7
5 6 3 8 2 5 6
*/

#携程笔试#