csp-201809

20180901（卖菜）

问题描述

　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。
　　第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。
　　给定第一天各个商店的菜价，请计算第二天每个商店的菜价。

输入格式

　　输入的第一行包含一个整数n，表示商店的数量。
　　第二行包含n个整数，依次表示每个商店第一天的菜价。

输出格式

　　输出一行，包含n个正整数，依次表示每个商店第二天的菜价。

样例输入

8
4 1 3 1 6 5 17 9

样例输出

2 2 1 3 4 9 10 13

数据规模和约定

　　对于所有评测用例，2 ≤ n ≤ 1000，第一天每个商店的菜价为不超过10000的正整数。

代码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
34
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> prices;
vector<int> prices2;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    prices.resize(n);
    prices2.resize(n);
    for(int i=0;i<n;i++){
        cin>>prices[i];
    }
    for(int i=0;i<n;i++){
        if(i==0){
            prices2[i] = (prices[i]+prices[i+1])/2;
        }else if(i==n-1){
            prices2[i] = (prices[i]+prices[i-1])/2;
        }else{
            prices2[i] = (prices[i-1]+prices[i]+prices[i+1])/3;
        }
    }

    //output
    for(int i=0;i<n;i++){
        if(i==0){
            cout<<prices2[i];
        }else cout<<" "<<prices2[i];
    }
}

20180902（买菜）

代码1

这题也是使用双指针法，假如当前指针指向两个人所在的时间段[a,b]和[c,d]，先累加相交叉的时间段，然后应该会有一下几种情况：1. d>b-1，前者指针推进，2. b>d-1，累加相交叉的时间段，后者指针推进，3. 否则，两者指针都推进。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<array<int,2>> times1,times2;
int ans=0;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    times1.resize(n);
    times2.resize(n);

    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        times1[i] = {a,b};
    }
    for(int i=0;i<n;i++){
        cin>>a>>b;
        times2[i] = {a,b};
    }

    int i=0,j=0;
    while(i<n && j<n){
        int a=times1[i][0],b=times1[i][1],c=times2[j][0],d=times2[j][1];
        ans += max(0,min(b,d)-max(a,c));
        if(d>b-1){
            i++;
        }else if(b>d-1){
            j++;
        }else{
            i++;
            j++;
        }
    }

    cout<<ans<<endl;
}

20180903（元素选择器）

1

1

1

代码1

设计一个struct来表示一行：

1
2
3
4
5
struct Line{
    int layer; //从0开始
    string ele; 
    string id; //空字符串表示没有id属性
}

这样就可以表示每一行了。然后输入所有行到vector<Line> lines中。对于查询，若查询的是标签或id，就好办了，直接线性遍历匹配；若查询的是后代，则要用到栈，匹配一个祖先就压栈，直到所有祖先都压栈了，然后就看下一层级下有没有对应的，若有，就记录结果，那什么时候弹栈呢？假如你上次压栈的是1层的，这次又到了a层，那就弹栈，直到栈顶的层数比a小或空栈。

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
126
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Line{
    int layer; //从0开始
    string ele;
    string id; //空字符串表示没有id属性
};

int n,m;
vector<Line> lines;

Line dealLine(string str){
    int i=0, dotNum=0;
    Line ans;
    while(i<str.size() && str[i]=='.'){
        dotNum++;
        i++;
    }
    ans.layer = dotNum/2;
    int k=str.find(' ',i);
    if(i<str.size() && k!=string::npos){
        ans.ele = str.substr(i,k-i);
        i = k+1;
    }else if(i<str.size()){
        ans.ele = str.substr(i);
        i = str.size();
    }
    if(i<str.size()){
        ans.id = str.substr(i+1);
        //全变为小写
        for(int j=0;j<ans.id.size();j++){
            ans.id[j] = tolower(ans.id[j]);
        }
    }
    return ans;
}
void dealSelect(string str, vector<string>& selections){
    int i=0;
    while(i<str.size()){
        int k = str.find(' ',i);
        if(k == string::npos){
            selections.push_back(str.substr(i));
            i = str.size();
        }else{
            selections.push_back(str.substr(i,k-i));
            i = k+1;
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    cin.get();
    lines.resize(n+1);
    for(int i=1;i<=n;i++){
        string line;
        getline(cin,line);
        lines[i] = dealLine(line);
    }

    while(m--){
        string line;
        getline(cin,line);
        vector<string> selections;
        dealSelect(line, selections);
        vector<int> ans; //保存结果
        if(selections.size()==1){
            if(selections[0][0]=='#'){
                string s = selections[0].substr(1);
                for(int i=0;i<s.size();i++){ //全变为小写
                    s[i] = tolower(s[i]);
                }
                for(int i=1;i<=n;i++){
                    if(lines[i].id==s){
                        ans.push_back(i);
                    }
                }
            }else{
                for(int i=1;i<=n;i++){
                    if(lines[i].ele==selections[0]){
                        ans.push_back(i);
                    }
                }
            }
        }else{
            stack<int> stk; //保存已经找到的祖先的层级
            int k=0;
            for(int i=1;i<=n;i++){
                while(!stk.empty() && stk.top()>=lines[i].layer){
                    stk.pop();
                    k--;
                }
                if(selections[k][0]=='#'){
                    string s = selections[k].substr(1)l
                    for(int i=0;i<s.size();i++){ //全变为小写
                    	s[i] = tolower(s[i]);
                	}
                    if(s==lines[i].id){
                        if(k==selections.size()-1){
                            ans.push_back(i);
                        }else{
                            stk.push(lines[i].layer);
                            k++;
                        }
                    }
                }else{
                    if(selections[k]==lines[i].ele){
                        if(k==selections.size()-1){
                            ans.push_back(i);
                        }else{
                            stk.push(lines[i].layer);
                            k++;
                        }
                    }
                }
            }
        }
        //output
        cout<<ans.size();
        for(int i=0;i<ans.size();i++) cout<<" "<<ans[i];
        cout<<endl;
    }
}

80分。错误。我没有注意到id属性大小写不敏感

测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
11 5
html
..head
....title
..body
....h1
....p #subtitle
....div #main
......h2
......p #one
......div
........p #two
p
#subtitle
h3
div p
div div p

20180904（再卖菜）

问题描述

　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。
　　第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。
　　给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。
　　字典序大小的定义：对于两个不同的价格序列(a1, a2, …, an)和(b1, b2, b3, …, bn)，若存在i (i>=1), 使得ai<bi，且对于所有j<i，aj=bj，则认为第一个序列的字典序小于第二个序列。

输入格式

　　输入的第一行包含一个整数n，表示商店的数量。
　　第二行包含n个正整数，依次表示每个商店第二天的菜价。

输出格式

　　输出一行，包含n个正整数，依次表示每个商店第一天的菜价。

样例输入

8
2 2 1 3 4 9 10 13

样例输出

2 2 2 1 6 5 16 10

数据规模和约定

　　对于30%的评测用例，2<=n<=5，第二天每个商店的菜价为不超过10的正整数；
　　对于60%的评测用例，2<=n<=20，第二天每个商店的菜价为不超过100的正整数；
　　对于所有评测用例，2<=n<=300，第二天每个商店的菜价为不超过100的正整数。
　　请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

代码1

设置第一天菜价为prices1, 第二天菜价为prices2。因为prices2[0]=2，所以prices1[0]+prices1[1]的取值范围只能是[2*2, 3*2-1]，也就是[4,5]；因为prices2[1]=2，所以prices1[0]+prices1[1]+prices1[2]的取值范围是[2*3,3*3-1]，也就是[6, 8]；后面的以此类推。用vector<array<int>> scopes 保存每2/3天的菜价总和范围，scopes[0]表示第0和1天的，scopes[1]表示第0,1,2天的，scopes[n-1]表示第n-2, n-1天的。

我们采用dfs的方法，以题目给的样例为例，首先在第一天的时候，遍历每种可能的情况[1,4]，然后第二天根据第一天的取值，遍历每种可能的情况，第三天也是……。若中间出现有一天，不能取到合法的值的时候，就是要回溯的时候。若顺利地进行到了最后一天，那么这个结果就是最终结果。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> prices1, prices2;
vector<array<int,2>> scopes; //计算每三天的菜价范围

bool flag = false;
void dfs(int day){
    if(day == n){
        flag = true;
        return;
    }
    if(day==0){ //不超过scopes[0]的最大值
        for(int i=1;i<scopes[day][1];i++){
            prices1[day] = i;
            dfs(day+1);
            if(flag) break;
        }
    }else if(day==1 && day==n-1){
        int a = scopes[day-1][0]-prices1[day-1];
        prices1[day] = (a>=1?a:1);
        dfs(day+1);
    }else if(day==1){
        int a = scopes[day-1][0]-prices1[day-1];
        int i = (a>=1?a:1);
        for(;i+prices1[day-1]<=scopes[day-1][1]&&i+prices1[day-1]<scopes[day][1];i++){
            prices1[day] = i;
            dfs(day+1);
            if(flag) break;
        }
    }else if(day==n-1){
        int a = scopes[day-1][0]-prices1[day-1]-prices1[day-2];
        a = (a>=1?a:1);
        int b = scopes[day-1][1]-prices1[day-1]-prices1[day-2];
        int c = scopes[day][0]-prices1[day-1];
        c = (c>=1?c:1);
        int d = scopes[day][1]-prices1[day-1];
        if(max(a,c)<=min(b,d)){
            prices1[day] = max(a,c);
            dfs(day+1);
        }
    }else{
        int a = scopes[day-1][0]-prices1[day-1]-prices1[day-2];
        a = (a>=1?a:1);
        int b = scopes[day-1][1]-prices1[day-1]-prices1[day-2];
        for(int i=a;i<=b&&i+prices1[day-1]<scopes[day][1];i++){
            prices1[day] = i;
            dfs(day+1);
            if(flag) break;
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    prices1.resize(n);
    prices2.resize(n);
    scopes.resize(n);

    for(int i=0;i<n;i++){
        cin>>prices2[i];
        if(i==0 || i==n-1){
            scopes[i][0] = prices2[i]*2;
            scopes[i][1] = (prices2[i]+1)*2-1;
        }else{
            scopes[i][0] = prices2[i]*3;
            scopes[i][1] = (prices2[i]+1)*3-1;
        }
    }

    dfs(0);

    //output
    for(int i=0;i<n;i++){
        if(i==0) cout<<prices1[i];
        else cout<<" "<<prices1[i];
    }
}

80分。运行超时

展开全文 >>

csp-201812

20181201（小明上学）

代码1

若经过道路，则直接累加时间；若经过路口，则看亮的是什么灯，然后写一个函数getWaitTime(int type, int leftTime) 来计算要等多久。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int r,y,g,n;
int time2 = 0;

int getWaitTime(int type, int leftTime){
    if(type==1){
        return leftTime;
    }else{
        return leftTime+r;
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>r>>y>>g>>n;
    for(int i=0;i<n;i++){
        int type, leftTime;
        cin>>type>>leftTime;
        if(type==0){
            time2+=leftTime;
        }else if(type!=3){
            time2+=getWaitTime(type, leftTime);
        }
    }
    cout<<time2<<endl;
}

测试数据

1
2
3
4
5
6
7
8
9
10
30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

20181202（小明放学）

代码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
34
35
36
37
38
39
40
41
42
43
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int r,y,g,n;
long long time2 = 0;

int getWaitTime(int type,int leftTime){
    long long a;
    if(type==1){
        a = r-leftTime;
    }else if(type==2){
        a = r+g+y-leftTime;
    }else{
        a = r+g-leftTime;
    }
    a += time2;
    a = a%(r+y+g);
    if(a>=0 && a<r){
        return r-a;
    }else if(a>=r && a<r+g){
        return 0;
    }else{
        return (r+g+y-a+r);
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>r>>y>>g>>n;
    for(int i=0;i<n;i++){
        int type, leftTime;
        cin>>type>>leftTime;
        if(type==0){
            time2+=leftTime;
        }else{
            int temp = getWaitTime(type,leftTime);
            time2+=temp;
        }
    }
    cout<<time2<<endl;
}

这题要注意一点，因为1e6*1e5大于int的表示范围，所以计算绝对时间时用到long long，同时计算总的时间time2也要用long long。

20181203（CIDR合并）

代码1

我们设置一个结构体来表示标准的IP前缀。

1
2
3
4
struct Ippre{
    array<int,4> ip;
    int len; //[0,32]
}

写一个函数bool isContain(Ippre& ip1,Ippre& ip2) 来看ip1是否包含ip2。写一个函数bool merge2(Ippre& ip1,Ippre& ip2, Ippre ip3)来判断ip1和ip2是否可以合并，若可以则返回true，并把合并结果放到ip3中，否则，返回false。

一开始，输入数据，来将形形色色的Ip前缀转化为标准形式。Ippre convert(string str) 来完成转换的功能。将所有的ip前缀存放在set<Ippre> ipSet 中。

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Ippre{
    array<int,4> ip;
    int len; //[0,32]
    bool operator<(const Ippre& ip2)const{
        if(ip[0]!=ip2.ip[0]){
            return ip[0]<ip2.ip[0];
        }else if(ip[1]!=ip2.ip[1]){
            return ip[1]<ip2.ip[1];
        }else if(ip[2]!=ip2.ip[2]){
            return ip[2]<ip2.ip[2];
        }else if(ip[3]!=ip2.ip[3]){
            return ip[3]<ip2.ip[3]; 
        }else{
            return len<ip2.len;
        }
    }
};

int n;
set<Ippre> ipSet;

Ippre convert(string str){
    Ippre ip;
    int k1=0,k2,dotNum=0;
    k2 = str.find('.',k1);
    while(k2 != string::npos){
        ip.ip[dotNum] = stoi(str.substr(k1,k2-k1));
        k1 = k2+1;
        k2 = str.find('.',k1);
        dotNum++;
    }
    if(dotNum==3 && str.find('/')!=string::npos){ //标准型
        k2 = str.find('/');
        ip.ip[dotNum] = stoi(str.substr(k1,k2-k1));
        ip.len = stoi(str.substr(k2+1));
    }else if(str.find('/')!=string::npos){ //省略后缀型
        k2 = str.find('/');
        for(int i=dotNum;i<4;i++){
            if(i==dotNum){
                ip.ip[i] = stoi(str.substr(k1,k2-k1));
            }else{
                ip.ip[i] = 0;
            }
        }
        ip.len = stoi(str.substr(k2+1));
    }else{ //省略长度型
        for(int i=dotNum;i<4;i++){
            if(i==dotNum){
                ip.ip[i] = stoi(str.substr(k1));
            }else{
                ip.ip[i] = 0;
            }
        }
        ip.len = (dotNum+1)*8;
    }
    return ip;
}

bool isContain(const Ippre& ip1,const Ippre& ip2){
    if(ip1.len > ip2.len){
        return false;
    }else if(ip1.len == ip2.len){
        for(int i=0;i<4;i++){
            if(ip1.ip[i] != ip2.ip[i]){
                return false;
            }
        }
        return true;
    }else{
        for(int i=0;i<ip1.len/8;i++){
            if(ip1.ip[i]!=ip2.ip[i]){
                return false;
            }
        }
        int a = ip1.len%8;
        int num1=ip1.ip[ip1.len/8], num2=ip2.ip[ip1.len/8];
        num1 = (num1>>(8-a));
        num2 = (num2>>(8-a));
        return num1==num2;
    }
}

bool merge2(const Ippre& ip1,const Ippre& ip2, Ippre& ip3){
    if(ip1.len != ip2.len){
        return false;
    }
    for(int i=0;i<ip1.len/8;i++){
        if(ip1.ip[i]!=ip2.ip[i]){
            return false;
        }
    }
    int a = ip1.len%8;
    int num1=ip1.ip[ip1.len/8], num2=ip2.ip[ip1.len/8];
    num1 = (num1 >> (8-a+1));
    num2 = (num2 >> (8-a+1));
    if(num1==num2){
        num1 = (num1<<(8-a+1));
        ip3.ip = ip1.ip;
        ip3.ip[ip1.len/8] = num1;
        ip3.len = ip1.len-1;
        return true;
    }else{
        return false;
    }
}
void outputIp(Ippre ip){
    for(int i=0;i<4;i++){
        if(i<3){
            cout<<ip.ip[i]<<".";
        }else{
            cout<<ip.ip[i]<<"/";
        }
    }
    cout<<ip.len;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n;
    string ip;
    for(int i=0;i<n;i++){
        cin>>ip;
        ipSet.insert(convert(ip));
    }

    set<Ippre>::iterator it = ipSet.begin();
    for(;it!=ipSet.end();){
        set<Ippre>::iterator it2 = ++it;
        it--;
        if(it2 == ipSet.end()){
            it++;
            continue;
        }
        if(isContain(*it, *it2)){
            ipSet.erase(it2);
        }else{
            it++;
        }
    }

    it = ipSet.begin();
    for(;it!=ipSet.end();){
        set<Ippre>::iterator it2 = ++it;
        it--;
        if(it2 == ipSet.end()){
            it++;
            continue;
        }
        Ippre ip3;
        if(merge2(*it,*it2,ip3)){
            it2 = ipSet.erase(it);
            ipSet.erase(it2);
            it = ipSet.insert(ip3).first;
            if(it != ipSet.begin()){
                it--;
            }
        }else{
            it++;
        }
    }

    //output
    it = ipSet.begin();
    for(;it!=ipSet.end();it++){
        outputIp(*it);
        cout<<endl;
    }
}
//num>>2不会改变num的值

第17行我把3错写成2了，好坑啊。

80分。答案错误

20181204（数据中心）

代码1

仔细观察$T_{MAX}$ 的定义，发现它其实就是最小支撑树的最大边。我们直接使用Kruskal算法。

我们定义一个数据结构：

1
2
3
struct Edge{
    int u,v,w;
}

然后把每个输入的边作为Edge存入vector<Edge> edges 中。按照w属性排序。由于要用到并查集，所以要设置vector<int> father 数组，然后再写int findFather(int x)，以及void union2(int a,int b) 函数。

在运行kruskal时，记录选择的边的最大权值。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Edge{
    int u,v,w;
};
int n,m,root;
vector<Edge> edges;
vector<int> father;
int ans = 0;

int findFather(int x){
    if(father[x] == x){
        return x;
    }
    int fx = findFather(father[x]);
    father[x] = fx;
    return fx;
}
void union2(int a,int b){
    int fa=findFather(a), fb=findFather(b);
    if(fa!=fb){
        father[fa]=fb;
    }
}
bool cmp(const Edge& e1, const Edge& e2){
    return e1.w<e2.w;
}
void Kruskal(){
    //init
    sort(edges.begin(),edges.end(),cmp);
    for(int i=0;i<n+1;i++) father[i]=i;

    int cnt=0;
    for(int i=0;i<m&&cnt<n-1;i++){
        int u=edges[i].u, v=edges[i].v, w=edges[i].w;
        int fu=findFather(u), fv=findFather(v);
        if(fu != fv){
            union2(u,v);
            ans = max(ans,w);
            cnt++;
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m>>root;
    //init
    edges.resize(m);
    father.resize(n+1);

    //input
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges[i] = {u,v,w};
    }

    Kruskal();

    cout<<ans<<endl;
}

展开全文 >>

csp-201903

20190301（小中大）

代码1

用一个数组vector<input> 来表示输入数据, n是个数，然后取出这组数据的第一个和最后一个数，它们两个是最值。若n是偶数，则取n/2, n/2+1下标的数相加除以2，四舍五入，若n是奇数，则取n/2下标的数作为中位数。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n, maxn, midn, minn;
double midn2;
bool flag = true; //是整数
vector<int> input;

int main(){
    //input
    scanf("%d",&n);
    input.resize(n);
    for(int i=0;i<n;i++) {
        int temp;
        scanf("%d",&temp);
        input[i] = temp;
    }

    if(input[0]<input[n-1]){
        minn = input[0];
        maxn = input[n-1];
    }else{
        maxn = input[0];
        minn = input[n-1];
    }
    if(n%2 == 0){
        int temp = input[n/2]+input[n/2-1];
        if(temp%2 == 0){
            midn = temp/2;
        }else{
            flag = false;
            midn2 = (double)temp/2;
        }
    }else{
        midn = input[n/2];
    }

    //output
    printf("%d",maxn);
    if(flag) printf(" %d",midn);
    else printf(" %.1f",midn2);
    printf(" %d",minn);
}

我一开始犯了一个错误，没有考虑到，当中位数不整时，要保留一位小数。

20190302（二十四点）

代码1

由于n很小，所以我们可以用getline(cin, line) 函数来输入数据，不用考虑输入时间的问题。对于每一行输入line，我们用栈来实现运算，有两个栈：stack<int> stk1; stack<char> stk2 ，stk1用于存放数字，stk2用于存放操作符。还有一个map<char, int> mp 用于表示每个操作符的优先级，* / 的优先级为1，+ - 的优先级为0。每当输入的操作符优先级比stk2栈顶操作符的优先级相等或者小，则计算，否则，压栈。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
string line;
map<char,int> mp = {{'+',0},{'-',0},{'x',1},{'/',1}};

int compute(int a,int b,char op){
    if(op=='+'){
        return a+b;
    }else if(op=='-'){
        return a-b;
    }else if(op=='x'){
        return a*b;
    }else{
        return a/b;
    }
}
int dealLine(){
    stack<int> stk1;
    stack<char> stk2;
    for(int i=0;i<7;i++){
        char c = line[i];
        if(isdigit(c)){
            stk1.push(c-'0');
        }else{
            if(stk2.empty() || mp[c]>mp[stk2.top()]){
                stk2.push(c);
            }else{
                int b=stk1.top();
                stk1.pop();
                int a = stk1.top();
                stk1.pop();
                char op = stk2.top();
                stk2.pop();
                int res = compute(a,b,op);
                stk1.push(res);
                stk2.push(c);
            }
        }
    }
    while(stk1.size() > 1){
        int b=stk1.top();
        stk1.pop();
        int a = stk1.top();
        stk1.pop();
        char op = stk2.top();
        stk2.pop();
        int res = compute(a,b,op);
        stk1.push(res);
    }
    return stk1.top();
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    while(n--){
        cin>>line;
        int res = dealLine();
        if(res == 24){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
}

测试数据

1
2
3
4
5
6
7
8
9
10
11
10
9+3+4x3
5+4x5x5
7-9-9+8
5x6/5x4
3+5+7+9
1x1+9-9
1x9-5/9
8/5+6x9
6x7-3x6
6x4+4/5

20190303（损坏的RAID5）

代码1

输入的时候会指明哪些盘是存在的，那些没有指明的盘就是丢失的盘，根据输入，我们也可以确定每个磁盘有多少个半字节，设为len。一个块是4B，一个条带是s个块，根据数据布局规则，我们可以通过块号计算它在哪个磁盘，以及在哪个半字节，用getPos(int blockNum) 函数来计算，这个函数的过程为，根据块号blockNum计算条带号stripeNum = blockNum/s，然后index1 = stripeNum/(n-1)得到这个条带在磁盘的第几个条带处，以及在blockIndex = s*index1+(blockNum-blockNum/s*s)的块索引处。 以及index2 = stripeNum - index1*(n-1)表示P块后面的第index2+1处，P块的磁盘位置pPos = n-1-index1%n，因此这个块就在diskNum = (pPos+index2+1)%n的磁盘处。

getPos()函数得到的磁盘号和半字节，可以用于判断是否越界，是否是坏了的磁盘。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,s,l,m;
vector<string> disks;
int len; //每个磁盘有多少个半字节

array<int,2> getPos(int blockNum){
    int stripeNum = blockNum/s;
    int index1 = stripeNum/(n-1);
    int blockIndex = s*index1+(blockNum-blockNum/s*s);
    int index2 = stripeNum-index1*(n-1);
    int pPos = n-1-index1%n;
    int diskNum = (pPos+index2+1)%n;
    return {diskNum, blockIndex*4*2};
}

//恢复diskNum磁盘上从halfByteIndex开始的8个半字节
string restore(int diskNum, int halfByteIndex){
    char str[9];
    for(int i=halfByteIndex; i<halfByteIndex+8; i++){
        int a = 0;
        for(int j=0;j<n;j++){
            if(j!=diskNum){
                if(isdigit(disks[j][i])){
                    a = a^(disks[j][i]-'0');
                }else{
                    a = a^(disks[j][i]-'A'+10);
                }
            }
        }
        str[i-halfByteIndex] = (a<10?((char)a+'0'):((char)a-10+'A'));
    }
    str[8] = '\0';
    return string(str);
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    //input
    cin>>n>>s>>l;
    disks.resize(n);
    for(int i=0;i<l;i++){
        int diskNum;
        cin>>diskNum;
        cin.get();
        getline(cin,disks[diskNum]);
        len = disks[diskNum].size();
    }

    cin>>m;
    while(m--){
        int blockNum;
        cin>>blockNum;
        array<int,2> pos = getPos(blockNum);
        if(disks[pos[0]].size()>0){
            if(pos[1]<len){
                string str = disks[pos[0]].substr(pos[1],8);
                cout<<str<<endl;
            }else{
                cout<<"-"<<endl;
            }
        }else{
            if(l>=n-1){
                string str = restore(pos[0], pos[1]);
                cout<<str<<endl;
            }else{
                cout<<"-"<<endl;
            }
        }
    }
}

测试数据

1
2
3
4
5
6
2 1 2
0 000102030405060710111213141516172021222324252627
1 000102030405060710111213141516172021222324252627
2
0
1
1
2
3
4
5
6
3 2 2
0 000102030405060710111213141516172021222324252627
1 A0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7
2
2
5

20190304（消息传递接口）

代码1

给出几个进程顺序执行的指令，判断是否死锁。pointer[n]表示每个进程正在执行第几条指令，初始时全为0，若遇到两个匹配的指令，才能向前推进，比如第0号进程第pointer[0]个指令是R1，第1号进程第pointer[1]个指令是S0，则0号进程和1号进程可以推进。那么如何在n个进程中找匹配的两个进程的指令呢？我想的是0和1,2,3…比较，然后1和2,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
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int T,n;
vector<vector<string>> instructions;
vector<int> pointers;

bool allEnd(){ //所有指令都执行完毕
    for(int i=0;i<n;i++){
        if(pointers[i]<instructions[i].size())
            return false;
    }
    return true;
}
bool isMatch(int i, string& s1, int j, string& s2){
    if(stoi(s1.substr(1))==j && stoi(s2.substr(1))==i && s1[0]!=s2[0]){
        return true;
    }else return false;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>T>>n;
    instructions.resize(n);
    pointers.resize(n);

    string s1;
    while(T--){
        //init
        for(int i=0;i<n;i++){
            instructions[i].clear();
            pointers[i] = 0;
        }

        for(int i=0;i<n;i++){
            char c;
            do{
                cin>>s1;
                instructions[i].push_back(s1);
            }while((c=cin.get())!='\n' && c!=EOF); //一行结束
        }
        bool forwd = true; //是否推进了至少一次
        while(!allEnd() && forwd){
            forwd = false;
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    int pi = pointers[i], pj = pointers[j];
                    if(pi>=instructions[i].size()) break;
                    if(pj>=instructions[j].size()) continue;
                    string &si = instructions[i][pi], &sj = instructions[j][pj];
                    if(isMatch(i, si, j, sj)){
                        pointers[i]++;
                        pointers[j]++;
                        forwd = true;
                    }
                }
            }
        }
        if(allEnd()){
            cout<<"0"<<endl;
        }else{
            cout<<"1"<<endl;
        }
    }
}

60分。超时。

测试数据

1
2
3
4
5
6
7
3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 S0 R0 R0 R0 R0
1
2
3
4
5
6
7
2 3
R1 S1
R2 S0 R0 S2
S1 R1
R1
R2 S0 R0
S1 R1

代码2

我们可以不用一个一个比较。从0进程开始，看它当前的指令对应哪个进程，如R1对应1进程，S2对应2进程。若i进程的指令对应的进程在它后面而且有指令而且可以匹配，则推进，然后从0进程再开始找；若没有指令，则必定死锁；若有指令，但不匹配，则看i+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
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int T,n;
vector<vector<string>> instructions;
vector<int> pointers;

bool allEnd(){ //所有指令都执行完毕
    for(int i=0;i<n;i++){
        if(pointers[i]<instructions[i].size())
            return false;
    }
    return true;
}
bool isMatch(int i, string& s1, int j, string& s2){
    if(stoi(s1.substr(1))==j && stoi(s2.substr(1))==i && s1[0]!=s2[0]){
        return true;
    }else return false;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>T>>n;
    instructions.resize(n);
    pointers.resize(n);

    string s1;
    while(T--){
        //init
        for(int i=0;i<n;i++){
            instructions[i].clear();
            pointers[i] = 0;
        }

        for(int i=0;i<n;i++){
            char c;
            do{
                cin>>s1;
                instructions[i].push_back(s1);
            }while((c=cin.get())!='\n' && c!=EOF); //一行结束
        }
        bool forwd = true; //是否推进了至少一次
        while(!allEnd() && forwd){
            forwd = false;
            for(int i=0;i<n;i++){
                int pi = pointers[i];
                if(pi>=instructions[i].size()) continue;
                string si = instructions[i][pi];
                int j = stoi(si.substr(1));
                int pj = pointers[j];
                if(j>i && pj<instructions[j].size() && isMatch(i,si,j,instructions[j][pj])){
                    pointers[i]++;
                    pointers[j]++;
                    forwd = true;
                    break;
                }else if(pj>=instructions[j].size()){
                    break;
                }
            }
        }
        if(allEnd()){
            cout<<"0"<<endl;
        }else{
            cout<<"1"<<endl;
        }
    }
}

80分。运行超时

代码3

参考了别人的代码，我使用isBlocked标志位。bool isBlocked[]，初始化为false，当一个进程a没有找到与之匹配的进程的指令后，就blocked，当a找到与之匹配的进程b后，a和b就可以推进，并且isBlocked设为false，然后a继续找直到找不到，然后设a的isBlocked为true。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int T,n;
vector<vector<string>> instructions;
vector<int> pointers;
bool isBlocked[10005];

bool allEnd(){ //所有指令都执行完毕
    for(int i=0;i<n;i++){
        if(pointers[i]<instructions[i].size())
            return false;
    }
    return true;
}
bool isMatch(int i, string& s1, int j, string& s2){
    if(stoi(s1.substr(1))==j && stoi(s2.substr(1))==i && s1[0]!=s2[0]){
        return true;
    }else return false;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>T>>n;
    instructions.resize(n);
    pointers.resize(n);

    string s1;
    while(T--){
        //init
        for(int i=0;i<n;i++){
            instructions[i].clear();
            pointers[i] = 0;
        }
        memset(isBlocked,0,sizeof(isBlocked));

        for(int i=0;i<n;i++){
            char c;
            do{
                cin>>s1;
                instructions[i].push_back(s1);
            }while((c=cin.get())!='\n' && c!=EOF); //一行结束
        }
        bool f = false;
        while(!allEnd() && !f){
            f = true;
            for(int i=0;i<n;i++){
                if(pointers[i]>=instructions[i].size() || isBlocked[i]) continue;
                isBlocked[i] = true;
                int id2 = stoi(instructions[i][pointers[i]].substr(1));
                while(pointers[i]<instructions[i].size()
                      && pointers[id2]<instructions[id2].size()
                      && isMatch(i,instructions[i][pointers[i]],id2,instructions[id2][pointers[id2]])){
                    f = false;
                    pointers[i]++;
                    pointers[id2]++;
                    isBlocked[id2] = false;
                    if(pointers[i]<instructions[i].size()) id2 = stoi(instructions[i][pointers[i]].substr(1));
                }
            }
        }
        if(allEnd()) cout<<"0"<<endl;
        else cout<<"1"<<endl;
    }
}

100分。

展开全文 >>

基础算法

Floyd算法

使用动态规划的方法求解全源最短路径问题。

Floyd算法的流程如下：

1
2
3
4
枚举顶点k 属于 [1,n]
	以顶点k作为中介点，枚举所有顶点对i和j(i 属于 [1,n]，j 属于 [1,n])
		如果dis[i][k] + dis[k][j] < dis[i][j]成立
			赋值dis[i][j] = dis[i][k] + dis[k][j]

C语言实现的是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXV 200
int dis[MAXV][MAXV]; //dis[i][j]表示顶点i和顶点j的最短距离，初始为INF，顶点i到i的距离设为0，主函数中更新存在的边的距离

void floyd(){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dis[i][k]!=INF && dis[k][j]!=INF && dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

展开全文 >>

csp-201909

20190901（小明种苹果）

代码1

用struct AppleTree记录苹果树的相关信息，比如一开始的总苹果树，总共疏果的个数。苹果树编号从1开始

1
2
3
4
5
struct AppleTree{
    int id;
    int totNum;
    int shuguoNum;
}

有数据AppleTree trees[]。然后写一个cmp函数，对所有的AppleTree进行排序。

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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

struct AppleTree{
    int id, totNum, shuguoNum;
};
int n,m,T=0,k,p;
vector<AppleTree> trees;

bool cmp(AppleTree t1, AppleTree t2){
    if(t1.shuguoNum > t2.shuguoNum){
        return true;
    }else if(t1.shuguoNum == t2.shuguoNum){
        return t1.id < t2.id;
    }else{
        return false;
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    //init
    trees.resize(n);

    //input
    for(int i=0;i<n;i++){
        trees[i].id = i+1;
        cin>>trees[i].totNum;
        int a=0,b;
        for(int j=0;j<m;j++){
            cin>>b;
            a+=(-b);
        }
        trees[i].shuguoNum = a;
    }

    for(int i=0;i<n;i++){
        T+=(trees[i].totNum-trees[i].shuguoNum);
    }
    sort(trees.begin(),trees.end(),cmp);
    k = trees[0].id;
    p = trees[0].shuguoNum;

    //output
    cout<<T<<" "<<k<<" "<<p<<endl;

}

20190902（小明种苹果续）

代码1

我们设置一个结构体struct AppleTree来表示每个苹果树的id，一开始苹果树，疏果的个数，掉落的个数。

1
2
3
4
5
6
struct AppleTree{
    int id;
    int totNum;
    int shuguoNum;
    int dropNum = 0;
}

在第一次统计之后，以后每遇到疏果值，就累加shuguoNum，每遇到统计值a，就计算totNum-shuguoNum-dropNum-a，就得到当前的掉落的苹果个数，累加至dropNum。

如何计算相邻连续三棵苹果树发生苹果掉落情况的组数？int E，对于每个tree[i]，0<=i<=n-1，计算它前面的，它，它后面的是否都掉落了，若是，则累加组数E。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct AppleTree{
    int id, totNum, shuguoNum, dropNum; //shuguoNum,dropNum初始为0
};
int n,T=0,D=0,E=0;
vector<AppleTree> trees;

int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n;
    //init
    trees.resize(n);
    for(int i=0;i<n;i++){
        trees[i].id = i+1;
        trees[i].shuguoNum = trees[i].dropNum = 0;
    }

    //input
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        for(int j=0;j<a;j++){
            if(j==0){
                cin>>trees[i].totNum;
            }else{
                int b;
                cin>>b;
                if(b > 0){
                    trees[i].dropNum += (trees[i].totNum-trees[i].shuguoNum-trees[i].dropNum-b);
                }else{
                    trees[i].shuguoNum += (-b);
                }
            }
        }
    }

    for(int i=0;i<n;i++){
        T+=(trees[i].totNum-trees[i].shuguoNum-trees[i].dropNum);
        if(trees[i].dropNum > 0) D++;
        if(trees[(i==0?(n-1):(i-1))].dropNum>0 && trees[i].dropNum>0 && trees[(i+1)%n].dropNum>0){
            E++;
        }
    }

    //output
    cout<<T<<" "<<D<<" "<<E<<endl;
}

测试用例

1
2
3
4
5
4
4 74 -7 -12 -5
5 73 -8 -6 59 -4
5 76 -5 -10 60 -2
5 80 -6 -15 59 0

20190903（字符画）

代码1

我用array<int,3> picture[][] 来表示图画，用array<int,3> curBack 记录当前的背景颜色， 默认是0,0,0 。由于每一行有m/p个小区域，然后整个图画被分为n/q行，因此我要遍历m*n/(p*q)次，这样遍历：先遍历一行，看一个区域的颜色，若它的颜色跟当前的curBack相同，则直接输出空格，否则，更改终端的背景色（若颜色正好为黑色，则使用重置终端），然后输出空格，遍历了一行后，若与默认背景色不同，则重置终端，最后输出换行符。

对于输入，要判断三种情况：#abcd #abc #a

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXM 1925
#define MAXN 1085

array<int,3> picture[MAXM][MAXN];
int m,n,p,q;
array<int,3> defBack = {0,0,0};

array<int,3> getColor(int xmin,int xmax,int ymin,int ymax){
    array<int,3> ans={0,0,0};
    for(int i=ymin;i<=ymax;i++){
        for(int j=xmin;j<=xmax;j++){
            ans[0]+=picture[i][j][0];
            ans[1]+=picture[i][j][1];
            ans[2]+=picture[i][j][2];
        }
    }
    int temp = p*q;
    ans[0] /= temp;
    ans[1] /= temp;
    ans[2] /= temp;
    return ans;
}

void printNum(int x){
    string str = to_string(x);
    for(int i=0;i<str.size();i++){
        printf("\\x%02X",str[i]);
    }
}
array<int,3> dealInput(char input[]){
    for(int i=0;i<strlen(input);i++){
        if(input[i]=='\n' || input[i]=='\0'){
            input[i]='\0';
            break;
        }
    }
    string str(input);
    if(strlen(input)==7){
        int a,b,c;
        sscanf(str.substr(1,2).c_str(),"%x",&a);
        sscanf(str.substr(3,2).c_str(),"%x",&b);
        sscanf(str.substr(5,2).c_str(),"%x",&c);
        return {a,b,c};
    }else if(strlen(input)==4){
        int a,b,c;
        string s;
        s = str.substr(1,1);
        s = s+s;
        sscanf(s.c_str(),"%x",&a);
        s = str.substr(2,1);
        s = s+s;
        sscanf(s.c_str(),"%x",&b);
        s = str.substr(3,1);
        s = s+s;
        sscanf(s.c_str(),"%x",&c);
        return {a,b,c};
    }else{
        int a;
        string s;
        s = str.substr(1,1);
        s = s+s;
        sscanf(s.c_str(),"%x",&a);
        return {a,a,a};
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //input
    scanf("%d%d\n%d%d\n",&m,&n,&p,&q);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char input[10];
            fgets(input,10,stdin);
            picture[i][j] = dealInput(input);
        }
    }

    for(int i=0;i<n/q;i++){
        int ymin=i*q, ymax=i*q+q-1;
        array<int,3> curBack = {0,0,0};
        for(int j=0;j<m/p;j++){
            int xmin=j*p, xmax=j*p+p-1;
            array<int,3> color = getColor(xmin,xmax,ymin,ymax);
            if(color == curBack){
                printf("\\x%02X",' ');
            }else{
                if(color != defBack){
                    printf("\\x1B\\x%02X\\x%02X\\x%02X\\x%02X\\x%02X\\x%02X",'[','4','8',';','2',';');
                    printNum(color[0]);
                    printf("\\x%02X",';');
                    printNum(color[1]);
                    printf("\\x%02X",';');
                    printNum(color[2]);
                    printf("\\x%02X",'m');
                }else{
                    printf("\\x1B\\x%02X\\x%02X\\x%02X",'[','0','m');
                }
                printf("\\x%02X",' ');
            }
            curBack = color;
        }
        if(curBack != defBack){
            printf("\\x1B\\x%02X\\x%02X\\x%02X",'[','0','m');
        }
        printf("\\x%02X",'\n');
    }
}

//在输出每一行字符后，如果不是默认值，就设为默认值
//计算每个区域的坐标时弄错了，被q,n/q,p,m/p搞晕了
//输入函数对第二种情况的处理写错了

80分。

20190904（推荐系统）

代码1

设计一个结构体struct Commodity，表示商品，设有属性：商品的类别，商品编号，商品的得分。

1
2
3
4
5
struct Commodity{
    int type; //0..m-1
    int id;
    int score;
}

有一个set<Commodity> cmdSet ，存有每个商品的信息，显然需要指定比较函数，先按score，然后按照type，然后按照id。如果要删除或增加，只需要正常操作就好了。如果要查询，则用迭代器从头开始查，若某类商品已经选择够了，则跳到下一类商品继续查，直到达到了总的查询商品数或遍历完毕, 在这个过程中，保存商品类别到商品编号集合的映射， vector<set<int>> ans，不用map<int,vector<int>> ans的原因是，它较慢。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXM 55

struct Commodity{
    int type; //0..m-1
    int id;
    int score;
    bool operator<(const Commodity c)const{
        if(score == c.score){
            if(type == c.type){
                return id<c.id;
            }
            return type<c.type;
        }else{
            return score>c.score;
        }
    }
    Commodity(int a,int b,int c){
        type=a;
        id=b;
        score=c;
    }
};
int m,n,opNum,k;
set<Commodity> cmdSet;
unordered_map<int,int> idToScore[MAXM];
int veck[MAXM];


vector<set<int>> ans;
void query(int k){
    //init
    for(int i=0;i<m;i++) ans[i].clear();

    set<Commodity>::iterator it = cmdSet.begin();
    while(k>0 && it!=cmdSet.end()){
        int type = (*it).type;
        if(veck[type] != 0){
            ans[type].insert((*it).id);
            k--;
            veck[type]--;
        }
        it++;
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    scanf("%d%d",&m,&n);
    //init
    ans.resize(m);

    //input
    for(int i=0;i<n;i++){
        int id,score;
        scanf("%d%d",&id,&score);
        for(int j=0;j<m;j++){
            cmdSet.insert(Commodity(j,id,score));
            idToScore[j][id]=score;
        }
    }

    cin>>opNum;
    while(opNum--){
        int kind;
        scanf("%d",&kind);
        if(kind==1){
            int type,id,score;
            scanf("%d%d%d",&type,&id,&score);
            cmdSet.insert(Commodity(type,id,score));
            idToScore[type][id]=score;
        }else if(kind==2){
            int type,id;
            scanf("%d%d",&type,&id);
            cmdSet.erase(Commodity(type,id,idToScore[type][id]));
            idToScore[type].erase(id);
        }else{ //查询
            scanf("%d",&k);
            for(int i=0;i<m;i++) scanf("%d",&veck[i]);
            query(k);
            for(int i=0;i<m;i++){
                if(!ans[i].empty()){
                    set<int>::iterator it = ans[i].begin();
                    for(;it!=ans[i].end();it++){
                        printf("%d ",(*it));
                    }
                    printf("\n");
                }else{
                    printf("-1\n");
                }
            }
        }
    }
}

这个代码是通过的。我以前犯的错误是删除：我才用迭代的方式逐个去比较每个商品的type与id和给的type与id是否相同，然后删除，但是这样会很耗时，所以0分了，正确的做法是，对每个type建立id到score的映射，也就是unordered_map<int,int> idToScore[MAXM]，这样的话，可以使用函数cmdSet.erase(Commodity(type,id,score)) 来删除，效率更高。

20190905（城市规划）

代码1

设置一个邻接表vector<vector<int>> dis 表示相邻两个点之间的最短路径，当然一开始只有直接相连的两个点的最短距离，之后可以用floyd算法算出每两个点之间的最短距离。设置一个vector<int> imp 表示重要的点的集合，然后不断选出K个点，计算它们的两两之间距离总和。

关于如何选出K个点，可以使用递归的方式。

具体如何写递归，可以看代码具体实现

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18

int n,m,k;
vector<vector<long long>> dis;
vector<int> imp;

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][k]!=INF && dis[k][j]!=INF && dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

long long minSum = INF;
vector<int> veck; //保存那选出来的k个地点
long long computeSum(){
    long long temp=0;
    for(int i=0;i<k;i++){
        for(int j=i+1;j<k;j++){
            temp+=dis[veck[i]][veck[j]];
        }
    }
    return temp;
}
//从imp[beg,ed]中找x个
void getK(int beg,int ed,int x){
    if(ed-beg+1==x){
        for(int i=beg;i<=ed;i++){
            veck.push_back(imp[i]);
        }
        long long temp = computeSum();
        if(temp<minSum) minSum=temp;
        for(int i=beg;i<=ed;i++){
            veck.pop_back();
        }
        return;
    }else if(x==0){
        long long temp = computeSum();
        if(temp<minSum) minSum=temp;
        return;
    }
    getK(beg,ed-1,x);
    veck.push_back(imp[ed]);
    getK(beg,ed-1,x-1);
    veck.pop_back();
}
int main(){
    //freopen("D://input.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    //init
    dis.resize(n+1);
    for(int i=0;i<n+1;i++){
        dis[i].resize(n+1);
        for(int j=0;j<n+1;j++){
            if(i==j) dis[i][j]=0;
            else dis[i][j] = INF;
        }
    }
    imp.resize(m);

    //input
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d",&a);
        imp[i]=a;
    }
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        dis[a][b]=dis[b][a]=c;
    }

    floyd();
    getK(0,m-1,k);

    //output
    cout<<minSum<<endl;
}

0分。超时

代码2

但是floyd算法太慢了，由于这个题本身考虑的是树，所以可以用每个点的BFS来求最短路径，把floyd算法替换掉。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18

int n,m,k;
vector<vector<long long>> dis;
vector<int> imp;

struct Node{
    int v;
    long long dist;
};

void computeShortestDist(){
    for(int i=1;i<=n;i++){
        //init
        vector<bool> vis(n+1);
        for(int i=1;i<=n;i++) vis[i]=false;

        Node node = {i,0};
        queue<Node> q;
        q.push(node);
        vis[i] = true;
        while(!q.empty()){
            node = q.front();
            q.pop();
            for(int j=1;j<=n;j++){
                if(dis[node.v][j] != INF && node.v!=j && vis[j]==false){
                    dis[i][j] = node.dist + dis[node.v][j];
                    q.push({j,dis[i][j]});
                    vis[j] = true;
                }
            }
        }
    }
}

long long minSum = INF;
vector<int> veck; //保存那选出来的k个地点
long long computeSum(){
    long long temp=0;
    for(int i=0;i<k;i++){
        for(int j=i+1;j<k;j++){
            temp+=dis[veck[i]][veck[j]];
        }
    }
    return temp;
}
//从imp[beg,ed]中找x个
void getK(int beg,int ed,int x){
    if(ed-beg+1==x){
        for(int i=beg;i<=ed;i++){
            veck.push_back(imp[i]);
        }
        long long temp = computeSum();
        if(temp<minSum) minSum=temp;
        for(int i=beg;i<=ed;i++){
            veck.pop_back();
        }
        return;
    }else if(x==0){
        long long temp = computeSum();
        if(temp<minSum) minSum=temp;
        return;
    }
    getK(beg,ed-1,x);
    veck.push_back(imp[ed]);
    getK(beg,ed-1,x-1);
    veck.pop_back();
}
int main(){
    //freopen("D://input.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    //init
    dis.resize(n+1);
    for(int i=0;i<n+1;i++){
        dis[i].resize(n+1);
        for(int j=0;j<n+1;j++){
            if(i==j){
                dis[i][j]=0;
            }
            else {
                dis[i][j] = INF;
            }
        }
    }
    imp.resize(m);

    //input
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d",&a);
        imp[i]=a;
    }
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        dis[a][b]=dis[b][a]=c;
    }

    computeShortestDist();
    getK(0,m-1,k);

    //output
    cout<<minSum<<endl;
}

0分。还是超时。

代码3

这题采用动态规划的方法，但是这个动态规划是最难的。dp[i][j] 表示以i为根节点的子树中选j个重要节点时，这个子树内选中的重要节点的两两距离之和，再加上，子树内j个重要节点到达剩余K-j个重要节点需要经过的子树内路径的长度之和。

1

例如图1，要选出3个重要节点。在1子树中，dp[1][2] = 2+2+2，(注意，这里的dp[1][2]没有计算完，只是中间值，后面还要考虑(3,6,7)部分才能得到最终解)，第一个2表示4和5之间的距离，第二个2表示4为了到达剩余的3-2=1个重要节点所需要经过的<4,2,1>这个1子树内路径的长度之和，也就是1=<4,2,1>的长度 (3-2)；对于第三个2，表示5为了到达剩余的3-2个重要节点所需要经过的<5,2,1>这个1子树内路径的长度之和，也就是1=<5,2,1>的长度 (3-2)。

但是如何用递推的方式求dp[i][j] 呢。对于图1的2子树，dp[2]的计算由它的子树4和5的dp计算而来。dp[i]初始为{0, -1, -1}，表示i子树选中0个重要节点时，dp值为0，选中1个和2个重要节点时，dp值为-1，也就是表示2子树内选择不出这么多的重要节点。下面是计算过程的样例。

  1. 计算dp[4]为{0, 0, -1}
  2. 更新dp[2]为{0, 2, -1}, 这个结果是(2,4)部分的dp[2]的结果。
  3. 计算机dp[4]为{0, 0, -1}
  4. 更新dp[2]为{0, 2, 4}，这时，要合并(2,4)部分和(5)部分。(2,4)部分有1个选中的重要节点，(5)部分有1个选中的重要节点，因此(2,4,5)可以有2个选中的重要节点，dp[2][2] = dp[2][1] + dp[5][1] + 2。2代表5到达另外两个重要节点，所要经过的2次<5,2>路径的长度之和。dp[2][1]=0+1+1，dp[5][1]=0，所以dp[2][2] = 0+1+1+0+1+1，第1个1和第3个1组成2，表示4和5之间的距离，第2个1表示4到达另外一个重要节点要经过的<4,2>路径长度，第4个1表示5到达另外一个重要节点要经过的<5,2>路径长度。

还有一个问题，要更新dp[i]时，从dp[i][k]更新到dp[i][1] 还是从dp[i][1] 更新到dp[i][k]。答案是前者，如果要用后者，可以开一个dp2，然后计算完成后，把dp2赋值到dp就好了。

还有一个情况，万一2子树的根节点2就是重要节点呢？我们之前的计算只考虑2子树的子树的重要节点情况对于2子树的影响，但是没有考虑2节点本身。假如2子树的子树有2个重要节点，那么2子树的dp[2][2]可以为选择2节点和子树中的1个节点组成的2个选中的重要节点，说不定这种情况就比选择2子树的子树中的2个重要节点的情况要好。而且，2子树也可以有选择3个重要节点的情况，也就是子树中的2个加上2节点的1个。

还有就是最优性原理的证明。dp[i][j]的j个重要节点是来自不同的子树的，那么不同的情况选出不同的dp[i][j] 的值，当然最小的那个就是最优的，假如后面的最优决策中用到了这个dp[i][j]，那么是否说明这个dp[i][j]就是最优的？是的。为什么？因为dp[i1][j1] = dp[i][j] + dp[i1][j2] + num 这个公式是进行推导dp的递推式，假如后面的决策最优，那么dp[i][j]也最优。

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 <vector>
using namespace std;

int N, M, K;
vector<bool> imp;
vector<vector<pair<int, int>>> tree;
vector<vector<long long>> dp; 

void solve(int u, int fa) {
    vector<long long>& cur = dp[u];        // 当前要求解的数组
    cur[0] = 0;                            // j = 0(一个重要节点都不选)时，路径和显然为0
    for (const auto& pr: tree[u]) if (pr.first != fa) {
        solve(pr.first, u);                // 先解出子问题dp[pr.first]，然后合并，分治思想
        vector<long long>& sub = dp[pr.first];
        for (int x = K; x > 0; --x) {      // 合并时，重用了数组cur。应该将此时的cur视为前n-1个子树合并后的结果
            for (int y = x; y >= 0; --y) {
                if (cur[y] != -1 && sub[x - y] != -1) {
                    long long t = cur[y] + sub[x - y] + (long long)pr.second * (x - y) * (K - x + y);
                    if (cur[x] == -1 || cur[x] > t) cur[x] = t;
                }
            }
        }
    }
    if (imp[u]) {
        for (int i = K; i > 0; --i)
            if (cur[i] == -1 || cur[i] > cur[i - 1]) // cur[i] != -1的话，cur[i-1]不可能等于-1
                cur[i] = cur[i - 1];
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> N >> M >> K;
    imp.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        imp[x] = true;
    }
    tree.resize(N + 1);
    for (int i = 1; i < N; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].emplace_back(b, c);
        tree[b].emplace_back(a, c);
    }
    dp.resize(N + 1, vector<long long>(K + 1, -1));
    solve(1, 0);
    cout << dp[1][K] << endl;
    return 0;
}

展开全文 >>

csp-201912

20191201（报数）

1

代码1

写一个canSkip(int x) 函数，判断一个数是否可以跳过，设置数组skip[]表示每个人跳过的次数。在循环中，判断num是第a=(num-1)%4的人报数；若num可以跳过，则skip[a]++, 否则，循环计数n减1；然后num++；n==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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
int skip[4] = {0,0,0,0};

bool canSkip(int x){
    if(x%7==0){
        return true;
    }else{
        while(x != 0){
            int b=x%10;
            x = (x-b)/10;
            if(b == 7){
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin>>n;
    int num=1;
    while(n>0){
        if(canSkip(num)){
            skip[(num-1)%4]++;
        }else{
            n--;
        }
        num++;
    }
    //output
    for(int i=0;i<4;i++){
        cout<<skip[i]<<endl;
    }
}

20191202（回收站选址）

1

代码1

用vector<array<int,2>> pos 存储所有的垃圾点，然后建立倒排索引：点坐标的哈希值到pos中对应下标的映射map<long long, int> mp。例如，<10e9, 10e9>的哈希值为(10e9+10e9)*(2*10e9+1)+(10e9+10e9)，它对应pos中的下标0。

写一个哈希函数long long hash(int x, int y)。用vector<array<int,8>> flag 表示每个点的8个相邻位置是否有垃圾站，当一个点A的右方检查到有垃圾站B时，B的左方也可以设置为由垃圾站。遍历pos，来更新flag，再遍历一遍pos，看每个垃圾站的分数，并记录每个分数的垃圾站个数，int score[5]。

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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<array<int,2> > pos;
vector<array<bool,8> > flag;
map<long long, int> mp;
int score[5] = {0,0,0,0,0};
int dirx[8] = {0,1,0,-1,-1,1,1,-1}; //一个点的第i个相邻位置的x坐标的偏移
int diry[8] = {1,0,-1,0,1,1,-1,-1}; //一个点的第i个相邻位置的y坐标的偏移

long long hash2(int x, int y){
    long long h;
    h = (x+1000000000);
    h = h*(long long)(2000000000+1);
    h += (y+1000000000);
    return h;
}

int reversePos(int x){ //x位置的逆位置，如A的0位置是B，则B的2位置是A
    if(x==0){
        return 2;
    }else if(x==1){
        return 3;
    }else if(x==2){
        return 0;
    }else if(x==3){
        return 1;
    }else if(x==4){
        return 6;
    }else if(x==5){
        return 7;
    }else if(x==6){
        return 4;
    }else{
        return 5;
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    //init
    pos.resize(n);
    flag.resize(n);
    for(int i=0;i<n;i++){
        flag[i] = {false,false,false,false,false,false,false,false};
    }

    //input
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        pos[i]={x,y};
        mp[hash2(x,y)] = i;
    }

    for(int i=0;i<n;i++){
        int x=pos[i][0], y=pos[i][1];
        for(int j=0;j<8;j++){
            if(flag[i][j] == false){
                int x1=x+dirx[j], y1=y+diry[j];
                long long h = hash2(x1,y1); //error
                if(mp.find(h) != mp.end()){
                    flag[i][j] = true;
                    flag[mp[h]][reversePos(j)] = true;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(flag[i][0]==true && flag[i][1]==true && flag[i][2]==true && flag[i][3]==true){
            int sm=0;
            for(int j=4;j<8;j++){
                sm+=(flag[i][j]==true?1:0);
            }
            score[sm]++;
        }
    }

    //output
    for(int i=0;i<5;i++){
        cout<<score[i]<<endl;
    }
}

20191203（化学方程式）

1

代码1

思路：vector<int> numLeft(27*27) 和 vector<int> numRight(27*27)分别表示 等式左右两边的各个元素的个数，若numLeft与numRight完全相同，则等式匹配，否则，不匹配。

我们写一个dealItem(string str, int a, vector<int>& num) 来处理一个化合物，也就是加好或等号之间的字符串，例如4Na(Au(CN)2)2，这个函数是个递归函数，递归出口是str是一个只有字母的字符串，而没有数字与括号，a表示对于每个元素，需要乘的倍数，num是输出参数。对于这个例子，处理过程为，进入1层dealItem，处理4Na(Au(CN)2)2，然后进入2层dealItem，处理Na(Au(CN)2)2，a=4，然后累加Na的个数，然后进入3层dealItem，处理Au(CN)2，倍数是8，累加Au的个数，然后进入4层dealItem，处理CN，倍数是16，累加C，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
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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n;
string input;

//根据元素字符串，得到它的hash值，若为单个字母，则返回字母下标，若为双字母，则返回x*27+y
int hash2(string str){
    if(str.size()==1){
        return str[0]-'A'+1;
    }else{
        return (str[0]-'A'+1)*27+(str[1]-'a'+1);
    }
}
vector<int> numLeft(27*27), numRight(27*27);
void dealItem(string str, int a, vector<int>& num){
    if(isdigit(str[0])){ //有系数
        int k=0, k1=0;
        while(k1<str.size() && isdigit(str[k1])) k1++;
        string s1 = str.substr(k,k1-k);
        int b = stoi(s1); //倍数
        dealItem(str.substr(k1),a*b,num);
    }else{
        int k=0,k1=0;
        while(k<str.size()){
            if(isalpha(str[k])){ //遇到元素
                k1 = k+1;
                if(k1<str.size() && islower(str[k1])) k1++;
                if(k1<str.size() && isdigit(str[k1])){ //元素后面跟数字
                    string s1 = str.substr(k,k1-k);
                    k = k1;
                    while(k1<str.size() && isdigit(str[k1])) k1++;
                    string s2 = str.substr(k,k1-k);
                    int b = stoi(s2);
                    dealItem(s1,a*b,num);
                }else{ //累加元素个数
                    string s1 = str.substr(k,k1-k);
                    int h = hash2(s1);
                    num[h] += a;
                }
                k = k1;
            }else{ //遇到括号
                int b = 1; //表示未匹配的左括号个数
                k++;
                k1=k;
                while(k1<str.size() && b!=0){
                    if(str[k1]=='('){
                        b++;
                    }else if(str[k1]==')'){
                        b--;
                    }
                    k1++;
                }
                string s1 = str.substr(k,k1-k-1);
                if(k1<str.size() && isdigit(str[k1])){ //括号后面跟数字
                    k=k1;
                    while(k1<str.size() && isdigit(str[k1])) k1++;
                    string s2 = str.substr(k,k1-k);
                    int c = stoi(s2);
                    dealItem(s1,a*c,num);
                }else{
                    dealItem(s1,a,num);
                }
                k = k1;
            }
        }
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    while(n--){
        cin>>input;
        //cout<<input<<endl;
        //init
        for(int i=0;i<27*27;i++){
            numLeft[i] = numRight[i] = 0;
        }

        int k = input.find('='); //等号的位置
        int k1=0, k2;
        while(k1<k){
            k2 = input.find('+',k1);
            if(k2 != string::npos && k2<k){
                dealItem(input.substr(k1,k2-k1),1,numLeft);
                k1 = k2+1;
            }else{
                dealItem(input.substr(k1,k-k1),1,numLeft);
                k1 = k+1;
            }
        }
        k1 = k+1;
        while(k1<input.size()){
            k2 = input.find('+',k1);
            if(k2 != string::npos){
                dealItem(input.substr(k1,k2-k1),1,numRight);
                k1 = k2+1;
            }else{
                dealItem(input.substr(k1),1,numRight);
                k1 = k2;
            }
        }

        bool flag = true;
        for(int i=0;i<27*27;i++){
            if(numLeft[i] != numRight[i]){
                flag = false;
                break;
            }
        }
        //cout<<"O: "<<numLeft['O'-'A'+1]<<" "<<numRight['O'-'A'+1]<<endl;
        if(flag) cout<<"Y"<<endl;
        else cout<<"N"<<endl;
    }
}

20191204（区块链）

代码1

我们设置一个节点的结构为：

1
2
3
4
5
6
struct Node{
    int u;
    vector<int> link; //初始为{0}
    map<int,int> mp1; //在某个时刻产生了一个块
    map<int,vector<int>> mp2;//在某个时刻接受了一个链
 }

在接收k个处理的时候，若是产生一个新块，则让对应节点的mp1更新。有一个系统时间time=0，当你要查询i时刻的某个节点的链子的时候，要从time开始模拟传播和链更新过程，并把mp1和mp2中已经更新到Link中的项目给删除掉。

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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

struct Node{
    int u;
    vector<int> link; //初始为{0}
    map<int,vector<int>> mp1; //在某个时刻产生了一个块
    map<int,vector<vector<int>>> mp2;//在某个时刻接受了一个链
 };
int n,m,k,t,time2=0;
vector<Node> nodes; //n+1大小
vector<vector<int>> graph; //n+1大小

//vec1是否可以更新vec2
bool canUpdate(vector<int>& vec1, vector<int>& vec2){
    if(vec1.size() > vec2.size()){
        return true;
    }else if(vec1.size()==vec2.size() && vec1.back()<vec2.back()){
        return true;
    }else{
        return false;
    }
}
//在tim时刻开始传播x号节点的链
void difuse(int tim,int x){
    for(int i=0;i<graph[x].size();i++){
        int v = graph[x][i];
        nodes[v].mp2[time2+t].push_back(nodes[x].link);
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    //init
    nodes.resize(n+1);
    for(int i=1;i<=n;i++) nodes[i].link.push_back(0);
    graph.resize(n+1);

    //input
    while(m--){
        int u,v;
        scanf("%d%d",&u,&v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    scanf("%d%d",&t,&k);
    while(k--){
        int a,b,c;
        scanf("%d%d",&a,&b);
        if(cin.get()==' '){
            scanf("%d",&c);
            nodes[a].mp1[b].push_back(c);
        }else{
            for(;time2<=b;time2++){
                for(int i=1;i<=n;i++){
                    bool changed = false;
                    map<int,vector<int>>::iterator it1 = nodes[i].mp1.begin();
                    map<int,vector<vector<int>>>::iterator it2 = nodes[i].mp2.begin();
                    while((it2!=nodes[i].mp2.end()&&(*it2).first==time2) || (it1!=nodes[i].mp1.end() && (*it1).first==time2)){
                        if(it2!=nodes[i].mp2.end()&&(*it2).first==time2){
                            for(int j=0;j<(*it2).second.size();j++){
                                if(canUpdate((*it2).second[j], nodes[i].link)){
                                    nodes[i].link = (*it2).second[j];
                                    changed = true;
                                }
                            }
                            it2 = nodes[i].mp2.erase(it2);
                        }
                        if((it1!=nodes[i].mp1.end() && (*it1).first==time2)){
                            for(int j=0;j<(*it1).second.size();j++){
                                nodes[i].link.push_back((*it1).second[j]);
                                changed = true;
                            }
                            it1 = nodes[i].mp1.erase(it1);
                        }
                    }
                    if(changed){
                        //传播
                        difuse(time2,i);
                    }
                }
            }
            cout<<nodes[a].link.size();
            for(int i=0;i<nodes[a].link.size();i++){
                cout<<" "<<nodes[a].link[i];
            }
            cout<<endl;
        }
    }
}

错误，40分。题目给的测试用例都过了。

测试用例

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
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 27
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 10 10
2 11 9
1 11
2 11
3 11
4 11
5 11
1 12
2 12
3 12
4 12
5 12
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
15 13
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 9
1 10
10 11
11 12
12 13
14 15
6 28
1 1 1
1 2 2
1 6
2 7
13 7
9 7
5 7
3 14
8 14
5 14
11 14
9 25
5 25
13 25
9 29 3
5 29 4
13 29 5
1 53
2 59 6
2 59
1 1000
3 1000
8 1000
9 1000
10 1000
13 1000
14 1000
15 1000

代码2

可以直接存储<时刻，所有结点产生的块或接收的链>，比如可以这样写数据结构：map<int, unordered_map<int, array<vector<int>,2>>> ，外层map建立时刻与所有结点产生的块或接收的链之间的映射，内层unordered_map建立结点编号与产生的块或接收的链之间的映射，这个时候用无序map更好，因为查询操作更多，array<vector<int>,2>的第一个部分是产生的块，第二各部分是接收的链，其实这个时候可以接收很多链，但是通过比较，只留下最优的那个。

展开全文 >>

最大流与最小割

网络流

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

1

对于每个边，我们定义了3个属性：

  1. capacity: 用C表示，最大容量，上图中边的数值就是capacity
  2. flow: 用F表示，每条边的流量
  3. residual: 用R表示，残留，R = C - F

斜对称性：F = -F. 基于斜对称性，当flow为负时，残留值可能大于最大容量

对于上图，假如存在一条流的路径：S->A->C->T. 那么这条路径的流就是这条路径的所有边的最大残留的最小值，也就是R=12. 此时，可以更新每条边的flow和residual, F=0+12=12, R=16-12=4, F=0+12=12, R=12-12=0, F=0+12=12, R=20-12=8, 每次边的flow增加一定数量，residual就必定减少一定数量，这个数量可以为负值. 这条路径被称为增广路，原因是路上的每个边的残留值都大于0，意味着可以有流从这个路径上通过。

最大流

一般使用Edmonds-Karp算法，即最短路径增广算法，简称EK算法。

通过多次运行BFS算法，得到一条增广路，也就是从S到T的可行的流大于0的路径，然后更新相关边的属性值，其中有一点要注意：设这条路径的流是flow，则flow+=flow, flow+=(-flow), residual-=(-flow)，每次一个边的残留值减去一个值，对应的反向边的残留值就会加上一个值。不断运行BFS算法，直到找不到一条增广路了。

下面是一个运行EK算法的例子：黑色数字表示残留值，一开始残留值就是最大容量值，红色数字表示流量值。

  1. 第一次运行BFS得到一个增广路：

    2

    更新残留值：

    3

  2. 第二次运行BFS算法得到一个增广路

    4

    更新残留值：

    5

  3. 第三次运行BFS得到一个增广路

    6

    更新残留值：

    7

最小割

最大流最小割定理(Maximum Flow, Minimum Cut Theorem):网络的最大流等于最小割

我们把S能到达的点集设为s, 不能到达的点集设为t，构造一个割集C[s,t]。如下图所示

7

C[s,t] 中含有边, , , .
其中满流边是前三个，它们构成了最小割。

展开全文 >>

工作日记-2020

PS：工作日记旨在记录一年内的工作事务，方便以后高效查找。

Fio+LS 2020会议展览：Paper Title: Eye3DVas

https://www.frontiersinoptics.com/home/registration/?utm_source=reg01&utm_medium=email&utm_campaign=20640_FIO 会议注册网址

Paper Information
Control Number: 3470924
Paper Title: Eye3DVas: three-dimensional reconstruction of retinal vascular structures by integrating fundus image features

Presentation Information
Presentation Number: JTu1B.22
Presenting Author: Fengfeng Zhou
Your Presentation Time: 8:30 AM to 9:00 AM [for posters?]
Real-time Presentation times: September 15, 2020 from 8:30 AM to 9:00 AM
Session Title: Joint Poster Session IIB

这是OSA（美国光学学会）旗下的一个重要会议，也算很有名的。我的OSA账号是：zhouhh2517@mails.jlu.edu.cn 密码：zhou19981209

8/19

在北京时间8月19号的时候，OSA发了一封邮件：FiO LS 2020 | Poster Presenter Presentation Preference。这封邮件经周老师转发到姚学长邮箱，再由姚学长转发到我这，哈哈，我是真的卑微。邮件地址：https://mails.jlu.edu.cn/webmailgo.php?v=1597804150

信中主要提了以下几件事情：

  1. 每个poster都要提供one-page poset pdf，3分钟的录屏演讲和参加实时的讨论。其实我只要满足前两个就够了，第三个只是强烈建议而已。
  2. 由于在EDT时间9月14日开始会议（也就是北京时间9月15日）前1个星期前提交材料（上面说的pdf，录屏之类的），也就是9月8日前提交。
  3. 在EDT时间8月25日前（北京时间8月26日）前登录网站，选择想要的presentaion method。

选择presentation preference的网址是：https://fio-ls2020.abstractcentral.com/login?NEXT_PAGE=WELCOME&PRE_ACTION=LOGIN&ssoToken=5170e43d-517c-4a7e-b8e2-893768b8c0c7&Site=osac

8/20

我本来想先解决Poster Presenter Presentation Preference的事情，但是正如邮件中所说的那样，可能发生账户问题，我不得不向cstech@osa.org 发送邮件:

1
2
3
4
5
6
7
8
Dear Sir or Madam，
	I have got a problem in my OSA account. I was about to check the invitations in the
ScholarOne Abstracts webpage for my FiO/LS poster prestations. Although I followed the 
instructions written in the "FiO LS 2020 | Poster Presenter Presentation Preference" 
email sent to me, I got the "you have no invitations to display" message in invitations
page. So please check my account: "zhouhh2517@mails.jlu.edu.cn"

Best regards.

还得看他们那边怎么解决。

http://www.cvent.com/events/2020-fio-ls-conference/event-summary-0b9bbbcc6d634745996f3473d0e04a97.aspx?i=48fa0d67-5876-41a3-a6e3-05a3d4dadd2b 这是会议链接的网址。通过这个网址，我恰巧弄明白了OSA，APS/DLS和FiO/LS的关系。OSA是美国光学学会，FiO/LS（Frontiers in Optics + Laser Science）是它旗下的一个重要国际会议，APS/DLS是美国物理学会的激光科学部，全称为American Physical Society’s Division of Laser Science 。OSA与APS/DLS是合作关系。

收到一封名为“Registration Confirmed - 2020 FiO + LS Conference”的邮件，可以在我的吉大邮箱中查看到。

1
2
3
4
5
Event: 2020 FiO + LS Conference
Attending: huahui zhou
Date: 14-Sep-2020 - 17-Sep-2020
 
Confirmation number: JYNZJ3Q8XJK

1

还有一件事，是invoice，需要这个来报销经费。因此我给custserv@osa.org 发邮件

1
2
3
4
5
6
7
8
9
10
Dear Sir or Madam,
	I have completed all the steps included in the registration. My registration number
is JYNZJ3Q8XJK and my registration accouont is "zhouhh2517@mails.jlu.edu.cn". Can you 
offer me an formal invoice so that I can get the reimbursement of $100 of publishing 
fee for presenting author. The addressee of invoice can be Fengfeng Zhou, College of 
Computer Science and Technology, Jilin University. If any other information for the 
invoice is needed, please tell me through email so that I can deal with this as soon as
possible.

Best regards.

之后我收到了回信，里面附有收据。

接收不到invitation的问题已经被叫Maria的人给解决了，原来是这个论文的invitation被列在了周老师的邮箱下，所以我收不到，但是经过Maria询问周老师后，认为我是presenter，就把invitation转发到我的邮箱下了。

8/21

但是，我还是没法用我的账号在那个网站上接收invitaion. 又发给她Sigillito,&nbsp,Maria\msigillito@osa.org\邮件

1
2
3
4
5
6
7
8
Dear Maria,
	Althouth I receive the email about presentation preferences, I still can't see the 
invitation when I get access to the site. I click the message button, then invitation 
button, but no message is sent to me. Can you check my account "zhouhh2517@mails.jlu.
edu.cn" and the control ID "3470924" again? Or must I use Fengfeng Zhou's email account
so I can deal with the invitaion? 
Thank you.
Huahui.

8/22

我开始做Poster Presenter Presentation Preference 的事情，按照QQ邮件“FiO LS 2020 | Poster Presenter Presentation Preference” sent by cstech@osa.org 的指示，登录网站操作。

This OSA Meeting may be virtual,but there are still opportunities to meet up and talk in-depth and
to make those professional connections. (The only thing you’ll miss is the handshake.) 这句话很幽默。

根据我在FIO/LS官方网站上的调查，我们的这篇摘要只是一个Poster，我们可以提交Poster PDF, 3-minute preview, 甚至在你的discord channel和参会者互动，但是我们不会做现场的presentation。https://www.frontiersinoptics.com/home/speaker-service-center/virtual-meeting-frequently-asked-questions/ 有关于提交材料的信息, 还有一些QA。

8/30

我以前收到的是这个邮件。

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
Dear Huahui Zhou,

The 2020 OSA Frontiers in Optics + Laser Science APS/DLS will be held in an all-virtual, web conference format, 14-17 September 2020. We are launching a new interactive Poster Session experience designed to increase presenter and attendee discussion at the Frontiers in Optics/Laser Science Conference.

All posters will be displayed in gallery view with search features by keyword, topic category, presentation times, and a flag displaying any poster presenters available for real-time communication. Each poster will have a dedicated page that will include a 3-minute poster preview and/or poster PDF, as well as an embedded chat window displaying the chat dialog supported by the discord platform.

Presenters will have the following opportunities to present your research and communicate with attendees:

• I will only submit a PDF of my poster.
• I will only submit a 3-minute video explaining my poster.
• I will submit a PDF and record a 3-minute video explaining my poster.
• I will submit a PDF, record a 3-minute video and be available for real-time discussion via text chat during my indicated presentation time. (Preferred)
• I will submit a PDF, record a 3-minute video and be available for real-time discussion via video / audio during my indicated presentation time.
• I am not interested in any of these options. Please withdraw my paper.

Presenters may choose one or multiple methods of presentation (example, provide a Poster PDF and be available for real-time discussion, or provide a 3-minute video and a poster PDF). Presenters are highly encouraged to fulfill all three options to best facilitate a robust and dynamic virtual Poster Session.

Please remit your poster file(s) to cstech@osa.org at least one week prior to the conference. The file name should be your presentation number followed by “-1” (e.g. your file should be named the following JTu1B.22-1). Poster PDFs can also be uploaded to CCR using the instructions that will be sent directly to you with a personal link to upload. All registrants will be able to access both your paper and your poster PDF from your presentation listing in the mobile app. In addition, OSA is happy to upload the poster PDF to the OSA Publishing platform as supplemental material to the actual paper. Note: your poster PDF should be one page only.

Using the information below, please log on to our system and select your desired presentation method no later than 24 August. You will receive an email with upload instructions closer to the meeting. You will have until at least 7 September to record your presentation. If you instead desire to withdraw your presentation, you may select this option here as well. However, please note that only authors who present virtually will have their abstract published in OSA Publishing’s Digital Library.

Please use the link and instructions below to log in to our ScholarOne system and select your preferred presentation method. Responses are due by 24 August 2020. If you need further clarification, we have also attached instructions with visuals via PDF.

For more information on presentation guidelines, click here. For frequently asked questions about the virtual conference, click here.

Selecting Your Presentation Preference

1. Click here to access the site to select your presentation preference. This link will direct you to an osa.org page for log-in. Once you log-in using your OSA username and password, you will then be directed to the ScholarOne site.

但是，今天我又收到了这样一封邮件。

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
Speaker Instructions and Access Codes for FiO + Laser Science,Quantum 2.0

Dear Huahui Zhou;

Welcome to the Presentation Submission Portal for the OSA Frontiers in Optics + Laser Science APS/DLS and Quantum 2.0 Conferences. Please submit your presentation through this site by Monday, 7 September 2020 for quality assurance. If you are unable to meet this deadline, please upload at your earliest convenience but at least 24 hours prior to your presentation. Management staff will do its best effort to check all presentations submitted after 7 September.

All papers MUST BE PRESENTED either via a pre-recorded video or live in order for your paper to be published. As such, it is preferable for you to also pre-record your presentation, which could be used as a real-time back-up in case of internet connection fluctuations. Refer to the FiO/LS Speaker Service Center or the Quantum 2.0 Speaker Service Center for the virtual presentation guidelines including step-by-step instructions using Zoom Technology as well as answers to frequently asked questions (including alternatives to downloading Zoom, if your institution has restricted your use of this technology).

Video Upload Instructions
Please click on the link below to access the presentation submission portal:

URL: https://ibk.nyc/pm/osa/fiolsq

If the link does not take you directly to the website, copy and paste it into your browser.

Your Personalized Access Code is: FFF5D806

A help e-mail link (Red Button) is available at the top of the page for technical assistance.

If you have any technical questions regarding this presentation submission portal, please send an email to our support team at eventsupport@ccrsolutions.com.

Once your presentation has been submitted via the website, you will be able to update it by resubmitting a revision. Please note that OSA staff will have access to the most recent submission. The latest approved presentation will be automatically uploaded to your session (Zoom Room) on the day of your presentation.

To view the complete Conference Program and schedule of talks visit the conference websites. If you have any questions regarding the Conferences, please contact cstech@osa.org. As a reminder, virtual conference resources, including Frequently Asked Questions, are available at the “For Speakers” Section of either the OSA Frontiers in Optics + Laser Science APS/DLS Conference or the Quantum 2.0 Conference websites.

OSA Management

所以到底要我干嘛？我要发送一个PDF，还是发送一个视频。我想，应该是两个都要做，PDF是为了展览，就像是放电影前要做海报一样，但是视频就是那个电影。

8/31

今天决定录好pre-recorded video，

https://www.usenix.org/conference/atc19/presentation/li-yongkun 这是李永坤老师在ATC（Annual Technical Conference）上的presentation，演讲的是他的博士生，以这个presentation做样例，自己也做一个。

9/14

conference websit

https://www.frontiersinoptics.com/home/schedule/ 这个是conference website 的网址，可以通过这个网址看到很多FIO/LS2020的现场报告，还可以下载论文，进入这个网址就知道了。

discord

I wanted to reach out to you to inform you of the changes we have made from our previous virtual meeting to provide a better engagement with you and the attendees. All posters will be displayed on the conference website in a gallery view with search features by keyword, topic category, presentation times, and a flag displaying any poster presenters available for real-time communication. In order for this last functionality to work, we require that you create a profile in Discord. More details and instructions related to Discord are below.。这个是FIO/LS发给我的，要让我注册discord账号。然后我就打开VPN，下载了dicord，用zhouhh2517的邮箱注册了账号。https://discord.gg/Hgqev8R，点击这个网址，会自动打开discord，to get started in the FiO+LS / Quantum 2.0 Discord Server。

As poster presenters, you have control of your poster presentation channel. In order to have the proper role applied you will need to submit the following command in the #role-request channel. To see this process in action click here:

http://www.frontiersinoptics.com/library/exhibits/auto-role.gif

Command: !presenter-sa-71849zhemu

shi xiangjun提供的数据库开发机会

9/3

因为我今天我发了一则说说，这位上交学长主动找我看简历，当看到我找的是基础架构部门时，就找我去做数据库，我一开始不想做，说我要去华科了，之后就我们打电话聊天，他说做这个数据库的好处是可以了解整个数据库的细节，我想这个经历加在简历中应该会很有好处，至少我可以说对数据库很懂，比以前什么都不懂要好，然后他给我的简历提了建议，说要在自我评价中写自己会什么技能，还给我看了一些人去投字节的简历。我在想如果是我来找人做数据库，会怎么劝说人，我该向学长学习。

https://github.com/CHIANGEL/2020_Summer_Intern_Logs

https://15445.courses.cs.cmu.edu/fall2019/ 一个课程

1

以上四个部分好好做下，github上有测试代码

1

1

https://github.com/MXWXZ/resume 简历模板

展开全文 >>

csp-202006

20200601（线性分类器）

1

1

思路

我们要设计一个函数classify 用来根据输入的点和直线确定点在这个直线的哪个区域：0/1。我们设置一个数组duiying[][]，duiying[i][j] 表示第i条直线在第j条区域应该是分类A还是分类B，对于每个直线，我们考虑每个点，计算出它在该直线下的区域，然后该区域下对应的类型和该点的类型是否相同。

代码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
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
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define MAXM 25

int n, m;
array<int, 3> points[MAXN]; //点
array<int, 3> lines[MAXM]; //线
int duiying[MAXN][2]; //每个线的0/1区域对应哪个类型（0表示对应A，1表示对应B）
bool flag[MAXM]; //表示每个线是否是分类器，默认是

//根据点和线，知道点在线的哪一个区域: 0/1
int classify(int x, int y, int a, int b, int c)
{
    if(b == 0)
    {
        double temp = -(double)a / c;
        return (double)y < temp ? 1 : 0;
    }
    else if(c == 0)
    {
        double temp = -(double)a / b;
        return (double)x > temp ? 1 : 0;
    }
    else if((b > 0 && c < 0) || (b < 0 && c > 0))
    {
        double temp = -(double)b * x / c - (double)a / c;
        return (double)y > temp ? 0 : 1;
    }
    else
    {
        double temp = -(double)b * x / c - (double)a / c;
        return (double)y > temp ? 1 : 0;
    }
}

int main()
{
    //freopen("D://input.txt","r",stdin);
    //init
    memset(duiying, -1, sizeof(duiying));
    for(int i = 0; i < MAXM; i++) flag[i] = true;

    //input points and lines
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        char type;
        cin >> x >> y >> type;
        points[i] = {x, y, type == 'A' ? 0 : 1};
    }
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        lines[i] = {a, b, c};
    }

    int x, y, a, b, c;
    for(int j = 0; j < m; j++)
    {
        a = lines[j][0];
        b = lines[j][1];
        c = lines[j][2];
        for(int i = 0; i < n; i++)
        {
            x = points[i][0];
            y = points[i][1];
            int area = classify(x, y, a, b, c);
            if(duiying[j][area] == -1)
            {
                duiying[j][area] = points[i][2];
            }
            else if(duiying[j][area] != points[i][2])
            {
                flag[j] = false;
                break;
            }
        }
    }

    //output
    for(int i = 0; i < m; i++)
    {
        if(flag[i] == false)
        {
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
    }

    return 0;
}

20200602（稀疏向量）

3

3

代码1

把(index, value)记录在数组当中，这样两个向量就用两个数组vec1, vec2表示了，用i, j 表示两个数组的下标，若两个index相同，则累加结果，然后i++, j++，否则，较小的index对应的数组下标递增。

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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n,a,b;
vector<array<int,2>> vec1,vec2; //不要用普通数组，因为不知道数组的大小应该设为多大，若设为最大1e9，则空间炸了

int main(){
	//freopen("D://input.txt","r",stdin);
	//input
	cin>>n>>a>>b;
	//init
	vec1.resize(a);
	vec2.resize(b);
	//input
	int index,value;
	for(int i=0;i<a;i++){
        scanf("%d%d",&index,&value);
		vec1[i] = {index,value};
	}
	for(int i=0;i<b;i++){
        scanf("%d%d",&index,&value);
		vec2[i] = {index,value};
	}

	int p1,p2,i=0,j=0;
	long long sum=0;
	while(i<a&&j<b){ //两个向量的元素都没有遍历完
		p1 = vec1[i][0];
		p2 = vec2[j][0];
		if(p1==p2){
			sum+=(long long)vec1[i][1]*vec2[j][1];
			i++;
			j++;
		}else if(p1<p2){
			i++;
		}else{
			j++;
		}
	}
	//output
	cout<<sum<<endl;

	return 0;
}

超时了，80分。原因是，用cin进行输入，在数据量很大时, cin比scanf慢了很多倍。

20200603（Markdown渲染器）

5

6

6

6

代码1

我将计算段落和项目的行数的任务交给了dealSeg(int beg, int ed)函数和dealItem(int beg, int ed)函数，只要给出输入的段落或项目所在的开始行和结束行，就可以正确算出来，前提是不要把开始行和结束行输入错了。接着，就可以把精力集中在段与段，段与项目，项目与项目之间该如何处理了。我们用pre标识前面处理了什么类型，pre=-1表示前面什么都没处理，也就是说刚开始，pre=0表示前面处理了段落，pre=1表示前面处理了一个项目。其实，在我的设计中，如果很多个连续的项目后跟了至少一个空行，那么这些项目可以看做是段落，见代码的109行。

  1. 若遇到了段落，则只要pre!=-1，就无脑递增行数
  2. 若遇到了项目。若前面发现有空行，如108-111行所示，且前面处理了项目，则递增行数；若前面处理了段落，则递增行数。

对于dealSeg与dealItem函数，注意去掉每行的收尾的连续空格。

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

vector<string> inputs; //所有的行
int w;
int ans=0; //结果，共有多少行
int pre=-1; //
int dealSeg(int beg, int ed){
    int line=0, col=0; //当前正在填写第几行第几列，col是[0,w-1]
    for(int i=beg;i<=ed;i++){
        if(i!=beg){ //新的一行开始了，先加上空格
            if(col!=0){
                col++;
                if(col==w){
                    line++;
                    col=0;
                }
            }
        }
        //去掉每行收尾的连续空格
        int lineBeg=0,lineEd=inputs[i].size()-1;
        while(inputs[i][lineBeg] == ' ') lineBeg++;
        while(inputs[i][lineEd] == ' ') lineEd--;

        for(int j=lineBeg;j<=lineEd;j++){
            if(inputs[i][j] != ' '){
                col++;
                if(col==w){
                    line++;
                    col=0;
                }
            }else{
                if(col != 0){
                    col++;
                    if(col==w){
                        line++;
                        col=0;
                    }
                }
            }
        }
    }
    if(col==0) return line;
    else return line+1;
}
int dealItem(int beg,int ed){
    int line=0,col=0; //由于项目的一行要先输出三个空格，所以col=[0,w-4]
    for(int i=beg;i<=ed;i++){
        if(i != beg){ //新的一行开始了，先加上空格
            if(col!=0){
                col++;
                if(col==w-3){
                    line++;
                    col=0;
                }
            }
        }
        //去掉每行收尾的连续空格
        int lineBeg=2,lineEd=inputs[i].size()-1;
        while(lineBeg<inputs[i].size() && inputs[i][lineBeg] == ' ') lineBeg++;
        while(lineEd>=0 && inputs[i][lineEd] == ' ') lineEd--;

        for(int j=lineBeg;j<=lineEd;j++){
            if(inputs[i][j] != ' '){
                col++;
                if(col==w-3){
                    line++;
                    col=0;
                }
            }else{
                if(col != 0){
                    col++;
                    if(col==w-3){
                        line++;
                        col=0;
                    }
                }
            }
        }
    }
    if(col==0){
        if(line==0) return 1; //这是一个空项目（特判）
        else return line;
    }
    else return line+1;
}
bool isSpaceLine(string& str){
    for(int i=0;i<str.size();i++){
        if(str[i]!=' ')
            return false;
    }
    return true;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //input, 输入w和inputs
    ios::sync_with_stdio(false);
    cin>>w;
    cin.get();
    string line;
    while(getline(cin,line)){
        inputs.push_back(line);
    }

    int i=0,j;
    while(i<inputs.size()){
        while(i<inputs.size() && isSpaceLine(inputs[i])){
            i++;
            if(pre==1) pre=0; //空行使得段的分隔，前面的项目已经完结，成为一个段落。
        }
        if(i>=inputs.size()) break;
        if(inputs[i].size()>=2 && inputs[i].substr(0,2)=="* "){ //是项目
            //找到j，使得[i,j)是一个项目
            j = i+1;
            while(j<inputs.size() && !isSpaceLine(inputs[j]) && inputs[j].size()>=2 && inputs[j].substr(0,2)=="  "){
                j++;
            }
            //检查是否用多输出一个空行
            if(pre == 0) ans++;

            ans+=dealItem(i,j-1);
            //cout<<"ITEM:"<<"i="<<i<<" j-1="<<j-1<<" "<<dealItem(i,j-1)<<endl;//////
            i = j;
            pre = 1;
        }else{ //是段落
            //找到j，使得[i,j)是一个段落
            j = i+1;
            while(j<inputs.size() && !isSpaceLine(inputs[j]) && !(inputs[j].size()>=2 && inputs[j].substr(0,2)=="* ")){
                //不是空白行，不是项目的开头行，则是属于段落
                j++;
            }
            if(pre==0 || pre==1) ans++;
            ans+=dealSeg(i,j-1);
            i = j;
            pre = 0;
        }
    }
    cout<<ans<<endl;
}

超时，80分。原因是输入太慢了，用ios::sync_with_stdio(false)

20200604（1246）

10

代码1

通过一个循环，计算出第n秒的串是什么（我知道，存储容量肯定不够，2的10亿次方，自己算一下这有多大），然后用正则表达式计算包含了多少个S串。

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
//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

string str = "1"; //保存每个经过以2为底的幂运算的结果
int n;
string S;
long long ans = 0;

int main(){
    //input
    cin>>n>>S;

    for(int i=0;i<n;i++){
        string temp;
        for(int j=0;j<str.size();j++){
            if(str[j]=='1'){
                temp += "2";
            }else if(str[j]=='2'){
                temp += "4";
            }else if(str[j] == '4'){
                temp += "16";
            }else{
                temp += "64";
            }
        }
        str = temp;
    }
    regex e(S);
    smatch sm;
    string::const_iterator iterBeg = str.begin();
    string::const_iterator iterEnd = str.end();
    while(regex_search(iterBeg, iterEnd, sm, e)){
        ans++;
        ans %= 998244353;
        iterBeg = sm[0].second;
    }
    cout<<ans<<endl;
}
//---------------------------------------------------------------------------------------------------------------------------------

超时，32分。

代码2

数字中只可能函数有1, 2, 4, 6，根据观察只可能产生的1数位和2数位是{1,2,4,6,16,26,41,42,44,46,61,62,64,66}。因此我们就对一个串，比如6416，看它可能产生哪些数位，以6416为例，6可以产生6,4,64; 4可以产生1,6,16; 1可以产生2; 6可以产生6,4,64; 64可以产生6,4,1,6,64,41,16,但是其中的6,4,64,1,6,16和6与4产生的重合了，所以就只剩下41; 41可以产生1,6,2,16,62,但是1,6,16,2和4与1产生的重合了，所以就剩下62; 16可以产生2,6,4,26,64，但是2,6,4,6,4和1与6产生的重合了，所以就剩下了26。所以最终结果是1,4,4,6,6,6,16,26,41,62,64,64，观察6416的下一个串6416264，结果一模一样。

我们可以设置一个矩阵mat，(14,14)的，保存每个数位在经过一次变换后得到的数位，比如16经过变换后得到26（要去掉与1和6重合的部分，所以才只有26一个）。我们可以设置1的id是0, 2的id是1, 4的id是2，等等，这样就可以方便将变换关系保存在mat中。

经过每次变换，我们都保存结果串中每种数位有多少个，比如说16对应的就是，1有1个, 6有1个，16有1个。这样，可以用一个数组int initMat[14] 来保存这个信息。如何计算每次变换后，每种数位有多少个呢？我们有变换矩阵，有目前每种数位有多少个（intMat），可以计算出来的。经过思考，initMat*mat 就是可以产生这个结果。如果要经过n次变换，就让initMat乘以n个mat。

为了效率，我们可以快速幂的方法加速上述运算。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,M = 998244353;
string s;
int baseEle[14] = {1,2,4,6,16,26,41,42,44,46,61,62,64,66};
vector<int> convert[14] = {{2},{4},{1,6,16},{4,6,64},{26},{46},{62},{64},{61},{66},{42},{44},{41},{46}}; //error: 最后一个46写成41了
unordered_map<int,int> mp = {{1,0},{2,1},{4,2},{6,3},{16,4},{26,5},{41,6},{42,7},{44,8},{46,9},{61,10},{62,11},{64,12},{66,13}};
int initMat[14];
int mat[14][14];

void mult1(int a[], int b[][14]){
    //init
    int c[14];
    memset(c,0,sizeof(c));

    for(int j=0;j<14;j++){
        for(int i=0;i<14;i++){
            long long temp = (long long)a[i]*b[i][j];
            int temp2 = (int)(temp%M);
            c[j] += temp2;
            c[j] %= M;
        }
    }

    //out
    for(int i=0;i<14;i++){
        a[i] = c[i];
    }
}
void mult2(int a[][14]){
    //init
    int b[14][14];
    memset(b,0,sizeof(b));

    for(int i=0;i<14;i++){
        for(int j=0;j<14;j++){
            for(int k=0;k<14;k++){
                long long temp = (long long)a[i][k]*a[k][j];
                int temp2 = (int)(temp%M);
                b[i][j] += temp2;
                b[i][j] %= M;
            }
        }
    }

    //out
    for(int i=0;i<14;i++){
        for(int j=0;j<14;j++){
            a[i][j] = b[i][j];
        }
    }
}
int main(){
    //init
    memset(initMat,0,sizeof(initMat));
    initMat[0] = 1;
    memset(mat,0,sizeof(mat));
    for(int i=0;i<14;i++){
        for(int j=0;j<convert[i].size();j++){
            int k = mp[convert[i][j]]; //error
            mat[i][k] = 1;
        }
    }

    cin>>n>>s;
    while(n>0){
        if(n%2==1){
            mult1(initMat,mat);
        }
        mult2(mat);
        n = n>>1;
    }
    cout<<initMat[mp[stoi(s)]];
}

96分。果然这题，又涉及到long long相关的错误。

20200605（乔乔与牛牛逛超市）

代码1

这题的做法可以总结为“水平选择，纵向贪心”。我们用邻接表发来建立商品与商品之间的关系，若有（x->y，1）边，则意味着必须有y，才能有x；若有边（x->y，2）边，则意味着必须要有y，x才能买正好$L_y$ 和 $R_y$ 件。我们建立一个vector\ itemNum，表示已经考虑了哪些商品并且买了多少件，itemNum[1]=0表示考虑了1商品并且1商品的个数为0，已经考虑好的商品不要去改个数。采用回溯法，向下深挖时将商品添加到itemNum中，回溯时将商品从itemNum中删除。从第1个商品开始考虑，进行回溯法，然后考虑第2个商品，若第2个商品在回溯时，需要第i个商品且第i个商品被考虑过且第i个商品的个数为0，则这是要继续考虑第i个商品但是不要再从i商品继续向下考虑了，否则，不再继续考虑，然后是第3，第4个…….

只有x被购买了，y才能被购买 意思不是先买了x，再买y，而是x和y可以同时买，也满足这个条件。

代码2

代码1的思路没法做，原因是每个点可能依赖很多个点，而且有不同的依赖类型，没法向下做了。

展开全文 >>

局域网技术与组网工程实验

交换机基础

通过telnet配置交换机

使用telnet方式访问交换机的前提条件是什么

对交换机进行初始化配置，否则用户无法正确登录和访问。初始化配置是为交换机配置正确的网段和IP地址，以便实现交换机互联。交换机配置的工作包括：

  1. 配置正确的交换机IP地址，这里所说的为交换机配置IP地址，实际上是指在交换机上配置管理VLAN接口的IP地址。
  2. 确定与PC相连的交换机端口属于该管理VLAN
  3. 如果PC和交换机相连的端口在同一个局域网内，则其IP地址必须配置为同一个网段；否则，要保证PC和交换机必须路由可达。

生成树协议STP

交换机STP原理

STP（Spanning Tree Protocol）是生成树协议，该协议的原理是按照树的结构来构造网络拓扑，消除网络中的环路，避免由于环路的存在而造成广播风暴以及MAC地址表不稳定等问题。可在提高可靠性的同时又能避免环路带来的各种问题。

STP的工作过程

运行STP算法的网桥（交换机），在规定的间隔内（默认2秒），通过网桥协议数据单元（BPDU）的组播帧与其他交换机交换配置信息，完成生成树的构建。

选举根桥(Root)

通过比较网桥优先级选取根网桥，给定广播域内只有一个根网桥。一般情况下， 网桥的BID（桥ID）最小的那个作为根网桥。

每个交换机假设自己为根，互相发送BPDU报文，然后通过比较BID竞选根桥。

根端口(RP)选举

交换机通过RP来向根交换机发送信息，可以有最小的路径开销，根端口负责向根交换机发送数据，并且通过这个端口发送数据较快。

  1. 非根交换机根据根路径开销（RPC，Root Path Cost）来选举根端口。根路径开销是指接收由根桥发送的BPDU所经过的所有路径的路径开销之和，交换机在接收BPDU时累加路径开销，转发BPDU时不累加路径开销。路径开销是设置在交换机的端口上的，表示这个端口的开销。

  2. 若该交换机的根路径开销相同，则比较两个路径的上一个交换机的BID（多个端口连接的对端交换机的BID），例如，有ABCD，AEFD两个从A到达D的路径，则比较C和F的BID来选择应该将哪个端口设置为RP。

  3. 若交换机多个端口连接的对端交换机也相同（即BID相同），比如ABDE, ACDE，从D的两个端口分别连接E的两个端口。此时比较连接的对端交换机的端口的PID。

RP的选举是向上的。与DP的选举相反，DP是向下的，指向深层的交换机和主机。

指定端口(DP)选举

选举指定端口是相对于两个交换机的，比如有两个交换机A和B相连，

  1. 比较A和B的RPC，选择RPC较小的那个交换机连接的端口为指定端口。
  2. 若RPC相同，则选择BID较小的那个交换机连接的端口作为DP。

阻塞端口（AP）

阻塞非跟端口和非指定端口。

网络中不再有环路了。

题目

  1. STP协议中端口处在（Forwarding）状态可以转发用户报文
  2. STP协议中桥ID(BID)的构成包括？（桥优先级，桥背板MAC地址）

交换机以太网端口

端口镜像配置方法

将指定的一个或多个端口的报文复制到观察端口，用于报文的分析和监视。

1

先设置观察端口，再设置镜像端口。缺省情况下，系统没有配置本地观察端口，如果要修改观察端口，需要删除原来的配置后再重新配置（将和观察端口绑定的镜像端口删除掉，再配置它们的观察端口）。

一个观察端口可以观察多个镜像端口，同时，一个镜像端口也可以被很多个观察端口观察。

设置观察端口后，该端口自动配置为Trunk端口，删除观察端口后，该端口自动配置为Access端口，且加入VLAN1。

端口绑定

利用了交换机的地址学习功能，只要取消了端口的地址学习功能，那么它就只能知道你告诉它的主机应该往哪个端口发送，而你没有告诉它的，它则不知道往哪里发送，因为这个端口不能学习了，这个你告诉它的主机就是存在于它的静态地址表项中的。如果你再设置：这个端口抛弃它不知道往哪里发的报文（目的MAC不在它的静态地址表项中），那它就只能转发目的MAC地址存在于静态地址表项中的报文，从而实现端口绑定的功能。

  1. 取消该端口的MAC地址学习功能
  2. 将授权设备的MAC地址添加到该端口的静态地址表项中。

题目

  1. negotiation 命令所在的视图是：（端口视图）

  2. 关于基于端口的镜像说法正确的是？（ABCD）

    • A、

      在S3700和S5700交换机上可以有两个观察端口。

    • B、

      一个观察端口可以监控多个镜像端口。

    • C、

      一个镜像端口可以被多个观察端口监控。

    • D、

      在配置镜像端口前，先要设置好观察端口。

  3. 关于MAC地址与端口绑定的说法正确的是？（AC）

    • A、

      静态MAC地址表项的优先级高于动态MAC地址表项。

    • B、

      交换机的端口被shutdown后，与该端口绑定的静态MAC地址表项和动态MAC地址表项都会被清空。

    • C、

      端口绑定是通过禁用端口学习功能，并将授权主机MAC地址与授权端口配对信息添加到静态MAC地址表项来实现的。

    • D、

      同一时刻、相同的MAC地址，在交换机的MAC地址表中可能会存在多个交换机端口与之绑定。

交换机链路聚合

VLAN

虚拟局域网原理

解决的问题

早期以太网基于CSMA/CD的共享通讯介质的通讯技术，当主机数目过多时会导致冲突严重，广播泛滥，性能显著下降甚至网络不可用等问题。通过交换机虽然可以解决冲突问题，但是仍然不能隔离广播报文和提升网络质量。VLAN技术可以把一个物理LAN划分为多个逻辑的VLAN，每个VLAN是一个广播域，VLAN内的主机通信就像在一个LAN内一样，而VLAN间则不能直接互通，这样，广播报文就限制在一个VLAN内。

2

VLAN标签

IEEE 802.1协议规定，在以太网数据帧的目的MAC地址之后，协议类型字段之前加上4字节的VLAN标签（VLAN tag），用以表示VLAN信息。

在以太网交换网络中，以太网帧主要有以下两种：有标记帧（Tagged帧）和无标记帧（Untagged 帧）。主机，服务器，Hub和傻瓜交换机只能收发Untagged帧；交换机，路由器既能收发Tagged帧也能收发Untagged帧。

接口的链路类型

现网中属于同一个VLAN的用户可能被连在不同的交换机上，且跨越交换机的VLAN不止一个，这就需要交换机间的接口能够同时识别和发送多个VLAN的数据帧。

​ 根据接口连接对象以及对收发数据帧处理的不同，分为4种接口链路类型：Access, Trunk, Hybrid, QinQ。

Access接口

Access接口一般用于主机/服务器和交换机的相连。交换机内部只处理Tagged帧，主机和服务器不能处理Tagged帧，所以Access接口需要给收到的数据帧添加VLAN Tag，因此Access接口也必须设置自己的缺省VLAN（PVID）。配置了PVID后，该Access接口也就加入了该VLAN。

3

Trunk接口

Trunk一般用于连接交换机，路由器。它可以允许多个VLAN的帧带Tag通过，但是只允许一个VLAN的帧从该接口上不带Tag（即剥除Tag）。

4

VLAN划分

基于接口划分是最常用的VLAN划分方式。网络管理员预先给交换机的每个接口配置不同的PVID。

优点是：定义成员简单，配置过程简单明了
缺点是：移动成员需要重新配置VLAN，配置不够灵活

VLAN内互访

VLAN内互访首先要进行ARP过程，这个过程与普通的局域网内的ARP过程的区别是：

  1. 交换机转发数据帧时检查是否是能够通过的VLAN的帧
  2. MAC地址表项是：（MAC，VID，端口）

由于Trunk接口可以允许多个VLAN的帧通过链路，这被称作透传。

管理VLAN

为交换机配置IP地址，通常是指在交换机上配置管理VLAN接口的IP地址。

问题

  1. 三层交换机和路由器是如何实现VLAN间通信的？

    三层交换机配置了很多VLANIF虚拟接口，并在该接口下配置了IP地址，三层交换机的各个端口是如何配置的呢？access端口配置了PVID，trunk端口配置了可允许特定VLAND的帧通过。当三层交换机收到一个帧时，通过它的目的IP地址就可以通过路由表或者MAC地址表知道它应该往哪个端口发送（假如是portA），并且知道了该目的网络属于哪个VLAN。

    路由器配置了子接口，以及下面的IP地址，在子接口下配置了dot1q termination vlan，这样的话，当路由器知道要往哪个子接口转发帧时，就可以将对应的VLAN标签加在帧上。

    14

VLAN实验

如图所示，某企业的交换机连接有很多用户，且相同业务用户通过不同的设备接入企业网络。为了通信的安全性和避免广播风暴，企业希望相同业务用户之间可以互相访问，不同业务用户不能互相访问。现在，通过在交换机上配置基于接口划分的VLAN，来满足企业的需求。

10

  1. 由于User1和User2是处于同一个VLAN，因此应该设置同一个网段的IP，因此我设置User1的IP是：192.168.10.1，User2的IP是：192.168.10.2。同理，我设置User3和User4的IP分别为：192.168.20.3，192.168.20.4。它们的子网掩码都是255.255.255.0。

  2. 配置SwitchA的VLAN以及交换机接口的链路类型

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    $<SwitchA> system-view #进入系统视图
    $[SwitchA] vlan batch 2 to 3 #创建VID为从2到3的VLAN
    $[SwitchA-vlan] quit #从vlan视图中退出来
    $[SwitchA] int g0/0/1 #进入g0/0/1端口视图
    $[SwitchA-GigabitEthernet0/0/1] port link-type access #g0/0/1端口设置为access接口
    $[SwitchA-GigabitEthernet0/0/1] port default vlan 2 #g0/0/1的PVID设置为2
    $[SwitchA-GigabitEthernet0/0/1] quit
    $[SwitchA] int g0/0/2 #进入g0/0/2端口视图
    $[SwitchA-GigabitEthernet0/0/2] port link-type access #g0/0/2端口设置为access接口
    $[SwitchA-GigabitEthernet0/0/2] port default vlan 3 #g0/0/2的PVID设置为3
    $[SwitchA-GigabitEthernet0/0/2] quit
    $[SwitchA] int g0/0/3 #进入g0/0/3端口视图
    $[SwitchA-GigabitEthernet0/0/3] port link-type trunk #g0/0/3设置为trunk接口
    $[SwitchA-GigabitEthernet0/0/3] port trunk allow-pass vlan 2 to 3 #让vlan tag为2,3的帧通过

  3. 配置SwitchB的VLAN以及交换机接口的链路类型，与2的配置一模一样

题目

  1. IEEE 802.1Q协议中，VLAN标签的长度是：（4字节）

三层交换机

三层交换机原理

VLAN间互访需要路由器的三层交换功能的支持。

但是每一个VLAN都要使用一条独占的物理连接连接到路由器的一个接口上，这对路由器是不现实的。使用Trunk技术和路由器子接口技术来解决这个问题，交换机与路由器只有一个物理连接连接到路由器的一个物理接口，然后这个物理接口被划分为多个逻辑接口。

由于路由器使用软件实现数据交换，效率不行，因此就有了三层交换机。

二层交换机和路由器的功能的集合构成了三层交换机，三层交换机有如下特性：

  1. 二层交换引擎：实现同一个网段内的快速二层转发
  2. 三层路由引擎：实现跨VLAN的三层路由转发。三层交换机的交换功能是路由器的交换功能的裁剪版，比如，IP选项，报文分片功能都被裁剪掉了；三层交换机使用精确地址匹配的方式，便于硬件实现；当收到数据帧时，发现目的MAC不在地址表项中，就转向三层路由引擎，查询目的IP地址所在的网段之后，向目的网段广播一个ARP包，发现目的MAC在地址表项中时，直接在二层进行转发，这就是后面要提到的流转发方式。
  3. 每一个VLAN对应一个IP网段
  4. 使用流交换方式。报文到报文的交换方式与流交换方式的区别：如果每一个报文都要经历第三层处理，并且业务流转发是基于第三层地址的，这种交换方式就是报文到报文交换方式；如果只是第一个报文经过第三层处理，其他后续报文只进行第二层转发，这种就是流交换方式。

三层交换机与路由器的不同

主要的不同在于三层交换功能：

  1. 查询路由表项时，三层交换机得到的结果是某个精确路由对应的VLAN或网段，而路由器得到的是最长匹配的网络号对应的下一跳IP地址。
  2. 三层交换机采用流交换方式，路由器采用报文到报文的交换方式
  3. 三层交换机裁剪了很多功能

题目

  1. 以下关于三层交换机的描述正确的是（A）

    • A、

      三层交换机使用硬件支持多个VLAN的二层转发。

    • B、

      三层交换机适合用于大型网络间的路由。

    • C、

      三层交换机使用报文到报文的交换方式。

    • D、

      三层交换机和同性能的路由器相比更加昂贵。

  2. [Huawei] interface vlanif 10

    [Huawei-Vlanif10] ip address 10.10.10.1 24

    以上命令用于配置（B）。

    • A、

      vlan10管理接口的IP地址。

    • B、

      vlan10三层接口的IP地址。

    • C、

      vlan10二层转发接口的IP地址。

    • D、

      除vlan10外的其它vlan的路由接口IP地址。

路由器基础

通用路由平台VRP（Versatile Routing Platform）：

  1. 以IP业务为核心，采用组件化的体系结构
  2. 提供了基于应用的可裁剪和可扩展的功能

题目

  1. 目前绝大多数华为设备使用的都是（B）版本。

    • A、

      VRP8

    • B、

      VRP5

    • C、

      VRP3

    • D、

      VRP2

路由器基础管理

静态路由基础

静态路由配置

串口连接

5

在串行接口上，可以通过指定下一跳路由或出端口来配置静态路由。

以太网连接

6

在以太网接口上配置静态路由时，必须要指定下一跳地址。

负载分担

两个路由器通过多条物理线路进行连接，多条物理线路对应多个网段和多个路由器接口，在每一个路由器接口上设置静态路由后，可以支持等值负载分担（ECMP，Equal-Cost Multiple Path） 。

ECMP是指到达同一个目的地有多条等价链路，流量在这些等价链路上平均分配，不会考虑链路带宽的差异。

ECMP的缺点是：在路径间带宽差异大时，带宽利用率低。

路由备份

又叫浮动静态路由。在链路正常的情况下，只有主路由在路由表中，在链路出现故障时，浮动静态路由会被激活。

设置浮动静态路由时，设置它的优先级比主路由的优先级低一些。

静态路由及路由器子接口实验

请运用静态路由，以及路由器子接口实现VLAN间通信，使得5台PC机可以互相通信。

11

分析：R1的g0/0/1物理端口必须划分为两个逻辑接口，因为这个端口底下有两个VLAN。同时，为了保证不同网段的主机能够跨路由器进行通信，R1和R2必须要进行静态路由设置。

我的拓扑图是下面的：

11

  1. 按照题目要求将PC01-PC05的IP地址和子网掩码先配置一下，等一下配置完了路由器，再来配置PC们的默认网关。

  2. 配置SWITCH1的VLAN和端口链路类型，和R1连接的g0/0/1端口要设置为trunk，和SWITCH2相连接的g0/0/4端口要设置为trunk。在系统视图下

    1
    2
    3
    int g0/0/1 #进入g0/0/1端口
    port link-type trunk #g0/0/1设置为trunk
    port trunk allow-pass vlan 10 to 20 #因为vlan10和20的主机都有可能访问外网，因此这个链路要允许10和20的vlan帧通过
    1
    2
    3
    int g0/0/2
    port link-type access
    port default vlan 10
    1
    2
    3
    int g0/0/3
    port link-type access
    port default vlan 20
    1
    2
    3
    int g0/0/4
    port link-type trunk
    port trunk allow-pass vlan 10 to 20

  3. SWITCH2与SWITCH1类似。SWITCH3不需要配置，因为R2的g0/0/1对应的网段没有设置VLAN。

  4. 配置R1的逻辑接口，IP和静态路由。在系统视图下

    1
    2
    int g0/0/0
    ip address 192.168.30.1 255.255.255.0
    1
    ip route-static 10.1.1.0 255.255.255.0 192.168.30.2 #R1的一个静态路由：到达10.1.1.0网络的下一条IP是192.168.30.2
    1
    2
    3
    4
    5
    int g0/0/1
    int g0/0/1.1 #在g0/0/1下面创建了一个逻辑接口
    dot1q termination vid 10 #g0/0/1.1接口对VLAN TAG为10的帧去掉tag
    ip address 192.168.10.1 255.255.255.0
    arp broadcast enable #允许进行ARP广播
    1
    2
    3
    4
    5
    int g0/0/1
    int g0/0/1.2 #在g0/0/1下面创建了一个逻辑接口
    dot1q termination vid 20 #g0/0/1.2接口对VLAN TAG为20的帧去掉tag
    ip address 192.168.20.1 255.255.255.0
    arp broadcast enable #允许进行ARP广播

  5. 配置R2的接口IP和静态路由

  6. 配置每个主机的默认网关。PC01和PC03的默认网关是192.168.10.1，因为192.168.10.1是一个逻辑接口的IP地址，与VLAN20相连接。其他的网关配置也类似。

题目

  1. 两个路由器R1和R2之间有3条链路，带宽分别是10Mbps、 20Mbps和30Mbps。如果使用等值负载分担，则R1和R2之间的总带宽为（B）

    • A、

      20M

    • B、

      30M

    • C、

      50M

    • D、

      60M

以太网帧结构

Ethernet_II帧的length类型值大于等于1536，帧长度在64到1518之间

802.3帧的length类型值大于1536，帧长度小于1500

RIP路由协议

12

路由环路问题

12

一开始，各个路由器的表项是：

1
2
3
A: 11.4.0.0 S0 2
B: 11.4.0.0 S1 1
C: 11.4.0.0 E0 0

1、当网络11.4.0.0 发生故障，路由器C 最先收到故障信息，路由器C 把网络11.4.0.0 设为不可达，并等待更新周期到来通告这一路由变化给相邻路由器。如果，路由器B的路由更新周期在路由器C之前到来，那么路由器C就会从路由器B那里学习到去往11.4.0.0的新路由（实际上，这一路由已经是错误路由了）。这样路由器C的路由表中就记录了一条错误路由（经过路由器B，可去往网络11.4.0.0，跳数增加到2 ）。
2、路由器C 学习了一条错误信息后，它会把这样的路由信息再次通告给路由器B，根据通告原则，路由器B也会更新这样一条错误路由信息，认为可以通过路由器C去往网络11.4.0.0，跳数增加到 3 。
3。这样，路由器 B 认为 可以通过路由器C 去往网络11.4.0.0，路由器C 认为 可以通过路由器B 去往网络11.4.0.0，就形成了环路。

解决办法

  1. 水平分割

    一种消除路由环路并加快网络收敛的方法是通过叫做“水平分割”的技术实现的。其规则就是不向原始路由更新的方向再次发送路由更新信息（个人理解为单向更新，单向反馈）。比如有三台路由器ABC，B向C学习到访问网络10.4.0.0的路径以后，不再向C声明自己可以通过C访问10.4.0.0网络的路径信息，A向B学习到访问10.4.0.0网络路径信息后，也不再向B声明，而一旦网络10.4.0.0发生故障无法访问，C会向A和B发送该网络不可达到的路由更新信息，但不会再学习A和B发送的能够到达10.4.0.0的错误信息。

    从接口X发出的路由更新中不能包括那些出口也为X的路由信息。

  2. 路由中毒

    定义最大值在一定程度上解决了路由环路问题，但并不彻底，可以看到，在达到最大值之前，路由环路还是存在的。为此，路由中毒就可以彻底解决这个问题。其原理是这样的：假设有三台路由器ABC，当网络10.4.0.0出现故障无法访问的时候，路由器C便向邻居路由发送相关路由更新信息，并将其度量值标为无穷大，告诉它们网络10.4.0.0不可到达，路由器B收到毒化消息后将该链路路由表项标记为无穷大，表示该路径已经失效，并向邻居A路由器通告，依次毒化各个路由器，告诉邻居10.4.0.0这个网络已经失效，不再接收更新信息，从而避免了路由环路。

  3. 毒性反转

  4. 抑制

  5. 触发更新

题目

  1. 距离向量路由算法采用哪些方法来减少路由环路？（ABCD）

    • A、

      水平分割

    • B、

      毒性反转

    • C、

      抑制

    • D、

      触发更新

OSPF路由协议

LS与DV的不同

采用链路状态路由协议的路由器不是交换到达目的地的距离，而是收集所有的链路信息来维护一张网络拓扑结构图，进而根据这个拓扑图计算最佳路由。当网络拓扑结构发生变化时，只需要将相应记录而非整个数据库通知其他节点，收到信息的各路由器相应地修改自身的链路状态数据库，并重新计算路由后，就可以继续正常工作了。

OSPF

OSPF是开放最短路径优先协议，基于链路状态的内部网关协议。

Router ID

一台路由器要运行OSPF协议，必须存在Router ID，这个可以手工配置，如果没有ID号，则：

  1. 若系统当前配置了Loopback接口的IP地址，则选择最后配置的Loopback接口的IP作为router id。
  2. 若系统当前没有配置Loopback接口，则选取第一个配置并UP的物理接口的IP地址作为router id。

区域（Area）

OSPF将自治系统（AS）划分为多个区域，最重要的区域是骨干区域0，可以实现一种分级的管理。

对于物理上与骨干区域不连续的区域，需要配置虚连接（virtual links）来保持与骨干区域在逻辑上的连续性。虚连接是在两台ABR之间，通过一个非骨干区域内部路由而建立的一条逻辑上的连接通道。

7

区域边界路由器（ABR, Area Border Router）：连接骨干区域与非骨干区域的路由器。

路由聚合

AS被划分为不同的区域后，每一个区域通过ABR相连，区域间可以通过路由汇聚来减少路由信息，减少路由表的规模。

OSPF中关键的表

邻居表

LSDB

路由表

DR和BDR

8

OSPF报文

有5种OSPF报文：

  1. Hello报文：发现，维持邻居关系，选举DR，BDR

  2. DD（Database Description）报文：用于形成LSDB

    路由器使用DD报文进行主从路由器的选举和数据库摘要信息的交互，Router ID大的作为主路由器；DD报文包含LSA的头部信息，用来描述LSDB的摘要信息

  3. LSR（LSA Request）报文：请求LSA

  4. LSU（LSA Update）：收到LSR后，应答LSA

  5. LSACK（Link State ACK）：收到LSU后，对LSU进行确认

邻居状态机

9

在2-way状态时，双方都已经建立了邻居关系，这时可以进行发送数据信息了。

ExStart表示双方可以发送信息了。

启动OSPF

OSPF支持多进程，一台路由器上启动的OSPF进程之间由不同的进程号区分。OSPF进程号在启动OSPF时进行设置，它只在本地有效，不影响与其他路由器之间的报文交换。

如果在启动OSPF时不指定进程号，将使用缺省的进程号1；关闭OSPF时不指定进程号，缺省关闭进程号1。

在同一个区域中的进程号必须一致。

OSPF路由协议实验

网络拓扑图如下所示，请使用OSPF路由协议配置各台路由器，使得PC1、PC2、PC3可以互相连通。

12

  1. 配置R1的接口IP地址，loopback接口地址

    1
    2
    int g0/0/0
    ip address 192.168.1.1 24
    1
    2
    int g0/0/1
    ip address 192.168.10.1 24
    1
    2
    int loopback1
    ip address 192.168.31.11 24 #设置loopback接口地址

  2. 配置R2,R3的，和R1类似

  3. 配置各个主机的IP和默认网关

题目

  1. 哪些类型的网络需要指定路由器？（AD）

    • A、

      广播类型

    • B、

      点到点类型

    • C、

      点到多点类型

    • D、

      非广播多路访问

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家