写在前面
比赛地址：https://ac.nowcoder.com/acm/contest/57356。
我是 MINUS-FIFTEEN 级超级战犯。
澄清一下，我不是声优厨，我不是声优厨，我不是声优厨。
同样是题目选补，我是飞舞。
以下个人向难度排序。
I
签到。
随便手玩一下就行。
D
虽然每个人都倾向于吃到自己最喜欢的菜，但给在前面点菜的人造成困扰的是后面的人也会点他最喜欢的菜，所以最计划通的方案是自己点一道后面的人不太喜欢的但是自己次喜欢的。
于是考虑倒着做，为靠后点菜的人分配他还能点的最喜欢的即可。
E
对于一个整数 \(x\)，定义一个数 \(y\) 是「玩原神玩的」，当且仅当 \(y\) 满足：
- \(0\le y\le 10^9\)。
- \(\exist k\in \mathbf{N}^+, \left\lfloor\frac{y^2}{10^k}\right\rfloor = x\)，即 \(x\) 是 \(y^2\) 的十进制中的一个前缀。
\(T\) 组数据，每组数据给定整数 \(x\)，判断是否存在一个整数 \(y\) 是「玩原神玩的」，如果存在则输出任意一个。
\(1\le T\le 10^5\)，\(0\le x\le 10^9\)。
1S，256MB。
要求 \(x\) 是 \(y^2\) 的前缀，所以有：
\[\left\lceil\sqrt{10^k\times x}\right\rceil \le y\le \left\lfloor\sqrt{10^k\times x + (10^k - 1)}\right\rfloor (k \ge 1) \]对于某个 \(k\) 只要上式成立则区间内的数均满足条件，枚举 \(k\) 检查直到 \(y\ge 10^9\) 即可。
像我这样暴力实现的话要开 int128。
tama 的还被 sqrt 卡精度了，场上没想到什么妙妙解决方案就直接手写了一个。
从大神 Aliemo 那里学到了，其实可以只检查 \(\left\lceil\sqrt{10^k\times x}\right\rceil\) 和 \(\left\lceil\sqrt{10^k\times x}\right\rceil + 1\) 是否能成为 \(y\) 即可。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <iostream>
#define LL __int128_t
const LL kInf = 1e9;
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
inline void print(LL n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10ll);
putchar(n % 10ll + '0');
}
LL mysqrt(LL y_) {
LL l = 0, r = kInf, ret = 0;
for (; l <= r; ) {
LL mid = (l + r) / 2ll;
if (1ll * mid * mid <= y_) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ret;
}
LL ceilsqrt(LL y_) {
LL ret = mysqrt(y_);
if (ret * ret < y_) ++ ret;
return ret;
}
LL floorsqrt(LL y_) {
LL ret = mysqrt(y_);
return ret;
}
void Solve(LL x_) {
x_ *= 10;
for (LL j = 9; ; x_ *= 10ll, j = 10ll * j + 9ll) {
LL l = ceilsqrt(x_), r = floorsqrt(x_ + j);
if (l > kInf) break;
if (r >= l) {
print(l);
printf("\n");
return ;
}
}
printf("-1\n");
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int x = read();
Solve(x);
}
return 0;
}
K
That's enough. There's no need to bring Genshin Impact into every little matter. Genshin Impact hasn't done anything to offend or harm you. Why do you keep mindlessly bashing it? miHoYo puts a lot of effort into promoting Chinese culture through their games, and all you do is sit behind a keyboard and criticize a conscientious company. People like you are ruining the future of Chinese games.
首先你正在玩原神，其次你正在玩原神，再次你正在玩原神。在原神里给定一长度为 \(n\) 的数列 \(a\)，表示有 \(n\) 个排成一列的盒子，第 \(i\) 个盒子内有价值为 \(a_i\) 的物品。
现在某些盒子上有盖子，你可以选择每次将一个盖子向前/向后移动一个位置，但每个盖子只能移动一次，并且某此操作后不能有两个盖子在同一个盒子上。
定义最后获得的价值为有盖子的盒子中物品价值之和，求若干次操作后可以获得的最大价值。
\(1\le n\le 10^6\)，\(0\le a_i\le 10^9\)。
1S，256MB。
原题。
我 tama 的用一个假 DP WA 了 5 发才发现能被我用脚指头造出来的 \(n=4\) 的数据叉掉、、、
考虑影响一个位置上的盖子移动的因素。
发现考虑前一个位置有没有被覆盖没什么用的，因为只是被覆盖的话情况太多了，我们无法区分出这些情况中有哪些能对该位置上盖子移动产生影响。
那什么会影响到盖子移动呢？如果前一个位置盖子往前移动了那么这个位置盖子可以随便乱跑；前一个位置盖子不动那这个位置只能不动或者往后，前一个位置盖子往后了那这个位置只能往后——
很有趣对吧！
于是我们先考虑设 \(f_{i, 0/1/2}\) 表示对于一个前缀 \(1\sim i\)，第 \(i\) 个位置上原有的盖子向前移动/不动/向后移动时，可以得到的最大价值。
对于原来有盖子的位置，有：
\[\begin{cases} f_{i, 0} &= f_{i - 1, 0} + a_{i - 1}\\ f_{i, 1} &= \max\{ f_{i - 1, 0}, f_{i -1, 1}\} + a_{i}\\ f_{i, 2} &= \max\{ f_{i - 1, 0}, f_{i - 1, 1}, f_{i - 1, 2}\} + a_{i + 1} \end{cases}\]对于原来没有盖子的位置，我们为了方便上面的转移，设 \(f_{i, 0/1}\) 表示第 \(i\) 个位置可以放新的盖子/不可以放新的盖子可以得到的最大价值，有：
\[\begin{cases} f_{i, 0} &= \max\{ f_{i - 1, 0}, f_{i -1, 1}\}\\ f_{i, 1} &= \max\{ f_{i - 1, 0}, f_{i - 1, 1}, f_{i - 1, 2}\}\\ \end{cases}\]初始化 \(f_{i, j} = +\infin\)，\(f_{0, 1} = 0\)，按照上述分类转移即可。答案即 \(\max\{f_{n, 0}, f_{n, 1}\}\)。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, a[kN], b[kN];
LL f[kN][3];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init(int l_, int r_) {
for (int i = l_; i <= r_; ++ i) {
for (int j = 0; j < 3; ++ j) {
f[i][j] = -kInf;
}
}
}
void DP() {
f[0][1] = 0;
for (int i = 1; i <= n; ++ i) {
if (b[i] == 0) {
f[i][0] = std::max(f[i - 1][0], f[i - 1][1]);
f[i][1] = std::max(f[i - 1][0], std::max(f[i - 1][1], f[i - 1][2]));
} else {
f[i][0] = f[i - 1][0] + a[i - 1];
f[i][1] = std::max(f[i - 1][0], f[i - 1][1]) + a[i];
f[i][2] = std::max(f[i - 1][0], std::max(f[i - 1][1], f[i - 1][2])) + a[i + 1];
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= n; ++ i) b[i] = read();
DP();
LL ans = std::max(f[n][0], f[n][1]);
printf("%lld\n", ans);
return 0;
}
/*
4
1 2 3 4
1 1 1 0
4
4 3 2 1
0 1 1 1
5
3 0 9 0 4
0 1 0 1 0
*/
H
给定两种对 \(k\) 位二进制数 \(x\) 的操作：
A：整个数 01 翻转。B：令二进制数 +1 并且自然溢出，即当 \(x\) 为 \(k\) 个 1 时操作后变为 0。给定一长度为 \(n\) 的仅由字符
A和B组成的字符串 \(s\)，描述了一个对二进制数的操作序列。给定 \(q\) 次询问，每次询问给定参数 \(l, r, x\)，询问对二进制数 \(x\) 依次进行操作 \(s_{l}\sim s_{r}\) 后 \(x\) 的形态。
强制在线。
\(3\le n\le 2\times 10^5\)，\(1\le q\le 2\times 10^5\)，\(1\le l, r\le n\)，\(1\le |x|\le 50\)。
2S，256MB。
超级好玩的题。场上想到二进制的性质还能这么玩的时候我直接感叹人类智慧，太厉害啦！
首先有个人尽皆知的性质，对于计算机中的补码表示法，正数的补码是其原码，负数的补码是正数的原码取反后 \(-1\)。
利用这个性质，我们把要被操作的二进制数 \(x\) 看做它对应的有符号十进制数 \(X\) 的补码表示，那么有：
A：\(X:=-X-1\)。B：\(X:=X+1\)。
发现我们可以把一个操作序列的影响抽象成 \(aX + b\) 的形式，两个操作序列 \(aX+b\)、\(cX+d\) 按顺序合并可以表示为 \(c(aX+b)+d\)。于是考虑倍增预处理所有长度为 \(2^k\) 的操作序列对于被操作数的影响，回答询问时拼接区间即可。输出时再把 \(X\) 取后 \(|x|\) 位还原回去就可以了。
想对补码进行操作直接用位运算就可以辣。
总复杂度 \(O((n+q)\log n)\) 级别。
代码里的 transforming 是很喜欢的马娘的角色歌。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
// #define ULL unsigned long long
const int kN = 2e5 + 10;
//=============================================================
int n, m, length;
char s[kN];
struct transforming {
LL a, b;
} f[kN][20];
LL x, ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read(), m = read();
scanf("%s", s + 1);
for (int i = 1; i <= n; ++ i) {
if (s[i] == 'A') {
f[i][0] = (transforming) {-1, -1};
} else {
f[i][0] = (transforming) {1, 1};
}
}
for (int j = 1; j <= 18; ++ j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
int a = f[i][j - 1].a, b = f[i][j - 1].b;
int c = f[i + (1 << (j - 1))][j - 1].a;
int d = f[i + (1 << (j - 1))][j - 1].b;
f[i][j] = (transforming) {a * c, b * c + d};
}
}
}
void Getans (LL val_, int pos_) {
if (pos_ == 1) {
s[pos_] = '0' + val_;
return ;
}
int r = val_ & 1;
Getans(val_ >> 1ll, pos_ - 1);
s[pos_] = '0' + r;
}
void Query(int l_, int r_) {
int temp1 = (ans xor l_) % n + 1, temp2 = (ans xor r_) % n + 1;
l_ = std::min(temp1, temp2), r_ = std::max(temp1, temp2);
x = 0;
for (int i = 1; i <= length; ++ i) x = 2ll * x + s[i] - '0';
for (int now = l_, i = 18; i >= 0; -- i) {
int k = 1 << i;
LL a = f[now][i].a, b = f[now][i].b;
if (now + k - 1 <= r_) {
x = a * x + b,
x &= ((1ll << length) - 1);
now = now + k;
}
}
ans = x;
Getans(ans, length);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
Init();
for (int i = 1; i <= n; ++ i) s[i] = 0;
while (m --) {
int l = read(), r = read();
scanf("%s", s + 1); length = strlen(s + 1);
Query(l, r);
printf("%s\n", s + 1);
for (int i = 1; i <= length; ++ i) s[i] = 0;
}
return 0;
}
G
对于一个字符串 \(S\)，我们定义它是中心对称的，当且满足它满足以下三条性质之一：
- \(S\) 为空。
- \(S\) 为字符串
o、s、x、z其中之一。- \(S\) 可以表示成
bTq、dTp、pTd、qTb、nTu、uTn、oTo、sTs、xTx、zTz的形式，其中 \(T\) 为一个中心对称的字符串。如果一个字符串 \(S\) 可以被按顺序分为 \(S=T_1T_2\dots T_n(n\ge 1)\)，并且满足 \(\forall 1\le i\le n\)，字符串 \(T_i\) 为中心对称的，则称字符串 \(S\) 是「不玩原神导致的」。
\(T\) 组数据，每组数据给定字符串 \(S\)，判断 \(S\) 是否为「不玩原神导致的」。
\(1\le T\le 10^6\)，\(1\le |S|\le 10^6\)，\(\sum |S|\le 5\times 10^6\)。
1S，256MB。
byd 这数据范围和时限是完全不准备把带 \(\log\) 的放过去是吧。
发现中心对称字符串本质上就是仅由字符 osxzbqdpnu 组成的多了几组相等关系的回文串，想到先搞个 Manacher 把以每个位置为对称中心最长可以扩展的中心对称串的半径跑出来。
然后考虑要怎么拆分 \(S\) 才能有解呢？
对可以拆成两端和更多段的 \(S\) 手玩了一下，于是猜了个结论：设 \(\operatorname{next}_{i}\) 为以位置 \(i\) 为左端点的，右端点最靠右的中心对称串的右端点，那么 \(S\) 可以被拆分当且仅当：
\[S = S[1 : \operatorname{next}_{1}] + S[\operatorname{next}_{1} + 1, \operatorname{next}_{\operatorname{next}_{1} + 1}] + \cdots+S[...:n] \]即从开头开始每次都找以该位置为左端点的最长的中心对称串向后延伸。
我赛时的写法是 \(O(n)\) 地处理出了这个 \(\operatorname{next}\) 数组之后再按照上述式子大力跳做的判断。显然，对于一个位置 \(i\)，它的 \(\operatorname{next}_i\) 对应的中心对称串一定是可以覆盖到它的对称中心最靠后的串，存在单调性。于是考虑倒序枚举对称中心 \(i\)，再维护一个位置 \(L\) 表示当前给 \(\operatorname{next}_L\) 赋值到的最靠前的位置。每次先判断是否有 \(L>i\) ，如果有则令其 \(=i\)，再将 \([i - r+1, L-1]\) 直接赋为另一侧对应位置即可。\(L\) 每次赋值后都会单调左移，则至多赋值 \(n\) 次。
不过推荐像题解一样在 Manacher 里就开始判断，在枚举对称中心的同时就维护一个位置 \(R\) 表示按照上述规则可以拼接出的最长前缀，如果当前对称中心延伸后可以覆盖 \(R\) 则将其调整为另一侧的对应位置。
总复杂度 \(O(n)\) 级别。
因为习惯抄板子所以一开始没想到还能在算法进行的同时就开始搞……幸亏还是想出来怎么搞了，不然身败名裂，学习了！
注意不管用什么方法，一定要把 osxzbqdpnu 之外的字符干掉……赛时吃惨了。
//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 2e6 + 10;
//=============================================================
int n, p[kN << 1], rrrr[kN << 1], next[kN << 1];
char s[kN], t[kN << 1];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool Judge(char ch1_) {
return ch1_ == 'o' || ch1_ == 's' || ch1_ == 'x' || ch1_ == 'z' || ch1_ == '%';
}
bool Equal(char ch1_, char ch2_) {
if (ch1_ > ch2_) std::swap(ch1_, ch2_);
if (ch1_ == ch2_) {
return ch1_ == 'o' || ch1_ == 's' || ch1_ == 'x' || ch1_ == 'z' || ch1_ == '%';
}
if (ch1_ == 'b') return ch2_ == 'q';
if (ch1_ == 'd') return ch2_ == 'p';
if (ch1_ == 'n') return ch2_ == 'u';
return false;
}
void Manacher() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++ i) t[2 * i - 1] = '%', t[2 * i] = s[i];
for (int i = 1; i <= n + 1; ++ i) s[i] = 0;
t[n = 2 * n + 1] = '%';
for (int i = 1; i <= n; ++ i) p[i] = 0;
int pos = 0, r = 0;
for (int i = 1; i <= n; ++ i) {
p[i] = 1;
if (i < r) p[i] = std::min(p[2 * pos - i], r - i + 1);
while (1 <= i - p[i] && i + p[i] <= n &&
Equal(t[i - p[i]], t[i + p[i]])) {
++ p[i];
}
if (!Judge(t[i])) p[i] = 0;
if (i + p[i] - 1 > r) pos = i, r = i + p[i] - 1;
}
// for (int i = 1; i <= n; ++ i) {
// printf("%c ", t[i]);
// }
// printf("\n");
for (int i = 1; i <= n; ++ i) {
rrrr[i] = p[i];
if (!Judge(t[i])) rrrr[i] = 0;
// printf("%d ", rrrr[i]);
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Manacher();
int nowl = n;
for (int i = 1; i <= n; ++ i) next[i] = 0;
for (int i = n; i; -- i) {
if (!rrrr[i]) continue;
int l = i - rrrr[i] + 1;
if (nowl > i) {
nowl = i;
}
while (nowl >= l) {
next[nowl] = i + i - nowl;
-- nowl;
}
}
int now = 1;
// printf("\n");
// for (int i = 1; i <= n; ++ i) printf("%d ", next[i]);
while (now != -1 && now < n + 1) {
if (!next[now]) {
now = -1;
break;
}
now = next[now] + 1;
}
printf("%s\n", now != n + 1 ? "No" : "Yes");
}
return 0;
}
/*
1
bsqobsqxbsqzbsq
1
sbssososzzsososq
1
a
1
bbxbbqqxqq
1
qqbbbb
*/
写在最后
学到了什么：
- 如果要之后的操作对之前的可能会有更优的影响，而之前的对之后的没有，可以考虑倒着做。
- 因地制宜地考虑影响某个决策的因素，别天天惦记着你那几把 DP 的套路辣。
- \(10^{18}\) 数量级直接
sqrt可能会有精度问题……暂时还不知道怎么在保留自带sqrt的基础上解决。 - 用算法求出来的信息完成的操作在算法进行过程中也可能实现，试试魔改算法？
- 想对补码进行操作直接用位运算就可以辣。
- 不玩原神导致的！
感觉眼睛要爆炸了。
标签：10,le,int,多校,盖子,牛客,ch,2023,include From： https://www.cnblogs.com/luckyblock/p/17573277.html