2019-03 CSP真题

2019-03 CSP真题

1. 小中大

• 题目链接：小中大

• 思路：计算中位数时，分情况讨论一下 $n$ 的奇偶性即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int n, a[N];
db mid;
int main(){
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);
    if(n % 2 == 1) mid = a[n / 2 + 1];
    else mid = (db)(a[n / 2] + a[n / 2 + 1]) / 2.0;
    if(floor(mid) < mid) printf("%d %.1f %d", a[n], mid, a[1]);
    else printf("%d %.0f %d", a[n], mid, a[1]);
}

2. 二十四点

• 题目链接：二十四点

• 思路：暴力枚举 $2^3=8$ 种情况。因为 + 和 - 优先级相同，于是设为 0；再将 x 和 / 优先级设为 1 。 其中有四种情况 $000,111,100,110$ 可按照从左到右顺序计算，简化一点点。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e5 + 5;
const db eps = 1e-10;
int n, a[10], ans, ans2;
map<char, int> mp;
string s;
int calc(char c, int a, int b){
    if(c == '+') return a + b;
    if(c == '-') return a - b;
    if(c == 'x') return a * b;
    if(c == '/') return a / b;
    return 0;
}
int main(){
    mp['+'] = 0, mp['-'] = 0;
    mp['x'] = 1, mp['/'] = 1;
    cin >> n;
    while(n--){
        cin >> s;
        ans = 0;
        if(mp[s[1]] >= mp[s[3]] && mp[s[3]] >= mp[s[5]]){  //四种情况
            ans = s[0] - '0';
            for(int i : {1, 3, 5}) ans = calc(s[i], ans, s[i + 1] - '0');
        }
        else if(mp[s[1]] == 0 && mp[s[3]] == 1 && mp[s[5]] == 0){
            ans = calc(s[3], s[2] - '0', s[4] - '0');
            ans = calc(s[1], s[0] - '0', ans);
            ans = calc(s[5], ans, s[6] - '0');
        }
        else if(mp[s[1]] == 1 && mp[s[3]] == 0 && mp[s[5]] == 1){
            ans = calc(s[1], s[0] - '0', s[2] - '0');
            ans2 = calc(s[5], s[4] - '0', s[6] - '0');
            ans = calc(s[3], ans, ans2);
        }
        else if(mp[s[1]] == 0 && mp[s[3]] == 0 && mp[s[5]] == 1){
            ans2 = calc(s[5], s[4] - '0', s[6] - '0');
            ans = calc(s[1], s[0] - '0', s[2] - '0');
            ans = calc(s[3], ans, ans2);
        }
        else if(mp[s[1]] == 0 && mp[s[3]] == 1 && mp[s[5]] == 1){
            ans = calc(s[3], s[2] - '0', s[4] - '0');
            ans = calc(s[5], ans, s[6] - '0');
            ans = calc(s[1], s[0] - '0', ans);
        }
        puts(ans == 24 ? "Yes" : "No");
    }
}

3. 损坏的RAID5

• 题目链接：损坏的RAID5

• 思路：

4. 消息传递接口

• 题目链接：消息传递接口

• 思路：将所有进程的指令存入自己的队列中。为了降低复杂度，在 q 队列中存入有可能可执行当前指令的进程，有些进程的当前指令若不能执行，便不在 q 队列中，直到被配对后，删除当前指令，再放入。

  1. 注意：输入时可用由于不知道指令数量，可输入一整行后用流输入 stringstream 再处理。
  2. 判断匹配时既要判断命令 $S,R$ 是否符合，又要判断进程是否对应。于是命令 $S,R$ 可设为 $0,1$，当异或为正时便表示命令匹配。

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long
#define db double
#define VI vector<int>
#define PII pair<int, int>
const db Pi = 3.141592653589793;
const int INF = 0x7fffffff;
const int N = 1e4 + 5;
const db eps = 1e-10;
int cas, n, ok;
string s, tmp;
queue<int> q;
queue<PII> v[N];
int main(){
    cin >> cas >> n;
    getline(cin, s);
    while(cas--){
        while(q.size()) q.pop();
        rep(i, 0, n - 1){
            while(v[i].size()) v[i].pop();
            getline(cin, s);
            stringstream ss(s);
            while(ss >> tmp){
                v[i].push({tmp[0] == 'R' ? 1 : 0, stoi(tmp.substr(1))});
            }
            q.push(i);
        }
        while(q.size()){
            if(v[q.front()].empty()){
                q.pop();
                continue;
            }
            PII top1 = v[q.front()].front();
            int num1 = top1.second;
            if(v[num1].empty()){
                q.pop();
                continue;
            }
            PII top2 = v[num1].front();
            int num2 = top2.second;
            if(top1.first ^ top2.first && num2 == q.front()){
                v[q.front()].pop(), v[num1].pop();
                q.push(num1);
            }
            else q.pop();
        }
        ok = 0;
        rep(i, 1, n) if(v[i].size()) ok = 1;
        printf("%d\n", ok);
    }
}
/*
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

2 3
R1 S1
R2 S0 R0 S2
S1 R1
R1
R2 S0 R0
S1 R1
*/