首页 > 其他分享 >CodeForces Round #951(Div. 2) 补题记录（A~D）

CodeForces Round #951(Div. 2) 补题记录（A~D）

时间：2024-06-07 09:55:26浏览次数：19  
标签：951 CodeForces cin int 补题 字符串 2k ldots define

A

容易发现对于任意一个长度为 \(n\)，下标从 \(1\) 开始的序列 \(a\)，若 \(1\le l\le r<n\)，则必然有 \(\max\limits_{i=l}^r a_i\le \max\limits_{i=l}^{r+1} a_i\)。若 \(1<l\le r\le n\)，则必然有 \(\max\limits_{i=l}^r a_i\le \max\limits_{i=l-1}^r a_i\)。

很显然 Bob 希望自己选取的数的 \(\max\) 的值尽量的小。那么 Bob 一定会选择区间长度尽量小的区间。因为题目要求 \(l<r\)，所以最小的区间长度 \(r-l+1=2\)。

因此只需要枚举所有长度为 \(2\) 的区间求最大值，然后将这个值减去 \(1\) 就是答案。时间复杂度为 \(O(n)\)。

B

考虑打表猜结论。从低到高枚举 \(x\) 和 \(y\) 在二进制下每一位的值，设当前枚举到的是第 \(i\) 位。若 \(x\) 的第 \(i\) 为位和 \(y\) 的第 \(i\) 位不同，那么答案就是 \(2^i\)。

因为 \(x\neq y\)，所以肯定至少存在一个 \(i\) 使得 \(x\) 的第 \(i\) 位和 \(y\) 的第 \(i\) 位的值不同。

时间复杂度为 \(O(\log n)\)。

auto main() [[O3]] -> signed {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int x, y;
        cin >> x >> y;
        F(i, 0, inf) {
            if ((x >> i & 1) != (y >> i & 1)) {
                cout << (1ll << i) << '\n';
                break;
            }
        }
    }
}

C

又是猜结论题。设 \(L=\operatorname{lcm}(k_1,k_2,k_3,\ldots,k_n)\) 的值。很显然有 \(L\le \text{lcm}(2,3,5,7,11,13,17,19)\le 10^7\)。然后考虑给每一个位置分配 \(\frac{L}{k_i}\) 的钱，最后 check 一下是否是满足条件的一组方案即可。

时间复杂度为 \(O(n)\)。

auto main() [[O3]] -> signed {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        F(i, 1, n) cin >> a[i].x, a[i].id = i;
        // stable_sort(a + 1, a + n + 1, [&](auto l, auto r) {
        //     return l.x < r.x;
        // });
        int res = a[1].x;
        F(i, 2, n) res = ll(res, a[i].x);
        F(i, 1, n) b[i] = res / a[i].x;
        int s = accumulate(b + 1, b + n + 1, 0ll);
        bool ok = true;
        F(i, 1, n) {
            if (s >= b[i] * a[i].x) {
                ok = false;
                break;
            }
        }
        if (ok) {
            F(i, 1, n) {
                cout << b[i] << ' ';
            }
            cout << '\n';
        } else {
            cout << "-1\n";
        }
    }
}

D

首先考虑暴力求解。枚举每一个 \(i\)，然后暴力 check 一下是否符合条件。

考虑优化上面的暴力。首先观察得到上面的这个操作其实就是让字符串 \(s\) 变为 \(s_{p+1}s_{p+2}s_{p+3}\ldots s_ns_ps_{p-1}s_{p-2}\ldots s_2s_1\)。

容易发现这个字符串其实可以被分割为 \(s_{p+1}s_{p+2}s_{p+3}\ldots s_n\) 和 \(s_ps_{p-1}s_{p-2}\ldots s_2s_1\) 两个部分。

然后再观察 \(k\) -proper 的性质。

容易发现一个 \(k\) -proper 其实只有两种不同的情况：

  • \(s_1=s_2=s_3=\ldots=s_k=1,s_{k+1}=s_{k+2}=s_{k+3}=\ldots=s_{2k}=0,s_{2k+1}=s_{2k+2}=s_{2k+3}=\ldots=s_{3k}=1,s_{3k+1}=s_{3k+2}=s_{3k+3}=\ldots=s_{4k}=0\)，以此类推。令生成的这个字符串为 \(S_1\)。
  • \(s_1=s_2=s_3=\ldots=s_k=0,s_{k+1}=s_{k+2}=s_{k+3}=\ldots=s_{2k}=1,s_{2k+1}=s_{2k+2}=s_{2k+3}=\ldots=s_{3k}=0,s_{3k+1}=s_{3k+2}=s_{3k+3}=\ldots=s_{4k}=1\)，以此类推。令生成的这个字符串为 \(S_2\)。

然后就可以去做这个题目啦。首先考虑字符串的前半部分 \(s_{p+1}s_{p+2}s_{p+3}\ldots s_n\)。容易发现这个部分必须和 \(S_1\) 或者 \(S_2\) 的长度为 \(n-p\) 的前缀完全相同。后半部分 \(s_ps_{p-1}s_{p-2}\ldots s_2s_1\) 的最长的长度为 \(k\) 的倍数的后缀必须和 \(S_1\) 或者 \(S_2\) 等长的前缀完全相同。

此时还（可能）在第二个字符串前缀中剩下 \(s_{p}s_{p-1}s_{p-2}\ldots s_q\) 这样的一个字符串，容易发现这样的一个字符串的长度为 \(p-q+1\)。那么此时将这个字符串直接接到第一个字符串上去，判断这个字符串是否仍然和 \(S_1\) 或者 \(S_2\) 等长的前缀字符串完全相同。

容易发现 \(S_1\) 和 \(S_2\) 的长度取到 \(n\) 就够了。但是问题是判断两个字符串匹配的时间复杂度仍然为 \(O(n)\)。因此考虑哈希判定（是显然的）。总的时间复杂度为 \(O(n)\)，注意要使用四哈希防止被卡。代码细节很多。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#ifdef int
#define inf (7611257611378358090ll/2)
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
int ll(int a, int b) {
    return a / __gcd(a, b) * b;
}
const int N = 400100;
int s1[N], s2[N];
struct Hash {
    int h1, h2, h3, h4;
    bool operator==(const Hash &r) const {
        return h1 == r.h1 && h2 == r.h2 && h3 == r.h3 && h4 == r.h4;
    }
} ;
const int m1 = 1e9 + 9, m2 = 998244353, m3 = 998244853, m4 = 19260817;
Hash hh1[N], hh2[N], hh3[N], hh4[N];
int bit1[N], bit2[N], bit3[N], bit4[N];
char ss[N], st[N];
Hash get(Hash *h, int l, int r) {
    int v1, v2, v3, v4;
    v1 = h[r].h1 - h[l - 1].h1 * bit1[r - l + 1] % m1, v1 %= m1; v1 += m1; v1 %= m1;
    v2 = h[r].h2 - h[l - 1].h2 * bit2[r - l + 1] % m2, v2 %= m2; v2 += m2; v2 %= m2;
    v3 = h[r].h3 - h[l - 1].h3 * bit3[r - l + 1] % m3, v3 %= m3; v3 += m3; v3 %= m3;
    v4 = h[r].h4 - h[l - 1].h4 * bit4[r - l + 1] % m4, v4 %= m4; v4 += m4; v4 %= m4;
    return {v1, v2, v3, v4};
}
signed main() {
    int T;
    cin >> T;
    bit1[0] = bit2[0] = bit3[0] = bit4[0] = 1;
    F(i, 1, N - 1) {
        bit1[i] = bit1[i - 1] * 131 % m1;
        bit2[i] = bit2[i - 1] * 1331 % m2;
        bit3[i] = bit3[i - 1] * 13331 % m3;
        bit4[i] = bit4[i - 1] * 133331 % m4;
    }
    while (T--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        s = ' ' + s;
        for (int i = 0; i <= n + 5; i++) {
            hh1[i].h1 = hh1[i].h2 = hh1[i].h3 = hh1[i].h4 = hh2[i].h1 = hh2[i].h2 = hh2[i].h3 = hh2[i].h4 = hh3[i].h1 = hh3[i].h2 = hh3[i].h3 = hh3[i].h4 = hh4[i].h1 = hh4[i].h2 = hh4[i].h3 = hh4[i].h4 = s1[i] = s2[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            if ((i - 1) % (2 * m) < m) {
                ss[i] = '1';
                st[i] = '0';
            } else {
                ss[i] = '0';
                st[i] = '1';
            }
        }
        for (int i = 1; i <= n; i++) {
            s1[i] = s1[i - 1];
            if (s[i] == '1') {
                s1[i]++;
            }
            hh1[i].h1 = hh1[i - 1].h1 * 131 + s[i]; hh1[i].h1 %= m1;
            hh1[i].h2 = hh1[i - 1].h2 * 1331 + s[i]; hh1[i].h2 %= m2;
            hh1[i].h3 = hh1[i - 1].h3 * 13331 + s[i]; hh1[i].h3 %= m3;
            hh1[i].h4 = hh1[i - 1].h4 * 133331 + s[i]; hh1[i].h4 %= m4;
        }
        for (int i = n; i; i--) {
            s2[i] = s2[i + 1];
            if (s[i] == '1') {
                s2[i]++;
            }
            hh2[n - i + 1].h1 = hh2[n - i + 1 - 1].h1 * 131 + s[i]; hh2[n - i + 1].h1 %= m1;
            hh2[n - i + 1].h2 = hh2[n - i + 1 - 1].h2 * 1331 + s[i]; hh2[n - i + 1].h2 %= m2;
            hh2[n - i + 1].h3 = hh2[n - i + 1 - 1].h3 * 13331 + s[i]; hh2[n - i + 1].h3 %= m3;
            hh2[n - i + 1].h4 = hh2[n - i + 1 - 1].h4 * 133331 + s[i]; hh2[n - i + 1].h4 %= m4;
        }
        for (int i = 1; i <= n; i++) {
            hh3[i].h1 = hh3[i - 1].h1 * 131 + ss[i]; hh3[i].h1 %= m1;
            hh3[i].h2 = hh3[i - 1].h2 * 1331 + ss[i]; hh3[i].h2 %= m2;
            hh3[i].h3 = hh3[i - 1].h3 * 13331 + ss[i]; hh3[i].h3 %= m3;
            hh3[i].h4 = hh3[i - 1].h4 * 133331 + ss[i]; hh3[i].h4 %= m4;
            hh4[i].h1 = hh4[i - 1].h1 * 131 + st[i]; hh4[i].h1 %= m1;
            hh4[i].h2 = hh4[i - 1].h2 * 1331 + st[i]; hh4[i].h2 %= m2;
            hh4[i].h3 = hh4[i - 1].h3 * 13331 + st[i]; hh4[i].h3 %= m3;
            hh4[i].h4 = hh4[i - 1].h4 * 133331 + st[i]; hh4[i].h4 %= m4;
        }
        int id = -1;
        for (int i = 1; i <= n; i++) {
            if (i == n || s[i + 1] == '1') {
                int len = n - i;
                if (get(hh1, i + 1, n) == get(hh3, 1, len)) {
                    int remainlen = (m - len % m) % m;
                    if (remainlen && ss[len + 1] == '1' || !remainlen && ss[len + 1] == '0') {
                        if (s1[i] - s1[i - remainlen] == remainlen) {
                            if (get(hh2, n - (i - remainlen) + 1, n) == get(hh4, 1, i - remainlen)) {
                                id = i;
                                break;
                            }
                        }
                    } else {
                        if (s1[i] - s1[i - remainlen] == 0) {
                            if (get(hh2, n - (i - remainlen) + 1, n) == get(hh3, 1, i - remainlen)) {
                                id = i;
                                break;
                            }
                        }
                    }
                }
            } else {
                int len = n - i;
                if (get(hh1, i + 1, n) == get(hh4, 1, len)) {
                    int remainlen = (m - len % m) % m;
                    if (st[len] == '1') {
                        if (s1[i] - s1[i - remainlen] == remainlen) {
                            if (get(hh2, n - (i - remainlen) + 1, n) == get(hh4, 1, i - remainlen)) {
                                id = i;
                                break;
                            }
                        }
                    } else {
                        if (s1[i] - s1[i - remainlen] == 0) {
                            if (get(hh2, n - (i - remainlen) + 1, n) == get(hh3, 1, i - remainlen)) {
                                id = i;
                                break;
                            }
                        }
                    }
                }
            }
        }
        cout << id << '\n';
    }
}

标签：951,CodeForces,cin,int,补题,字符串,2k,ldots,define
From： https://www.cnblogs.com/BaiduFirstSearch/p/18236581

相关文章

  • codeforces 1442 D Codeforces Round 681 (Div. 1, based on VK Cup 2019-2020 - Fina
    链接大意就是给你n组物品，这n组物品里面每组有\(t_i\)个，且他们是按照价值不降的顺序排列的。现在允许取k个物品，每个物品必须取在数组的开头处，每个物品在被取用后就会消失。问你最大能够拿到多少价值的物品。其中\(n,k\leq1500,\sumt_i\leq1e6,a_i\leq1e8\)很背包吧。可......
  • Codeforces Round 949题解（A、B、C）
    A.TurtleandPiggyArePlayingaGame首先\(p\)选\(2\)的话除得最慢，得的分多。考虑二进制表示，如果\(x=(1000000000)_{bin}\)，则每次除以\(2\)都是相当于右移一位，除完之后仍然是\(2\)的倍数，变成\(1\)的步数就是把最高位的\(1\)移动到\(0\)位的步数。因为\(2l\ler\)，所以\(l......
  • Codeforces Round 950 (Div. 3)个人题解(A~F1)
    CodeforcesRound950(Div.3)个人题解(A~F1)题解火车头#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<vector>#include<algorithm>#include<set>#include<unordered_map>#include<cstring>#include<cstdio&......
  • Codeforces Round 949 (Div. 2) 中文题解
    A对于一个特定的\(x\)，Piggy总是会选择\(p\)使得\(p\)是质数，所以分数就是\(x\)的质因子个数。容易发现至少有\(t\)个质因子的数是\(2^t\)。最大的满足\(2^t\ler\)的整数\(t\)是\(\left\lfloor\log_2r\right\rfloor\)。又因为\(2l\ler\)，所以\(\log_2l+......
  • Codeforces Round 950 (Div. 3)
    https://codeforces.com/contest/1980A.ProblemGenerator题意：Thereisgoingtobemroundsnextmouth,eachofthemonthshouldbeconsistof"ABCDEFG",countthenumebrofalphabetweshouldaddtosatisfythisrequirementunderagivingsequenc......
  • Educational Codeforces Round 166 (Rated for Div. 2)
    A.VerifyPassword题目描述Monocarpisworkingonhisnewsite,andthecurrentchallengeistomaketheuserspickstrongpasswords.Monocarpdecidedthatstrongpasswordsshouldsatisfythefollowingconditions:passwordshouldconsistonlyoflowerc......
  • [补题记录]LeetCode 6.Z字形变换
    传送门：Z字形变换转自：Z字形变换Thought/思路关键点在于，最后的答案是一行行连接起来的。这样我们就会发现，这个Z字，实际上会让行数不断加1，然后又不断减1。每次按顺序选择S中的一个字符即可。Code/代码classSolution{public:stringconvert(strings,int......
  • Codeforces Round 949 (Div. 2)
    目录写在前面ABCD写在最后写在前面比赛地址：https://codeforces.com/contest/1976妈的昨晚硬撑打了场edu上午实验下午爬山考试困困困妈的什么二进制场，C吃了个爽呃呃写得什么史山A二进制。一个显然的想法是选择区间\([l,r]\)中质因数次数之和最大的数。特别指出了限制......
  • Codeforces Round 949 (Div. 2)
    榜单#提交者=*ABCDEF1(2055)gutongxing20261388-1488900A#include<bits/stdc++.h>usingnamespacestd;intT,n,m;signedmain(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); printf(&quo......
  • Educational Codeforces Round 166 (Rated for Div. 2)
    目录写在前面ABCD写在最后写在前面比赛地址：https://codeforces.com/contest/1976满课，并且48小时之内只睡了8h。本来不想打的，但是手痒就上小号打了，然而唐唐唐掉大分呃呃A签到。感谢isdigit函数。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglon......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99