【蓝桥杯】每日练习 Day5-白红宇

【蓝桥杯】每日练习 Day5

阅读量：738 次

发布时间：2019-03-22

本文共 3017 字，大约阅读时间需要 10 分钟。

今天遇到了两个看起来挺有挑战性的编程题，一个是牛奶交换，另一个是布尔语句逻辑分析。让我先理清楚这两个问题吧。

牛奶交换问题

牛奶交换问题描述了n头牛组成一个环，每头牛有一桶牛奶，每分钟他们会分享牛奶，直到自己牛奶用完。目标是计算最后剩下的牛奶总量。主播在分析过程中提到了使用拓补排序，但后来觉得可以直接模拟，只是苦于没有模拟的思路，但后来找到了y的思路，想用破环成链的方法解决。

分析思路

问题分析：每头牛每分钟分享牛奶给指定的下一头牛，直到自己牛奶用完。这样会形成一个环状的牛奶流动，每个牛的牛奶会被传递下去，直到某个牛奶用完，整个环的流动就会被打断。

破环成链的方法：为了处理环状结构，可以将环断开，形成一个链。然后从某个起点开始，按顺序处理每个牛的牛奶传递情况。这样可以避免环状结构带来的复杂性。

算法选择：使用数组记录每个牛的牛奶传递情况。找到起点后，按顺序处理每个牛的牛奶传递，直到牛奶用完。

复杂度分析：这种方法的时间复杂度是O(n)，因为每头牛只需要处理一次。

代码实现

#include 
   
    
using namespace std;
const int N = 400010;
typedef long long LL;
int n, m;
char s[N];
int a[N];
LL l;
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s;
        cin >> a[i];
        l += a[i];
    }
    int x = 0;
    for (int i = 0; i < n; i++) {
        s[i + n] = s[i];
        a[i + n] = a[i];
    }
    while (x < n && s[x] == s[x + 1]) x++;
    if (x >= n) {
        cout << l;
        return 0;
    }
    for (int i = x + 1; i <= n; i++) {
        int y = i;
        LL q = 0;
        while (y <= x + n && s[i] == s[y]) {
            q += a[y];
            y++;
        }
        if (s[i] == 'R') q -= a[y - 1];
        else q -= a[i];
        l -= min(q, (LL)m);
        i = y - 1;
    }
    cout << l;
    return 0;
}

布尔语句逻辑分析

布尔语句逻辑分析题给了一个标准布尔语句，只包含true、false、or、and。我们需要根据布尔语句的结构，判断在给定区间内的值是否为true或false。由于布尔运算的优先级问题，and先于or处理，所以我们需要先处理所有的and，然后再处理or。

分析思路

问题分析：布尔语句中包含true、false、or、and，需要根据布尔逻辑计算给定区间内的值。由于没有括号，and的优先级高于or，所以需要先处理所有的and，然后再处理or。

分割区间：首先，找到布尔语句中的or节点，并分割成小区间。然后，记录这些小区间的结构。

前缀和数组：利用前缀和数组来记录每个or区间内的真值情况，从而快速查询给定区间内的值。

逆向分析：分析布尔语句，确定每个or节点的位置，并记录前缀和数组。

区间查询：对于每个查询，计算所需区间内的值，考虑前缀和数组中的信息。

代码实现

#include 
   
    
using namespace std;
const int N = 200010;
int n, m, cnt;
int l[N], r[N], q[N], id[N];
int ones[N], zeros[N];
int main() {
    cin >> n >> m;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        q[i] = (s == "true" || s == "or");
    }
    for (int i = 1; i <= n; i += 2) {
        if (i == 1 || q[i - 1]) {
            cnt++;
            l[cnt] = i;
            r[cnt - 1] = i - 2;
            if (cnt >= 2) ones[cnt - 1] = ones[cnt - 2] + !zeros[i - 2];
            zeros[i] = !q[i];
        } else {
            zeros[i] = zeros[i - 2] + !q[i];
        }
        id[i] = cnt;
    }
    r[cnt] = n;
    ones[cnt] = ones[cnt - 1] + !zeros[n];
    while (m--) {
        int left, right;
        cin >> left >> right >> s;
        bool t = s == "true";
        int lid = id[left], rid = id[right];
        int a = ones[lid - 1] + ones[cnt] - ones[rid];
        int b = zeros[r[rid]] - zeros[right];
        if (l[lid] != left) b += zeros[left - 2];
        if (t) {
            if (a || !b) {
                cout << 'Y';
            } else {
                cout << 'N';
            }
        } else {
            if (b == 0) {
                cout << 'Y';
            } else {
                cout << 'N';
            }
        }
    }
    return 0;
}

总结

今天虽然遇到了两个看起来挺有挑战性的编程题，但通过仔细分析和思考，逐渐理清了思路，并写出了相应的代码。虽然过程中有些困难，但最终还是能够解决问题。希望未来能继续保持这种学习和解决问题的状态，提升自己的编程能力。

转载地址：http://raywk.baihongyu.com/

你可能感兴趣的文章