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