TZOJ-STL系列题

  • C++实验：STL之vector

    #include <bits/stdc++.h>
using namespace std;
void Input(vector<int>& v) {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &m);
        v.push_back(m);
    }
}
int main()
{
    vector<int> vec;
    Input(vec);
    for(int i=0;i<vec.size();i++)
    {
        cout<<vec[i]<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之vector2

    #include <bits/stdc++.h>
using namespace std;
void Insert(vector<int>& v, int x) {
    for(int i = 0; i < v.size(); i++) // 由于vector内存中的存储方式是连续的，所以可以用下标直接访问，当然也可以用迭代器访问
    {
        if (v[i] == x) return; // 找到x说明不需要插入，直接返回
    }
    v.insert(v.begin(), x); // 在第x个数后面插入一个y可以写成v.insert(v.begin() + x, y);因为内存连续，所以迭代器也能直接加x
}
int main()
{
    vector<int> vec;
    int n, x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        Insert(vec, x);
    }
    for(vector<int>::iterator it=vec.begin();it!=vec.end();it++)
    {
        cout<<*it<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之vector3

    #include <bits/stdc++.h>
using namespace std;
bool Input(vector<int>& v) { // 返回值表示是否还有输入
    int n, m;
    v.clear();
    if (scanf("%d", &n) == EOF) return false;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &m);
        v.push_back(m);
    }
    return true;
}
bool cmp(int a, int b) {
    return a > b;
}
void Sort(vector<int>& v) {
    // sort的三个参数，排序的起始地址，排序的尾地址，比较函数
    sort(v.begin(), v.end(), cmp);
}
int main()
{
    vector<int> vec;
    while(Input(vec))
    {
        Sort(vec);
        for(vector<int>::iterator it=vec.begin();it!=vec.end();it++)
        {
            if(it!=vec.begin())
                cout<<" ";
            cout<<*it;
        }
        cout<<endl;
    }

    return 0;
}
    View Code

  • C++实验：STL之vector4

    #include <bits/stdc++.h>
using namespace std;
int Input(vector< vector<int> >& v1) {
    int n, m, k;
    scanf("%d%d", &n, &m);
    vector<int> v2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &k);
            v2.push_back(k);
        }
        v1.push_back(v2);// STL容器里还可以套其他容器，这里把v2当参数传进去
        v2.clear();
    }
}
int main()
{
    vector< vector<int> > vec;
    Input(vec);
    for(int i=0;i<vec.size();i++)
    {
        for(int j=0;j<vec[i].size();j++)
        {
            if(j)
                cout<<" ";
            cout<<vec[i][j];
        }
        cout<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之stack

    #include <bits/stdc++.h>
using namespace std;
void Op(stack<int>& st) {
    char p[10]; int m;
    scanf("%s", p);
    // 后面只需判断p[1]是什么就好了，因为三种操作的p[1]都不同，判断单个字符效率比strcmp(p, "push")要高。
    if (p[1] == 'u') {
        scanf("%d", &m);
        st.push(m);
    } else if (p[1] == 'o') {
        if (!st.empty())  // 数据可能有空栈pop的情况
            st.pop();
    } else {
        while (!st.empty()) st.pop();
    }
}
int main()
{
    stack<int> st;
    int n;
    cin>>n;
    while(n--)
    {
        Op(st);
    }
    while(!st.empty())
    {
        cout<<st.top()<<endl;
        st.pop();
    }
    return 0;
}
    View Code

    因为栈这个容器只能访问栈顶，所以不支持迭代器的操作，也没有clear方法

  • C++实验：STL之queue

    #include <bits/stdc++.h>
using namespace std;
int tail; // 因为队列只能访问队头，所以如果想访问队尾我们只能手动记录最后一次入队的是谁。
void Op(queue<int>& st) {
    char p[10]; int m;
    scanf("%s", p);
    if (p[1] == 'u') {
        scanf("%d", &m);
        st.push(m);
        tail = m;
    } else if (p[1] == 'o') {
        if (!st.empty()) st.pop();
    } else if (p[1] == 'l') {
        while (!st.empty()) st.pop();
    } else if (p[1] == 'i') {
        if (!st.empty()) printf("%d
", st.front());
    } else {
        if (!st.empty()) printf("%d
", tail);
    }
}
int main()
{
    queue<int> qu;
    int n;
    cin>>n;
    while(n--)
    {
        Op(qu);
    }
    while(!qu.empty())
    {
        cout<<qu.front()<<endl;
        qu.pop();
    }
    return 0;
}
    View Code

    因为栈这个容器只能访问队头，所以不支持迭代器的操作，也没有clear方法

  • C++实验：STL之priority_queue

    #include <bits/stdc++.h>
using namespace std;
// 优先队列，在普通队列的基础上增加了自动排序的功能，默认会把最大元素放到队头
void Input(priority_queue<char>& qu) { 
    string s;
    cin >> s;
    for (int i = 0; s[i] != ''; i++)
        qu.push(s[i]);
}
int main()
{
    priority_queue<char> qu;
    int n;
    cin>>n;
    while(n--)
    {
        Input(qu);
        while(!qu.empty())
        {
            cout<<qu.top();
            qu.pop();
        }
        cout<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之map

    #include <bits/stdc++.h>
using namespace std;
void Input(map<string, int>& mp) {
    int n; string s;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        mp[s] ++;
    }
}
int main()
{
    int m;
    map<string, int> sm;
    Input(sm);
    cin>>m;
    while(m--)
    {
        string s;
        cin>>s;
        cout<<sm[s]<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之priority_queue2

    #include <bits/stdc++.h>
using namespace std;
// greater<char> >这中间的空格不能少，否则 >> 两个尖括号连在一起会被认为是右移运算符。
priority_queue<char, vector<char>, greater<char> > qu;
void Input() {
    string s;
    cin >> s;
    for (int i = 0; s[i] != ''; i++)
        qu.push(s[i]);
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        Input();
        while(!qu.empty())
        {
            cout<<qu.top();
            qu.pop();
        }
        cout<<endl;
    }
    return 0;
}
    View Code

  • C++实验：STL之priority_queue3

    #include <bits/stdc++.h>
using namespace std;
struct Point {
    int x, y;
    // 因为Point是我们自己定义的一个数据类型，优先队列要排序不知道该怎么排，所以要实现小于号的重载
    friend bool operator < (Point a, Point b) {
        if (a.x != b.x) return a.x > b.x;
        else return a.y > b.y;
    }
};
priority_queue<Point> qu;
void Input() {
    int n; scanf("%d", &n);
    Point p;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p.x, &p.y);
        qu.push(p);
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        Input();
        while(!qu.empty())
        {
            Point p = qu.top();
            cout<<p.x<<" "<<p.y<<endl;
            qu.pop();
        }
    }
    return 0;
}
    View Code

    关于实现小于号那一部分可以看成是在结构体里写了一个像sort的cmp一样的东西，只不过写法不一样而已，实现了小于号两个Point之间就能进行比大小了

  • C++实验：STL之全排列

    #include <bits/stdc++.h>
using namespace std;
void Permutation(vector<int> v) {
    sort(v.begin(), v.end());
    do {
        printf("%d", v[0]);
        for (int i = 1; i < v.size(); i++)
            printf(" %d", v[i]);
        puts("");
    } while (next_permutation(v.begin(), v.end())); // 求v的下一个排列。1,2,3的下一个排列是1,3,2。会直接改变原数组
}
    View Code

    全排列的函数在acm的比赛中用处不是很大(因为需要全排列就说明算法效率低)，但是蓝桥杯比赛基本每年都考。

  • C++实验：STL之upper_bound

    #include <bits/stdc++.h>
using namespace std;
void PrintFind(vector<int> v, int x) {
    // upper_bound内部是用二分实现的，还记得育英比赛的唐伯虎点秋香的一题吗，所以为了二分，要先将v排好序
    sort(v.begin(), v.end());
    // upper_bound(查找首地址,查找尾地址,查找的元素),返回第一个大于查询元素的元素地址。
    vector<int>::iterator it = upper_bound(v.begin(), v.end(), x);
    // printf("%d
", *it);
    if (it == v.end()) puts("None"); // 当不存在的时候返回v.end();
    else printf("%d
", it - v.begin() + 1); // 为了得到下标减一下v.begin() + 1;
}
int main()
{
    vector<int> vec;
    int n, a, x;
    cin>>n>>x;
    while(n--)
    {
        int a;
        cin>>a;
        vec.push_back(a);
    }
    PrintFind(vec, x);
    return 0;
}
    View Code

  • C++实验：STL之upper_bound

    #include <bits/stdc++.h>
using namespace std;
void PrintFind(vector<int> v, int x) {
    // lower_bound内部是用二分实现的，还记得育英比赛的唐伯虎点秋香的一题吗，所以为了二分，要先将v排好序
    sort(v.begin(), v.end());
    // lower_bound(查找首地址,查找尾地址,查找的元素),返回第一个大于或等于查询元素的元素地址。
    vector<int>::iterator it = lower_bound(v.begin(), v.end(), x);
    // printf("%d
", *it);
    if (it == v.end()) puts("None"); // 当不存在的时候返回v.end();
    else printf("%d
", it - v.begin() + 1); // 为了得到下标减一下v.begin() + 1;
}
int main()
{
    vector<int> vec;
    int n, a, x;
    cin>>n>>x;
    while(n--)
    {
        int a;
        cin>>a;
        vec.push_back(a);
    }
    PrintFind(vec, x);
    return 0;
}
    View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Angel-Demon/p/12118237.html