机试重点题目-2018

B：AIQP操作

考察：vector容器的基本操作

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<int> v;
int n, m;

int main()
{
    cin >> n;
    for(int i = 0; i<n; i++){
        int t;
        cin >> t;
        v.push_back(t);
    }    
    
    cin >> m;
    m++;
    while(m --){
        string s;
        getline(cin, s);
        
        if(s[0] == 'A')
        {
            int a = s[2] - '0';
            v.push_back(a);
        }
        else if(s[0] == 'I')
        {
            int i = s[2] - '0';
            int a = s[4] - '0';
            vector<int> :: iterator itor = v.begin();
            v.insert(itor + i - 1, 1, a); //v.insert(p, n, val):在迭代器p之前插入n个值为val的元素
        }
        else if(s[0] == 'Q')
        {
            int a = s[2] - '0';
            cout << count(v.begin(),v.end(), a) << endl;
        }
        else
        {
            for(auto x : v)
                cout << x << " ";
            cout << endl;    
        }
    }
    return 0;
}
/*
5
1 2 3 4 5
4
A 8
I 2 5
Q 5
P
输出：5 
*/

C：小明坐火车

考察：DFS + 栈的合法顺序

#include <iostream>
#include <string>

using namespace std;

#define M 15 
const int N = 15;

int CalcCat(double n)
{
    int n_factorial = 1;
    //n!
    for(int i = 1; i<=n; i++) {
        n_factorial *= i;
    }

    int n_2_factorial = 1;
    for(int i = 1; i<=2*n; i++) {
        n_2_factorial *= i;
    }


    return (1 / (n + 1))  * (n_2_factorial) / (n_factorial * n_factorial);
}

//判断出栈顺序是否合法 
bool valid(char a[], int n)
{
    char buf[M];
    int top = -1;
    for(int i = 0; i<n; i++){
        for(int j = i + 1; j<n; j++){
            //本质上比较ASCII码值
            //出栈序列中，元素i之后所有比i小的元素之间必须是降序排列的
            if(a[j] < a[i]) buf[++ top] = a[j];
        }
        for(int j = 0; j<top; j++)
            if(buf[j] < buf[j + 1]) return false;
    }
    return true;
}

bool NotInList(char a[], int n, char c)
{
    for(int i = 0; i<n; i++)
        if(a[i] == c)
            return false;
    return true;
}

void func(char a[], int l, int n)
{
    //从左侧开始放数，一直放到n-1说明满了（此时l变成n了） 
    if(l == n) {
        if(valid(a, n)){
            //如果符合出栈规则，打印出来即可
            for(int i = 0; i<n; i++)
                cout << a[i];
            cout << endl; 
        }
        return;
    }
    
    for(int i = 0; i<n; i++) {
        char temp = 'a' + i;
        if(NotInList(a, l, temp)) {
            //如果当前字母不在已有序列中,则加进去 
             a[l] = temp;
             func(a, l + 1, n); //递归搜第下一个位置 
        }
    }
}

int main()
{
    int n;
    cin >> n;
    int catalan = CalcCat(n);
    cout << catalan << endl;
    char a[M];//用来保存n个字母全排列的情况，之后对每一序列进行判断是否符合出栈规则  
    func(a, 0, n);
    
    return 0;
}

F：解码方法

考察：计数类DP

#include <iostream>
#include <string.h>

using namespace std;

const int N = 10010;
int f[N];//f[i]：1~i个字符的解码方案数量 
char s[N];
/*
1、最后一个字母占1位
最后i位置不变，所以只有1~i-1会改变,而前i-1个字符的解码方案一定是包含了第i个（因为已经知道i可以解码了） 
f[i] = f[i - 1], 1 <= si <=9
2、最后一个字母占2位
同理，f[i] = f[i - 2]

f[i] = f[i - 1] + f[i - 2]，10 <= (si-1si-2) <= 26 
*/

int main()
{
    cin >> s + 1;
    int n = strlen(s + 1);
    f[0] = 1;
    for(int i = 1; i<=n; i++)
    {
        //当a[i]可以解释成单个数字时 
        if(s[i] >= '1' && s[i] <= '9')
            f[i] = f[i - 1];
        //当a[i]要和a[i-1]结合起来解释成一个数字时 
        if(i > 1)
        {
            int t = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(t >= 10 && t <= 26) f[i] += f[i - 2];
        }
    }
    
    cout << f[n] << endl;
    return 0;
}
/*
1725102
output:
4
*/