A小柒与啦啦啦的博弈
由于两位玩家都追求自身利益最大化，并且每次只能选择一个宝物，我们可以推导出他们的最优策略。
假设当前可供选择的宝物有若干个，其中价值最高的宝物是 A，次高的宝物是 B。
- 如果轮到某个玩家选择
- 如果他选择了宝物
A，那么他立刻获得了当前最大的收益。 - 如果他选择了宝物
B(或者更小的宝物)，那么宝物A就会留给对方。由于对方也采用最优策略，对方一定会立刻选择宝物A。这对于当前玩家来说，是损失了获得最大宝物的机会，使得自己的总价值减少。
- 如果他选择了宝物
因此，无论轮到谁，为了最大化自己的收益，他都会毫不犹豫地选择当前所有宝物中价值最高的那个。因为如果他不拿，对方就会拿走，那么他就永远失去了获得这个最大宝物的机会。
基于这个推理，整个游戏过程将是这样的：
- 小柒（先手）选择当前价值最高的宝物。
- 啦啦啦选择剩下宝物中价值最高的宝物。
- 小柒选择剩下宝物中价值最高的宝物。
- 啦啦啦选择剩下宝物中价值最高的宝物。 …依此类推，直到所有宝物被分完。
这等同于：我们首先将所有宝物按照价值从大到小排序。然后，小柒拿走第1个、第3个、第5个…（即所有奇数位置的）宝物，啦啦啦拿走第2个、第4个、第6个…（即所有偶数位置的）宝物。
- 时间复杂度：O(nlogn)，主要来自排序操作。
- 空间复杂度：O(n)，存储宝物价值。
#include<bits/stdc++.h>
using i64 = long long;
void DAOQI() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
i64 ans1 = 0, ans2 = 0;
std::sort(a.begin() + 1, a.end(), std::greater<>());
for (int i = 1; i <= n; i++) {
if (i & 1) {
ans1 += a[i];
} else {
ans2 += a[i];
}
}
std::cout << ans1 << " " << ans2 << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
B小柒的交替子数组
关键点：
-
不需在原数组中修改元素，而是计算将某区间变成奇偶交替所需的最少操作数。
-
由于操作的内容是“将元素值加一”，而奇偶状态只取决于元素的奇偶性；
也就是说，将元素变为奇数或偶数所需要的操作次数为：
- 若当前元素的奇偶性符合目标状态，则操作次数为0
- 若不符合，则需要1次操作（加一）以改变奇偶性。
实现步骤：
- 两种可能的目标模式：
- 起点为奇数，交替为：奇 — 偶 — 奇 — 偶 — …
- 起点为偶数，交替为：偶 — 奇 — 偶 — 奇 — …
- 预先计算在每个位置达到两种模式的最小操作数：
- 定义两个数组：
odd[]：以当前索引作为起点为奇数的模式下，到当前位置的最小操作次数（前缀状态）even[]：以当前索引作为起点为偶数的模式下，到当前位置的最小操作次数
- 定义两个数组：
- 递推关系（动态规划）：
- 从后往前遍历数组，使用递推维护两种状态：
- 若当前位置元素已经满足奇偶要求，则需要0次操作，继承下一位置的状态值；
- 若不满足，则需要1次操作（加一）来改变奇偶性。
- 从后往前遍历数组，使用递推维护两种状态：
- 求答案：
- 通过遍历，判断每个长度为 m 的区间对应的两个模式所需的总操作次数，选取最小值作为答案。
具体实现细节：
-
从后向前遍历数组，维护两个DP数组
odd[]和even[]：odd[i]表示：以第 i个元素开始，符合奇数起点交替时，到达位置的最小操作数。even[i]表示：以第 i个元素开始，符合偶数起点交替时，到达位置的最小操作数。
-
使用递推公式：
if a[i] is odd: odd[i] = even[i + 1] even[i] = 1 + odd[i + 1] else: odd[i] = 1 + even[i + 1] even[i] = odd[i + 1] -
在遍历过程中，当剩余长度（
n - i + 1）大于等于 m，计算以当前位置为起点的两种模式下，长度为 m 子数组的代价（通过差值获取子区间的总代价）。 -
最终答案是所有这些子区间中对应最小化的操作次数。
#include<bits/stdc++.h>
using i64 = long long;
void DAOQI() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
int ans = n;
std::vector<int> odd(n + 2), even(n + 2);
for (int i = n; i >= 1; i--) {
if (a[i] & 1) {
odd[i] = even[i + 1];
even[i] = 1 + odd[i + 1];
} else {
odd[i] = 1 + even[i + 1];
even[i] = odd[i + 1];
}
if (n - i + 1 >= m) {
if (m & 1) {
ans = std::min({ans, odd[i] - even[i + m], even[i] - odd[i + m]});
} else {
ans = std::min({ans, odd[i] - odd[i + m], even[i] - even[i + m]});
}
}
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
C小柒的幸运数
算法思路
采用 滑动窗口 结合 字符频次统计 的方法，动态维护窗口内的逆序对数量。
核心思想
- 滑动窗口：用双指针 l和 r 表示窗口的左右边界，逐步扩展右边界 r，并在逆序对数量超过 x 时收缩左边界 l。
- 逆序对计算：利用数组
pha统计窗口中各字符的出现次数。新增字符时，累加比它大的字符数量；移除字符时，减少比它小的字符数量。
步骤细节
- 初始化：数组
pha记录窗口中字符的频率，now记录当前窗口的逆序对数量。 - 扩展右边界：
- 新增字符 s[r]，逆序对数量增加
pha中比 s[r] 大的字符总数（因为每个比 s[r] 大的字符都会与 s[r]形成逆序对）。 - 更新
pha中对应字符的计数。
- 新增字符 s[r]，逆序对数量增加
- 收缩左边界：当
时，尝试收缩窗口以寻找更优解：
- 移除字符 s[l]，逆序对数量减少
pha中比 s[l] 小的字符总数（因为这些字符不再与 s[l]形成逆序对）。 - 更新
pha中对应字符的计数，并移动左指针。
- 移除字符 s[l]，逆序对数量减少
- 更新最优解：每次窗口变动后，检查当前
now是否更接近 x。
复杂度分析
- 时间复杂度：O(26n)，每个字符最多被加入和移除窗口各一次，每次操作需遍历 26 个字母。
- 空间复杂度：O(26)，使用固定大小的数组
pha。
STD
#include <bits/stdc++.h>
using i64 = long long;
void DAOQI() {
std::string s;
std::cin >> s;
i64 x, n = s.size();
std::cin >> x;
std::vector<int> pha(26);
i64 ans = 0, now = 0;
for (int l = 0, r = 0; r < n; r++) {
for (int j = s[r] - 'a' + 1; j < 26; j++) {
now += pha[j];
}
pha[s[r] - 'a']++;
if (std::abs(now - x) < std::abs(ans - x)) {
ans = now;
}
while (l <= r && now >= x) {
for (int j = 0; j < s[l] - 'a'; j++) {
now -= pha[j];
}
pha[s[l] - 'a']--;
l++;
if (std::abs(now - x) < std::abs(ans - x)) {
ans = now;
}
}
}
std::cout << std::abs(ans-x) << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
D小柒的特殊双节点
两数xor最大值，很明显01trie，但是更新顺序还需要再考虑一下
对于一个节点，他要找的另一个节点，应该既不是祖先节点，也不是子孙节点\
一个节点 不能作为祖先影响到子孙们，那么应该先遍历
的所有子孙们，让他们处理完了，再把
插入trie中
一个节点 不能作为子孙影响到祖先们，那么应该在子孙们插入前，去
中
但是这还不够，会漏掉一些
1
/ \
2 3
/ \ / \
4 5 6 7
dfs的顺序是 1 2 4 5 3 6 7
以4为例，他想要trie里是 5 3 6 7 ，但实际上是空的
以5为例，他想要trie里是 4 3 6 7 ，但实际上只有 4
以6为例，他想要trie里是 2 4 5 7 ，但实际上只有2 4 5\
以7为例，他想要trie里是 2 4 5 6 ，不多不少正好
可以发现，越靠前，差的越多，越靠后差的越少
所以我们只需要翻转邻接表，再次调用dfs，这个时候本来靠后的点就变考前了，本来靠前的点就变靠后了
两次dfs，去trie里查询的时候，和起来的点，正好就是所有 既不是祖先又不是子孙的节点
时间复杂度
STD
#include<bits/stdc++.h>
using i64 = long long;
struct Trie {
struct node {
std::array<int, 2> son;
node() : son{} {}
};
std::vector<node> t;
Trie() {
init();
}
void init() {
t.assign(1, node());
}
int newnode() {
t.emplace_back();
return t.size() - 1;
}
void insert(const int &val) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int ne = val >> i & 1;
if (t[p].son[ne] == 0) {
t[p].son[ne] = newnode();
}
p = t[p].son[ne];
}
}
int query(const int &val) {
int p = 0, ans = 0;
for (int i = 30; i >= 0; i--) {
int ne = val >> i & 1;
if (t[p].son[ne ^ 1]) {
ans |= 1 << i;
p = t[p].son[ne ^ 1];
} else {
p = t[p].son[ne];
}
}
return ans;
}
};
void DAOQI() {
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n + 1);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
Trie trie;
std::vector<int> ans(n + 1);
auto dfs = [&](auto &&dfs, int u, int fa) -> void {
ans[u] = std::max(ans[u], trie.query(a[u]));
for (int v: adj[u]) {
if (v == fa) continue;
dfs(dfs, v, u);
}
trie.insert(a[u]);
};
dfs(dfs, 1, 1);
for (int i = 1; i <= n; i++) {
std::ranges::reverse(adj[i]);
}
trie.init();
dfs(dfs, 1, 1);
for (int i = 1; i <= n; i++) {
std::cout << ans[i] << " \n"[i == n];
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
E小柒的特殊五元组
-
，固定住
，求出每个数作为
的个数，右边
的个数，乘法原理乘起来.
-
针对左边的
，那么
就是
模式的总个数(
和
是一个意思)再减掉
，就可以得到
-
和
右边同理
#include<bits/stdc++.h>
using i64 = long long;
using i128 = __int128;
// 重载输入运算符以支持__int128类型
std::istream &operator>>(std::istream &is, __int128 &val) {
std::string s;
bool flag = true;
is >> s, val = 0;
if (s[0] == '-') flag = false, val = std::stoi(s.substr(0, 2)), s = s.substr(2);
for (char &c: s) val = val * 10 + (c - '0') * (!flag ? -1 : 1);
return is;
}
//重载输出运算符以支持__int128类型
std::ostream &operator<<(std::ostream &os, __int128 val) {
if (val < 0) os << "-", val = -val;
if (val > 9) os << val / 10;
os << static_cast<char>(val % 10 + '0');
return os;
}
template<typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n + 5, T{});
}
void add(int x, const T &v) {
for (int i = x; i <= n; i += i & -i) {
a[i] = a[i] + v;
}
}
T sum(int x) {
T ans{};
for (int i = x; i > 0; i -= i & -i) {
ans = ans + a[i];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int select(const T &k) {
int x = 0;
T cur{};
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && cur + a[x + i] <= k) {
x += i;
cur = cur + a[x];
}
}
return x;
}
};
void DAOQI() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<i128> l(n + 1), r(n + 1), ll(n + 1), rr(n + 1);
Fenwick<i128> fw1(n + 1), fw2(n + 1);
for (int i = 1; i <= n; i++) {
l[i] = fw1.sum(a[i] - 1);
ll[i] = fw2.sum(a[i] - 1);
fw2.add(a[i], fw1.sum(a[i]));
fw1.add(a[i], 1);
}
fw1.init(n + 1), fw2.init(n + 1);
for (int i = n; i >= 1; i--) {
r[i] = fw1.rangeSum(a[i], n);
rr[i] = fw2.rangeSum(a[i], n);
fw2.add(a[i], fw1.rangeSum(a[i] - 1, n));
fw1.add(a[i], 1);
}
i128 ans = 0;
for (int i = 1; i <= n; i++) {
ans += (l[i] * (l[i] - 1) / 2 - ll[i]) * (r[i] * (r[i] - 1) / 2 - rr[i]);
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
FG三角符文
三角符文（F/G）题解：
我们需要在一个巨大的、通过递推规则生成的三角形中，快速查询任意位置的字符。直接模拟生成整个三角形的复杂度是 ，对于
的数据规模是无法接受的。因此，我们需要寻找更高效的计算方法。
首先，我们分析三角形的生成规则。一个字符由其左下方（L）和右下方（R）的字符决定：
- 如果
L == R，则结果为L。 - 如果
L != R，则结果为'a', 'b', 'c'中剩下的那一个。
这种规则暗示了某种代数结构。我们将字符 'a', 'b', 'c' 映射到整数 0, 1, 2。通过观察可以发现，这个规则等价于一个模3加法运算。
令 val(c) 为字符 c 对应的整数：val('a') = 0, val('b') = 1, val('c') = 2。
设 x_{i,j} 为第 i 行第 j 列的字符值，那么递推关系可以表示为：
这个关系可以通过 (3 - (a + b) % 3) % 3 来实现，这正是代码中 combine 函数的逻辑。
第一步：从单步递推到多步递推
现在我们有了代数表达式，考虑如何从第 行（输入行）直接计算出任意
(x, y) 的值，也就是从递推公式推导出通项公式。
我们已将问题转化为代数形式：
其中
是第
行第
列的值。
这是一个单步递推公式，它将 (i, j) 的值与下一行 i+1 的两个值关联起来。我们的目标是找到一个多步递推公式，将 (i, j) 与更下方的某一行 i+d 关联起来，从而实现“跳跃”。
让我们手动展开这个递推关系，看看能否发现规律。为了简化，我们暂时忽略每一步的负号，最后再统一处理。
-
跳1步（d=1）：
依赖于
和
。系数是
(1, 1)。 -
跳2步（d=2）：
。
和
。
。
- 所以
。
- 系数是
(1, 2, 1)。
你可能已经看出来了，这些系数正是二项式系数，也就是帕斯卡三角形中的数！
经过 步递推后，
的值可以表示为第
行从第
列开始的
个值的线性组合，其系数为二项式系数
。再考虑上每一步引入的负号，经过
步就会有
的系数。因此，我们得到一般性的多步递推公式：
此时可以套用这个式子，加上一点点卷积运算，就足以解决 F 题了，如果要做 G 题还需要发现更多的优化方法
第二步：寻找简化的突破口
这个公式虽然通用，但计算起来非常复杂，因为它依赖于第 i+d 行的 d+1 个值。如果 d 很大，这个求和的计算量是无法接受的。
我们的目标是让这个求和式变得极其简单。如果能找到一个特殊的 d，使得绝大部分的二项式系数 在模3意义下都为0，那么求和就会自动消失，只剩下少数几项。
【出题人的题外话：想想组合数mod2的余数是怎么算的？我们能否推广到mod3】
【结论： 等价于 在
的三进制加法中产生了进位，这种情况我们希望多多出现】
第三步：应用卢卡斯定理
卢卡斯定理是数论中计算组合数模素数 p 的强大工具。其一个至关重要的推论是：
推论：当
是素数
的幂次时，即
(
)，则二项式系数
模
在我们的问题中，模数是素数 。如果我们选择的跳跃步长
d 是 3的幂（例如 ），那么根据上述推论：
这意味着，在我们庞大的求和式 中，只有第一项（
）和最后一项（
）的系数不为0，其他所有中间项的系数全都变成了0！
第四步：代入化简，得到最终公式
现在，我们将这个惊人的简化结果代入我们的多步递推公式中。
选择 (其中
)：
由于 仅在
和
时为1，求和式大大简化：
代入 和
：
最后，我们处理系数 。因为我们选择的
(
) 是一个奇数，所以
。
(注：即使对于
,
也是奇数，该结论也成立。)
于是，公式最终化简为：
观察这个最终的公式，它和我们最开始的单步递推公式形式上完全一样！
这就得到了我们的核心结论：
计算
x_{i,j}的值，等同于计算combine(x_{i+d, j}, x_{i+d, j+d})，只要步长d是3的幂次。
通俗一点的说：对于边长 $d=3^m$ 的正三角形，三个顶点字符也满足：要么全部相同，要么全部不同
这个结论是革命性的，它意味着我们不再需要一步一步地向下递推，而是可以一次性地“跳跃” 行，并且计算方法和单步递推完全相同。这为我们设计高效的递归跳跃算法铺平了道路。
加速算法：分块预处理 + 递归跳跃
每次calc要跳2*log3(n/L)层，每跳一次，一个查询会分裂成两个查询，所以一次calc复杂度是2^(2log3(n/L))=(n/L)^1.26186
- 预处理：我们不计算整个三角形，而是只计算靠近底部的
L行（这里取的是）。将这
L行的结果存储在pre数组中。 - 查询：对于一个查询
(x, y)：- 如果
x足够大，已经落在了我们预处理的L行区域内，那么可以直接从pre数组中O(1)返回答案。 - 如果
x在预处理区域之上，我们就执行“跳跃”。计算x到最底部的距离dist = (n-1) - x。找到不大于dist的最大的3的幂，记为d。然后递归地调用calc(x,y) = combine(calc(x+d, y), calc(x+d, y+d))。
- 如果
通过这种方式，递归调用会迅速地将 x 增加，直到 x+d 落入预处理区域，递归结束。
代码解析
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAXN = 500000;
constexpr int MAXL = 2000;
int n, q;
int bottom, pre_min;
// pre[t][j] 存储第 (pre_min + t) 行的第 j 列，t ∈ [0..L-1]
static uint8_t pre[MAXL][MAXN];
static int len_pre[MAXL];
// idxs[d] = 最大的 3^k ≤ d
static int idxs[MAXN + 1];
// 存 3 的幂
static int p3[20];
int p3sz;
inline uint8_t combine(uint8_t a, uint8_t b) {
// 等价于: -(a + b) mod 3
return (3 - (a + b) % 3) % 3;
}
int calc(int x, int y) {
// 如果已经在预存区，直接 O(1) 返回
if (x >= pre_min) {
return pre[x - pre_min][y];
}
// 否则跳跃到 x + d
int d = idxs[bottom - x];
int r1 = calc(x + d, y);
int r2 = calc(x + d, y + d);
return combine(r1, r2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
string s;
cin >> s;
bottom = n - 1;
int L = min(n, MAXL);
pre_min = bottom - (L - 1);
// 读入最底行到 pre[L-1]
len_pre[L - 1] = n;
for (int j = 0; j < n; j++) {
char c = s[j];
pre[L - 1][j] = (c == 'a' ? 0 : (c == 'b' ? 1 : 2));
}
// 向上推 L-1 行
for (int t = L - 2; t >= 0; t--) {
int p = t + 1;
len_pre[t] = len_pre[p] - 1;
for (int j = 0; j < len_pre[t]; j++) {
pre[t][j] = combine(pre[p][j], pre[p][j + 1]);
}
}
// 生成 3 的幂
p3[0] = 1;
p3sz = 1;
while ((ll)p3[p3sz - 1] * 3 <= bottom) {
p3[p3sz] = p3[p3sz - 1] * 3;
++p3sz;
}
// 填 idxs[d] = 最大的 3^k ≤ d
for (int k = 0; k < p3sz; k++) {
int lo = p3[k];
int hi = (k + 1 < p3sz ? min(p3[k + 1], bottom + 1) : bottom + 1);
for (int v = lo; v < hi; v++) {
idxs[v] = lo;
}
}
// 回答查询
string ans(q, '?');
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
int r = calc(x - 1, y - 1);
ans[i] = (r == 0 ? 'a' : (r == 1 ? 'b' : 'c'));
}
cout << ans << "\n";
return 0;
}
复杂度分析
- 预处理时间: 计算
L行，每行最多n个元素。总时间复杂度为。
- 预处理空间: 存储
L行数据，空间复杂度为 - 总时间复杂度:
。通过选择合适的
L，可以在时间和空间上取得平衡，高效地解决问题(反正n=2000莫名可以过)。
那么F可以通过卷积来通过，G也可以使用bitset来，下面是一位大佬的G
#include <bits/stdc++.h>
using namespace std;
constexpr int L = 729;
using B = bitset<500000>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<int> p;
for (int i = n; i > 0; i -= L) {
p.push_back(i);
}
reverse(p.begin(), p.end());
const int m = p.size();
vector<array<B, 3>> f(m);
for (int i = 0; i < n; i++) {
if (s[i] == 'a') {
f.back()[0].set(i);
}
if (s[i] == 'b') {
f.back()[1].set(i);
}
if (s[i] == 'c') {
f.back()[2].set(i);
}
}
for (int i = m - 2; i >= 0; i--) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
f[i][(9 - j - k) % 3] |= f[i + 1][j] & (f[i + 1][k] >> L);
}
}
}
vector<vector<int>> c(L, vector<int>(L));
c[0][0] = 1;
for (int i = 1; i < L; i++) {
c[i][0] = -c[i - 1][0];
}
for (int i = 1; i < L; i++) {
for (int j = 1; j <= i; j++) {
c[i][j] = (-c[i - 1][j] - c[i - 1][j - 1]) % 3;
}
}
while (q--) {
int x, y;
cin >> x >> y;
int i = lower_bound(p.begin(), p.end(), x) - p.begin();
int ans = 0;
for (int j = y; j <= y + (p[i] - x); j++) {
if (f[i][1][j - 1] || f[i][2][j - 1]) {
ans = (ans + c[p[i] - x][j - y]) % 3;
}
if (f[i][2][j - 1]) {
ans = (ans + c[p[i] - x][j - y]) % 3;
}
}
ans = (ans + 3) % 3;
cout << char('a' + ans);
}
cout << '\n';
return 0;
}
京公网安备 11010502036488号