1112 字符串

题目大意： 坏的键盘可能会连续打出K个字母。给你一个字符串(由a-z, 0-9 和 '_' 组成，不超过1000个字符)，指出可能坏了的键，以及原始的字符串。
思路： 两次遍历字符串。第一次遍历，统计每次每个字符连续出现的次数，用map<char , vector<int> >存储。然后遍历这个map，若发现某个字符有一次连续出现的次数不是k, 则是没错的字符。第二次遍历，若遍历到错误的字符，若还未输出，则输出（这样就可以按照原次序输出了，map和set里存储的是排序的），然后删除不正确的字符。

#include<iostream>
#include<string>
#include<vector> 
#include<set>
#include<map>
using namespace std;

int main(){
    int k;
    cin>>k;
    string s;
    cin>>s;
    map<char, vector<int> > mp;
    for(int i=0;i<s.length(); ){
        int count = 0;
        while( i+ count < s.length() && s[i] == s[i+count]) count++;
        mp[s[i]].push_back(count);
        i += count;
    }
    
    set<char> wrong; //记录错误字母 
    map<char, vector<int> >::iterator iter;
    for(iter = mp.begin(); iter != mp.end(); iter++){
        bool flag = true;
        for(int j=0; j < mp[iter->first].size(); j++){
            if(mp[iter->first][j] % k != 0){ //但凡有一个值不为k都不是错的 
                flag = false;
                break;
            }
        }
        if(flag) wrong.insert(iter->first);
    }
    
    set<char> exist; //记录已输出字母 
    for(int i = 0;i<s.length();i++){
        if(wrong.find(s[i]) != wrong.end()){ //若是错误字母 
            s.erase(i+1,k-1); //删除后面k-1个
            if(exist.find(s[i]) == exist.end()){
                cout<<s[i];
                exist.insert(s[i]);
            }
        }
    } 
    cout<<endl<<s;
    return 0;
}

1113 逻辑题

题目大意： 给n个正整数，分成两个不相交集合；记集合的元素数量分别为n1和n2，元素和为s1,s2；首先使得|n1 - n2|最小，其次使得|s1-s2|最大
思路： 要使得|n1 - n2|最小，若n为偶数，则均分，若n为奇数，则给较大集合多一个元素让他变得更大。要使使得|s1-s2|最大，则对n个数进行排序，较大的数给较大集合，小数给小集合即可。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n; // 2<= n <= 10^5
    cin>>n;
    vector<int> v(n); //后面有sort，就不能初始化为n+1 
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sort(v.begin(), v.end());
    if( n % 2 == 0){
        cout<<"0 ";
    }else{
        cout<<"1 ";
    }
    int sum1 = 0;
    for(int i=0;i<n/2;i++){
        sum1+=v[i];
    }
    int sum2=0;
    for(int i=n/2;i<n;i++){
        sum2+=v[i];
    }
    cout<<sum2-sum1<<endl;
    return 0;
}

1114 并查集

题目大意： 已知每个人的家庭成员、名下房产。求每个家庭的总人数，以及平均拥有房产
思路： 这题考察并查集，好麻烦。

1115 二叉搜索树 DFS

题目大意： 二叉搜索树 (可插入重复节点，重复加点插入在左子树)。给你二叉搜索树节点的插入顺序，求最低两层的节点总数。结点数范围：[1,1000],结点值范围：[-1000,1000]
思路： 先建树，然后遍历求得每层结点数，输出最后两层结点数即可。但是测试点3过不去，不知道为什么。

#include<iostream>
#include<vector>
#include<map> 
using namespace std;

typedef struct node{
    int val;
    int left,right;
}node;

map<int ,node> tree;
map<int, int> height; 
int maxh = 0;
int n;
int root;

void insert(int r, int val, int h){
    if(val <= r && tree[r].left == -1){
        tree[r].left = val;
        node temp;
        temp.val = val; temp.left = -1; temp.right = -1;
        tree[val] = temp;
        height[h+1]++;
        if(h+1>maxh){
            maxh = h+1; 
        }
        return;
    }else if(val > r && tree[r].right == -1){
        tree[r].right = val;
        node temp;
        temp.val = val; temp.left = -1; temp.right = -1;
        tree[val] = temp;
        height[h+1]++;
        if(h+1>maxh){
            maxh = h+1; 
        }
        return;
    }else if(val > r && tree[r].right != -1){
        insert(tree[r].right, val, h+1);
    }if(val <= r && tree[r].left != -1){
        insert(tree[r].left, val, h+1);
    }
    
}

int main(){
    cin>>n;
    cin>>root;
    node temp;
    temp.val = root; temp.left = -1; temp.right = -1;
    tree[root] = temp;
    height[0] = 1;
    for(int i=1;i<n;i++){
        int x;
        cin>>x; 
        insert(root, x, 0);
    }
    cout<<height[maxh]<<" + "<<height[maxh-1]<<" = "<<height[maxh] + height[maxh-1]<<endl;
    return 0;
}