茶6.10-6.14

Mon

Most socially-distanced subsequence_649B

输入 T(≤2e4) 表示 T 组数据。所有数据的 n 之和 ≤1e5。
每组数据输入 n(2≤n≤1e5) 和一个 1~n 的排列 p。

选一个 p 的长度至少为 2 的子序列 b，最大化 b 的所有相邻元素的绝对差的和。
即 S=|b1-b2|+|b2-b3|+…
在 S 最大的前提下，b 的长度尽量小。
输出任意一个符合要求的 b。

注：子序列不一定连续。

输入
2
3
3 2 1
4
1 3 4 2
输出
2
3 1
3
1 4 2

Sol：

上升段和下降段只需要考虑首尾元素，例如 p=[1,3,5,4,2] 选 b=[1,5,2]。

选上升段/下降段中间的元素，不会影响 S，所以不选。

结论：选择所有的峰顶峰谷，以及第一个数和最后一个数。

注：在本题的约束下，其实 b 是唯一的。

Code:

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    FOR(i, 0, n - 1) cin >> a[i];   
    vi ans;
    ans.push_back(a[0]);
    for(int i = 1; i < n - 1; i++) {
        if (a[i - 1] < a[i] == (a[i] > a[i + 1])) {
            ans.push_back(a[i]);
        }
    }
    ans.push_back(a[n - 1]);
    cout<<ans.size();
    cout<<'\n';
    print(ans);
    cout<<'\n';
}

Tue

https://codeforces.com/problemset/problem/1362/C

输入 T(≤1e4) 表示 T 组数据。
每组数据输入 n(1≤n≤1e18)。

定义 popcount(x) 为 x 二进制中的 1 的个数。
输出 popcount(0^1) + popcount(1^2) + popcount(2^3) + … + popcount((n-1)^n)。
其中 ^ 表示异或。

输入
5
5
7
11
1
2000000000000
输出
8
11
19
1
3999999999987

Sol：

考虑每一位的贡献。

由于任意相邻数字的奇偶性不同，所以 i 和 i-1 的二进制最低位不同，这贡献了 n 个 1。

当且仅当 i 是偶数时，i 和 i-1 的二进制次低位不同，这贡献了 floor(n/2) 个 1。

当且仅当 i 是 4 的倍数（二进制末尾是 00）时，i 和 i-1 的二进制从低到高第三位不同，这贡献了 floor(n/4) 个 1。

依此类推。所以答案为 n + floor(n/2) + floor(n/4) + … 考虑到下取整舍去的数字，这也等于 2n - popcount(n)。

灵神：写法一写法二

Code：

//重点是思路
void solve()
{
    ll n;
    cin >> n;
    ll ans = 0;
    while(n) {
        ans += n;
        n /= 2;
    }
    cout << ans << endl;
}

Wed

Sum of XOR Functions_155D

输入 n(1≤n≤3e5) 和长为 n 的数组 a(0≤a[i]≤1e9)。

定义 f(L,R) 为连续子数组 a[L] 到 a[R] 的异或和。

计算所有 f(L,R)*(R-L+1) 的和，其中 L <= R。

输出答案模 998244353 的结果。

样例：

输入 3 1 3 2

输出 12

输入 4 39 68 31 80

输出 1337

输入 7 313539461 779847196 221612534 488613315 633203958 394620685 761188160

输出 257421502

Sol:

让我们分别解决每个位的问题。

当我们固定一个比特（记为 $b$ ）时，我们要做的就是求解二进制字符串（记为 $s$ ）的原始问题。需要注意的是，如果某段上有奇数个 $1$ ，则该段上的 XOR 值为 $1$ ，否则为 $0$ 。因此，对于固定位 $b$ ，我们必须计算 $\sum{l=1}^{n} \sum{r=l}^{n} g(l, r) \cdot (r - l + 1)$ ，其中如果子串 $sl, s{l + 1}, \dots, s_r$ 中字符 1 的个数是奇数，则计算 $g(l, r) = 1$ ，否则计算 $g(l, r) = 0$ 。

现在我们来研究一下，如果子串的右边界是固定的（记为 $r$ ），如何解决这个问题。我们来表示一个函数（我们称之为 $pref(x)$ ），它等于长度为 $x$ 的前缀上的 $1$ 个数，模数为 $2$ 。因此，如果前缀 $x$ 中 $1$ 的个数为偶数，则为 $pref(x) = 0$ ，否则为 $pref(x) = 1$ 。

如果子串 $r$ 的右边界固定不变，那么我们需要考虑左边界 $l$ 、 $l < r$ 和 $pref(l) + pref(r) = 1$ 。我们需要维护这样的左边界的数量（对于有 $pref(l) = i$ 的边界，让它成为 $cnt_i$ ）和它们的总和（对于有 $pref(l) = i$ 的边界，让它成为 $sumOfL_i$ ）。当我们遍历 $r$ 时，可以很容易地保持这些值。

为什么需要这些值？如果我们将 $(r - l + 1)$ 段的长度表示为右边界和左边界之差，就可以计算出固定右边界 $r$ 的 $\sum{l=1}^{r} g(l, r) \cdot (r - l + 1)$ 值（如果我们将 $l$ 视为包含边界，将 $r$ 视为不包含边界，就可以从公式中舍弃 $1$ ）。因此， $\sum{l=1}^{r} g(l, r) \cdot (r - l + 1)$ 可以表述为这些线段的右边界之和（等于 $r$ 乘以不同左边界的个数）与这些线段的左边界之和（保持在 $sumOfL$ 中）的差。

现在我们只需遍历右边界并求和，同时保持 $cnt_i$ 和 $sumOfL_i$ 的值。不要忘了，我们只解决了 $b$ 位的问题，稍后我们需要合并每一位的结果（并确保将 $b$ /-th 位的结果乘以 $2^b$ ）。

总体复杂度为 $O(n \log A)$ ，其中 $A$ 是对数组中数值的限制。

Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 300005;
const ll MOD = 998244353;
ll n;
ll a[N];
int  main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    ll res = 0;    
    for (ll b = 0; b < 30; ++b) {
        ll cur = 0;
        vector <int> cnt(2);
        vector <int> sumOfL(2);
        cnt[0] = 1;
        ll x = 0;
        for (int i = 0; i < n; ++i) {
            x ^= ((a[i] >> b) & 1);
            ll sumOfR = (cnt[x ^ 1] * 1LL * (i + 1)) % MOD;
            cur = (cur + (sumOfR - sumOfL[x ^ 1] + MOD) % MOD) % MOD;
            cnt[x]++;
            sumOfL[x] = (sumOfL[x] + (i + 1)) % MOD;
        }
        res = (res + (1 << b) * 1LL * cur) % MOD;
    }
    cout << res << endl;
}

Thu

Balanced Playlist_Global5D

输入 n(2≤n≤1e5) 和长为 n 的数组 a(1≤a[i]≤1e9)。

0x3F 的播放列表中有 n 首歌，列表中的第 i 首歌的好听度为 a[i]。这 n 首歌按照【列表循环】模式播放。播放完第 n 首歌，就会播放第 1 首歌。如果 0x3F 听到一首歌，发现它的好听度 * 2 小于之前听到的最好听的歌，那么 0x3F 就会立刻停止播放。

输出 n 个数，其中第 i 个数等于，从播放列表中的第 i 首歌开始听，到停止播放时，完整播放的歌曲数目（停止播放时的那首歌不算）。

对于同一首歌，如果它被完整播放 x 次，就会统计 x 次。见示例 2。

如果可以无限循环，输出 -1。

样例：

输入 4 11 5 2 7 输出 1 1 3 2

输入 4 3 2 5 3 输出 5 4 3 6

输入 3 4 3 6 输出 -1 -1 -1

Sol:

这个问题有很多解决方法。

首先，要确定答案是否都是 $-1$ ，可以比较最大值 $x_i$ 的一半和最小值 $x_i$ 。

其次，请注意，在前 $n$ 个音轨中，我们将听最大值为 $x_i$ 的音轨，而在接下来的 $n$ 个音轨中，我们将停在最小值为 $x_i$ 的音轨上。因此，要假装循环播放列表是线性的，只需重复三次即可。

对于每首曲目 $i$ ，让我们找到下一首曲目 $j$ ，其冷却度大于 $x_i$ ，下一首曲目 $k$ 的冷却度小于 $\frac{x_i}{2}$ 。那么很容易看出，如果是 $j < k$ ，我们就有 $c_i = c_j + j - i$ ，如果是 $j > k$ ，我们就有 $c_i = k - i$ 。

因此，剩下的工作就是在每条音轨 $i$ 之后找到下一条音轨，而该音轨的冷度位于某个值段中。这可以通过二进制搜索 $O(n \log^2 n)$ 中的段树，二进制搜索 $O(n \log n)$ 中的稀疏表，二进制搜索 $O(n \log n)$ 中的堆栈来实现…另外，如果我们按照cool的程度递增/递减的顺序排列轨道，我们也可以用两个指针和类似于 C++ 集合或 Java TreeSet 的结构来回答这些查询。

Code:

void solve()
{
    int n;
    cin >> n;
    vi a(3 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i + n] = a[i + 2 * n] = a[i];
    }
    vi ans(3 * n);
    vi st_max;
    vi st_min;
    for (int i = 3 * n - 1; i >= 0; i--) {
        while (!st_max.empty() && a[st_max.back()] < a[i]) {
            st_max.pop_back();
        }
        while (!st_min.empty() && a[st_min.back()] > a[i]) {
            st_min.pop_back();  
        }
        int low = 0, high = (int) st_min.size();
        while (low < high) {
            int mid = (low + high) >> 1;
            if (a[st_min[mid]] * 2 < a[i]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int nxt = 3 * n;
        if (low > 0) {
            nxt = min(nxt, st_min[low - 1]);
        }
        if (!st_max.empty()) {
            nxt = min(nxt, st_max.back());
        }
        if (nxt < 3 * n && a[nxt] >= a[i]) {
            ans[i] = ans[nxt];
        } else {
            ans[i] = nxt;
        }
        st_min.push_back(i);
        st_max.push_back(i);
    }
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << (ans[i] == 3 * n ? -1 : ans[i] - i);
    }
    cout << '\n';
}

Fri

Strange LCS

输入 T(≤5) 表示 T 组数据。

每组数据输入 n(2≤n≤10) 和 n 个字符串，只包含大写和小写英文字母，且对于每个字符串，每个字母最多出现两次。

计算这 n 个字符串的最长公共子序列（LCS）。

输出 LCS 的长度和任意 LCS。

样例：

输入

ABC

CBA

bacab

defed

abcde

aBcDe

ace

codeforces

technocup

输出

ace

coc

Sol:

首先思考：如果每个字母至多出现一次，要怎么做？

如果对于每个字符串，字母x都出现在字母y的左边，那么就在x到y之间连一条有向边。

问题变成求有向无环图（DAG）的最长路，这可以用记忆化搜索（或者拓扑排序）来解决。

那么有两个字符串，字母x的在第一个字符串的下标为i1和i2,在第二个字符串中下标为j1和j2，那么字母x就有四种不同位置的组合。

推广到n个字符串，每个字母至多有2ⁿ种不同的位置组合。

用二进制数mask记录字母c在各个字符串中的位置，记为（mask，c）。

mask二进制从低到高第i位为0，表示c位于s[i]中的左边那个c的下标。
mask二进制从低到高第i位为1，表示c位于s[i]中的右边那个c的下标。

如果对于每个字符串，字母x都出现在字母y的左边，那么就在（mask，x）到（mask2，y）之间连一条有向边。同样，就变成了上述的问题。

考虑使用记忆话搜索计算，定义dfs(mask,c)表示LCS首字母为c，位置组合为mask时的LCS长度。

枚举下一个字母ch，设ch在各个字符串中的位置为mask2，则用dfs（mask2，ch）+1更新答案的最大值（下面代码把+1放在返回前计算）。

注意这里mask2要贪心的计算如果两个ch都满足，优先取最左边的。

答案为dfs(0,0) - 1,这里取字符’\0’作为LCS的首字母，这样就无需在dfs外面枚举LCS的首字母了。

为了输出具体方案，可以用一个from数组，在dfs中记录转移来源。

Code(buhui）:

void solve()
{
    int n;
    cin >> n;
    vector<string> a(n);
    for (auto &c : a) cin >> c;
    vector<map<char, vector<int>>> gist(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (int)a[i].size(); j++) gist[i][a[i][j]].pb(j);
    }
    map<vector<int>, int> dp;
    map<vector<int>, vector<int>> pr;
    dp[vector<int>(n, -1)] = 0;
    set<vector<int>> q;
    q.insert(vector<int>(n, -1));
    while (q.size()) {
        vector<int> now = *q.begin();
        q.erase(q.begin());
        int val = dp[now];
        for (char c = 'a'; c <= 'z'; c++) {
            vector<int> nxt(n);
            bool bad = 0;
            for (int i = 0; i < n; i++) {
                int id = upper_bound(all(gist[i][c]), now[i]) - gist[i][c].begin();;
                if (id == (int)gist[i][c].size()) {
                    bad = 1;
                    continue;
                }
                nxt[i] = gist[i][c][id];
            }
            if (bad) continue;
            if (!dp.count(nxt)) q.insert(nxt);
            if (!dp.count(nxt) || dp[nxt] < val + 1) {
                dp[nxt] = val + 1;
                pr[nxt] = now;
            }
        }
        for (char c = 'A'; c <= 'Z'; c++) {
            vector<int> nxt(n);
            bool bad = 0;
            for (int i = 0; i < n; i++) {
                int id = upper_bound(all(gist[i][c]), now[i]) - gist[i][c].begin();;
                if (id == (int)gist[i][c].size()) {
                    bad = 1;
                    continue;
                }
                nxt[i] = gist[i][c][id];
            }
            if (bad) continue;
            if (!dp.count(nxt)) q.insert(nxt);
            if (!dp.count(nxt) || dp[nxt] < val + 1) {
                dp[nxt] = val + 1;
                pr[nxt] = now;
            }
        }
    }
    int ans = 0;
    vector<int> now(n, -1);
    for (auto &c : dp) {
        if (ans < c.second) {
            ans = c.second;
            now = c.first;
        }
    }
    cout << ans << "\n";
    string s = "";
    while (now != vector<int>(n, -1)) {
        s += a[0][now[0]];
        now = pr[now];
    }
    reverse(all(s));
    cout << s << "\n";
    return;
}

codeforces

#math #greedy #bitmask #stack #binary_search #lcs

茶6.10-6.14

https://www.polarishaw.top/2024/06/11/茶6.10-6.14/

作者

Polaris

发布于

2024年6月11日

许可协议

CMU15445-lecture4 上一篇

div3-950 下一篇