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

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

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