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