XCPC wiki - 模拟

Brute Force

CF1997E. Level Up

Monocarp 正在玩一款电脑游戏。他从等级$1$ 开始。他将依次与$n$ 只怪物战斗，这些怪物的等级从$1$ 到$n$ 不等。

对于按顺序给出的每个怪物，Monocarp的遭遇如下：

• 如果 Monocarp 的等级高于怪物的等级，则怪物会逃跑；
• 否则，Monocarp会与怪物战斗。

在每与第$k$ 个怪物战斗（逃跑的怪物不计算在内）后，Monocarp的等级会增加$1$ 。因此，他在与$k$ 个怪物战斗后等级变为$2$ ，在与$2k$ 个怪物战斗后等级变为$3$ ，以此类推。

你需要处理$q$ 个查询，每个查询的格式如下：

• $i~x$ ：如果参数$k$ 等于$x$ ，Monocarp 是否会与第$i$ 个怪物战斗？

方法一 首先离线询问。

无论用什么方法，$k=1$ 时总是退化为暴力，因此考虑根号分治，当$k<\sqrt{ n }$ 时暴力。这部分的复杂度$\Theta(n\sqrt{ n })$。

当$k>\sqrt{ n }$ 时，level 的变化不会太大，在$\cfrac{n}{k}=\sqrt{ n }$ 级别。所需从某个 level 快速跳到下一个 level 的位置，也就使得区间内 > level 的数的个数刚好为$k$，预处理前缀和，在前缀和数组上二分实现。这部分的复杂度是个调和级数，约为$\Theta(\sqrt{ n }\log^{2} n)$。

总的时间复杂度不会超过$\Theta(n\sqrt{ n })$。

由于空间有限，预处理前缀和不能处理太多，我们取$M=300$，这样可以取分治的分界线为$\max\left\lbrace \cfrac{n}{300},\sqrt{ n } \right\rbrace$，最终取定$B=1000$。

空间复杂度$\Theta(300n)$。

constexpr int M = 300, B = 1000;

void eachT() {
	int n = read(), q = read();

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

	vector pre(M, vector<int>(n + 1, 0));
	for (int j = 0; j < M; ++j) {
		for (int i = 1; i <= n; ++i) {
			pre[j][i] = pre[j][i - 1] + (a[i] > j);
		}
	}

	vector<vector<pair<int, int>>> ask(n + 1);
	vector<int> ans(q + 1);
	for (int i = 1; i <= q; ++i) {
		int id = read(), k = read();
		if (k > n / 2) {
			ans[i] = id <= k or a[id] > 1;
		}  // 小小优化 k>n/2 直接出答案
		else {
			ask[k].emplace_back(id, i);
		}
	}

	for (int k = 1; k <= n / 2; ++k) {
		if (ask[k].empty()) continue;
		sort(ask[k].begin(), ask[k].end());  // 注意要排序

		// 小范围直接暴力
		if (k <= B) {
			int now = 1, cnt = 0, it = 0;
			for (int i = 1; i <= n; ++i) {
				while (it < ask[k].size() and ask[k][it].first == i) {  // 注意询问有相同 因此是while
					ans[ask[k][it].second] = a[i] >= now;
					++it;
				}
				if (a[i] >= now and ++cnt == k) ++now, cnt = 0;
			}
		}

		// 大范围二分跳
		else {
			int pos = 0, now = 0, it = 0;
			while (pos <= n) {
				pos = lower_bound(pre[now].begin() + pos, pre[now].end(), pre[now][pos] + k) - pre[now].begin();  // 跳到第一个>now有k个的位置
				now += 1;
				while (it < ask[k].size() and ask[k][it].first <= pos) {  // 和上面一样的
					ans[ask[k][it].second] = a[ask[k][it].first] >= now;
					++it;
				}
			}
		}
	}

	for (int i = 1; i <= q; ++i) {
		printf("%s\n", ans[i] ? "YES" : "NO");
	}
}

方法二 预处理答案，在线询问输出也是可以做的。

constexpr int M = 300, B = 3000;

void eachT() {
	int n = read(), q = read();

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

	vector pre(M, vector<int>(n + 1, 0));
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < M; ++j) {
			pre[j][i] = pre[j][i - 1] + (a[i] > j);
		}
	}
	
	vector<vector<int>> uplevel(n + 1);
	for (int k = 1; k <= n; ++k) {
		uplevel[k].push_back(0);
		if (k <= B) {
			int now = 0, cnt = 0;
			for (int i = 1; i <= n; ++i) {
				if (a[i] > now and ++cnt == k) {
					uplevel[k].push_back(i);
					now++;
					cnt = 0;
				}
			}
		}
		else {
			int now = 0, pos = 0;
			while (pos <= n) {
				pos = lower_bound(pre[now].begin(), pre[now].end(), k + pre[now][pos]) - pre[now].begin();
				uplevel[k].push_back(pos);
				now++;
			}
		}
	}

	for (int i = 0; i < q; ++i) {
		int id = read(), k = read();
		auto ok = a[id] >= uplevel[k].size() or id <= uplevel[k][a[id]];
		printf("%s\n", ok ? "YES" : "NO");
	}
}

BUC2L - 超级 Fibonacci

两个字符串按照$\rm Fibonacci$ 的规则运算，求字符串的指定位。

迁移学习是一种很重要的技能，小F 决心将斐波那契迁移到字符串上。给定两个初始字符串A和B，若之后每个字符串都是前两个字符串拼接而成，那么称这些字符串为斐波那契字符串组，即 F[i]=F[i-1]+F[i-2]。例如，假如 A="a",B="b"，那么斐波那契字符串组是：a b ba bab babba babbabab……
给定 A 和 B，小F 想知道斐波那契字符串组中第$x$ 项的第$y$ 个字符是什么，下标从 1 开始。

Input	Output
a b 4 1 1 2 1 3 2 4 3	a b a b

举个栗子，a="abcd", b="efg"，可计算出：

s[1] = "abcd";
s[2] = "efg";
s[3] = "efgabcd";
s[4] = "efgabcdefg";
s[5] = "efgabcdefgefgabcd"; // 与题目表述一致，这里所有下标从 1 开始

首先弄清这个「广义$\rm Fibonacci$」 的每一项的长度。显然，它亦满足$\rm Fibonacci$ 的运算规则，即$F_n=F_{n-1}+F_{n-2}$​，上面的栗子中，

len(s[1]) = 4;
len(s[2]) = 3;
len(s[3]) = 7 = 3 + 4;
len(s[4]) = 10 = 7 + 3;
len(s[5]) = 17 = 10 + 7;

注意到，除了第 1 项外，每一项的前面所有字母都是相同的，只需计算 无穷长的数列 的第$y$ 项$\varphi(y)$ 即可（题给$x$ 几乎是无效数据，它只用于判断$x=1$ 时的特例，下文详述）

而且，数列的$\pmb{F_{n-1}\sim F_{n}}$ 项和第$\pmb{1\sim F_{n-2}}$ 项完全相同。

基于此，我们希望逐步缩小$y$，化归为最基本的情形，如$\varphi(16)=\varphi(6)=\varphi(3)=c$。（最基本的情形即是两个所给字符串，$\varphi(1)=e,~\varphi(2)=f,~\varphi(3)=g,~\varphi(4)=a,~\varphi(5)=b,~\varphi(6)=c,~\varphi(7)=d$）

一般地，对于每一个$y$，一定存在$n$ 满足$F_{n-1}<y\leqslant F_{n}$，即$F_{n-1}<y\leqslant F_{n-1}+F_{n-2}$，也可写为$0<y-F_{n-1}\leqslant F_{n-2}$，且$\varphi(y)=\varphi(y-F_{n-1})$，这样就成功缩小了$y$ 的上界。重复这个过程，最终便能得到答案。

对于每次询问，首先搜索它在哪个区间内，即搜索满足$F_{p-1}<y\leqslant F_{p}$ 的$p$。而刚才已经算过$F_i$ 了，二分查找即可。

然后模拟化归的过程：

ll p = std::lower_bound(f, f + cnt, y) - f; 
while (p > 0 && y > f[0] + f[1]) {
    if (y <= f[p]) --p;
    else y -= f[p];
}

其中，if (y <= f[p]) --p; 用来找到每次要减去的$F_{n-1}$，两个约束 p>0 && y>f[0]+f[1] 防止减为负数（我最初只写 y>f[0]+f[1] 一直$\rm RE$。。。

现在就化为基本情形了，也就是上文 s[3] 的那几项，显然前面是 s[2]，后面是 s[1]，用三目愉快输出就好咯！（注意字符串的下标从 0 开始，查询的下标从 1 开始，需要 -1。

#include <cstdio>
#include <algorithm>
#include <cstring>

typedef long long ll;
const ll maxN = 4e3 + 7;
const ll INF = 3e18;
ll f[maxN];
char s1[maxN], s2[maxN];

int main() {
    scanf("%s%s", s1, s2);

    ll cnt = 2;
    f[0] = strlen(s1), f[1] = strlen(s2);
    for (ll i = 2; f[i - 1] < INF; ++i) {
        f[i] = f[i - 1] + f[i - 2];
        ++cnt;
    }
    
    ll q;
    scanf("%lld", &q);
    while (q--) {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        if (x == 1) {
            printf("%c\n", s1[y - 1]);
        } else {
            ll p = std::lower_bound(f, f + cnt, y) - f;
            while (p > 0 && y > f[0] + f[1]) {
                if (y <= f[p]) --p;
                else y -= f[p];
            }
            printf("%c\n", (y > f[1] ? s1[y - f[1] - 1] : s2[y - 1]));
        }
    }
    return 0;
}//*/

CF919D. Array Repetition

有一个初始为空的序列$a$，你需要对其进行$n$ 次操作，每次操作为以下两种之一：

• 1 x：向序列末尾加入一个正整数$x$；
• 2 x：将序列复制$x$ 份插入原序列末尾，保证之前已经进行过$1$ 操作。

所有操作结束后有$q$ 个询问，每次给定一个正整数$k$，表示询问最终序列第$k$ 位的数（序列从$1$ 开始编号）。

数据范围：$1 \leqslant n,q \leqslant 10^5,\ 1 \leqslant k \leqslant \min(10^{18},c)$，其中$c$ 为最终序列长度。

void eachT() {
	int n, q;
	cin >> n >> q;

	vector<pair<int, int>> que(n);
	for (auto& [op, x] : que) {
		cin >> op >> x;
	}

	vector<node> a;
	a.push_back({ 0,0,{} });

	ll len = 0;
	for (auto& [op, x] : que) {
		if (op == 1) {
			a.back().vec.push_back(x);
			len++;
		}
		else {
			++x;
			x = min<ll>(x, ((ll)1e18 + len - 1) / len);
			if (x == 1) continue;
			a.push_back({ x, len, {} });
			len *= x;
		}
	}
	reverse(a.begin(), a.end());

	while (q--) {
		ll p;
		cin >> p;

		int ans = -1;
		for (auto& [x, p1, vec] : a) {
			if (p > p1 * x) {
				ans = vec[p - p1 * x - 1];
				break;
			}
			else {
				p = (p - 1) % p1 + 1;
			}
		}
		assert(ans != -1);
		cout << ans << ' ';
	}
	cout << '\n';
}

模拟

2024 牛客多校 10L. Tada!

一个$n$ 位$0 \sim9$ 的转轮密码锁，拨动方式是每次选择一个区间，顺时针或者逆时针转动一位。从某个特定的密码出发，给定$m$ 条转动了$t$ 次到达了状态$s$ 的记录，问密码是否有解，如果有唯一解输出唯一解。

void eachT() {
    int n = read(), q = read();
    int K = int(pow(10, n));

    auto check = [&](int x, int l, int r, int k) {
        for (int i = 0, pow = 1; i < n; i++, pow *= 10) {
            if (l <= i && i <= r) {
                int digit = x / pow % 10;
                x -= digit * pow;
                digit = (digit + (k ? 9 : 1)) % 10;
                x += digit * pow;
            }
        }
        return x;
    };
    auto delta = [&](int x, int y) {
        int res = 0;
        for (int i = 0, pow = 1; i < n; i++, pow *= 10) {
            int digit = x / pow % 10 - y / pow % 10;
            if (digit < 0) digit += 10;
            res += pow * digit;
        }
        return res;
    };
    vector dis(2, vector(K, inf));
    queue<pair<int, int>> Q;
    dis[0][0] = 0;
    Q.push({ 0, 0 });

    while (!Q.empty()) {
        auto [d, x] = Q.front(); Q.pop();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                for (int k = 0; k < 2; k++) {
                    auto tx = check(x, i, j, k);
                    if (dis[d ^ 1][tx] > dis[d][x] + 1) {
                        dis[d ^ 1][tx] = dis[d][x] + 1;
                        Q.push({ d ^ 1, tx });
                    }
                }
            }
        }
    }

    vector<pair<int, int>> que(q);
    for (auto& [x, y] : que) {
        x = read(), y = read();
    }
    vector <int> ans;
    for (int i = 0; i < K; i++) {
        bool flag = true;
        for (auto& [x, y] : que) {
            if (dis[y % 2][delta(x, i)] > y) {
                flag = false;
                break;
            }
        }
        if (flag) ans.push_back(i);
    }
    if (!ans.size()) cout << "IMPOSSIBLE\n";
    else if (ans.size() > 1) cout << "MANY\n";
    else {
        string w = to_string(ans[0]);
        while ((int)w.size() < n) w = '0' + w;
        cout << w << '\n';
    }
}

VJwin1A - 疾羽的救赎

vector<vector<int>> c(10);
c[2].push_back(1);
c[3].push_back(2);
c[4].push_back(3);
for (int ti = 0; ti < 12; ti++) {
	int a, b;
	cin >> a >> b;
	bool flag = 0;
	for (int i = 1; i <= 9; i++) {
		for (int j = 0; j < c[i].size(); j++) {
			if (c[i][j] == a) {
				for (int k = j; k < c[i].size(); k++) {
					c[i + b].push_back(c[i][k]);
				}
				for (int k = c[i].size() - 1; k >= j; k--) {
					c[i].erase(c[i].begin() + k);
				}
				flag = 1;
				break;
			}
		}
		if (flag)
			break;
	}
}
cout << (c[9].size() == 3 ? "Y" : "N") << "\n";