set类型和dict类型一样，用list初始化（用来初始化的list中的元素要求全为不可变元素），set也是一组key的集合，但是set不能储存value。同时，由于key的不重复性，set会自动过滤掉重复的输入(再也不用担心重复字符串过滤了)。

通过add()可以添加key到set中，重复添加会被自动过滤。

通过remove(key)方法可以删除key

set可以看成数学意义上的无序和无重复元素的集合，因此，两个set可以做数学意义上的交集、并集等操作（这个舒服，C++里求交集并集简直恶心）：

>>> s1 = set([1, 2, 3])
>>> s2 = set([2, 3, 4])
>>> s1 & s2
{2, 3}
>>> s1 | s2
{1, 2, 3, 4}

与dict类型要求一样，key的值必须为可hash的不可变值，所以输入为二维list是行不通的

tuple类型由于也是不可变对象，所以可以放入set中，如：

>>> s=(1,2,3)
>>> text=set(s)
>>> text
{1, 2, 3}
>>> d=(2,3,4)
>>> text.add(d)
>>> text
{1, 2, 3, (2, 3, 4)}

注：在tuple中放list的骚操作在set中不被允许。

Python内置了字典：dict的支持，dict全称dictionary，在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度

先初始化(用list初始化)一个dict:

>>> d = {'Michael': 95, 'Bob': 75, 'Tracy': 85}
>>> d['Michael']
95

把数据放入dict的方法，除了初始化时指定外，还可以通过key放入：

>>> d['Adam'] = 67
>>> d['Adam']
67

一个key只能对应一个value，多次对一个key放入value等同于对其对应的value重新赋值：

>>> d['Jack']
90
>>> d['Jack'] = 88
>>> d['Jack']
88

判断key是否存在:

>>> 'Thomas' in d
False

通过返回的bool值确定

通过dict提供的get()方法，如果key不存在，可以返回None，或者自己指定的value：

>>> d.get('Thomas')
>>> d.get('Thomas', -1)
-1

注意：返回None的时候Python的交互环境不显示结果(也就是无任何反应)。

删除一个key同样用pop(key),该key所对应的value也会从dict中删除

dict：

1. 查找和插入的速度极快，不会随着key的增加而变慢

2. 需要占用大量的内存，内存浪费多

list：

1. 查找和插入的时间随着元素的增加而增加

2. 占用空间小，浪费内存很少

dict的key必须是不可变对象。

通过key计算位置的算法称为哈希算法（Hash）

Python中语句是否执行依靠的是缩进规则 （强制格式化 ^ _ ^ 再也不用担心碰到不会缩进的同事，，等等，，事情好像并不简单，难道创造者的目的是这个？）

缩进规则

缩进四个空格以表示隶属关系//标准的tab

if <条件判断1>:
    <执行1>
elif <条件判断2>:
    <执行2>
elif <条件判断3>:
    <执行3>
else:
    <执行4>

python中用input()函数输入，括号内的参数是输入提示

但是input函数只能返回str类型，若是其他类型需要进行数据转换否则会报错

循环

for x in …循环就是把每个元素代入变量x，然后执行缩进块的语句

while循环，只要条件满足，就不断循环，条件不满足时退出循环。比如我们要计算

在循环内部变量n不断自减，直到变为-1时，不再满足while条件，循环退出

其他的和C++差不多

list

Python内置的一种数据类型是列表：list。list是一种有序的集合，可以随时添加和删除其中的元素。

比如，列出班里所有同学的名字，就可以用一个list（有点像数组又有点像链表）表示：

>>> classmates = ['Michael', 'Bob', 'Tracy']
>>> classmates
['Michael', 'Bob', 'Tracy']
>>> classmates[0]
'Michael'
>>> classmates[1]
'Bob'
>>> classmates[2]
'Tracy'
//负数表示从后往前
>>> classmates[-1]
'Tracy'        //倒数第一个
>>> classmates[-2]
'Bob'        //倒数第二个    
>>> classmates[-3]
'Michael'    //倒数第三个

越界时Python会报一个IndexError错误

替换时，直接赋值给对应位置：

>>> classmates[1] = 'Sarah'
>>> classmates
['Michael', 'Sarah', 'Tracy']

用.append()追加元素到末尾:

>>> classmates.append('Adam')
>>> classmates
['Michael', 'Bob', 'Tracy', 'Adam']

用.insert( x , y )可以把y元素插入到下标为x的位置:

>>> classmates.insert(1, 'Jack')
>>> classmates
['Michael', 'Jack', 'Bob', 'Tracy', 'Adam']

.pop()将末尾元素删除:

>>> classmates.pop()
'Adam'
>>> classmates
['Michael', 'Jack', 'Bob', 'Tracy']

.pop(i)将指定位置的删除，其中i是下标：

>>> classmates.pop(1)
'Jack'
>>> classmates
['Michael', 'Bob', 'Tracy']

list里面的元素的数据类型也可以不同，比如：

>>> L = ['Apple', 123, True]

ist元素也可以是另一个list，比如：

>>> s = ['python', 'java', ['asp', 'php'], 'scheme']
>>> len(s)
4

注意s只有4个元素，其中s[2]又是一个list

拆开写:

>>> p = ['asp', 'php']
>>> s = ['python', 'java', p, 'scheme']

要拿到’php’可以写p[1]或者s[2][1]，因此s可以看成是一个二维数组

tuple

tuple类型（和list相似但是tuple中元素一旦确定便不能更改//指向不变）

也就是说当定义一个tuple时，在定义的时候，tuple的元素就必须被确定下来

（但是元素可以乱搞啊 -_- 反正py大法好，里面的元素可以是变量、list,还随时可以改类型）

据说用tuple类型更安全

要定义一个只有1个元素的tuple，如果这么定义：

>>> t = (1)
>>> t
1

定义的不是tuple，是1这个数，因为括号()既可以表示tuple，又可以表示数学公式中的小括号，这就产生了歧义

Python规定，这种情况下，按小括号进行计算，所以结果是1

只有1个元素的tuple定义时必须加一个逗号,，来消除歧义：

>>> t = (1,)
>>> t
(1,)

Python在显示只有1个元素的tuple时，也会加一个逗号

特征，打开后里面文件带*号 然而爆破不出密码（一般遇到这种还是不要上来就爆破的好） 50 4B 03 04是文件头标记 14 00 解压所需的pkware（并不知道是什么） 00 00(全局方式位标记）其中09 00 就是加密了的标志 如果一个未加密的通过修改加密标志就可以实现怎么也解不开的密码 如09 00就是加密了的，四个数字中只有第二个数字对其有影响。 p.s. 要改要改一对，改一个是没用的（别问我怎么知道）

转义字符\（用法和C++差不多） 如果字符串里面有很多字符都需要转义，就需要加很多\，为了简化，Python还允许用r’’表示’’内部的字符串默认不转义

>>> print(r'\\\t\\')
\\\t\\

Python变量命名法与C++一致，区分大小写 在Python中，等号=是赋值语句，可以把任意数据类型赋值给变量，同一个变量可以反复赋值，而且可以是不同类型的变量 （这种变量本身类型不固定的语言称之为动态语言，与之对应的是静态语言。静态语言在定义变量时必须指定变量类型，如果赋值的时候类型不匹配，就会报错） 当我们写：

a = 'ABC'

Python解释器 在内存中创建了一个’ABC’的字符串 在内存中创建了一个名为a的变量（指针？），并把它指向’ABC’。 （这就是可以随便乱赋值的原因吗） 空值是Python里一个特殊的值，用None表示。None不能理解为0，因为0是有意义的，而None是一个特殊的空值。（和C++一致） 在Python中，通常用全部大写的变量名表示常量：

PI = 3.14159265359

/除法计算结果是浮点数，即使是两个整数恰好整除，结果也是浮点数：

>>> 9 / 3
3.0

还有一种除法是//，称为地板除，两个整数的除法仍然是整数：

>>> 10 // 3
3

%用法在计算中与C++一致 Python的整数没有大小限制，而某些语言的整数根据其存储长度是有大小限制的 Python的浮点数也没有大小限制，但是超出一定范围就直接表示为inf（无限大） 对于单个字符的编码，Python提供了ord()函数获取字符的整数表示，chr()函数把编码转换为对应的字符 注意区分’ABC’和b’ABC’，前者是str，后者虽然内容显示得和前者一样，但bytes的每个字符都只占用一个字节。 以Unicode表示的str通过encode()方法可以编码为指定的bytes

>>> 'ABC'.encode('ascii')
b'ABC'
>>> '中文'.encode('utf-8')
b'\xe4\xb8\xad\xe6\x96\x87'

要计算str包含多少个字符，可以用len()函数 如果是bytes, len()函数计算的是字节数 在操作字符串时，我们经常遇到str和bytes的互相转换。为了避免乱码问题，应当始终坚持使用UTF-8编码对str和bytes进行转换。 由于Python源代码也是一个文本文件，所以，当你的源代码中包含中文的时候，在保存源代码时，就需要务必指定保存为UTF-8编码。当Python解释器读取源代码时，为了让它按UTF-8编码读取，我们通常在文件开头写上这两行：

#!/usr/bin/env python3    //为了告诉Linux/OS X系统，这是一个Python可执行程序，Windows系统会忽略这个注释
# -*- coding: utf-8 -*-    //第二行注释是为了告诉Python解释器，按照UTF-8编码读取源代码，否则在源代码中写的中文输出可能会有乱码

%用来格式化输出的字符串 占位符 替换内容 %d 整数 %f 浮点数 %s 字符串 %x 十六进制整数 其中%_d表示占_位(表示填入的数)(当为0开头的数表示用0代替空格填充) 为浮点数时%._f表示小数点后保留_位（小数点前与%d一致） 如果不确定应该用什么，用%s把任何数据类型转换为字符串 字符串中有%时，用%%将其转义（此时\转义无效）

本题关键为链表的数组实现，用nxt数组模拟txt中元素之间的指向关系。 构造nxt数组时，头元素指向尾0，遍历txt并将元素的指向关系插入到nxt中。

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

#include <iostream>
#include <cstring>
using namespace std;
int nxt[100005];
char txt[100005];
int main()
{
	while (cin >> txt + 1)
	{
		int i = 1, len =  strlen(txt + 1), last = 0, ans = 0;
		nxt[0] = 0;
		while (i <= len)
		{
			if (txt[i] == '[')
			{
				ans = 0;
			}
			else if (txt[i] == ']')
			{
				ans = last;
			}
			else
			{
				nxt[i] = nxt[ans];
				nxt[ans] = i;
				if (ans == last)
					last = i;
				ans = i;
			}
			i++;
		}
		for (int i = nxt[0]; i; i = nxt[i])
			cout << txt[i];
		cout << endl;
	}
	return 0;
}

Times: 23 mins 栈在表达式计算的应用，参考数据结构课程。

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

#include <iostream>
#include <stack>
#include <string>
#include <utility>
#define p pair<int, int>
using namespace std;
p x[30];
long long solve(string& exp)
{
	stack<p> cal;
	long long tot = 0, sum = 0;
	if (exp.length() == 1)
		return 0;
	while (tot < exp.length())
	{
		if (exp[tot] == ')')
		{
			p x2 = cal.top(); cal.pop();
			p x1 = cal.top(); cal.pop();
			if (x1.second != x2.first)
				return -1;
			else
				sum += x1.first * x1.second * x2.second;
			cal.push(make_pair(x1.first, x2.second));
		}
		else if (exp[tot] != '(')
			cal.push(x[exp[tot] - 'A']);
		tot++;
	}
	return sum;
}
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		char xx;
		int r, c;
		cin >> xx >> r >> c;
		x[xx - 'A'] = make_pair(r, c);
	}
	string exp;
	while (cin >> exp) 
	{
		long long res = solve(exp);
		if (res != -1)
			cout << res;
		else
			cout << "error";
		cout << endl;
	}
	return 0;
}

TImes: 17 mins. 栈混洗模板，模拟混洗过程秒。

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

#include <iostream>
#include <stack>
using namespace std;
stack<int> A, C;
int res[1005] = { 0 };
void clear(stack<int> &x)
{
	while (!x.empty())
		x.pop();
}
bool solve(int N)
{
	int tot = 1;
	while (!A.empty())
	{
		if (!C.empty() && C.top() == res[tot])
		{
			C.pop();
			tot++;
		}
		else
		{
			C.push(A.top());
			A.pop();
		}
	}
	while (!C.empty())
	{
		if (C.top() != res[tot])
			return false;
		C.pop();
		tot++;
	}
	return true;
}
int main()
{
	int N;
	while (cin >> N && N)
	{
		while (cin >> res[1] && res[1])
		{
			for (int i = 2; i <= N; i++)
				cin >> res[i];
			clear(A); clear(C);
			for (int i = N; i > 0; i--)
				A.push(i);
			cout << (solve(N) ? "Yes" :"No") << endl;
		}
		cout << endl;
	}
	return 0;
}

Times： 2 hrs. 很好的一道STL题，本题核心练习了queue和deque的运用。 首先，本题的输入就比较麻烦，带空格，选用cin.getline()读取整行，使用string流读取了操作数。储存方式最终选择用了两个向量，一个储存指令类型，一个储存指令对应的操作数（无操作数用-1填充），这两个向量都是从1开始储存，第0位保存当前并行程序运行位置（类似于IP寄存器）。 过程模拟上没有太多问题，主要注意对quantum、lock和unlock含义。quantum决定一个程序最多执行的操作数量，lock会阻止其他并行程序的lock，并挂起到等待queue，直到unlock，恢复等待queue挂起的第一个程序。

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

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int var[26] = { 0 };
deque<int> exc, wait;
vector<vector<int>> opc, opd;
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	int T, kase = 0;
	cin >> T;
	while (T--)
	{
		opc.clear(); opd.clear(); wait.clear();  memset(var, 0, sizeof var);
		int n, time[5], q, cnt = 0;
		cin >> n >> time[0] >> time[1] >> time[2] >> time[3] >> time[4] >> q;
		opc.resize(n); opd.resize(n);
		opc[0].push_back(1);
		opd[0].push_back(-1);
		cin.ignore();
		while (cnt < n)
		{
			char cmd[20];
			char x;
			cin.getline(cmd, 20);
			if (cmd[0] == 'p' && cmd[1] == 'r')
			{
				opc[cnt].push_back(1);
				opd[cnt].push_back(cmd[6] - 'a');
			}
			else if (cmd[0] == 'l' && cmd[1] == 'o')
			{
				opc[cnt].push_back(2);
				opd[cnt].push_back(-1);
			}
			else if (cmd[0] == 'u' && cmd[1] == 'n')
			{
				opc[cnt].push_back(3);
				opd[cnt].push_back(-1);
			}
			else if (cmd[0] == 'e' && cmd[1] == 'n')
			{
				opc[cnt].push_back(4);
				opd[cnt].push_back(-1);
				exc.push_back(cnt);
				cnt++;
				if (cnt < n)
				{
					opc[cnt].push_back(1);
					opd[cnt].push_back(-1);
				}
			}
			else
			{
				stringstream ss(cmd + 3);
				int xx;
				opc[cnt].push_back(cmd[0] - 'a' + 5);
				ss >> xx;
				opd[cnt].push_back(xx);
			}
		}
		int lock = 0;
		if (kase++) cout << endl;
		while (!exc.empty())
		{
			int prom = exc.front(), tot = opc[prom][0], sum = 0, flag = 1;
			exc.pop_front();
			while (sum < q)
			{
				//cout << opc[prom][tot] << endl;
				if (opc[prom][tot] >= 5)
					var[opc[prom][tot] - 5] = opd[prom][tot], sum += time[0];
				else if (opc[prom][tot] == 1)
					cout << prom + 1 << ": " << var[opd[prom][tot]] << endl, sum += time[1];
				else if (opc[prom][tot] == 2)
				{
					if (!lock)
						lock = 1;
					else
						wait.push_back(prom), flag = 0, sum = q + 1;
					sum += time[2];
				}
				else if (opc[prom][tot] == 3)
				{
					lock = 0, sum += time[3];
					if (!wait.empty())
					{
						exc.push_front(wait.front());
						wait.pop_front();
					}
				}
				else
					sum = q + 1, flag = 0;
				if (flag)
					tot++;
			}
			opc[prom][0] = tot;
			if (flag)
				exc.push_back(prom);
		}

	}
	return 0;
}