csp-201503-201312

20150303（节日）

代码1

先计算每年a月的第1天是星期几，然后计算该月有几天，然后就知道第b个星期c存不存在了。int getWeekday(int year,int month, int day)得到星期几，int getMonthdays(int year, int month) 得到这个年的这个月有几天。

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

int a,b,c,y1,y2; //a月, 第b个星期c
int daysOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool isRun(int year){
    return (year%400==0 || (year%4==0&&year%100!=0));
}
int getMonthdays(int year, int month){
    if(month!=2){
        return daysOfMonth[month];
    }else{
        if(isRun(year)) return 29;
        else return 28;
    }
}
int getWeekday(int year,int month){
    int wkd = 2;
    for(int y=1850;y<year;y++){
        if(isRun(y)){
            wkd += 366;
        }else{
            wkd += 365;
        }
        wkd %= 7;
    }
    for(int m=1;m<month;m++){
        wkd += getMonthdays(year,m);
        wkd %= 7;
    }
    if(wkd==0) return 7;
    else return wkd;
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>a>>b>>c>>y1>>y2;
    for(int y=y1;y<=y2;y++){
        int wkd = getWeekday(y,a);
        int mthds = getMonthdays(y,a);
        int len; //第b个星期c距离1号多少天
        if(c>=wkd){
            len = c-wkd+(b-1)*7;
        }else{
            len = (7-wkd)+c+(b-1)*7;
        }
        if(len<mthds){
            cout<<y<<"/";
            cout<<setw(2)<<setfill('0')<<right<<a<<"/";
            cout<<setw(2)<<setfill('0')<<right<<1+len<<endl;
        }else{
            cout<<"none"<<endl;
        }
    }
}

20150304（网络延时）

代码1

这题用邻接表表示法，然后求树的最长长度。交换机用1-n表示，主机用n+1到n+m表示。

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

int n,m;
vector<int> graph[MAXNM];

//以u为根遍历的最大深度和最大深度的节点编号
array<int,2> bfs(int u){
    queue<array<int,2>> q;
    bool inq[MAXNM];
    memset(inq,0,sizeof(inq));
    q.push({0,u});
    inq[u] = true;
    int maxLayer = 0;
    int maxLayerId;

    while(!q.empty()){
        array<int,2> a = q.front();
        q.pop();
        u = a[1];
        if(maxLayer<a[0]){
            maxLayer = a[0];
            maxLayerId = u;
        }
        for(int i=0;i<graph[u].size();i++){
            int v = graph[u][i];
            if(!inq[v]){
                q.push({a[0]+1,v});
                inq[v] = true;
            }
        }
    }
    array<int,2> a = {maxLayer, maxLayerId};
    return a;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int id;
        cin>>id;
        graph[id].push_back(i);
        graph[i].push_back(id);
    }
    for(int i=n+1;i<=n+m;i++){
        int id;
        cin>>id;
        graph[id].push_back(i);
        graph[i].push_back(id);
    }
    array<int,2> a = bfs(1);
    a = bfs(a[1]);
    cout<<a[0];
}

20141202（Z字形扫描）

代码1

为了清除地知道应该往哪个方向走，设置一个方向数组int dirGroup[2][4] = {0,1,2,3,2,1,0,3};，最初时使用dirGroup[0]，当向右或向下走不动时，改为dirGroup[1]。设置groupIndex=0，dirIndex = 0，表示当前应该走a = dirGroup[0][dirIndex]号的方向，当a表示0或2时，走完这个方向后，应该dirIndex = (dirIndex+1)%4，当a这个方向走不动时，就应该换一个groupIndex和dirIndex。

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

int n;
int dirGroups[2][4] = {0,1,2,3,2,1,0,3};
int dirGroup=0, dirIndex=0;
int matrix[MAXN][MAXN];

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    int i=0,j=0;
    int cnt = 0;
    while(i!=n-1 || j!=n-1){
        if(cnt==0) cout<<matrix[i][j];
        else cout<<" "<<matrix[i][j];
        cnt++;
        int a = dirGroups[dirGroup][dirIndex];
        if(a==0){
            if(j<n-1){
                j++;
                dirIndex = (dirIndex+1)%4;
            }else{
                i++;
                dirGroup = 1;
                dirIndex = 1;
            }
        }else if(a==1){
            i++; j--;
            if(i+1>=n || j-1<0){
                dirIndex = (dirIndex+1)%4;
            }
        }else if(a==2){
            if(i<n-1){
                i++;
                dirIndex = (dirIndex+1)%4;
            }else{
                j++;
                dirGroup = 1;
                dirIndex = 3;
            }
        }else{
            i--; j++;
            if(i-1<0 || j+1>=n){
                dirIndex = (dirIndex+1)%4;
            }
        }
    }
    if(cnt==0) cout<<matrix[i][j];
    else cout<<" "<<matrix[i][j];
}

20141203（集合竞价）

代码1

用一个结构体表示所有交易：

1
2
3
4
5
6
struct Trans{
    int type; //0表示买，1表示卖
    double price;
    int num;
    bool isCanceled; //false
};

把所有交易存在Trans transes[]中，然后排序。int num1, num2分别表示当p0为0时买家的交易数量和卖家的交易数量，num1=所有买家的交易数量之和，num2=0。然后随着p0不断增大，相应地减少num1和增加num2，若有一个p0使得min(num1, num2)变小了，则上一个p0就是答案。

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

struct Trans{
    int type; //0表示买，1表示卖
    double price;
    int num;
    bool isCanceled; //false
};
bool cmp(Trans t1, Trans t2){
    if(t1.isCanceled==true || t2.isCanceled==true){
        return t1.isCanceled<t2.isCanceled;
    }else{
        if(t1.price != t2.price){
            return t1.price<t2.price;
        }
        return t1.type>t2.type;
    }
}
Trans transes[MAXN];

int main(){
    //freopen("D://input.txt","r",stdin);
    string line;
    int cnt = 1;
    while(getline(cin,line)){
        stringstream ss(line);
        string s1;
        ss>>s1;
        if(s1=="buy" || s1=="sell"){
            transes[cnt].isCanceled = false;
            transes[cnt].type = (s1=="buy"?0:1);
            ss>>transes[cnt].price;
            ss>>transes[cnt].num;
        }else{
            transes[cnt].isCanceled = true;
            int lineNum;
            ss>>lineNum;
            transes[lineNum].isCanceled = true;
        }
        cnt++;
    }

    long long num1=0,num2=0;
    double preP0=0.0,p0=0.0;
    long long preMinNum=0,minNum=0;
    for(int i=1;i<cnt;i++){
        if(transes[i].isCanceled == false && transes[i].type==0){
            num1 += transes[i].num;
        }
    }
    sort(transes+1,transes+cnt,cmp);
    int i;
    for(i=1;i<cnt&&transes[i].isCanceled==false;){
        preP0 = p0;
        preMinNum = minNum;
        p0 = transes[i].price;
        int j = i-1;
        for(int j2=j;j2>=1&&transes[j2].price==transes[j].price;j2--){
            if(transes[j2].type==0)
                num1 -= transes[j2].num;
        }
        for(j=i;j<cnt&&transes[j].isCanceled==false&&transes[j].price==p0;j++){
            if(transes[j].type==1){
                num2 += transes[j].num;
            }
        }
        minNum = min(num1,num2);
        if(minNum<preMinNum){
            break;
        }
        i = j;
    }
    if(i==cnt || transes[i].isCanceled==true){
        cout<<fixed<<setprecision(2)<<p0;
        cout<<" "<<minNum;
    }else{
        cout<<fixed<<setprecision(2)<<preP0;
        cout<<" "<<preMinNum;
    }
}

我发现了一个严重的错误，可能会酿成大错。

1
2
3
4
5
6
7
8
9
10
11
/*bool cmp(Trans t1, Trans t2){
    if(t2.isCanceled==true){
        return true;
    }else if(t1.isCanceled==true){
        return false;
    }else if(t1.price!=t2.price){
        return t1.price<t2.price;
    }else{
        return t1.type>t2.type;
    }
}*/
1
2
3
4
5
6
7
8
9
10
bool cmp(Trans t1, Trans t2){
    if(t1.isCanceled==true || t2.isCanceled==true){
        return t1.isCanceled<t2.isCanceled;
    }else{
        if(t1.price != t2.price){
            return t1.price<t2.price;
        }
        return t1.type>t2.type;
    }
}

对于上面两个cmp函数，貌似都实现了同一个功能，但是只有第二个函数是对的。因为要保证，在t1.isCanceled和t2.isCanceled相同时，返回false。

当输入浮点数时，用scanf("%lf",&d)

代码2

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

struct Trans{
    int type; //0表示卖，1表示买
    double price;
    int num;
    bool isCanceled; //false
};
bool cmp(Trans t1, Trans t2){
    if(t1.isCanceled==true || t2.isCanceled==true){
        return t1.isCanceled<t2.isCanceled;
    }else{
        if(t1.price != t2.price){
            return t1.price<t2.price;
        }
        return t1.type<t2.type;
    }
}
Trans transes[MAXN];

int main(){
    //freopen("D://input.txt","r",stdin);
    string line;
    int cnt = 1;
    while(getline(cin,line)){
        stringstream ss(line);
        string s1;
        ss>>s1;
        if(s1=="buy" || s1=="sell"){
            transes[cnt].isCanceled = false;
            transes[cnt].type = (s1=="buy"?1:0);
            ss>>transes[cnt].price;
            ss>>transes[cnt].num;
        }else{
            transes[cnt].isCanceled = true;
            int lineNum;
            ss>>lineNum;
            transes[lineNum].isCanceled = true;
        }
        cnt++;
    }
    sort(transes+1,transes+cnt,cmp);
    long long num1=0,num2=0,minNum=-1;
    int i;
    for(i=1;i<cnt && transes[i].isCanceled==false;i++){
        if(i==1){
            if(transes[i].type==0){
                num2 += transes[i].num;
            }
            for(int j=i;j<cnt&&transes[j].isCanceled==false;j++){
                if(transes[j].type==1){
                    num1 += transes[j].num;
                }
            }
            minNum = min(num1,num2);
            continue;
        }
        if(transes[i].type==0){
            num2 += transes[i].num;
        }
        if(transes[i-1].type==1){
            num1 -= transes[i-1].num;
        }
        if(minNum>min(num1,num2)){
            break;
        }else{
            minNum = min(num1,num2);
        }
    }
    i--;
    printf("%.2f %lld",transes[i].price,minNum);
}

47行把long long写成long了，害我找了半天，若找不出来，就70分了。

20140904（最优配餐）

代码1

这题使用BFS的方法，但是有一点很难想到的是：初始时居然要把每个分店都加入到队列中，好灵性啊。

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;
#define MAXN 1005

int n,m,k,d;
int graph[MAXN][MAXN]; //0表示空，-1表示分店，-2表示障碍，大于0表示客户的订餐量
vector<array<int,2>> stores; //存储分店的位置
int dirr[4] = {0,0,1,-1};
int dirc[4] = {1,-1,0,0};

long long bfs(){
    queue<array<int,3>> q; //x,y,layer
    bool vis[MAXN][MAXN];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<stores.size();i++){
        q.push({stores[i][0],stores[i][1],0});
        vis[stores[i][0]][stores[i][1]] = true;
    }

    long long ans = 0;
    while(!q.empty()){
        int row=q.front()[0],col=q.front()[1],layer=q.front()[2];
        q.pop();
        if(graph[row][col]>0){
            ans += (long long)graph[row][col]*layer;
        }
        for(int i=0;i<4;i++){
            int row2=row+dirr[i], col2=col+dirc[i];
            if(row2>=0&&row2<n&&col2>=0&&col2<n
               &&graph[row2][col2]!=-2
               &&!vis[row2][col2]){
                q.push({row2,col2,layer+1});
                vis[row2][col2] = true;
            }
        }
    }
    return ans;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //init
    memset(graph,0,sizeof(graph));

    cin>>n>>m>>k>>d;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        graph[n-y][x-1] = -1;
        stores.push_back({n-y,x-1});
    }
    for(int i=0;i<k;i++){
        int x,y,c;
        cin>>x>>y>>c;
        graph[n-y][x-1] = c;
    }
    for(int i=0;i<d;i++){
        int x,y;
        cin>>x>>y;
        graph[n-y][x-1] = -2;
    }

    cout<<bfs()<<endl;
}

展开全文 >>

csp-201509

20150903（模板生成系统）

代码1

用unordered_map<string, string> varToStr 来建立变量到字符串的映射。对于每一行，找到，若找不到则把它看做正常字符串，若找到了，再看中间的字符串是不是，例如name，若是，则替换，否则将它看做正常的字符串。

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;

vector<string> input;
int m,n;
unordered_map<string,string> varToStr;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>m>>n;
    cin.get();
    for(int i=0;i<m;i++){
        string line;
        getline(cin,line);
        input.push_back(line);
    }
    for(int i=0;i<n;i++){
        string line,var,str;
        getline(cin,line);
        int k = line.find(' ');
        var = line.substr(0,k);
        int k1 = line.find('"',k);
        int k2 = line.find('"',k1+1);
        str = line.substr(k1+1,k2-k1-1);
        varToStr[var] = str;
    }

    for(int i=0;i<m;i++){
        string& line = input[i];
        string line2;
        int k1=0, k2;
        while(k1<line.size()){
            k2 = line.find("{{",k1);
            if(k2==string::npos){
                line2 += line.substr(k1);
                k1 = line.size();
            }else{
                line2 += line.substr(k1,k2-k1);
                k1 = k2;
                k2 = line.find("}}",k1+2);
                string s1 = line.substr(k1+3,k2-k1-4);
                if(varToStr.find(s1)!=varToStr.end()){
                    line2 += varToStr[s1];
                }
                k1 = k2+2;
            }
        }
        cout<<line2<<endl;
    }
}

20150904（高速公路）

代码1

对每个点运行BFS算法，得到这个点可达的所有点，然后就可以知道哪两个点是互通的了。但是肯定超时，得60或70分没问题。

代码2

用tarjan算法求强联通分量。

展开全文 >>

csp-201512

20151201（数位之和）

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
    cin>>n;
    int ans = 0;
    while(n!=0){
        ans += n%10;
        n /= 10;
    }
    cout<<ans;
}

20151202（消除类游戏）

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

int n,m;
int graph[MAXN][MAXN];
array<int,4> dir[MAXN][MAXN]; //上，下，左，右

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

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>graph[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1) dir[i][j][0] = 0;
            else dir[i][j][0] = (graph[i][j]==graph[i-1][j]?dir[i-1][j][0]+1:0);
            if(j==1) dir[i][j][2] = 0;
            else dir[i][j][2] = (graph[i][j]==graph[i][j-1]?dir[i][j-1][2]+1:0);
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(dir[i][j][0]>=2){
                for(int k=0;k<=dir[i][j][0];k++){
                    graph[i-k][j] = 0;
                }
            }
            if(dir[i][j][2]>=2){
                for(int k=0;k<=dir[i][j][2];k++){
                    graph[i][j-k] = 0;
                }
            }
        }
    }
    //output
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==1) cout<<graph[i][j];
            else cout<<" "<<graph[i][j];
        }
        cout<<endl;
    }
}

20151203（画图）

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

int m,n,q;
char graph[MAXN][MAXN];

int dirr[4] = {0,0,1,-1};
int dirc[4] = {1,-1,0,0};
void fillChar(int x,int y,char c){
    //init
    int row=n-y-1,col=x;
    bool vis[MAXN][MAXN];
    memset(vis,0,sizeof(vis));
    queue<array<int,2>> q;
    q.push({row,col});
    vis[row][col] = true;

    while(!q.empty()){
        row = q.front()[0];
        col = q.front()[1];
        q.pop();
        graph[row][col] = c;
        for(int i=0;i<4;i++){
            int row2=row+dirr[i], col2=col+dirc[i];
            if(row2>=0&&row2<n&&col2>=0&&col2<m
               &&vis[row2][col2]==false
               &&graph[row2][col2]!='-'&&graph[row2][col2]!='|'&&graph[row2][col2]!='+'){
                q.push({row2,col2});
                vis[row2][col2]=true;
            }
        }
    }
}
void drawLine(int x1,int y1,int x2,int y2){
    int row1=n-y1-1,col1=x1,row2=n-y2-1,col2=x2;
    if(row1>row2){
        swap(row1,row2);
    }
    if(col1>col2){
        swap(col1,col2);
    }
    if(row1==row2){
        for(int j=col1;j<=col2;j++){
            if(graph[row1][j]=='|') graph[row1][j]='+';
            else graph[row1][j]='-';
        }
    }else{
        for(int i=row1;i<=row2;i++){
            if(graph[i][col1]=='-') graph[i][col1]='+';
            else graph[i][col1]='|';
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>m>>n>>q;
    //init
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            graph[i][j] = '.';
        }
    }

    while(q--){
        int type,x1,y1,x2,y2;
        char c;
        cin>>type;
        if(type==0){
            cin>>x1>>y1>>x2>>y2;
            drawLine(x1,y1,x2,y2);
        }else{
            cin>>x1>>y1>>c;
            fillChar(x1,y1,c);
        }
    }
    //output
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<graph[i][j];
        }
        cout<<endl;
    }
}

90分，错误。注意，输出的时候，每一行没有空格，这个非常重要，0分和90分的区别。

20151204（送货）

代码1

采用DFS的方法，若当前的点时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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005

int n,m;
bool graph[MAXN][MAXN];
vector<int> path;

bool dfs(int u,int num){
    path.push_back(u);
    if(num==m){
        return true;
    }
    for(int i=1;i<=n;i++){
        if(u!=i && graph[u][i]==1){
            graph[u][i] = graph[i][u] = false;
            if(dfs(i,num+1)){
                return true;
            }else{
                graph[u][i] = graph[i][u] = true;
            }
        }
    }
    path.pop_back();
    return false;
}

int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    //init
    memset(graph,0,sizeof(graph));

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a][b] = graph[b][a] = 1;
    }
    //output
    if(dfs(1,0)){
        for(int i=0;i<path.size();i++){
            if(i==0)cout<<path[i];
            else cout<<" "<<path[i];
        }
    }else{
        cout<<"-1";
    }
}

70分，超时。这题我犯了两个错误：1. 27行的时候，忘了返回false，2. 没有计算空间复杂度，导致运行错误，0分，int graph[10000][10000]的空间大小是400M，远远超过了256M，所以应该用bool graph[10000][10000]就好了。

代码2

有一个很重要的定理：对于无向图，奇点的个数一定是偶数，如果奇点个数超过2，那么无法一笔画，如果奇点个数为2或者0，只要图是连通的就可以一笔画，不是连通的图自然无法一笔画，而且起始点必须是奇点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005

int n,m;
bool graph[MAXN][MAXN];
int du[MAXN];

bool isLiantong(){
    //init
    bool vis[MAXN];
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1] = true;

    int num = 0;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        num++;
        for(int i=1;i<=n;i++){
            if(!vis[i] && x!=i && graph[x][i]==true){
                q.push(i);
                vis[i] = true;
            }
        }
    }
    return num==n;
}

vector<int> path;
bool getPath(int u){
    path.push_back(u);
    if(path.size()-1==m){
        return true;
    }
    for(int i=1;i<=n;i++){
        if(u!=i && graph[u][i]==true){
            graph[u][i] = graph[i][u] = false;
            if(getPath(i)) return true;
            else{
                graph[u][i] = graph[i][u] = true;
            }
        }
    }
    path.pop_back();
    return false;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    //init
    memset(graph,0,sizeof(graph));
    memset(du,0,sizeof(du));
    int odd=0,even=0;

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a][b] = graph[b][a] = 1;
        du[a]++;
        du[b]++;
    }
    for(int i=1;i<=n;i++){
        if(du[i]%2==0)even++;
        else odd++;
    }
    //output
    if(odd>2 || odd==1 || (odd==2&&du[1]%2==0)){
        cout<<"-1";
    }else if(!isLiantong()){
        cout<<"-1";
    }else{
        getPath(1);
        //output
        for(int i=0;i<path.size();i++){
            if(i==0)cout<<path[i];
            else cout<<" "<<path[i];
        }
    }
}

70分，超时。

展开全文 >>

csp-201604

20160402（俄罗斯方块）

代码1

用int pane[16][11]表示面板，用int block[5][5]表示一个板块，用int row, col 表示板块在当前面板中的位置。在每次下降前，都要判断是否有板块中的方块在面板中的方块上面和到达面板最底部，若是则停止下降，否则，继续下降。停止下降后将板块补充到面板中。

我对下降到最底部的理解弄疏忽了，比如下面的块：

1
2
3
4
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0

不是说第4行到了pane的15行就算到底了，这个是错的，因为第4行为空，而是第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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int pane[16][11];
int block[5][5];
int row=1, col;
int endRow;

bool isAbove(){
    for(int i=1;i<=endRow;i++){
        for(int j=1;j<=4;j++){
            if(block[i][j]==1 && pane[row+i][col+j-1]==1){
                return true;
            }
        }
    }
    return false;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    for(int i=1;i<=15;i++){
        for(int j=1;j<=10;j++){
            cin>>pane[i][j];
        }
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin>>block[i][j];
        }
    }
    for(int i=4;i>=1;i--){
        bool spaceLine = true;
        for(int j=1;j<=4;j++){
            if(block[i][j]==1) spaceLine = false;
        }
        if(!spaceLine){
            endRow = i;
            break;
        }
    }
    cin>>col;

    while(row+endRow-1<15 && !isAbove()){
        row++;
    }
    for(int i=1;i<=endRow;i++){
        for(int j=1;j<=4;j++){
            if(block[i][j]==0) continue; //error
            pane[row+i-1][col+j-1] = block[i][j];
        }
    }
    //output
    for(int i=1;i<=15;i++){
        for(int j=1;j<=10;j++){
            if(j==1) cout<<pane[i][j];
            else cout<<" "<<pane[i][j];
        }
        cout<<endl;
    }
}

当block停止的时候，在方块补充到面板的过程中出错了，50行，注意对于0，要忽略，否则可能会把pane中原本为方块的地方变为没有方块，这肯定是错的。

20160403（路径解析）

代码1

一个路径经过正规化操作后，其指定的文件不变，但是会变成一个不包含 . 和 .. 的绝对路径，且不包含连续多个 / 符号。

若路径为空字符串，则正规化操作的结果是当前目录。（特判）

如果一个路径以 / 结尾，那么它代表的一定是一个目录，正规化操作要去掉结尾的 /

在进行路径解析的过程中，要建立一个栈，表示当前的路径。比如先输入了/d2/d3 ，栈中就为/, d2, d3 ，再输入/d2/d4/f1，栈就变为/, d2, d4, f1 了。

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 p;
vector<string> path;
string fileName=""; //表示当前目录下的文件，为空表示没有选中任何文件

string dealLine(string line){
    fileName = "";
    if(line==""){
        path.clear();
        path.push_back("/");
        return "/";
    }
    int i1=0,i2;
    while(i1<line.size()){
        i2 = line.find('/',i1);
        string s1;
        if(i2!=string::npos) s1 = line.substr(i1,i2-i1);
        else s1 = line.substr(i1);
        if(s1==""){
            path.clear();
            path.push_back("/");
        }else if(s1=="."){
        }else if(s1==".."){
            if(path.size()>1)
                path.pop_back(); //error
        }else{
            if(i2==string::npos){
                fileName = s1;
            }else{
                path.push_back(s1);
            }
        }

        if(i2==string::npos){
            i1 = line.size();
        }else{
            while(i2<line.size()&&line[i2]=='/') i2++;
            i1 = i2;
        }
    }
    string line2;
    for(int i=0;i<path.size();i++){
        line2+=path[i];
        if(i!=0 && i<path.size()-1) line2+="/";
    }
    if(fileName!=""){
        line2+="/";
        line2+=fileName;
    }
    return line2;
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>p;
    string line;
    cin>>line;
    line = dealLine(line);

    while(p--){
        cin>>line;
        line = dealLine(line);
        cout<<line<<endl;
    }
}

50分。注意29行，当path中只有根目录时，不要再pop了，这时.. 指令无效了。我只得了50分的原因是，题意说的很不清楚，因为题目中给的p个路径全都是基于第一条路径的，而不是上一条路径，我记得以前也犯过这个错误，现在又犯了。

20160404（游戏）

代码1

用array<int,2> barrels[MAXN][MAXM]来表示每个方格的障碍时间。用set<int> vis[MAXN][MAXM 表示每个每个方格在哪些时间点被访问过，一个方格不能同时被多个相同的时间点访问。采用BFS进行遍历。

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

int n,m,t;
array<int,2> barrels[MAXN][MAXM];
unordered_map<int,int> vis[MAXN][MAXM];

int dirr[4] = {1,-1,0,0};
int dirc[4] = {0,0,-1,1};
int bfs(){
    queue<array<int,3>> q;
    q.push({0,1,1});
    vis[1][1][0] = 0;
    while(!q.empty()){
        int time,r,c;
        time = q.front()[0];
        r = q.front()[1];
        c = q.front()[2];
        q.pop();
        if(r==n && c==m) return time;
        for(int i=0;i<4;i++){
            int r2=r+dirr[i], c2=c+dirc[i];
            if(r2>=1&&r2<=n&&c2>=1&&c2<=m
               &&(barrels[r2][c2][0]>time+1||barrels[r2][c2][1]<time+1)
               &&vis[r2][c2].find(time+1)==vis[r2][c2].end()){
                q.push({time+1,r2,c2});
                vis[r2][c2][time+1] = 0;
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m>>t;
    for(int i=0;i<t;i++){
        int r,c,a,b;
        cin>>r>>c>>a>>b;
        barrels[r][c] = {a,b};
    }
    cout<<bfs()<<endl;
}

我一开始超时了，原因是10行我原来写的是set<int> vis[MAXN][MAXM] ，每次查询的时间复杂度为log n级别，但是我用了一个trick，把它换成unordered_map<int,int> vis[MAXN][MAXM]，时间复杂度就变成了1，原因是unordered_map是使用hash表实现的，比set要快速。最后的最高时间为703ms。

20160405（网络连接）

代码1

展开全文 >>

csp-201609

20160901（最大波动）

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005

int n;
int prices[MAXN];

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++) cin>>prices[i];
    int diff = INT_MIN;
    for(int i=0;i<n-1;i++){
        diff = max(diff,abs(prices[i+1]-prices[i]));
    }
    cout<<diff;
}

20160902（火车购票）

代码1

用bool seats[20][6] 来描述每个座位号是否被占，seats[][0] 表示每一排被占了几个座位。对于购票请求，先看有没有一排的空座位数大于等于购票数（空座位数一定连续），否则，就从最小的座位号开始分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int seats[20][6];
int n;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    memset(seats,0,120);

    while(n--){
        int num;
        cin>>num;
        bool flag = false;
        for(int i=0;i<20;i++){
            if(5-seats[i][0]>=num){
                flag = true;
                for(int j=seats[i][0]+1;j<seats[i][0]+1+num;j++){
                    seats[i][j] = 1;
                    if(j == seats[i][0]+1) cout<<i*5+j;
                    else cout<<" "<<i*5+j;
                }
                cout<<endl;
                seats[i][0] += num;
                break;
            }
        }
        int cnt = 0;
        if(!flag){
            for(int i=0;i<20&&cnt<num;i++){
                for(int j=1;j<=5&&cnt<num;j++){
                    if(seats[i][j] == 0){
                        seats[i][j] = 1;
                        if(cnt==0) cout<<i*5+j;
                        else cout<<" "<<i*5+j;
                        cnt++;
                        seats[i][0]++;
                    }
                }
            }
            cout<<endl;
        }
    }
}

20160903（炉石传说）

代码1

设计一个结构体表示每一方的战斗力，包括英雄和随从的情况，以及是否输掉；

1
2
3
4
5
struct Player{
    int health; //30
    int attacks[8]; //[1,7]使用
    int healths[8]; //[1,7]使用
};

有Player players[2] 表示两个玩家，players[0] 表示先手玩家。int playerId=0 表示当前的玩家id，一旦遇到end命令，就将playerId变为对手的。

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

struct Player{
    int health; //30
    int attacks[8]; //[1,7]使用
    int healths[8]; //[1,7]使用
    Player(){
        health = 30;
        memset(attacks,-1,sizeof(attacks));
        memset(healths,-1,sizeof(healths));
    }
};
int n;
Player players[2];
int playerId=0;

//当playerId的arg1号随从被攻击后，检查是否需要移动
void postAttack(int playerId, int arg1){
    if(players[playerId].healths[arg1]<=0){
        int j = arg1 + 1;
        while(j<8){
            players[playerId].healths[j-1] = players[playerId].healths[j];
            players[playerId].attacks[j-1] = players[playerId].attacks[j];
            j++;
        }
        players[playerId].healths[j-1] = -1;
        players[playerId].attacks[j-1] = -1;
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //init
    players[0] = players[1] = Player();

    cin>>n;
    string op;
    int arg1,arg2,arg3;
    for(int i=0;i<n;i++){
        cin>>op;
        if(op == "summon"){
            cin>>arg1>>arg2>>arg3;
            int attack1=arg2,attack2,health1=arg3,health2;
            int j = arg1;
            do{
                attack2 = players[playerId].attacks[j];
                health2 = players[playerId].healths[j];
                players[playerId].attacks[j] = attack1;
                players[playerId].healths[j] = health1;
                attack1 = attack2;
                health1 = health2;
                j++;
            }while(j<8);
        }else if(op == "attack"){
            cin>>arg1>>arg2;
            if(arg2 != 0){
                players[playerId].healths[arg1] -= players[playerId^1].attacks[arg2];
            }
            if(arg2 == 0){
                players[playerId^1].health -= players[playerId].attacks[arg1];
                postAttack(playerId,arg1);
                if(players[playerId^1].health<=0) break;
            }else{
                players[playerId^1].healths[arg2] -= players[playerId].attacks[arg1];
                postAttack(playerId,arg1);
                postAttack(playerId^1,arg2);
            }
        }else{
            playerId = playerId^1;
        }
    }
    //output
    if(players[0].health <= 0){
        cout<<"-1"<<endl;
    }else if(players[1].health<=0){
        cout<<"1"<<endl;
    }else{
        cout<<"0"<<endl;
    }
    for(int i=0;i<2;i++){
        cout<<players[i].health<<endl;
        int num = 0;
        for(int j=1;j<=7;j++){
            if(players[i].healths[j]!=-1){
                num++;
            }
        }
        cout<<num;
        for(int j=1;j<=7;j++){
            if(players[i].healths[j]!=-1){
                cout<<" "<<players[i].healths[j];
            }
        }
        cout<<endl;
    }
}

这题我做的有很大问题，可能会出现巨大错误。原因是56行到69行的对postAttack函数放在哪个位置进行处理这个问题变得很糊涂，也犯了很多逻辑错误。正常的做法是，我要将双方的角色生命值都减去后再进行双发角色的postAttack操作（也就是对随从的位置移动操作），还要注意，当攻击对方的英雄时，也就是，arg2=0时，不要对对方进行postAttack操作，因为，我会把[1,7] 位置的数据全部移动到[0,6]位置，这是个很严重的错误。

20160904（交通规划）

代码1

这题是使用dijkstra算法，但是不同的是，每次在选出一个u点时，都要从它的所有最短路径前驱路径点a中，选出使得<a,u> 最小的那个a。因此有set<int> pre[] 来存储最短的<a,u> 的距离。然后将<a,u>累加到结果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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define INF 1e9

struct Node{
    int v,w;
};
int n,m;
vector<Node> graph[MAXN];
long long ans = 0;

int pre[MAXN];
int vis[MAXN];
long long dist[MAXN];
void Dijkstra(){
    //init
    memset(vis,0,sizeof(vis));
    for(int i=0;i<MAXN;i++){
        dist[i]=1e18;
        pre[i] = INF;
    }
    dist[1] = 0;
    pre[1] = 0;

    for(int i=0;i<n;i++){
        int u=-1;
        long long minDist = 1e18;
        for(int j=1;j<=n;j++){
            //cout<<dist[j]<<endl;//////
            if(!vis[j] && dist[j]<minDist){
                minDist = dist[j];
                u = j;
            }
        }
        if(u==-1) break;
        vis[u] = 1;
        ans += pre[u];
        for(int j=0;j<graph[u].size();j++){
            int v=graph[u][j].v, w=graph[u][j].w;
            if(!vis[v]){
                if(dist[u]+w < dist[v]){
                    dist[v] = dist[u]+w; //error: dist[j]
                    pre[v] = w;
                }else if(dist[u]+w == dist[v]){
                    pre[v] = min(pre[v],w);
                }
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    Dijkstra();
    cout<<ans;
}

最近总是犯小错误，像45行的错误：把v错当成j，真的太低级了；第5行，我想写10005的，结果写成了1005，报了运行错误。

展开全文 >>

csp-201612

20161201（中间数）

代码1

现将数字从小到大排序得到values[]，然后用vector<int> minNum，vector<int> maxNum 来表示每个数的比它小的数目和比它大的数目。若知道了minNum[i]，那么minNum[i+1]是下面这么算的。

1
2
3
4
5
6
7
8
if(values[i] == values[i+1]){
    minNum[i+1] = minNum[i];
}else{
    int a = 0;
    for(int j=i;j>=0&&values[j]==values[i];j--)
        a++;
    minNum[i+1] = minNum[i] + a;
}

对于maxNum的计算也是类似。

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

int n;
vector<int> values;
vector<int> minNum,maxNum;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    values.resize(n);
    minNum.resize(n);
    maxNum.resize(n);
    for(int i=0;i<n;i++) cin>>values[i];

    sort(values.begin(),values.end());
    for(int i=0;i<n;i++){
        if(i==0){
            minNum[i] = 0;
            int a = 0;
            for(int j=i;j<n&&values[j]==values[i];j++){
                a++;
            }
            maxNum[i] = n-a;
        }else{
            if(values[i-1] == values[i]){
                minNum[i] = minNum[i-1];
                maxNum[i] = maxNum[i-1];
            }else{
                int a = 0;
                for(int j=i-1;j>=0&&values[j]==values[i-1];j--)
                    a++;
                minNum[i] = minNum[i-1] + a;
                a = 0;
                for(int j=i;j<n&&values[j]==values[i];j++){
                    a++;
                }
                maxNum[i] = maxNum[i-1]-a;
            }
        }
    }
    //output
    bool flag = false;
    for(int i=0;i<n;i++){
        if(minNum[i]==maxNum[i]){
            cout<<values[i]<<endl;
            flag = true;
            break;
        }
    }
    if(!flag) cout<<"-1"<<endl;
}

20161202（工资计算）

代码1

这题把不同税前工资分段的税后工资分段算出来就可以了，然后if else

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);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int lowerBound[8] = {0,3500,5000,8000,12500,38500,58500,83500};
int rate[8] = {-1,97,90,80,75,70,65,55};
vector<array<int,2>> scopes(8); //表示各个税后工资段
int T;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>T;

    for(int i=0;i<8;i++){
        if(i==0){
            scopes[i][0] = 0;
            scopes[i][1] = 3500;
        }else if(i<7){
            scopes[i][0] = scopes[i-1][1];
            scopes[i][1] = scopes[i][0] + rate[i]*(lowerBound[i+1]-lowerBound[i])/100;
        }else{
            scopes[i][0] = scopes[i-1][1];
            scopes[i][1] = -1;
        }
    }
    int S = 0;
    for(int i=0;i<8;i++){
        if(scopes[i][1]==-1 || T<=scopes[i][1]){
            if(i==0){
                S = T;
            }else{
                S = (T-scopes[i][0])*100/rate[i]+lowerBound[i];
            }
            break;
        }
    }
    //output
    cout<<S<<endl;
}

20161203（权限查询）

代码1

当记录角色有哪些权限时，使用unordered_map<string,unoredered_map<string,int>> roleToAuth，我们用unordered_map<string,set<string>> userToRole 来表示每个用户有哪些角色。

当查询的时候，我先查是否有这个用户，然后再查询是否有这个权限。

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;

unordered_map<string,unordered_map<string,int>> roleToAuth;
unordered_map<string,set<string>> userToRole;
int p,r,u,q;

int main(){
    //freopen("D://input.txt","r",stdin);
    string auth;
    cin>>p;
    while(p--) cin>>auth;
    cin>>r;
    for(int i=0;i<r;i++){
        string role;
        int num;
        cin>>role>>num;
        while(num--){
            cin>>auth;
            int k = auth.find(':');
            if(k == string::npos){
                roleToAuth[role][auth] = -1;
            }else{
                int level = stoi(auth.substr(k+1));
                string authName = auth.substr(0,k);
                if(roleToAuth[role].find(authName) != roleToAuth[role].end()){
                    roleToAuth[role][authName] = max(roleToAuth[role][authName],level);
                }else{
                    roleToAuth[role][authName] = level;
                }
            }
        }
    }
    cin>>u;
    for(int i=0;i<u;i++){
        string user,role;
        int num;
        cin>>user>>num;
        while(num--){
            cin>>role;
            userToRole[user].insert(role);
        }
    }
    cin>>q;
    while(q--){
        string user,auth,authName;
        cin>>user>>auth; //error
        int level;
        int k = auth.find(':');
        if(k==string::npos){
            authName = auth;
            level = -1;
        }else{
            authName = auth.substr(0,k);
            level = stoi(auth.substr(k+1));
        }

        if(userToRole.find(user)==userToRole.end()){ //error: authName
            cout<<"false"<<endl;
        }else{
            set<string>& st = userToRole[user];
            set<string>::iterator it = st.begin(); //这个用户的所有角色
            bool flag = false; //是否查询到指定的权限
            int level2 = -1; //查询到的指定权限的等级
            for(;it!=st.end();it++){
                string role = (*it);
                unordered_map<string,unordered_map<string,int>>::iterator it2 = roleToAuth.find(role);
                if(it2!=roleToAuth.end()){
                    unordered_map<string,int>::iterator it3 = (*it2).second.find(authName);
                    if(it3 != (*it2).second.end()){
                        flag = true;
                        level2 = max(level2,(*it3).second);
                    }
                }
            }
            if(!flag){
                cout<<"false"<<endl;
            }else{
                if(level2!=-1 && level==-1){
                    cout<<level2<<endl;
                }else if(level2!=-1 && level!=-1){
                    if(level<=level2){
                        cout<<"true"<<endl;
                    }else{
                        cout<<"false"<<endl;
                    }
                }else if(level2==-1&&level==-1){
                    cout<<"true"<<endl;
                }else{
                    cout<<"false"<<endl;
                }
            }
        }
    }
}

注意28行，因为在输入每个角色的很多权限时，可能出现auth1:1 和 auth1:2这两个输入，这是要比较1和2中较大者作为auth1的等级，一开始没有考虑这点时90分，考虑了就100分。还有60行，我被user，auth，authName给弄晕了，本来应该根据user来查询的，我写成根据authName来查询，而且我还忘了输入cin了。

20161204（压缩编码）

代码1

假设输入有n个点，那么考虑范围就是[0, n*2-2]，下面是递推公式。

其中W(i,j) 表示$a_i$ 到 $a_j$ 范围内的频率相加之和。

所以可以利用动态规划的方法，先算使得j-i=0的，再算j-i=3的，一直到j-i=n*2-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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005

int n;
int C[2*MAXN-1][2*MAXN-1];
int W[2*MAXN-1][2*MAXN-1];
int F[2*MAXN-1];

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

    for(int i=0;i<n;i++){
        cin>>F[2*i];
    }
    for(int len=0;len<=n*2-2;len=len+2){
        if(len==0){
            for(int i=0;i+len<2*n-1;i=i+2){
                int j = i+len;
                W[i][j] = F[i];
                C[i][j] = 0;
            }
        }else{
            for(int i=0;i+len<2*n-1;i=i+2){
                int j = i+len;
                W[i][j] = W[i][i] + W[i+2][j];
                for(int k=i+1;k<j;k=k+2){
                    int temp = C[i][k-1]+C[k+1][j] + W[i][j];
                    if(k==i+1) C[i][j] = temp;
                    else C[i][j] = min(temp,C[i][j]);
                }
            }
        }
    }
    //output
    cout<<C[0][2*n-2]<<endl;
}

这道题告诉我一个很重要的事实：能不用vector就不用vector，直接中静态数组，这样就是20分的区别，因为这题用vector就恰好超时，丢掉了那20分。

展开全文 >>

csp-201703

20170301（分蛋糕）

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

int n,k;
vector<int> weights;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>k;
    weights.resize(n);
    for(int i=0;i<n;i++) cin>>weights[i];
    int ans = 0,i=0;
    while(i<n){
        int w = 0;
        while(w<k && i<n){
            w+=weights[i];
            i++;
        }
        ans++;
    }
    cout<<ans;
}

20170302（学生排队）

代码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 n,m;
struct Node{
    int id;
    struct Node *pre, *next;
    Node(int x){
        id = x;
        pre = next = nullptr;
    }
};
Node* head;

void eraseNode(Node* node){
    node->pre->next = node->next;
    if(node->next) //error
        node->next->pre = node->pre;
    delete node;
}
//node1后面加入x节点
void addNode(Node* node1, int x){
    Node* node = new Node(x);
    node->pre = node1;
    node->next = node1->next;
    node1->next = node;
    if(node->next)
        node->next->pre = node;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    Node* node;
    for(int i=0;i<=n;i++){
        if(i==0){
            head = new Node(i);
            node = head;
        }else{
            node->next = new Node(i);
            node->next->pre = node;
            node = node->next;
        }
    }
    int p,q;
    while(m--){
        cin>>p>>q;
        Node *node1, *node2;
        node1 = head;
        while(node1->id != p) node1 = node1->next;
        node2 = node1;
        if(q>0){
            while(q-- && node2->next) node2 = node2->next;
        }else{
            while(q++ && node2->pre) node2 = node2->pre;
            node2 = node2->pre;
        }
        eraseNode(node1);
        addNode(node2,p);
    }
    //output
    node = head->next;
    while(node){
        if(node == head->next) cout<<node->id;
        else cout<<" "<<node->id;
        node = node->next;
    }
}

20170303（Markdown）

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

vector<string> markdown;

bool isSpaceLine(const string& line){
    for(int i=0;i<line.size();i++){
        if(line[i]!=' '){
            return false;
        }
    }
    return true;
}

void dealQiangdiao(string& line, int beg, int ed){
    cout<<"<em>";
    cout<<line.substr(beg+1,ed-beg-1);
    cout<<"</em>";
}
void dealLink(string& line, int beg, int ed){
    int i1=beg+1,i2;
    for(;line[i1]!=']';i1++){};
    i2 = i1+1;
    cout<<"<a href=\""<<line.substr(i2+1,ed-i2-1)<<"\">"<<line.substr(beg+1,i1-beg-1)<<"</a>";
}
void dealLine(string& line, int beg){
    int i1=beg; //error
    for(;i1<line.size();){
        if(line[i1]=='_'){
            int i2 = i1+1;
            int i3 = -1, i4;
            for(;line[i2]!='_';i2++){
                if(line[i2] == '[')
                    i3 = i2;
                else if(line[i2] == ')')
                    i4 = i2;
            }
            if(i3==-1){
                dealQiangdiao(line, i1, i2);
            }else{
                cout<<"<em>";
                cout<<line.substr(i1+1,i3-i1-1);
                dealLink(line,i3,i4);
                cout<<line.substr(i4+1,i2-i4-1);
                cout<<"</em>";
            }
            i1 = i2+1;
        }else if(line[i1]=='['){
            int i2 = i1+1;
            int i3 = -1, i4;
            for(;line[i2]!=')';i2++){
                if(line[i2] == '_' && i3==-1)
                    i3 = i2;
                else if(line[i2] == '_')
                    i4 = i2;
            }
            if(i3==-1){
                dealLink(line,i1,i2);
            }else{
                int i5 = i1+1,i6;
                for(;line[i5]!=']';i5++){};
                i6 = i5+1;
                if(i3>i1 && i3<i5){
                    cout<<"<a href=\""<<line.substr(i6+1,i2-i6-1)<<"\">";
                    cout<<line.substr(i1+1,i3-i1-1);
                    dealQiangdiao(line,i3,i4);
                    cout<<line.substr(i4+1,i5-i4-1)<<"</a>";
                }else{
                    cout<<"<a href=\""<<line.substr(i6+1,i3-i6-1);
                    dealQiangdiao(line,i3,i4);
                    cout<<line.substr(i4+1,i2-i4-1);
                    cout<<"\">"<<line.substr(i1+1,i5-i1-1)<<"</a>";
                }
            }
            i1 = i2+1;
        }else{
            cout<<line[i1++];
        }
    }
}
void dealBlock(int beg, int ed){
    int sharpNum = 0;
    int i;
    for(i=0;i<markdown[beg].size();i++){
        if(markdown[beg][i] == '#'){
            sharpNum++;
        }else{
            break;
        }
    }
    if(sharpNum>0 && markdown[beg][i]==' ' && beg==ed){ //是标题
        cout<<"<h"<<sharpNum<<">";
        for(;markdown[beg][i]==' ';i++){};
        dealLine(markdown[beg],i);
        cout<<"</h"<<sharpNum<<">"<<endl;
    }else{
        i = 0;
        if(markdown[beg].substr(0,2) == "* "){ //是无序列表
            cout<<"<ul>"<<endl;
            for(int lineNum=beg;lineNum<=ed;lineNum++){
                cout<<"<li>";
                i = 2;
                for(;markdown[lineNum][i]==' ';i++){};
                dealLine(markdown[lineNum],i);
                cout<<"</li>"<<endl;
            }
            cout<<"</ul>"<<endl; //error: </ul
        }else{ //是普通段落
            cout<<"<p>";
            for(int lineNum=beg;lineNum<=ed;lineNum++){
                dealLine(markdown[lineNum],0);
                if(lineNum != ed)
                    cout<<endl;
            }
            cout<<"</p>"<<endl;
        }
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    string line;
    while(getline(cin,line)){
        markdown.push_back(line);
    }
    int i1=0,i2;
    while(i1<markdown.size() && isSpaceLine(markdown[i1])) i1++;
    while(i1<markdown.size()){ //error:line.size()
        i2 = i1;
        while(i2<markdown.size() && !isSpaceLine(markdown[i2])) i2++;
        dealBlock(i1,i2-1);
        i1 = i2;
        while(i1<markdown.size() && isSpaceLine(markdown[i1])) i1++;
    }
}

29行i1赋值错误；130行，markdown写成line了。

展开全文 >>

csp-201709

20170901（打酱油）

代码1

这题运用贪心的方法，N元钱能买多少个5瓶就买多少个，剩下能买多少个3瓶就买多少个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int N;
int ans = 0;

int main(){
    cin>>N;
    int a = N/50;
    int b = N - a*50;
    ans += a*7;
    int c = b/30;
    int d = b - c*30;
    ans += c*4;
    ans += d/10;
    cout<<ans<<endl;
}

20170902（公共钥匙盒）

代码1

设计一个数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
struct Trans{
    int time,id,type;
    bool operator<(const Trans& t2){
        if(time != t2.time){
			return time<t2.time;
        }else if(type != t2.type){
            return type>t2.type;
        }else{
            return id<t2.id;
        }
    }
}

表示在什么时间做什么事，第一个表示取/还的时间，第二个表示钥匙编号，第三个表示0是取，1是还。根据输入将所有的trans保存在vector<Trans> transes 中，然后排序。vector<int> keys 保存每个位置的钥匙编号，-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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Trans{
    int time,id,type;
    Trans(int a,int b,int c){
        time = a;
        id = b;
        type = c;
    }
    bool operator<(const Trans& t2)const{
        if(time != t2.time){
            return time<t2.time;
        }else if(type != t2.type){
            return type>t2.type;
        }else{
            return id<t2.id;
        }
    }
};
int N,K;
vector<int> keys;
vector<Trans> transes;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>N>>K;
    keys.resize(N);
    for(int i=0;i<N;i++) keys[i] = i+1;
    for(int i=0;i<K;i++){
        int id,time,dur;
        cin>>id>>time>>dur;
        transes.push_back(Trans{time,id,0});
        transes.push_back(Trans{time+dur,id,1});
    }
    sort(transes.begin(),transes.end());

    for(int i=0;i<transes.size();i++){
        Trans& t = transes[i];
        if(t.type == 0){
            for(int j=0;j<N;j++){
                if(keys[j]==t.id){
                    keys[j] = -1;
                }
            }
        }else{
            for(int j=0;j<N;j++){
                if(keys[j]==-1){
                    keys[j] = t.id;
                    break;
                }
            }
        }
    }

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

20170903（JSON查询）

代码1

将所有的输入的行都保存在一个没有换行符的字符串中string input。将查询分解为vector<string> query ，第0个表示0级查询的字符串，第1个表示1级查询的字符串。构建一个函数pair<int,string> Query(int beg, vector<string>& query, int k) 表示从beg位置的左括号开始查找当前层的query[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
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
string input;

//从x开始找到下一个引号的位置，若没有则返回-1
int findNextYinhao(int x){
    int i;
    for(i=x;i<input.size()&&input[i]!='"';){
        if(input[i]=='\\'){
            i = i+2;
        }else{
            i++;
        }
    }
    return (i<input.size()?i:-1);
}
//x可以是右引号后面的位置。看对应的值是对象还是字符串，若是对象，则first=false
pair<bool,int> findValue(int x){
    int i;
    for(i=x;input[i]!='{'&&input[i]!='"';i++){}
    if(input[i]=='{') return {false,i};
    else return {true,i};
}
//将s中的转义字符去掉
void dealString(string& s){
    string s2;
    int i=0,j;
    while(i<s.size()){
        j = s.find('\\',i);
        if(j != string::npos){
            s2 += s.substr(i,j-i);
            s2 += s.substr(j+1,1);
            i = j+2;
        }else{
            s2 += s.substr(i);
            i = s.size();
        }
    }
    s = s2; //error
}
//first=0表示找到了字符串，first=1表示对象，first=2表示不存在
pair<int,string> Query(int beg, vector<string>& query, int k){
    int i1=findNextYinhao(beg),i2;
    while(i1!=-1){ //每次循环开始，i1总是指向键的第一个引号
        i2=findNextYinhao(i1+1);
        string s1 = input.substr(i1+1,i2-i1-1);
        dealString(s1); //error
        pair<bool,int> valueType = findValue(i2+1); //表明后面的值是字符串还是对象
        if(s1==query[k]){
            if(k==query.size()-1){
                if(valueType.first==false){ //object
                    return {1,""};
                }else{ //string
                    int j1 = valueType.second;
                    int j2 = findNextYinhao(j1+1);
                    string value = input.substr(j1+1,j2-j1-1);
                    dealString(value);
                    return {0,value};
                }
            }else{
                if(valueType.first==false){ //递归
                    return Query(valueType.second,query,k+1);
                }else{
                    return {2,""};
                }
            }
        }else{
            if(valueType.first == false){ //后面是对象
                i1 = valueType.second+1;
                int layer=1;
                while(layer>0){
                    if(input[i1]=='{'){
                        layer++;
                    }else if(input[i1]=='}'){
                        layer--;
                    }
                    i1++;
                }
                i1 = findNextYinhao(i1);
            }else{ //后面时字符串
                i1 = findNextYinhao(valueType.second+1);
                i1 = findNextYinhao(i1+1);
            }
        }
    }
    return {2,""};
}

void splitQuery(string line, vector<string>& query){
    int i1 = 0, i2;
    while(i1<line.size()){
        i2 = line.find('.',i1);
        query.push_back(line.substr(i1,i2-i1));
        i1 = (i2==string::npos?line.size():i2+1);
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    cin.get();
    for(int i=0;i<n;i++){
        string line;
        getline(cin,line);
        input += line;
    }

    while(m--){
        string line;
        cin>>line;
        vector<string> query;
        splitQuery(line,query);
        pair<int,string> ans = Query(0,query,0);
        if(ans.first == 0){
            cout<<"STRING "<<ans.second<<endl;
        }else if(ans.first == 1){
            cout<<"OBJECT"<<endl;
        }else{
            cout<<"NOTEXIST"<<endl;
        }
    }
}

43行，51行，犯了点粗心错误。

20070904（通信网络）

代码1

对每个点a运行BFS算法，就知道a和谁可以互相知道。vector<set<int>> know 表示哪个点知道哪个点，know[1]里面的点就是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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<bool>> graph;
vector<set<int>> know;

void bfs(int x){
    know[x].insert(x);
    queue<int> q;
    vector<bool> vis(n+1);
    for(int i=0;i<n+1;i++) vis[i] = false;
    q.push(x);
    vis[x] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int j=1;j<=n;j++){
            if(j!=u && graph[u][j] && !vis[j]){
                know[x].insert(j);
                know[j].insert(x);
                q.push(j);
                vis[j] = true;
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    know.resize(n+1);
    graph.resize(n+1);
    for(int i=0;i<n+1;i++){
        graph[i].resize(n+1);
        for(int j=0;j<n+1;j++){
            graph[i][j] = false;
        }
    }
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a][b] = true;
    }

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

    //output
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(know[i].size()==n){
            ans++;
        }
    }
    cout<<ans;
}

60分。运行超时。

代码2

其实我只要将vector<set<int>> know 换成int know[][] 就好了。从k1开始遍历，所有能遍历到的k2，都有know[k1][k2]=1和know[k2][k1]=1。还有，要把邻接矩阵改为邻接表，这很重要，因为可以减少遍历每个点的邻接点的时间，以前是要遍历n次，但是现在只用遍历邻接点数量次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> graph;
int know[1005][1005];

void bfs(int x){
    know[x][x] = 1;
    know[x][0]++;
    queue<int> q;
    vector<bool> vis(n+1,false);
    //for(int i=0;i<n+1;i++) vis[i] = false;
    q.push(x);
    vis[x] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int j=0;j<graph[u].size();j++){
            int v = graph[u][j];
            if(v!=u && !vis[v]){
                if(know[x][v]==0){
                    know[x][v] = 1;
                    know[x][0]++;
                }
                if(know[v][x]==0){
                    know[v][x] = 1;
                    know[v][0]++;
                }
                q.push(v);
                vis[v] = true;
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    graph.resize(n+1);
    memset(know,0,sizeof(know));

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
    }

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

    //output
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(know[i][0]==n){
            ans++;
        }
    }
    cout<<ans;
}

展开全文 >>

csp-201712

20171201（最小差值）

代码1

排序，找出每相邻两个数差值的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> num;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    num.resize(n);
    for(int i=0;i<n;i++) cin>>num[i];
    sort(num.begin(),num.end());
    int ans = INT_MAX;
    for(int i=0;i<n-1;i++){
        ans = min(ans,num[i+1]-num[i]);
    }
    cout<<ans;
}

20171202（游戏）

代码1

使用vector<bool> isOut 来表示各个小朋友是否出局, isOut[0]=true表示0+1=1号小朋友出局。int cnt=1 记录当前应该报第什么数，int outNum=0记录出局了多少个人。bool canOut(int x) 判断数字x是否可以出局。

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

int n,k;
int cnt=1, outNum=0;
vector<bool> isOut;

bool canOut(int x){
    if(x%k==0){
        return true;
    }else if(x-(x/10)*10==k){
        return true;
    }else{
        return false;
    }
}

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

    int i=0;
    while(outNum != n-1){
        if(isOut[i]){
            i = (i+1)%n;
            continue;
        }
        if(canOut(cnt)){
            isOut[i]=true;
            outNum++;
        }
        cnt++;
        i = (i+1)%n;
    }
    //output
    for(int i=0;i<n;i++){
        if(isOut[i]==false){
            cout<<i+1;
            break;
        }
    }
}

20171203（Crontab）

代码1

设计一个数据结构来表示每个任务的可满足的运行时间段和系统时间

1
2
3
4
5
6
7
8
9
10
11
12
13
struct RunnableTime{
    bool minutes[60];
    bool hours[24];
    bool days[32]; //[1,31]
    bool months[13]; //[1,12]
    bool weekdays[7]; //表示星期几
}
struct Time{
    int year, month, day, hour, minute;
    bool operator<(const Time& t2)const{
        
    }
}

写一个函数void incTime(Time& t) 来递增系统时间。bool satisfy(const RunnableTime& rt, const Time& t) 来看rt是否在满足t时间，这个函数可能要用到星期转换的函数int getWeekDay(const Time& t) 。

对于输入，要处理, 和- 的情况。可以写一个函数pair<RunnableTime,string> dealInput(string input) 来得到时间段和任务名的对应关系，最后存储到vector<pair<RunnableTime,string>> rtToDuty 中。

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct RunnableTime{
    bool minutes[60];
    bool hours[24];
    bool days[32]; //[1,31]
    bool months[13]; //[1,12]
    bool weekdays[7]; //表示星期几
    RunnableTime(){
        memset(minutes,0,sizeof(minutes));
        memset(hours,0,sizeof(hours));
        memset(days,0,sizeof(days));
        memset(months,0,sizeof(months));
        memset(weekdays,0,sizeof(weekdays));
    }
};
struct Time{
    int year, month, day, hour, minute;
    bool operator<(const Time& t2)const{
        if(year!=t2.year){
            return year<t2.year;
        }else if(month != t2.month){
            return month<t2.month;
        }else if(day != t2.day){
            return day<t2.day;
        }else if(hour != t2.hour){
            return hour<t2.hour;
        }else{
            return minute<t2.minute;
        }
    }
};

int n;
Time beg,ed;
vector<pair<RunnableTime,string>> rtToDuty;
int daysOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
map<string,int> monthToNum = {{"jan",1},{"feb",2},{"mar",3},{"apr",4},{"may",5},{"jun",6},{"jul",7},{"aug",8},{"sep",9},{"oct",10},{"nov",11},{"dec",12}};
map<string,int> weekdayToNum = {{"sun",0},{"mon",1},{"tue",2},{"wed",3},{"thu",4},{"fri",5},{"sat",6}};

bool isRunYear(int year){
    if(year%4==0&&year%100!=0 || year%400==0){
        return true;
    }else{
        return false;
    }
}

void incTime(Time& t){
    t.minute++;
    if(t.minute!=60){
        return;
    }
    t.minute=0;
    t.hour++;
    if(t.hour!=24){
        return;
    }
    t.hour=0;
    t.day++;
    if(t.month!=2&&t.day!=daysOfMonth[t.month]+1 || t.month==2&&(isRunYear(t.year)&&t.day!=30 || !isRunYear(t.year)&&t.day!=29)){
        return;
    }
    t.day = 1;
    t.month++;
    if(t.month != 13){
        return;
    }
    t.month=1;
    t.year++;
}
void tolower2(string& s){
    for(int i=0;i<s.size();i++){
        s[i] = tolower(s[i]);
    }
}
pair<RunnableTime,string> dealInput(string input){
    pair<RunnableTime,string> prs;
    prs.first = RunnableTime();
    string s;
    int i1=0,i2;
    int cnt = 0;
    while(i1!=input.size()){
        i2 = input.find(' ',i1);
        s = input.substr(i1,i2-i1);
        if(cnt==5){
            prs.second = s;
            break;
        }
        if(s=="*"){
            if(cnt==0){
                for(int i=0;i<60;i++) prs.first.minutes[i]=true;
            }else if(cnt==1){
                for(int i=0;i<24;i++) prs.first.hours[i]=true;
            }else if(cnt==2){
                for(int i=0;i<32;i++) prs.first.days[i]=true;
            }else if(cnt==3){
                for(int i=0;i<13;i++) prs.first.months[i]=true;
            }else{
                for(int i=0;i<7;i++) prs.first.weekdays[i]=true;
            }
        }else{
            int j1=0,j2=0;
            for(;j1<s.size();){
                if(j2<s.size() && s[j2]==',' || j2>=s.size()){
                    //prs.first.minute[stoi(s.substr(j1,j2-j1))] = true;
                    string s1 = s.substr(j1,j2-j1);
                    int num1;
                    if(isdigit(s1[0])){
                        num1 = stoi(s1);
                    }else{
                        tolower2(s1);
                        num1 = (cnt==3?monthToNum[s1]:weekdayToNum[s1]);
                    }
                    if(cnt==0){
                        prs.first.minutes[num1]=true;
                    }else if(cnt==1){
                        prs.first.hours[num1]=true;
                    }else if(cnt==2){
                        prs.first.days[num1]=true;
                    }else if(cnt==3){
                        prs.first.months[num1]=true;
                    }else{
                        prs.first.weekdays[num1]=true;
                    }
                    if(j2<s.size()){
                        j1 = j2+1;
                        j2++;
                    }else{
                        j1 = j2;
                    }
                }else if(j2<s.size() && s[j2]=='-'){
                    int j3 = j2;
                    for(j2=j2+1;j2!=s.size()&&s[j2]!=',';j2++){};
                    string s1=s.substr(j1,j3-j1),s2=s.substr(j3+1,j2-j3-1);
                    int num1,num2;
                    if(isdigit(s1[0])){
                        num1=stoi(s1);
                    }else{
                        tolower2(s1);
                        num1 = (cnt==3?monthToNum[s1]:weekdayToNum[s1]);
                    }
                    if(isdigit(s2[0])){
                        num2=stoi(s2);
                    }else{
                        tolower2(s2);
                        num2 = (cnt==3?monthToNum[s2]:weekdayToNum[s2]);
                    }
                    if(cnt==0){
                        for(int i=num1;i<=num2;i++) prs.first.minutes[i]=true;
                    }else if(cnt==1){
                        for(int i=num1;i<=num2;i++) prs.first.hours[i]=true;
                    }else if(cnt==2){
                        for(int i=num1;i<=num2;i++) prs.first.days[i]=true;
                    }else if(cnt==3){
                        for(int i=num1;i<=num2;i++) prs.first.months[i]=true;
                    }else{
                        for(int i=num1;i<=num2;i++) prs.first.weekdays[i]=true;
                    }
                    if(j2!=s.size()){
                        j1 = j2+1;
                        j2++;
                    }else{
                        j1 = j2;
                    }
                }else if(j2<s.size()){
                    j2++;
                }
            }
        }
        cnt++;
        i1 = i2+1;
    }
    return prs;
}
int getWeekDay(const Time& t){
    int weekday=4;
    for(int year=1970;year<t.year;year++){
        if(isRunYear(year)){
            weekday = (weekday+366)%7;
        }else{
            weekday = (weekday+365)%7;
        }
    }
    for(int month=1;month<t.month;month++){
        if(month!=2){
            weekday = (weekday+daysOfMonth[month])%7;
        }else{
            if(isRunYear(t.year)){
                weekday = (weekday+29)%7;
            }else{
                weekday = (weekday+28)%7;
            }
        }
    }
    weekday = (weekday+t.day-1)%7;
    return weekday;
}
bool satisfy(const RunnableTime& rt, const Time& t){
    if(!rt.months[t.month]){
        return false;
    }
    if(!rt.days[t.day]){
        return false;
    }
    if(!rt.hours[t.hour]){
        return false;
    }
    if(!rt.minutes[t.minute]){
        return false;
    }
    int weekday = getWeekDay(t);
    if(!rt.weekdays[weekday]){
        return false;
    }
    return true;
}
void printTime(const Time& t){
    cout<<setw(4)<<setfill('0')<<right<<t.year;
    cout<<setw(2)<<setfill('0')<<right<<t.month;
    cout<<setw(2)<<setfill('0')<<right<<t.day;
    cout<<setw(2)<<setfill('0')<<right<<t.hour;
    cout<<setw(2)<<setfill('0')<<right<<t.minute;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    rtToDuty.resize(n);
    for(int i=0;i<2;i++){
        string str;
        cin>>str;
        Time t;
        t.year = stoi(str.substr(0,4));
        t.month = stoi(str.substr(4,2));
        t.day = stoi(str.substr(6,2));
        t.hour = stoi(str.substr(8,2));
        t.minute = stoi(str.substr(10,2));
        if(i==0) beg = t;
        else ed = t;
    }
    cin.get();
    for(int i=0;i<n;i++){
        string input;
        getline(cin,input);
        rtToDuty[i] = dealInput(input);
    }

    for(Time t=beg;t<ed;incTime(t)){
        vector<string> duties;
        for(int j=0;j<n;j++){
            if(satisfy(rtToDuty[j].first,t)){
                duties.push_back(rtToDuty[j].second);
            }
        }
        for(int j=0;j<duties.size();j++){
            printTime(t);
            cout<<" "<<duties[j]<<endl;
        }
    }
}

95分。运行超时。2个小时做完。

代码2

我可以直接用Long long 存储系统时间，减少了转换为结构体的工作；代码1是对所有时间，计算符合该时间的crontab，时间复杂度是O(时间长度*n)，代码2根据每个crontab计算符合要求的时间，过程是遍历每个可能的年，每个可能的月，每个可能的日，每个可能的时，每个可能的分，看最后的时间是否在[beg, ed)内并满足星期的要求，若是，则在该时间对应的crontab set集合中插入该crontab，这个方案更好。

核心代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void computeCrontab(int c){//计算符合该crontab的时间，以及建立时间点到命令的映射ans
    for(int y=s/year; y<=t/year; y++){ //遍历所有年份
        for(int m : commandTime[3]){ //遍历crontab中符合要求的月份
            for(int d : commandTime[2]){ //遍历crontab中的所有天
                if(d > daysOfMonth(y,m))
                    continue;
                if(find(commandTime[4].begin(),commandTime[4].end(),
                        determineWeek(y,m,d)) != commandTime[4].end()){
                    //说明这一天的星期数是符合crontab要求的
                    for(int h : commandTime[1]){
                        for(int minute : commandTime[0]){
                            //格式化时间
                            long long temp = (long long)y*year + m*month + d*day + h*hour + minute;
                            if(temp>=s && temp<t){
                                ans[temp].push_back(c);
                            }
                        }
                    }
                }
            }

        }
    }
}

20171204（行车路线）

代码1

这题运用Dijkstra算法，但是有一点不同时，每次计算距离，不是直接累加，而是通过完整的路径来计算，所以核心是要记录路径。vector<int> pre 来保存每个点的最短路径的前驱结点，有了这个，就有了路径。

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

int n,m;
vector<vector<array<int,2>>> graph; //第一个数字表示道路类型(-1表示没有连接),第二个数字表示距离

long long getPathCost(vector<int>& path){
    long long ans = 0;
    int i = 0;
    while(i<path.size()-1){
        int a=path[i],b=path[i+1];
        if(graph[a][b][0]==0){
            ans += graph[a][b][1];
            i++;
        }else{
            int j=i+1;
            long long a = graph[path[i]][path[j]][1];
            while(j<path.size()-1 && graph[path[j]][path[j+1]][0]==1){
                a += graph[path[j]][path[j+1]][1];
                j++;
            }
            ans += a*a;
            i = j;
        }
    }
    return ans;
}

vector<int> pre;
vector<long long> dist;
vector<bool> vis;
void Dijkstra(){
    //init
    for(int i=0;i<=n;i++) pre[i]=0;
    for(int i=0;i<=n;i++) dist[i]=INF;
    for(int i=0;i<=n;i++) vis[i]=false;

    int u = 1;
    dist[1] = 0;
    for(int i=0;i<n;i++){
        u = -1;
        long long minDist = INF;
        for(int j=1;j<=n;j++){
            if(!vis[j] && dist[j]<minDist){
                u = j;
                minDist = dist[j];
            }
        }
        if(u == -1) break;
        vis[u] = true;
        for(int j=1;j<=n;j++){
            if(u!=j && graph[u][j][0]!=-1 && !vis[j]){
                vector<int> path;
                path.push_back(j);
                int a = u;
                while(a!=0){
                    path.push_back(a);
                    a = pre[a];
                }
                reverse(path.begin(),path.end());
                long long pathCost = getPathCost(path);
                if(pathCost < dist[j]){
                    dist[j] = pathCost;
                    pre[j] = u;
                }
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    graph.resize(n+1);
    for(int i=0;i<=n;i++){
        graph[i].resize(n+1);
        for(int j=0;j<=n;j++){
            graph[i][j] = {-1,0};
        }
    }
    pre.resize(n+1);
    dist.resize(n+1);
    vis.resize(n+1);

    //input
    int type,a,b,c;
    for(int i=0;i<m;i++){
        cin>>type>>a>>b>>c;
        graph[a][b] = {type,c};
        graph[b][a] = {type,c};
    }

    Dijkstra();
    cout<<dist[n]<<endl;
}

90分。错误。

展开全文 >>

csp-201803

20180301（跳一跳）

代码1

用vector<int> scores 表示每一次的得分，用sumScore记录总得分。

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

vector<int> scores;
int sumScore = 0;

int main(){
    //freopen("D://input.txt","r",stdin);
    int num, cnt=0;
    do{
        cin>>num;
        if(num==1){
            scores.push_back(1);
            sumScore+=1;
            cnt++;
        }else if(num==2){
            if(cnt==0 || scores.back()==1){
                scores.push_back(2);
                sumScore+=2;
            }else{
                int temp = scores.back()+2;
                scores.push_back(temp);
                sumScore+=temp;
            }
            cnt++;
        }
    }while(num!=0);
    //output
    cout<<sumScore<<endl;
}

20180302（碰撞的小球）

问题描述

　　数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒。
　　当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小。
　　当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。
　　现在，告诉你线段的长度L，小球数量n，以及n个小球的初始位置，请你计算t秒之后，各个小球的位置。

提示

　　因为所有小球的初始位置都为偶数，而且线段的长度为偶数，可以证明，不会有三个小球同时相撞，小球到达线段端点以及小球之间的碰撞时刻均为整数。
　　同时也可以证明两个小球发生碰撞的位置一定是整数（但不一定是偶数）。

输入格式

　　输入的第一行包含三个整数n, L, t，用空格分隔，分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。
　　第二行包含n个整数a1, a2, …, an，用空格分隔，表示初始时刻n个小球的位置。

输出格式

　　输出一行包含n个整数，用空格分隔，第i个整数代表初始时刻位于ai的小球，在t秒之后的位置。

样例输入

3 10 5
4 6 8

样例输出

7 9 9

代码1

记录每个位置都有哪些小球，位置可以是[0,L]。小球用结构体表示。

1
2
3
struct Ball{
    int id, dir; //dir=1表示向右
};

题目中问t秒之后小球的位置，那么就在循环t次，在循环内部，处理情况，以更改每个位置的小球情况和小球的方向属性。当循环完毕之后，就记录每个小球的位置vector<int> pos ，然后输出。

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

struct Ball{
    int id, dir; //dir=1表示向右
    bool operator<(const Ball& b)const{
        return id<b.id;
    }
    Ball(int a,int b){
        id=a;
        dir=b;
    }
};
int n,L,t;
vector<set<Ball>> ballOfPos;
vector<int> pos;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>L>>t;
    ballOfPos.resize(L+1);
    pos.resize(n);

    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        ballOfPos[a].insert(Ball(i,1));
    }

    for(int i=0;i<t;i++){
        vector<set<Ball>> ballOfPos2;
        ballOfPos2.resize(L+1);
        for(int j=0;j<=L;j++){
            if(ballOfPos[j].size()==1){
                set<Ball>::iterator it = ballOfPos[j].begin();
                if(j==L){
                    ballOfPos2[j-1].insert(Ball((*it).id, 0));
                }else if(j==0){
                    ballOfPos2[j+1].insert(Ball((*it).id, 1));
                }else{
                    if((*it).dir == 1){
                        ballOfPos2[j+1].insert(Ball((*it).id, 1));
                    }else{
                        ballOfPos2[j-1].insert(Ball((*it).id, 0));
                    }
                }
            }else if(ballOfPos[j].size()==2){
                set<Ball>::iterator it1 = ballOfPos[j].begin();
                set<Ball>::iterator it2 = ++it1; it1--;
                if((*it1).dir == 1){
                    ballOfPos2[j-1].insert(Ball((*it1).id, 0));
                }else{
                    ballOfPos2[j+1].insert(Ball((*it1).id, 1));
                }
                if((*it2).dir == 1){
                    ballOfPos2[j-1].insert(Ball((*it2).id, 0));
                }else{
                    ballOfPos2[j+1].insert(Ball((*it2).id, 1));
                }
            }
        }
        ballOfPos = ballOfPos2;
    }

    for(int i=0;i<=L;i++){
        set<Ball>::iterator it = ballOfPos[i].begin();
        for(;it!=ballOfPos[i].end();it++){
            pos[(*it).id] = i;
        }
    }
    //output
    for(int i=0;i<n;i++){
        if(i==0) cout<<pos[i];
        else cout<<" "<<pos[i];
    }
}

20180303（URL映射）

问题描述

　　URL 映射是诸如 Django、Ruby on Rails 等网页框架 (web frameworks) 的一个重要组件。对于从浏览器发来的 HTTP 请求，URL 映射模块会解析请求中的 URL 地址，并将其分派给相应的处理代码。现在，请你来实现一个简单的 URL 映射功能。
　　本题中 URL 映射功能的配置由若干条 URL 映射规则组成。当一个请求到达时，URL 映射功能会将请求中的 URL 地址按照配置的先后顺序逐一与这些规则进行匹配。当遇到第一条完全匹配的规则时，匹配成功，得到匹配的规则以及匹配的参数。若不能匹配任何一条规则，则匹配失败。
　　本题输入的 URL 地址是以斜杠 / 作为分隔符的路径，保证以斜杠开头。其他合法字符还包括大小写英文字母、阿拉伯数字、减号 -、下划线 _ 和小数点 .。例如，/person/123/ 是一个合法的 URL 地址，而 /person/123? 则不合法（存在不合法的字符问号 ?）。另外，英文字母区分大小写，因此 /case/ 和 /CAse/ 是不同的 URL 地址。
　　对于 URL 映射规则，同样是以斜杠开始。除了可以是正常的 URL 地址外，还可以包含参数，有以下 3 种：
　　字符串 ：用于匹配一段字符串，注意字符串里不能包含斜杠。例如，abcde0123。
　　整数 ：用于匹配一个不带符号的整数，全部由阿拉伯数字组成。例如，01234。
　　路径 ：用于匹配一段字符串，字符串可以包含斜杠。例如，abcd/0123/。
　　以上 3 种参数都必须匹配非空的字符串。简便起见，题目规定规则中 和 前面一定是斜杠，后面要么是斜杠，要么是规则的结束（也就是该参数是规则的最后一部分）。而 的前面一定是斜杠，后面一定是规则的结束。无论是 URL 地址还是规则，都不会出现连续的斜杠。

输入格式

　　输入第一行是两个正整数 n 和 m，分别表示 URL 映射的规则条数和待处理的 URL 地址个数，中间用一个空格字符分隔。
　　第 2 行至第 n+1 行按匹配的先后顺序描述 URL 映射规则的配置信息。第 i+1 行包含两个字符串 pi 和 ri，其中 pi 表示 URL 匹配的规则，ri 表示这条 URL 匹配的名字。两个字符串都非空，且不包含空格字符，两者中间用一个空格字符分隔。
　　第 n+2 行至第 n+m+1 行描述待处理的 URL 地址。第 n+1+i 行包含一个字符串 qi，表示待处理的 URL 地址，字符串中不包含空格字符。

输出格式

　　输入共 m 行，第 i 行表示 qi 的匹配结果。如果匹配成功，设匹配了规则 pj ，则输出对应的 rj。同时，如果规则中有参数，则在同一行内依次输出匹配后的参数。注意整数参数输出时要把前导零去掉。相邻两项之间用一个空格字符分隔。如果匹配失败，则输出 404。

样例输入

5 4
/articles/2003/ special_case_2003
/articles// year_archive
/articles/// month_archive
/articles//// article_detail
/static/ static_serve
/articles/2004/
/articles/1985/09/aloha/
/articles/hello/
/static/js/jquery.js

样例输出

year_archive 2004
article_detail 1985 9 aloha
404
static_serve js/jquery.js

样例说明

　　对于第 1 个地址 /articles/2004/，无法匹配第 1 条规则，可以匹配第 2 条规则，参数为 2004。
　　对于第 2 个地址 /articles/1985/09/aloha/，只能匹配第 4 条规则，参数依次为 1985、9（已经去掉前导零）和 aloha。
　　对于第 3 个地址 /articles/hello/，无法匹配任何一条规则。
　　对于第 4 个地址 /static/js/jquery.js，可以匹配最后一条规则，参数为 js/jquery.js。

代码1

假如自己不会正则表达式，如何做这道题，还是可以做的。我们先把每个规则和名字建立映射，vector<array<string,2>> pToName ，然后输入URL，依次遍历pToName的每个规则，看是否匹配。

我们写一个函数bool isMatch(const string& p, const string& u), vector<string>& params 假如我们考虑规则p和URL u，我们按照/ 字符进程分割p和u，看对应是否匹配，若有参数匹配，则记录这个参数到params中，最后若p和u完全匹配，则返回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
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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Param{
    int type; //0:int 1:str/path
    int value;
    string str;
};
int n,m;
vector<array<string,2>> pToName;

bool isInt(string s){
    for(int i=0;i<s.size();i++){
        if(!isdigit(s[i]))
            return false;
    }
    return true;
}

bool isStr(string s){
    for(int i=0;i<s.size();i++){
        if(!isdigit(s[i]) && !isalpha(s[i]) && s[i]!='-' && s[i]!='_' && s[i]!='.'){
            return false;
        }
    }
    return true;
}

bool isPath(string s){
    for(int i=0;i<s.size();i++){
        if(!isdigit(s[i]) && !isalpha(s[i]) && s[i]!='-' && s[i]!='_' && s[i]!='.' && s[i]!='/'){
            return false;
        }
    }
    return true;
}
bool isMatch(const string& p, const string& u, vector<Param>& params){
    if(p[0]!=u[0]){
        return false;
    }
    int i1=1,i2,j1=1,j2;
    while(i1<p.size() && j1<u.size()){
        i2 = p.find('/',i1);
        string s1 = p.substr(i1,i2-i1), s2;
        if(s1 == "<int>"){
            j2 = u.find('/',j1);
            if(i2==string::npos&&j2!=string::npos || i2!=string::npos&&j2==string::npos){
                return false;
            }
            s2 = u.substr(j1,j2-j1);
            if(isInt(s2)){
                params.push_back({0,stoi(s2),""});
            }else{
                return false;
            }
            j1 = (j2==string::npos?u.size():j2+1);
        }else if(s1 == "<str>"){
            j2 = u.find('/',j1);
            if(i2==string::npos&&j2!=string::npos || i2!=string::npos&&j2==string::npos){
                return false;
            }
            s2 = u.substr(j1,j2-j1);
            if(isStr(s2)){
                params.push_back({1,0,s2});
            }else{
                return false;
            }
            j1 = (j2==string::npos?u.size():j2+1);
        }else if(s1 == "<path>"){
            s2 = u.substr(j1);
            if(isPath(s2)){
                params.push_back({1,0,s2});
            }else{
                return false;
            }
            j1 = u.size();
        }else{
            j2 = u.find('/',j1);
            if(i2==string::npos&&j2!=string::npos || i2!=string::npos&&j2==string::npos){
                return false;
            }
            s2 = u.substr(j1,j2-j1);
            if(s1 != s2){
                return false;
            }
            j1 = (j2==string::npos?u.size():j2+1);
        }
        i1 = (i2==string::npos?p.size():i2+1);
    }
    if(i1>=p.size() && j1>=u.size()){
        return true;
    }else{
        return false;
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    pToName.resize(n);
    for(int i=0;i<n;i++){
        cin>>pToName[i][0]>>pToName[i][1];
    }
    while(m--){
        string u;
        cin>>u;
        bool flag = false;
        for(int i=0;i<n;i++){
            vector<Param> params;
            if(isMatch(pToName[i][0], u, params)){
                cout<<pToName[i][1];
                for(int j=0;j<params.size();j++){
                    if(params[j].type == 0){
                        cout<<" "<<params[j].value;
                    }else{
                        cout<<" "<<params[j].str;
                    }
                }
                cout<<endl;
                flag = true;
                break;
            }
        }
        if(!flag){
            cout<<"404"<<endl;
        }
    }
}

//要考虑最后的/符号
//92行笔误，把j1写成i2了

20180304（棋局评估）

问题描述

　　Alice和Bob正在玩井字棋游戏。
　　井字棋游戏的规则很简单：两人轮流往3*3的棋盘中放棋子，Alice放的是“X”，Bob放的是“O”，Alice执先。当同一种棋子占据一行、一列或一条对角线的三个格子时，游戏结束，该种棋子的持有者获胜。当棋盘被填满的时候，游戏结束，双方平手。
　　Alice设计了一种对棋局评分的方法：

　　- 对于Alice已经获胜的局面，评估得分为(棋盘上的空格子数+1)；
　　- 对于Bob已经获胜的局面，评估得分为 -(棋盘上的空格子数+1)；
　　- 对于平局的局面，评估得分为0；

1

例如上图中的局面，Alice已经获胜，同时棋盘上有2个空格，所以局面得分为2+1=3。
　　由于Alice并不喜欢计算，所以他请教擅长编程的你，如果两人都以最优策略行棋，那么当前局面的最终得分会是多少？

输入格式

　　输入的第一行包含一个正整数T，表示数据的组数。
　　每组数据输入有3行，每行有3个整数，用空格分隔，分别表示棋盘每个格子的状态。0表示格子为空，1表示格子中为“X”，2表示格子中为“O”。保证不会出现其他状态。
　　保证输入的局面合法。(即保证输入的局面可以通过行棋到达，且保证没有双方同时获胜的情况)
　　保证输入的局面轮到Alice行棋。

输出格式

　　对于每组数据，输出一行一个整数，表示当前局面的得分。

样例输入

3
1 2 1
2 1 2
0 0 0
2 1 1
0 2 1
0 0 2
0 0 0
0 0 0
0 0 0

样例输出

3
-4
0

代码1

可以写一个函数int dfs(int player)来计算在当前棋局下若player来以最优策略下棋，可以得到多少分，分数为正表示Alice赢了，分数为负数表示对手赢了。player为0表示Alice，1表示对手。

dfs函数先判断上一个人有没有赢，若赢了，则返回一个值，否则，继续。设置一个分数score，遍历每个可以下棋的地方，然后递归，根据返回值a来更新score，若player为0，则应该取score和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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int T;
int graph[3][3];

//看player是否赢了
bool isWin(int player){
    int a = (player==0?1:2); //看要找什么数字连续
    if(graph[0][0]==a && graph[0][1]==a && graph[0][2]==a){
        return true;
    }else if(graph[1][0]==a && graph[1][1]==a && graph[1][2]==a){
        return true;
    }else if(graph[2][0]==a && graph[2][1]==a && graph[2][2]==a){
        return true;
    }else if(graph[0][0]==a && graph[1][0]==a && graph[2][0]==a){
        return true;
    }else if(graph[0][1]==a && graph[1][1]==a && graph[2][1]==a){
        return true;
    }else if(graph[0][2]==a && graph[1][2]==a && graph[2][2]==a){
        return true;
    }else if(graph[0][0]==a && graph[1][1]==a && graph[2][2]==a){
        return true;
    }else if(graph[0][2]==a && graph[1][1]==a && graph[2][0]==a){
        return true;
    }else{
        return false;
    }
}
//在player赢了的情况下，计算成绩
int getScore(int player){
    int ans=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(graph[i][j]==0) ans++;
        }
    }
    ans++;
    if(player==0) return ans;
    else return -ans;
}
//看棋盘是否满了
bool isFull(){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(graph[i][j]==0) return false;
        }
    }
    return true;
}
int dfs(int player){
    int prePlayer = player^1;
    if(isWin(prePlayer)){
        return getScore(prePlayer);
    }
    if(isFull()) return 0; //平手
    int score = (player==0?INT_MIN:INT_MAX);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(graph[i][j]!=0) continue;
            graph[i][j] = (player==0?1:2);
            int a = dfs(prePlayer);
            if(player==0){
                score = max(score,a);
            }else{
                score = min(score,a);
            }
            graph[i][j] = 0;
        }
    }
    return score;
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>T;
    while(T--){
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                cin>>graph[i][j];
            }
        }
        int ans = dfs(0);
        cout<<ans<<endl;
    }
}

一开始70行的代码忘写了，细节。

展开全文 >>

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>谢谢大家