csp-201903

20190301（小中大）

代码1

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

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

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

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

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

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

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

20190302（二十四点）

代码1

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

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

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

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

测试数据

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

20190303（损坏的RAID5）

代码1

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

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

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

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

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

测试数据

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

20190304（消息传递接口）

代码1

给出几个进程顺序执行的指令，判断是否死锁。pointer[n]表示每个进程正在执行第几条指令，初始时全为0，若遇到两个匹配的指令，才能向前推进，比如第0号进程第pointer[0]个指令是R1，第1号进程第pointer[1]个指令是S0，则0号进程和1号进程可以推进。那么如何在n个进程中找匹配的两个进程的指令呢？我想的是0和1,2,3…比较，然后1和2,3…比较，以此类推，一旦找到了，就推进，然后再继续开始找，等一个轮回结束了，再从1开始找，但是这个方法有点慢。

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

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

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

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

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

60分。超时。

测试数据

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

代码2

我们可以不用一个一个比较。从0进程开始，看它当前的指令对应哪个进程，如R1对应1进程，S2对应2进程。若i进程的指令对应的进程在它后面而且有指令而且可以匹配，则推进，然后从0进程再开始找；若没有指令，则必定死锁；若有指令，但不匹配，则看i+1号进程，一直这样，直到最后一个进程，若遍历到最后一个进程后没有推进一次，则死锁。

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

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

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

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

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

80分。运行超时

代码3

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

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

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

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

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

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

100分。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

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