P8094 USACO22JAN Cow Frisbee S

题目概括

给定一个数组，求所有 $1 \leq i \leq j \leq n$，且对于所有 $i \leq k \leq j$，都满足 $a[i] \geq a[k] \cap a[j] \geq a[k]$ 的有序数对 $(i, j)$ 的长度（$j – i + 1$）。

算法 & 数据结构 & 思想

单调栈

错误点

暂无

思路

建一个单调栈，满足从栈顶到栈底是单调递增的，遍历每个数的时候，都把这个数和目前的栈顶做一个比较，如果大于现在的栈顶，就记录下这个数对，然后弹出现在的栈顶，继续比较。要注意的时候就是弹到最后的时候要再记录一下最后剩下的 top 和要插入的数。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define int long long
int n, a[1000005], ans;
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    stack <int> st;
    st.push(1);
    for (int i = 2; i <= n; i ++) {
        while (st.size() && a[i] > a[st.top()]) {
            int x = st.top();
            ans += i - x + 1;
            st.pop();
            // cout << i << " " << x << "\n";
        }
        if (st.size()) ans += i - st.top() + 1;
        st.push(i);
        // cout << ans << "\n";
    }
    cout << ans;
    return 0;
}

P8186 USACO22FEB Redistributing Gifts S

题目概括

FJ 有 $N$ 个礼物给他的 $N$ 头奶牛，这 $N$ 个礼物和 $N$ 头奶牛都被标记为 $1 \dotsm N (1 \le N \le 500)$ 。 每头奶牛都有一个愿望单，记录着一个含有 $N$ 个礼物的排列。比起在愿望单中出现更晚的礼物，奶牛更喜欢先出现在愿望单中的礼物。

因为 FJ 太懒了，他直接把 $i$ 号礼物分配给了 $i$ 号奶牛。现在，奶牛们聚在了一起，决定重新分配礼物，以便在重新分配后，每头奶牛都能得到跟原来一样，或是它更喜欢的礼物。

对于每个 $i$ （$i$ 从 $1$ 到 $N$），计算出重新分配后， $i$ 号奶牛可能拿到的最好的礼物（这个奶牛经过重新分配后能拿到的最喜欢的礼物）。

算法 & 数据结构 & 思想

图论，Floyd，最短路，建图。

错误点

注意奶牛可以多个轮流换礼物，所以不能两两考虑。

思路

我们可以在当奶牛 A 想要奶牛 B 的礼物的时候，可以建一条 $a \to b$ 的边。
那么我们发现，如果奶牛 A 想要奶牛 B 的礼物，奶牛 B 想要奶牛 C 的礼物，而奶牛 C 最后想要奶牛 A 的礼物，这样这几个就都可以换了。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define rank rrrrrrrrrr
int n;
int li[505][505], ans[505], rank[505][505], wh[505], xx[505][505], f[505][505];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> li[i][j];
            rank[i][li[i][j]] = j; 

        }
        ans[i] = i;
        wh[i] = i;
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= rank[i][ans[i]]; j ++) {
            int toV = li[i][j];
            int fromV = ans[i];
            int toid = wh[li[i][j]];
            int fromid = i;
            // cout << i << " " << j << " " << toV << " " << fromV << " " << toid << " " << fromid;
            f[i][li[i][j]] = 1;
            // if (rank[toid][toV] > rank[toid][fromV]) {
            //     // ans[toid] = fromV;
            //     // ans[fromid] = toV;
            //     // wh[fromV] = toid;
            //     // wh[toV] = fromid;
            //     f[toid][fromid] = f[fromid][toid] = 1;
            //     break;
            //     // cout << " !!!\n";
            // }
            // else cout << "\n";
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            for (int k = 1; k <= n; k ++) {
                if (f[j][i] && f[i][k]) f[j][k] = 1;
            }
        }
    }
    // for (int i = 1; i <= n; i ++) {
    //     for (int j = 1; j <= n; j ++) {
    //         cout << f[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= n; j ++) {
            if (f[i][li[i][j]] && f[li[i][j]][i]) {
                cout << li[i][j] << "\n";
                break;
            }
        }
    return 0;
}

P8271 USACO22OPEN COW Operations S

题目概括

给定一个由三个字母："C","O","W" 组成的字符串，现在可以进行如下操作：

1. 选择两个相邻相等的字母并将其删除。
2. 选择一个字母，将其替换为另外两个字母的任一排列。

求在询问的区间中一个可否通过上述操作把在这个区间中的字串变为一个字母：“C”。

算法 & 数据结构 & 思想

前缀和。
难度比较简单。
奇偶性。

错误点

讨论的太麻烦了，应该在最开始就写清楚有哪些操作。

思路

可以得出性质：

1. 字符串可以随便换位置：比如说 “OW” 可以通过 “WCCO” 变换为 “WO”。
2. “WW” 可以变换为 “OO”。
3. “OW” 可以变为 “C”
4. 只要可以变出奇数个 “C” 就行了。

代码

#include <bits/stdc++.h>
using namespace std;
/*
*/
string s;
int n, Q, cn[5][1000005];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s >> Q;
    n = s.size();
    for (int i = 0; i < n; i ++) {
        if (i) {
            cn[1][i] = cn[1][i - 1];
            cn[2][i] = cn[2][i - 1];
            cn[3][i] = cn[3][i - 1];
        }
        if (s[i] == 'C') cn[1][i] ++;
        else if (s[i] == 'O') cn[2][i] ++;
        else cn[3][i] ++; 
        // cout << cn[1][i] << " " << cn[2][i] << " " << cn[3][i] << "\n";
    }
    while (Q --) {
        int l, r; cin >> l >> r;
        l --;
        r --;
        int c1 = cn[1][r] - cn[1][l - 1];
        int c2 = cn[2][r] - cn[2][l - 1];
        int c3 = cn[3][r] - cn[3][l - 1];
        // cout << c1 << " " << c2 << " " << c3 << "\n";
        if (c3 % 2 == c2 % 2 && c1 % 2 == 1 && c3 % 2 == 0) cout << "Y";
        else if (c3 % 2 == c2 % 2 && c1 % 2 == 0 && c3 % 2 == 1) cout << "Y";
        else cout << "N";
    }
    return 0;
}