1124 STL

题目大意： 给出m个人名序列，从第s个开始，每隔n人挑选出一个人（包括第s个人），若这个人已经被挑选过，那么就挑选这个人的下一个人。最后，按照输入的顺序输出挑选出的人。
思路： 由于需要判断 某个人是否已经被挑选过，因此第一反应用set，因为set中不允许重复元素出现。但是set每插入一个元素，就会将元素排列。因此用vector<string> ans来记录原序的答案。变读取边处理，不需要存储。

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

int main(){
    int m, n, s;//总人数，跳过人数，第一个赢家的编号 
    cin>>m>>n>>s;
    int count = 0, p = 0;
    set<string> winners;
    vector<string> ans;//要按照输入的顺序输出，set本身自带排序 
    for(int i=1;i<=m;i++){
        string name;
        cin>>name;
        if(i == count*n + s + p){
            if(winners.find(name) == winners.end()){
                winners.insert(name);
                ans.push_back(name); 
                count++;
            }else{
                p++; 
            }
        }
    }
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<endl;
    }
    if(ans.size()==0){
        cout<<"Keep going..."<<endl;
    }
    return 0;
} 

1125 贪心

be rounded to 四舍五入
题目大意： 给出绳子的片段，将他们拼接成一条绳子；每次可以将两段连成一段；连接过后的绳子长度是之前两者相加的一半；给N个片段，找到最大连接后的绳子长度。最终结果向下取整。
思路： 其实是一个哈夫曼树的问题。每次挑选最小的两段拼接，将拼接后的绳子放入所有片段内再排序。最终剩下的最后一个绳子就是最长的绳子。用priority_queue会简单很多。中间结果不能省略小数，所以要用double。

#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    priority_queue<double , vector<double>, greater<double> > q;
    for(int i=0;i<n;i++){
        double x;
        cin>>x;
        q.push(x);
    }
    while(q.size() != 1){
        double a = q.top();
        q.pop();
        double b= q.top();
        q.pop();
        q.push((a+b)/2);
    }
    cout<<floor(q.top())<<endl;
    q.pop();
    return 0;
} 

但是奇怪的是，排序后，从头到尾从小到大分别将每一段依次加入结绳的绳子中也通过了。也就是说得到的绳子不用和以前的序列重新排序。
？_？ 纳闷??????????????????????????????

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    sort(v.begin(), v.end());
    int result = v[0];
    for (int i = 1; i < n; i++)
        result = (result + v[i]) / 2;
    printf("%d", result);
    return 0;
}

1126 欧拉图

• Eulerian path:欧拉路径 （每条边经过一次）
• Eulerian circuit：欧拉回路（起点终点是同一个点的欧拉路径）
• 连通图中每个点的度数为偶数，则存在欧拉回路。这个图成为欧拉图。
• 如果有两个点的度数为奇数，存在欧拉路径不存在欧拉回路。这个图称为半欧拉图。

题目大意： 给你一个无向图，判断是欧拉图、半欧拉图 还是 不是欧拉图。
思路： 首先用深度搜索（或者并查集）判断是否是联通图（测试点3），如果不联通则不是欧拉图。然后统计每个节点的度数，就能判断。

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

int n, m;  //节点数（<=500）,边数
vector<int> nodeNum;
vector< vector<int> > v;
bool visit[505] = {false};
int sum = 0; //记录深搜节点个数 

void dfs(int x){
    if(visit[x] == true){
        return;
    }
    if(sum == n){
        return;
    } 
    visit[x] = true;
    sum++; 
    for(int i=0;i<v[x].size();i++){
        dfs(v[x][i]);
    }
}

int main(){
    cin>>n>>m;
    v.resize(n+1);
    nodeNum.resize(n+1);
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        nodeNum[a]++;
        nodeNum[b]++;
        v[a].push_back(b);
        v[b].push_back(a);
    } 
    dfs(1);
    int oddNum = 0, evenNum = 0;
    for(int i=1;i<=n;i++){
        if(i != 1){
            cout<<" ";
        }
        cout<<nodeNum[i];
        if(nodeNum[i] %2 ==0){
            evenNum++;
        }else{
            oddNum++;
        }
    }
    cout<<endl;
    //cout<<sum<<endl;
    if(sum != n){//若不联通 
        cout<<"Non-Eulerian"<<endl;
    }else if(evenNum == n){
        cout<<"Eulerian"<<endl;
    }else if(oddNum == 2){
        cout<<"Semi-Eulerian"<<endl;
    }else{
        cout<<"Non-Eulerian"<<endl;
    }
    return 0;

1127 树的遍历

题目大意： 树中每个节点的值都是不同的正整数。知道 后序遍历和中序遍历，先从左到右打印一层的节点，再从右到做打印一层的节点 。
思路： 首先根据中序遍历和后序遍历转化为层次遍历，同时记录每层的节点数。然后再Z字型输出。

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

typedef struct node{
    int root;
    int inp, inq, postp, postq, l;  
    int val;
}node;

int n;
vector<int> in;
vector<int> post;
vector<int> level;
map<int, int> lNum; //记录每层的节点数
queue<node> qu;

//递归转层次 
void ChangeLevelorder(){
    node temp;
    temp.val = post[n-1]; 
    temp.inp = 0; temp.inq = n-1; temp.postp = 0; temp.postq = n-1;
    temp.l = 0;
    int root = temp.inp;
    level.push_back(post[n-1]);
    lNum[temp.l]++;
    while(in[root] != post[n-1]) root++;
    temp.root = root;
    qu.push(temp);
    while(qu.size() != 0){
        temp = qu.front();
        qu.pop();
        //找左孩子 
        for(int p = temp.inp; p < temp.root; p++){
            if(in[p] == post[temp.postq-(temp.inq-temp.root)-1]){
                node tt;
                tt.l = temp.l + 1;
                tt.val = in[p];
                tt.inp = temp.inp; tt.inq = temp.root-1; tt.postp = temp.postp; tt.postq = temp.postq-(temp.inq-temp.root)-1;   
                tt.root = p;
                qu.push(tt);
                level.push_back(in[p]);
                lNum[tt.l]++;
            }
        }
        //找右孩子 
        for(int p = temp.root+1; p <= temp.inq; p++){
            if(in[p] == post[temp.postq-1]){
                node tt;
                tt.l = temp.l + 1;
                tt.val = in[p];
                tt.inp = temp.root+1; tt.inq = temp.inq; tt.postp = temp.root; tt.postq = temp.postq-1; 
                tt.root = p;
                qu.push(tt);
                level.push_back(in[p]);
                lNum[tt.l]++;
            }
        }
    }
}

int main(){
    cin>>n;
    
    in.resize(n);
    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    post.resize(n);
    for(int i=0;i<n;i++){
        cin>>post[i];
    }

    ChangeLevelorder();

    cout<<level[0];//输出根节点 
    int p = 1;
    map<int, int>::iterator iter = lNum.begin();//先让他等于第0层 
    //从第一层开始挨个输出 
    for(iter++; iter != lNum.end(); iter++){
        //cout<<iter->first<<" "<<iter->second<<endl; 
        if(iter->first % 2 ==1){//奇数层从左到右遍历 
            for(int q = p; q < p+iter->second; q++){
                cout<<" "<<level[q];
            } 
        }else{//偶数层从右到左遍历
            for(int q = p+iter->second-1; q >= p; q--){
                cout<<" "<<level[q];
            } 
        }
        p += iter->second;
        //cout<<endl;
    }
    return 0;
}