【记录】「COCI 2024/2025」四道模拟赛/8.11

榜二体验单。

https://www.luogu.com.cn/problem/P11751

简单题，但要注意 ‘ \\ ’ 这个字符要写两个才行·。

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

int main(){
ios::sync_with_stdio(false);
cin.tie(0);

int n;
string sa, sb;
cin >> n;
cin >> sa >> sb;

for (int i = 0; i < sa.size(); i ++) {
if (sa[i] == '\\\\') {
if (sa[i + 4] == '.') {
cout << "v";
i += 4;
}
else if (sa[i + 4] == '\\\\'){
cout << "w";
i += 8;
}
else{
cout << "v";
}
}
}
return 0;
}

https://www.luogu.com.cn/problem/P11752

，我想了半个小时这能不能过。

后来被逼得没着了打了个骗分的，结果是正解？

谁能告诉我  是怎么过的？

还是做比赛不够多，不然看到  就知道可以打。

如果一个区间计数问题，区间合法性质可以转化成一个条件是是否满足。

同时越扩大越糟糕（找最大可能方案），就可以用双指针。

像本题，如果问至少 k 个钉子，就应该把问题转换成总数 – 至多 k – 1 个钉子解决。

枚举上下界 + 双指针。

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

typedef long long LL;
const int N = 510;
char s[N];

LL a[N][N], sum[N][N];

LL get_(int sti, int edi, int stj, int edj) {
return sum[edi][edj] – sum[sti – 1][edj] – sum[edi][stj – 1] + sum[sti – 1][stj – 1];
}

int main () {
ios::sync_with_stdio(false);
cin.tie(0);

int n, m;
cin >> n >> m;
memset(a, 0, sizeof(a));
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i ++) {
cin >> (s + 1);
for (int j = 1; j <= m; j ++) {
if (s[j] == '#') {
a[i][j] = 1;
}
}
}

for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
sum[i][j] = a[i][j] + sum[i – 1][j] + sum[i][j – 1] – sum[i – 1][j – 1];
}
}

LL ans = 0;
for (int i = 1; i <= n; i ++) {
for (int j = i; j <= n; j ++) {
int tp = 1;
for (int k = 1; k <= m; k ++) {
while (get_(i, j, k, tp) <= 1 && tp <= m) {
tp ++;
}
ans += (tp – k);
}
}
}

cout << ans << "\\n";

return 0;
}

https://www.luogu.com.cn/problem/P11753

wyh 给我透的做法，我自己的话估计 st 表 + 二分乱搞。

注意到可以分为 和  分别处理，两边处理方式是一样的，这里假设是处理左端点。

对于每个点，我们要找离它最近的不能被它整除的点，即不是该点倍数的最近点，所谓“截断点”。

对于点  和再它右边的点 ，如果点  是点  的倍数，无疑点  是更好的“截断点”人选。

因为点  包含的因子少于（可能等于）点  所包含的因子，这样能成为别的点倍数的可能性更小。

这类似滑动窗口取最小值，我们考虑使用单调栈（毕竟又没规定范围）。

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

typedef long long LL;
const int N = 1e6 + 10;
LL a[N];
int sta[N], l[N], r[N];

int main () {
ios::sync_with_stdio(false);
cin.tie(0);

int n;
cin >> n;

for (int i = 1; i <= n; i ++) {
cin >> a[i];
}

int tp = 1;
sta[0] = 0;
sta[tp] = 1;
l[1] = 1;
for (int i = 2; i <= n; i ++) {
while ((a[sta[tp]] % a[i] == 0) && tp >= 1) {
tp –;
}
l[i] = sta[tp] + 1;
tp ++; sta[tp] = i;
}

tp = 1;
sta[0] = n + 1;
sta[tp] = n;
r[n] = n;
for (int i = n – 1; i >= 1; i –) {
while ((a[sta[tp]] % a[i] == 0) && tp >= 1) {
tp –;
}
r[i] = sta[tp] – 1;
tp ++; sta[tp] = i;
}

for (int i = 1; i <= n; i ++) {
cout << (r[i] – l[i] + 1) << " ";
}
cout << "\\n";

return 0;
}

https://www.luogu.com.cn/problem/P11754

四人合力做出来的，我在赛后 7 min AC 了。

最终答案一定是乘法原理，我们考虑连续的一段 0。

对于第 i 个点，我们可以选择涂 i + 1 的颜色 / 涂自己的颜色 / 强制不涂（填 -1）。

（1）涂 i + 1 的颜色

如果颜色 > 0，涂 i + 1 的时候顺着涂过来就好。

如果颜色是 0，也算 i + 1 顺位过来的，不管 i + 1 是 0 还是 -1，反正就是没有自己的选择。

（2）涂自己的颜色

我们这里从左到右涂色，这样就可以保证每个点都有自主选择了。

（3）强制不涂，就是涂 -1

然后发现如果总共有  个 ，答案就是 。

（一群人想半天，还用了牛顿二项式定理，结果就是这么简单的东西 TwT）

考虑到数据范围，用动态开点线段树就好。

我这里为了方便，用线段树管理值的 1 代表原来的 0，管理值 0 代表原来的 -1。

这样求 0 的个数用整一段的和就行，反转操作用异或 lazy tag。

你问我线段树开多大？

实测 1.5e7 能过，害怕炸用 vector 就好。

线段树里面就四个 long long 参啊！不要学某人开六个。。

81 分就看看是不是哪里有该开 long long 的没开，0 的个数作为幂次是千千万万不能 % MOD 的！

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

typedef long long LL;
const int N = 15e6 + 10;
const LL P = 1e9 + 7;
int a[N];

LL q_pow(LL a, LL b) {
LL c = 1;
while (b) {
if (b & 1) {
c = c * a % P;
}
a = a * a % P;
b >>= 1;
}
return c;
}

#define lc(p) tr[p].ls
#define rc(p) tr[p].rs

struct node {
int ls, rs;
LL siz;
int lazy;
} tr[N];
int rt, trlen;
LL n;

void newd(int &p, LL L, LL R) {
trlen ++; p = trlen;
tr[p] = {0, 0, R – L + 1, 0};
}

void pushup(int p) {
tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz;
}

void pushdown(int p, LL L, LL R) {
if (tr[p].lazy) {

LL mid = (L + R) >> 1;
if (!lc(p)) {
newd(lc(p), L, mid);
}
if (!rc(p)) {
newd(rc(p), mid + 1, R);
}

tr[lc(p)].lazy ^= 1;

tr[lc(p)].siz = (mid – L + 1) – tr[lc(p)].siz;

tr[rc(p)].lazy ^= 1;

tr[rc(p)].siz = (R – (mid + 1) + 1) – tr[rc(p)].siz;

tr[p].lazy = 0;
}
}

void change(int &p, LL L, LL R, LL l, LL r) {
if (!p) {
newd(p, L, R);
}
if (r < L || R < l) {
return ;
}
if (l <= L && R <= r) {
tr[p].siz = (R – L + 1) – tr[p].siz;
tr[p].lazy ^= 1;
return ;
}
LL mid = (L + R) >> 1;
pushdown(p, L, R);
change(lc(p), L, mid, l, r);
change(rc(p), mid + 1, R, l, r);
pushup(p);
}

int main () {
ios::sync_with_stdio(false);
cin.tie(0);

int q;
cin >> n >> q;
trlen = 0; rt = 0;
while (q –) {
LL l, r;
cin >> l >> r;
change(rt, 1ll, n, l, r);
cout << q_pow(3, tr[rt].siz) << "\\n";
}

return 0;
}