markdown 文章内容

7-1 计算阶乘和

求的是前n项的阶乘和，阶乘可以递归方式定义：0!=1，n!=(n-1)!×n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 15;

int f[N];//全局变量

int solve(int i) {

  f[i] = i * f[i - 1];

  return f[i];

}

int main() {

  f[0] = 1;

  int n;

  cin >> n;

  int sum = 0;

  for (int i = 1; i <= n; i++) {

    sum += solve(i);

  }

  cout << sum;

7-2 求两个一元多项式的和

利用map。

map可以直接查找键值对。把指数当做键，因为不同指数惟一的，系数当做值。

map默认按照键值升序排列，题目输入是按指数降序，计算过程按指数有序。最后输出结果时要再按指数降序输出，可以利用rbegin()，rend()（还可以使用reverse _iterator）。还要注意每行后面不能有多余的空格。当map为空时，输出 0 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
map<int, int>a;

int n, m;

cin >> n;

for (int i = 0; i < n; i++) {

  int x, y;

  cin >> x >> y;

  a[y] = x;
}

//第二个多项式

cin >> m;

for (int i = 0; i < m; i++) {

  int x, y;

  cin >> x >> y;

  a[y] += x;

}

int temp = 0;

for (auto it = a.rbegin(); it != a.rend(); it++) {

  if (it->second != 0) {

   if (temp == 0) {

     cout << it->second << " " << it->first;

      temp = 1;

    }

    else {

      cout << " " << it->second << " " << it->first;

    }

  }

}

if (temp == 0) {

  cout << "0 0";

}

7-3 一元多项式求导

求导，系数乘以指数，指数-1，可直接进行运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  int x, y;

  int temp = 0;

  while (cin >> x >> y) {

​    if (y != 0)

​    {

​      if (temp == 0)

​        cout << x * y << " ";

​      else {

​        cout << " " << x * y << " ";

​      }

​      cout << y - 1;

​      temp = 1;

​    }

​    if (y == 0 && temp == 0) {

​      cout << "0 0";

​    }

  }

7-4 分寝室

寝室数最大为10^5，可以遍历一遍,遍历的条件：女寝为1，男寝为n-1时…

遍历的过程中：

(1)先判断寝室数是否能满足每间寝室入住的人数都必须相同，即n0%i == 0 && n1%(n-i) == 0

(2)然后进行判断，如果是第一次就直接复制，否则进行判断当前i,n-i是否最优（两种性别每间寝室入住的人数差最小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n0, n1, n;

  cin >> n0 >> n1 >> n;

  int num = 0;

  for (int i = 1; i < n && i != n0; i++) {

​    if (n0 % i == 0 && n1 % (n - i) == 0) {

​      if (!num)num = i;

​      else {

​        if (abs(n0 / num - n1 / (n - num)) > abs(n0 / i - n1 / (n - i))) 

​            num = i;

​      }

​    }

  }

  if (num) {

​    cout << num << " " << n - num;

  }

  else

​    cout << "No Solution" << endl;

7-5 括号配对问题

检查行括号是否配对时，其离得最近的同种括号一定要是匹配的，否则为错误的。所以输入字符串时，遇到左括号则存到堆栈中，遇到右括号与从栈取出来的元素进行匹配，其他符号不需要管。如果右括号和取出来的元素不匹配就返回false，退出循环。如果字符串循环完后，栈里面还有元素，则说明有左括号是单个的，也返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 bool judge(string s) {

  stack<char>stk;

  for (int i = 0; i < s.size(); i++) {

​    if (s[i] == '(')

​    {

​      stk.push(s[i]);

​    }

​    else if (s[i] == '[') {

​      stk.push(s[i]);

​    }

​    else if (s[i] == '{') {

​      stk.push(s[i]);

​    }

​    else if (s[i] == ')') {

​      if (stk.empty()) {

​        return false;

​      }

​      else if (stk.top() == '(') {

​        stk.pop();

​      }

​      else {

​        return false;

​      }

​    }

​    else if (s[i] == ']') {

​      if (stk.empty()) {

​        return false;

​      }

​      else if (stk.top() == '[') {

​        stk.pop();

​      }

​      else {

​        return false;

​      }

​    }

​    else if (s[i] == '}') {

​      if (stk.empty()) {

​        return false;

​      }

​      else if (stk.top() == '{') {

​        stk.pop();

​      }

​      else {

​        return false;

​      }

​    }

  }

  return stk.empty();

}

int main() {

  int n;

  cin >> n;

  while (n--) {

​    string s;

​    cin >> s;

​    if (judge(s)) {

​      cout << "Yes" << endl;

​    }

​    else {

​      cout << "No" << endl;

​    }

  }

}

7-6 堆栈操作合法性

这是一道非常简单的栈模拟题，你甚至都不需要真正申请一个栈，用一个数维护当前栈中元素个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9+7;
int n,m;

void solve(){
    int cnt = 0;
    string s;
    cin>>s;
    bool fg = true;
    for(int i=0;i<s.size();i++){
        if(s[i] == 'S'){
            cnt++;
            if(cnt>m){
                fg = false;
                break;
            }
        }else{
            if(cnt==0){
                fg = false;
                break;
            }
            cnt--;
        }
    }
    if(fg && !cnt)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main()
{
    cin>>n>>m;
    while(n--)solve();
    return 0;
}

7-7 彩虹瓶

还是栈模拟题，详情看代码，有注释。看不懂的话，晚上直播讲解，不用担心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N =1010;
int n,m,t;
int a[N];

void solve(){
    bool fg = true;
    for(int i=1;i<=n;i++)cin>>a[i];

    int color = 1;
    stack<int> stk;
    for(int i=1;i<=n;i++){
        //拿来的刚好是需要的颜色
        if(a[i] == color){
            color++;
            //看货架上可不可以继续放
            while(stk.size() && stk.top() == color){
                stk.pop();
                color++;
            }
        }
        else {
            //判断货架是否放满
            if(stk.size()>=m){
                fg = false;
                break;
            }else stk.push(a[i]);
        }
    }

    if(fg && color == n + 1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


int main()
{
    cin>>n>>m>>t;
    while(t--)solve();
    return 0;
}

7-8 h0181. 约瑟夫问题

非常经典的一道题，我们可以用一个队列来模拟这个过程，数数的时候，队首出队，队尾入队，数到m的猴子不再入队，这样做，直到队列中只剩一个元素即可，当然这道题用数学方法可以O（1）计算得出，不过很难，感兴趣的同学可以在知乎搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9+7;
int n,m;

int findTheWinner(int n, int k) {
    queue<int> q;
    for(int i=1;i<=n;i++)q.push(i);

    while(q.size()!=1){
        for(int i=1;i<m;i++){
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    return q.front();
}

int main()
{
    cin>>n>>m;
    while(n!=0 && m!=0){
        cout<<findTheWinner(n,m)<<endl;
        cin>>n>>m;
    }
    return 0;
}

7-9 小明的第一个扑克牌“魔术”（队列或链表操作）

这道题需要逆向思维，你是怎么把手里牌放到桌上的，你就怎么把这些牌从桌上拿到手里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9+7;
int n,m;

int main()
{
    int n;
    cin>>n;
    queue<int> q;
    for(int i=n;i>=1;i--){
        q.push(i);
        q.push(q.front());
        q.pop();
    }
    vector<int> res;
    while(q.size()){
        res.push_back(q.front());
        q.pop();
    }
    reverse(res.begin(),res.end());
    for(int i=0;i<res.size();i++){
        if(i)cout<<",";
        cout<<res[i];
    }
    return 0;
}

7-10 队的基本操作

这是一道简单的队列模拟题，不过需要注意的是：这是一个循环队列，里面有一个空间不能用于储存元素，所以其实际大小是9，详细原因为什么请大家学习数据结构，队列中的循环队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9+7;
int n;
queue<int> q;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x == 0){
            if(q.size()==0)cout<<"EMPTY ";
            else{
                cout<<q.front()<<" ";
                q.pop();
            }
        }else{
            if(q.size()>=9)cout<<"FULL ";
            else{
                q.push(x);
            }
        }
    }
    if(q.size()){
        cout<<endl;
        while(q.size()){
            cout<<q.front()<<" ";
            q.pop();
        }
    }
    return 0;
}