第二十八天（2）：机试技巧(STL)(滚动数组)(调试)(输入外挂)(流氓剪枝)_userwarning: zstandard could not be imported. runn

标准模板库（STL）

string模板库基本操作

#include <string>
using namespace std;
string s;
cin >> s;

char str[] = "test";
s = str;

s += 'c';

s += "string";

string b = "class"
s += b;

string b = "class";
string a = "Two";
if(a == b)
	cout << a;

string b = "class";
string a = "Two";
if(a <= b)
	cout << a;

string c = "cout";
cout << c << endl;

string c = "cout";
printf("%s\b", c.c_str());

for(int i = 0;i < s.size();i++)
	char c = s[i];

s.erase(10, 8);
//删除s[10]到s[17]的字符

string a = "asdfsdfadfafd";
string b = "fadf";
int startPos = 0;
int pos = a.find(b, startPos);
//在 a 中从下标 startPos 位置开始查找 b 字符串

string a = "AAAA";
string b = "BBB";
a.insert(2, b);
cout << a << endl;
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

T1

字符串的查找删除
时间限制:1 秒
内存限制:32 兆
特殊判题:否

题目描述: 给定一个短字符串(不含空格) ,再给定若干字符串,在这些字符串中删除所含有的短字符串。

输入: 输入只有 1 组数据。

输入一个短字符串(不含空格) ,再输入若干字符串直到文件结束为止。

输出: 删除输入的短字符串(不区分大小写)并去掉空格,输出。

样例输入:
in
#include
int main()
{

printf(" Hi ");
}

样例输出:
#clude
tma()
{
prtf(“Hi”);
}

//
//  main.cpp
//  StringOpe
//
//  Created by Apple on 2019/9/4.
//  Copyright © 2019 Apple_Lance. All rights reserved.
//

#include <iostream>
#include <string>
#include <stdio.h>
#include <ctype.h>
using namespace std;

int main(int argc, const char * argv[]) {
    char str[101];
    gets(str);
    string a = str;
    for(int i = 0;i < a.size();i++)
        a[i] = towlower(a[i]);
    while(gets(str)){
        string b = str, c = b;
        for(int i = 0;i < b.size();i++)
            b[i] = towlower(b[i]);
        int t = b.find(a, 0);
        while(t != string::npos){
            c.erase(t, a.size());
            b.erase(t, a.size());
            t = b.find(a, t);
        }
        t = c.find(' ', 0);
        while(t != string::npos){
            c.erase(t, 1);
            t = c.find(' ', t);
        }
        cout << c << endl;
    }
    return 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

Map模板库基本操作

map内部实现是一颗红黑树

map<string, int> M;
M.clear();
M.find(b);
M[b] = idx;
idxb = M[b];
1
2
3
4
5

T 2

产生冠军
时间限制:1 秒
内存限制:32 兆
特殊判题:否

题目描述:
有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。
球赛的规则如下:如果 A 打败了 B,B 又打败了 C,而 A 与 C 之间没有进行过比赛,那么就认定,A 一定能打败 C。
如果 A 打败了 B,B 又打败了 C,而且,C 又打败了 A,那么 A、B、C 三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

输入: 输入含有一些选手群,每群选手都以一个整数 n(n<1000)开头,后跟 n 对选手的比赛结果, 比赛结果以一对选手名字 (中间隔一空格) 表示, 前者战胜后者。
如果 n 为 0,则表示输入结束。

输出: 对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。

样例输入:
3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

样例输出:
Yes
No

//
//  main.cpp
//  Champion
//
//  Created by Apple on 2019/9/5.
//  Copyright © 2019 Apple_Lance. All rights reserved.
//

#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <queue>
using namespace  std;

map<string,int> M;
int in[2002];


int main(int argc, const char * argv[]) {
    int n;
    while(scanf("%d", &n) != EOF && n != 0){
        for(int i =0;i < 2*n;i++)
            in[i] = 0;
        M.clear();
        int idx = 0;
        for(int i = 0;i < n;i++){
            char str1[50], str2[50];
            scanf("%s%s", str1, str2);
            string a = str1, b = str2;
            int idxa, idxb;
            if(M.find(a) == M.end()){
                idxa = idx;
                M[a] = idx++;
            }
            else
                idxa = M[a];
            if(M.find(b) == M.end()){
                idxb = idx;
                M[b] = idx++;
            }
            else
                idxb = M[b];
            in[idxb]++;
        }
        int cnt = 0;
        for(int i = 0;i < idx;i++)
            if(in[i] == 0)
                cnt ++;
        puts(cnt == 1? "YES":"NO");
    }
    return 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

滚动数组

用来完成常熟优化和减少代码量
如对状态转移方程

for(int i = 1;i <= n;i++){
	for(int j = 1;j <= m;j++)
		buf[j] = max(dp[j + 1], dp[j - 1]);
	for(int  j = 1;j <= m;j++)
		dp[j] = buf[j]
}
int ans = dp[m]
1
2
3
4
5
6
7

-----每次状态转移后都要进行一次循环次数为m的赋值操作

//优化
int dp[2][M];
//初始状态保存在 dp[0][i] 中
int *src;
//源指针
int *des;
//目的指针
src = dp[1]
des = dp[0]

for(int i = 1;i <= n;i++){
	swap(src, des);
	for(int j = 1;j <= m;j++)
		des[j] = max(src[j + 1], src[j - 1]);
int ans = des[m];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

每次循环进行状态转移前交换源数组和目的数组的指针

1. 优化原始的状态空间
2. 减少循环次数，节约程序的运行时间
3. 缩减代码

调试技巧

输出调试

观察动态规划问题中的状态转移，输出每一个状态

for(int i = 1;i <= n;i++){
	for(int j = s;j >= list[i].w;j--)
		buf[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
	for(int  j = 1;j <= n;j++)
		printf("%d", dp[j]);
	print("\n");
}
1
2
3
4
5
6
7

1. 方便快捷
2. 快速定位
3. 检查算法思路

断点

添加调试断点

运行到断点的其他用处

补充技巧

位运算

提高程序的效率

if(a % 2 == 1)
//相当于
if(a & 1 == 1)

a /= 2;
//相当于
a >>= 1;
1
2
3
4
5
6
7

输出外挂

1. 输入整数，保存在ret中

bool readint(int &ret){
	int sgn;
	char c;
	c = getchar()
	while(c != '-' && c<'0' || c > '9')
		c = getchar();
sgn = (c=='-')?-1:1;
ret = (c=='-')?0:(c - '0');
while((c = getchar() >= '0' && c <= '9')
	ret = ret*10 + (c - '0');
ret*=sgn;
return true;
1
2
3
4
5
6
7
8
9
10
11
12

2. 读入浮点数，结果保存在ret中

bool readdouble(double &ret){
int sgn;
double bit = 0.1;
char c;
c = getchar()
if(c == EOF)
	return false;
while(c != '-' && c != '.' && (c < '0' || c >'9')) 
	c = getchar()
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while((c = getchar()) >= '0' && c <= '9')
	ret = ret * 10 + (c - '0');
if(c == ' ' || c == '\n'){
	ret*=sgn;
	return true;
while((c = getchar()) >='0' && c <= '9'){
	ret += (c - '0')*bit
	bit/=10;
}
ret *= sgn;
return true;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

流氓剪枝

强行减去我们看气力啊不太可能存在答案的状态

//example 1
//深度搜索时， 当递归层数超过一定限度时强行返回
void DFS(int deep){
	if(dee[ > MAXDEEP)
		return;
	//其他处理
	DFS(deep + 1);
}
//example 2
//广度搜索，随机的对某些状态不进行扩展
if(rand() % 100 < 5)
	//不扩展
else 
	//扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14

有必要的提醒

1. 提前了解正式机试时将会使用的评判系统，编译环境和可以使用的开发环境，尽早做适当的练习，特别是64位整数的定义和使用（long long 和 __int64)
2. 正式考试前有试机，练习时间，检查开发工具各个功能是否正常，如编译、调试等
3. 在编写每一题时，特别注意其时间复杂度
4. 注意题目要求的输出格式
5. 先挑选人数较多的题目作答
6. 不要混用 printf 和 cout