比赛主页：牛客练习赛135

目录

• A题
• B题
• C题

A

A题链接

题意：

给定两个数字 x、y，满足 2*x <= y，问 [1, n] 内有多少个数 z，满足 z/x = z/y

思路：

1. 打表发现 cnt = min(x-1,n)
2. 如果 z 小于 x，那么 z/x 以及 z/y 都是 0，如果 z >= x，那么 z/x 相比 z/y 结果就会不同

//      https://ac.nowcoder.com/acm/contest/103151/A
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;

int T, n, m, k;
void solve()
{
    int x, y;
    cin >> x >> y >> n;
    cout << min(x - 1, n) << "\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

B

B题链接

题意：

给定一个排列，逆序对数量为 m，有 q 次询问，每次询问输入 x、y，表示交换下标为 x、y 的值，问交换后的逆序对数量为奇数还是偶数

思路：

线性代数中排列逆序数的性质：

• 排列逆序数的性质：交换任意两个数一次，逆序数奇偶性改变一次

//      https://ac.nowcoder.com/acm/contest/103151/B

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;

int T, n, m, k;
void solve()
{
    cin >> n >> m >> k;
    for (int i = 0, x; i < n; i++)
        cin >> x;
    bool sign = m & 1;
    while (k--)
    {
        int x, y;
        cin >> x >> y;
        if (x != y)
        {
            if (sign)
                cout << "even\n", sign = 0;
            else
                cout << "odd\n", sign = 1;
        }
        else
            cout << (sign ? "odd\n" : "even\n");
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    T = 1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
    return 0;
}

C

C题链接

题意：

给定一个字符串以及 q 次询问，每次询问规定新的字典序顺序，问在这种字典序下字符串的逆序数是多少？

思路：

• 在真正的字典序下，序列 a...c 的数量记为 cnt[a][c]，序列 c...a 的数量记为 cnt[c][a]

• 先计算出字符串在真正字典序下的逆序对数量 ans

• 在新规定的字典序下，如果字母 a 字典序 > 字母 c 字典序，那么与原来到字典序不符，原来 ans 记录的是 cnt[c][a] 的数量，现在我们需要计算的是 cnt[a][c] 的数量，因为在新规定的字典序中，a>c，a...c 才是构成逆序对，所以现在 res = res - cnt[c][a] + cnt[a][c]

• 其他两两字母同理

• 所以我们需要在询问之前预处理 由两个字母组成的所有序列的个数

对于 pos：

• 按照真正的字典序 pos[i] = i，而现在不一定了
• 遍历过程我们知道 j<i，按照真正的字典序，pos[j] < pos[i];
• 但是如果 pos[j] > pos[i]，那就说明与真正的字典序不符，我们需要的是 cnt[j][i] 的数量了

//        https://ac.nowcoder.com/acm/contest/103151/C

#include <bits/stdc++.h>
using namespace std;
#define int long long

int ch[30][30];
int cnt[30], pos[30];
string s;
int n, m, ans = 0;
void solve()
{
    string op;
    cin >> op;
    for (int i = 0; i < 26; i++)
        pos[op[i] - 'a'] = i; // 规定新的字典序
    // 按照真正的字典序 pos[i] = i，而现在不一定了
    // 遍历过程我们知道 j<i，按照真正的字典序，pos[j] < pos[i];
    // 但是如果 pos[j] > pos[i]，那就说明与真正的字典序不符
    int res = ans;
    for (int i = 0; i < 26; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (pos[j] > pos[i])
                res = res - ch[i][j] + ch[j][i];
        }
    }
    cout << res << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            if (j > s[i] - 'a') // (j+'a',s[i]) 构成逆序对，所以 ans 要加上 cnt[j] 的数量
                ans += cnt[j];
            ch[j][s[i] - 'a'] += cnt[j]; // (j+'a',s[i]) 的序列对数量再加一份 cnt[j]，因为 s[i] 会与前面的 j 构成新的序列对
        }
        cnt[s[i] - 'a']++;
    }
    while (m--)
        solve();
}

// pos[op[i]-'a'] 表示字母 op[i] 的新字典序为 i
// pos 的下标 0~26 依然是表示 a~z，只是对应的字典序：pos[i] 不一样了
// 遍历过程中我们知道 j<i，也就是说按照真正的字典序，pos[j]<pos[i]，即字母(j+'a',i+'a')不会构成逆序对
// 但是如果pos[j]>pos[i]，说明与真正的字典序不符，所以我们真正要的是字母(j+'a',i+'a')的序列对数量，因为字典序j+'a' > i+'a'
// 而ans记录的是字母(i+'a',j+'a')的序列对数量，因为之前字典序 i+'a' > j+'a'，只有逆序才会记录到答案里面