26牛客暑假多校9

点击查看题面

Problem H. Set

题目大意

给定一个包含 $n$ 个互不相同正整数的集合 $S = {a_{1}, a_{2}, \dots, a_{n}}$ 。每次操作可以执行以下步骤：

从集合 $S$ 中任选一个元素 $x$ （此时由于 $x \in S$ ，操作后 $x$ 会从集合中移除）。
将 $x$ 拆分为两个正整数 $u, v$ ，满足 $u + v = x$ 。
依次对集合 $S$ 作用对称差操作： $S \leftarrow ((S \oplus x) \oplus u) \oplus v$ 。

对称差定义为：若元素在集合中则将其删除，若不在则加入集合。
即：若 $u = v$ ，则翻转两次等价于集合状态不变（ $u$ 不会被加入）；若 $u \neq v$ ，则分别翻转 $u$ 和 $v$ 在集合中的存在状态。

现允许进行任意次（可以为零次）上述操作，求最终能够构造出多少种仅包含单一元素的集合 $S$ （即满足 $| S | = 1$ ）。

数据范围：

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{9}$ （保证所有 $a_{i}$ 互不相同）
时间限制： $1.0 s$
空间限制： $512 MB$

思路

1.题目分析

对于拆分后的集合 $s$ ,相当于就是去掉一个 $x$ ,加上 $u 、 v$ 两个数，并且只保留个数为奇数的数
特别的，如果 $x$ 为偶数，可以使得 $u = v$ ,拆分 $x$ 后，相当于从集合 $s$ 中简单删除 $x$ ,z这就意味着偶数可以直接从集合 $s$ 中删除，并且可以选择保留 $\leq x$ 的任意一个偶数 $^{①}$

①

x为偶数 $\to$ x=u+v $\to$ u、v为偶数 $\to$ 消除v $\to$ 保留u
所有可以保留任意 $\leq x$ 的偶数

相反同理，如果 $x$ 为奇数，则必然会保留一个奇数，奇数可以是 $\leq x$ 的任意奇数

于是具体分析起来就容易了

总结起来就是：如果 $x$ 为偶数，直接消除或者保留比x小的偶数。如果 $x$ 为奇数，则保留比x小的奇数

2.全部为偶数

由于全部是偶数，可以直接任意消除偶数，可以选择保留任意小的偶数，所以直接找到集合中最大的数，公式计算出 $\leq m x$ 的偶数有多少个

3.含有偶数个奇数

对于含有偶数个奇数，可以把所有奇数变成最小的的奇数1，这样就会留下偶数个1，于是就相当于把所有奇数都消除了，只剩下偶数，变成2.的情况

4. 含有奇数个奇数

我们可以按照3.的方法消除偶数个奇数，最终只剩下一个奇数，偶数可以全部删除，所以可以保留不超过任意剩下的最大的那个奇数的奇数，这对吗？当然不对，原来集合中万一最大的数是偶数呢，可以将集合中最大数拆分出一个1变成最大的奇数，这样就是比原来集合中的最大奇数更大，最终能够留下的最多最优

5.总结

通过上面的分析，肯定有奇妙发现吧！
留下只能全部是奇数或者全部是偶数吧

总的来说：

如果全部为偶数，或者含有偶数个奇数，那就是 $\leq m x$ 的偶数个数（ $\geq 0$ 的偶数）
如果含有奇数个奇数，那能留下的数就是 $\leq m x$ 的奇数个数吧
$m x$ 为 $s$ 集合中最大的数

复杂度分析

所有我们只需要找到初始集合中奇数的个数，和最大值就可以

所有时间复杂度是 $O (n)$ 的

参考代码

c++

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

void fc() {
    int n;std::cin>>n; 
    int mx=0,cnt=0;
    for(int i=0;i<n;i++){
        int x;std::cin>>x;
        mx=std::max(mx,x); 
        if(x&1)cnt++;
    }
    
    std::cout<<(mx+(cnt&1?1:0))/2;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//std::cin>>t;
	while (t--) fc();
	return 0;
}

Problem B. Bingo Game

题目大意

在一个 $n \times n$ 的网格中，已有 $m$ 个格子处于点亮状态，其中第 $i$ 个被点亮的格子位于坐标 $(x_{i}, y_{i})$ 。现在允许点亮任意未被点亮的格子，求最少还需要额外点亮多少个格子，才能使得网格中至少存在完整的一行或完整的一列被全部点亮。

数据范围：

$1 \leq n, m \leq 10^{5}$
$1 \leq x_{i}, y_{i} \leq n$
保证给出的 $m$ 个格子坐标两两互不相同。

思路

本题的核心在于独立统计每一行与每一列已点亮格子的数量，并通过贪心思想寻找使得某一行或某一列填满所需的最小补齐代价。

频数统计：

定义数组 $r [x]$ 表示第 $x$ 行中当前已被点亮的格子数。
定义数组 $c [y]$ 表示第 $y$ 列中当前已被点亮的格子数。
遍历输入的 $m$ 个坐标 $(x_{i}, y_{i})$ ，分别执行计数累加： $r [x_{i}] \leftarrow r [x_{i}] + 1$ 与 $c [y_{i}] \leftarrow c [y_{i}] + 1$ 。

代价计算与最优解推导：

要将第 $i$ 行完全点亮，所需额外点亮的格子数量为 $n - r [i]$ 。
要将第 $j$ 列完全点亮，所需额外点亮的格子数量为 $n - c [j]$ 。
题目要求至少有一行或一列完全点亮，因此只需取所有行与列所需代价的最小值：

ans = min (min_{1 \leq i \leq n} (n - r [i]), min_{1 \leq j \leq n} (n - c [j]))

这等价于求解已有点亮格子最多的那一行或那一列所对应的剩余空缺数：

ans = n - max (max_{1 \leq i \leq n} r [i], max_{1 \leq j \leq n} c [j])

复杂度分析

时间复杂度： $O (n + m)$ 。统计 $m$ 个坐标的频数耗时 $O (m)$ ，遍历 $1 \sim n$ 的行与列求最小值耗时 $O (n)$ 。在 $n, m \leq 10^{5}$ 的规模下，整体运行时间约为数毫秒，效率极高。
空间复杂度： $O (n)$ 。仅需开辟大小为 $n + 1$ 的线性辅助数组记录每行、每列的点亮数量。

参考代码

cpp

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

void fc() {
    int n,m;std::cin>>n>>m;
    
    std::vector<int>l(n+1),r(n+1);
    for(int i=0;i<m;i++){
        int x,y;std::cin>>x>>y;
        l[y]++;
        r[x]++;
    }
    
    int mn=n;
    for(int i=1;i<=n;i++){
        mn=std::min(mn,n-l[i]);mn=std::min(mn,n-r[i]);
    }
    std::cout<<mn<<"\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//std::cin>>t;
	while (t--) fc();
	return 0;
}

Problem I. Slay the Spire

题目大意

面对生命值为 $x$ 的敌人，每回合可以执行以下两种行动之一：

施加中毒：使敌人的中毒层数增加 $a$ 。
普通攻击：立即对敌人造成 $b$ 点直接伤害。

在每个回合行动结束后，若中毒层数大于 $0$ ，则立即对敌人造成等同于当前中毒层数的伤害，随后中毒层数衰减 $1$ 。中毒层数不会跨回合清空。求击杀敌人（即累计造成的总伤害不小于 $x$ ）所需的最少回合数。

数据范围：

$1 \leq x, a, b \leq 10^{9}$

思路

1. 单调性与二分答案

显然，允许的回合数越多，我们所能造成的最大伤害必然单调不减。因此，问题可转化为：二分所需的回合数 $n$ ，判定在 $n$ 个回合内能否造成至少 $x$ 点伤害。

二分上下界：

下界： $l = 1$ ；
上界： $r = x$ （即使每次只造成 $1$ 点伤害，至多也只需 $x$ 回合）。

2. 行动贪心策略

设在总共 $n$ 回合中，选择“施加中毒” $k$ 次（ $0 \leq k \leq n$ ），“普通攻击” $n - k$ 次。由于越早施加中毒，中毒层数在后续回合中持续生效的次数就越多，因此最优策略必然是将全部 $k$ 次中毒安排在最开始的第 $1 \sim k$ 回合，剩余的 $n - k$ 回合全部进行普通攻击。

3. 伤害函数闭式推导

我们将 $n$ 回合的总伤害划分为三个部分计算：

前 $k$ 回合的中毒结算伤害：第 $t$ 回合（ $1 \leq t \leq k$ ）行动后，中毒层数为 $t \cdot a - (t - 1) = t (a - 1) + 1$ 。前 $k$ 回合结算的总伤害为：

\sum_{t = 1}^{k} [t (a - 1) + 1] = (a - 1) \frac{k (k + 1)}{2} + k

第 $k$ 回合结算并衰减后，剩余的中毒层数为 $P_{k} = k (a - 1)$ 。 2. 后 $n - k$ 回合的普通攻击伤害：

(n - k) \cdot b

后 $n - k$ 回合的中毒结算伤害：在接下来的 $n - k$ 个回合中，中毒层数从 $P_{k}$ 开始每回合递减 $1$ 。实际能产生结算伤害的回合数为 $L = min (n - k, P_{k}) = min (n - k, k (a - 1))$ 。其贡献为首项为 $P_{k}$ 、项数为 $L$ 的等差数列求和：

\sum_{j = 0}^{L - 1} (P_{k} - j) = \frac{L (2 P_{k} - L + 1)}{2} = \frac{L (2 k (a - 1) - L + 1)}{2}

综上，总伤害 $D (n, k)$ 为上述三项之和。

4. 极值点优化分析

分析 $D (n, k)$ 关于 $k$ 的函数性质：

当 $k \leq ⌊ n / a ⌋$ 时， $L = k (a - 1)$ ，此时函数关于 $k$ 为下凸二次函数，极值必在区间端点取得；
当 $k > ⌊ n / a ⌋$ 时， $L = n - k$ ，此时函数关于 $k$ 为开口向下的上凸二次函数，其理论对称轴极值点位于 $k^{*} \approx n - \frac{b}{a} + \frac{1}{2}$ 附近。

因此，无需对 $k$ 遍历或使用复杂的局部搜索，最优的 $k$ 必然属于以下候选常数集：

K = {0, n, ⌊ \frac{n}{a} ⌋ - 1, ⌊ \frac{n}{a} ⌋, ⌊ \frac{n}{a} ⌋ + 1, n - ⌊ \frac{b}{a} ⌋ - 1, n - ⌊ \frac{b}{a} ⌋, n - ⌊ \frac{b}{a} ⌋ + 1}

在 check 函数中，只需在栈上评估这几个固定候选点（去除 std::vector 动态内存分配开销，配合 __int128_t 防止溢出），即可在 $O (1)$ 时间内完成单次判定。

复杂度分析

时间复杂度： $O (\log x)$ 。二分区间大小为 $x$ ，单次 check 仅需计算常数个候选点的闭式代数解，耗时 $O (1)$ 。
空间复杂度： $O (1)$ 。仅使用常数个局部变量进行运算，无额外内存开销。

参考代码

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
ll x,a,b;
i128 f(i128 n,i128 k){
    if(k<0||k>n)return 0;
    i128 mn=std::min(n-k,k*(a-1));
    i128 res=k*(k+1)/2*a-k*(k-1)/2+(n-k)*b+mn*(2*k*a-2*k+1-mn)/2;
    return res;
}

i128 fmx(i128 n){
    std::vector<i128>c;c.reserve(12);
    c.push_back(0);c.push_back(n);
    i128 x=n/a,y=n-b/a;
    for(int i=-1;i<=1;i++){
        c.push_back(x+i);
        c.push_back(y+i);
    }
    i128 res=0;
    for(auto d:c){
        res=std::max(res,f(n,d));
    }
    return res;
}
bool check(__int128_t k){
    __int128_t q=(__int128_t)k*b;
    __int128_t p=(__int128_t)(k*(k+1)/2)*a-(k*(k-1)/2);
    return std::max({q,p,fmx(k)})>=x;
}
void fc() {
    std::cin>>x>>a>>b;
    
    int l=0,r=1e9+1;
    while(l+1<r){
        int mid=l+((r-l)>>1);
        if(check(mid))r=mid;
        else l=mid;
    }
    std::cout<<r<<"\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//std::cin>>t;
	while (t--) fc();
	return 0;
}

Problem D. Escape Root

题目大意

给定一棵包含 $n$ 个结点的树，树根固定为 $1$ ，每条边的长度均为 $1$ 。树上有 $m$ 个人，第 $i$ 个人在第 $s_{i}$ 秒出现在结点 $x_{i}$ 处，并立即以每秒 $1$ 单位长度的恒定速度沿最短路径向树根 $1$ 移动。

如果在移动过程中的某一时刻，有至少 $2$ 个人处于同一位置（可以是结点内部，也可以是边内部），则这些相遇的人将同时消失。若某人到达树根 $1$ 时未曾与任何人相遇，则成功逃脱并立即移出树。

请判断每个人是否能成功逃脱，输出一个长度为 $m$ 的 01 字符串：第 $i$ 位为 '1' 表示第 $i$ 个人成功逃脱，为 '0' 表示在途中相遇消失。

数据范围：

$1 \leq n, m \leq 2 \times 10^{5}$
$1 \leq u, v \leq n (u \neq v)$
$1 \leq x_{i} \leq n, 0 \leq s_{i} \leq 10^{9}$

思路

1. 守恒时间戳与碰撞性质推导

设结点 $u$ 到树根 $1$ 的距离为 $dis [u]$ （定义 $dis [1] = 0$ ）。

对于第 $i$ 个人（起点为 $x_{i}$ ，出发时刻为 $s_{i}$ ）：

若其未曾消失，到达其祖先结点 $u$ 所需的移动时间为 $dis [x_{i}] - dis [u]$ 。
其到达结点 $u$ 的绝对时刻为：

T_{i} (u) = s_{i} + dis [x_{i}] - dis [u]

将公式移项整理可得：

T_{i} (u) + dis [u] = s_{i} + dis [x_{i}]

定义第 $i$ 个人的守恒时间戳（即若全程无阻碍，到达根节点 $1$ 的理论时刻）为：

t_{i} = s_{i} + dis [x_{i}]

由此可得出两个关键性质：

边上无追及相遇：所有人均以相同速度向根节点移动。若两人同向在一条边上移动且出发时刻不同，其相对距离恒定不变，绝不会在边内部相遇；若来自不同分支，其路径首次交汇点必然是某一祖先结点（即其 $LCA$ ）。因此，所有相遇碰撞必然发生在树的结点处。
相遇充要条件：多个人在某个公共祖先结点 $u$ 处同时相遇，当且仅当他们拥有完全相同的守恒时间戳 $t$ ，且此前在各自向上传递的过程中均未发生过其他相遇湮灭。

2. 树上启发式合并（Small-to-Large）

当多个具有相同时间戳 $t$ 的人在结点 $u$ 相遇时，根据题意，他们会全部同时消失，不再继续向根节点传递。

因此，我们可以通过拓扑排序（自叶向根）或树形 DFS，自底向上进行信息合并：

为每个结点 $u$ 维护一个存活映射表 $A_{u}$ （Map: t -> id），记录当前子树向上输送的未湮灭时间戳及其人员编号。
维护一个当前结点 $u$ 处的湮灭集合 $S_{u}$ （Set: t），记录在当前结点 $u$ 已经发生碰撞消失的时间戳。
遍历 $u$ 的各个子结点 $v$ 时，将子结点的映射表 $A_{v}$ 启发式合并入 $A_{u}$ （始终由小集合向大集合合并）：
若 $t \in S_{u}$ ：说明该时间戳此前已在 $u$ 处发生碰撞，新到达的该时间戳个体直接湮灭；
若 $t \in A_{u}$ ：说明来自两个不同子分支的时间戳 $t$ 在结点 $u$ 首次相遇，双方同时消失，将 $t$ 移入 $S_{u}$ 并从 $A_{u}$ 中移除；
否则：将 $(t, i d)$ 插入 $A_{u}$ 。
处理完所有子结点后，将以当前结点 $u$ 为起点（ $x_{i} = u$ ）的人员按相同规则合并至 $A_{u}$ 。
最终回溯至根节点 $1$ 时，仍保留在 $A_{1}$ 中的人员即为成功逃脱者。

复杂度分析

时间复杂度： $O (n + m \log m)$ 。
树的 BFS 层次遍历预处理耗时 $O (n)$ 。
利用启发式合并（Small-to-Large），每个元素至多被迁移合并 $O (\log m)$ 次。结合哈希表（std::unordered_map），单次插入查询均摊 $O (1)$ ，整体合并时间复杂度为 $O (m \log m)$ 。
空间复杂度： $O (n + m)$ 。
邻接表及树基础属性数组占用 $O (n)$ 空间。
所有结点的映射表与集合中元素总量不超过 $m$ ，占用 $O (m)$ 空间。

参考代码

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+5;
int n,m;
int tot,head[N],to[N<<1],nxt[N<<1],deg[N],fa[N]; 
void init(){
    tot=0;
    memset(head,0,sizeof(head));
}
void add(int u,int v){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int dis[N];
void get_dis(){
    memset(dis,-1,sizeof(dis));
    dis[1]=0;
    std::queue<int>q;q.push(1);
    int d=0;
    while(q.size()){
        d++;
        int si=q.size();
        while(si--){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=nxt[i]){
                int v=to[i];
                if(-1==dis[v]){
                    q.push(v);
                    dis[v]=d;
                    deg[u]++;
                    fa[v]=u;
                }
            }
        }
    }
}
void fc() {
    std::cin>>n>>m; 
    init();
    for(int i=1;i<n;i++){
        int u,v;std::cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    
    get_dis();
    
    std::vector<ll>t(m);
    std::vector<std::vector<int>>id(n+1);
    for(int i=0;i<m;i++){
        ll x,d;std::cin>>x>>d;
        t[i]=d+dis[x];
        id[x].push_back(i);
    }
    
    std::queue<int>q;
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            q.push(i);
        }
    }
    
    std::vector<std::unordered_map<ll,int>>a(n+1);
    while(q.size()){
        int u=q.front();q.pop();
        
        std::unordered_set<ll>s;
        for(int i=head[u];i;i=nxt[i]){
            
            int v=to[i];
            if(v==fa[u])continue;
            
            if(a[u].size()<a[v].size()){
                std::swap(a[u],a[v]);
                for(auto &x:s)a[u].erase(x);
            }
            for(auto& [st,sx]:a[v]){
                if(s.count(st))continue;
                if(a[u].count(st)){
                    a[u].erase(st);s.insert(st);
                }else a[u][st]=sx;
            }
            a[v].clear();
        }
        
        for(auto x:id[u]){
            if(s.count(t[x]))continue;
            if(a[u].count(t[x])){
                s.insert(t[x]);
                a[u].erase(a[u].find(t[x]));
            }else a[u][t[x]]=x;
        }
        
        if(u!=1&&--deg[fa[u]]==0){
            q.push(fa[u]);
        }
    }
    
    std::string ans(m,'0');
    for(auto &[st,x]:a[1])ans[x]='1';
    std::cout<<ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	//std::cin>>t;
	while (t--) fc();
	return 0;
}

abc

div. 2

div. 3

26牛客暑假多校9

Problem H. Set

题目大意

思路

1.题目分析

2.全部为偶数

3.含有偶数个奇数

4. 含有奇数个奇数

5.总结

复杂度分析

参考代码

Problem B. Bingo Game

题目大意

思路

复杂度分析

参考代码

Problem I. Slay the Spire

题目大意

思路

1. 单调性与二分答案

2. 行动贪心策略

3. 伤害函数闭式推导

4. 极值点优化分析

复杂度分析

参考代码

Problem D. Escape Root

题目大意

思路

1. 守恒时间戳与碰撞性质推导

2. 树上启发式合并（Small-to-Large）

复杂度分析

参考代码

26牛客暑假多校9 ​

Problem H. Set ​

题目大意 ​

思路 ​

1.题目分析 ​

2.全部为偶数 ​

3.含有偶数个奇数 ​

4. 含有奇数个奇数 ​

5.总结 ​

复杂度分析 ​

参考代码 ​

Problem B. Bingo Game ​

题目大意 ​

思路 ​

复杂度分析 ​

参考代码 ​

Problem I. Slay the Spire ​

题目大意 ​

思路 ​

1. 单调性与二分答案 ​

2. 行动贪心策略 ​

3. 伤害函数闭式推导 ​

4. 极值点优化分析 ​

复杂度分析 ​

参考代码 ​

Problem D. Escape Root ​

题目大意 ​

思路 ​

1. 守恒时间戳与碰撞性质推导 ​

2. 树上启发式合并（Small-to-Large） ​

复杂度分析 ​

参考代码 ​

26牛客暑假多校9

Problem H. Set

题目大意

思路

1.题目分析

2.全部为偶数

3.含有偶数个奇数

4. 含有奇数个奇数

5.总结

复杂度分析

参考代码

Problem B. Bingo Game

题目大意

思路

复杂度分析

参考代码

Problem I. Slay the Spire

题目大意

思路

1. 单调性与二分答案

2. 行动贪心策略

3. 伤害函数闭式推导

4. 极值点优化分析

复杂度分析

参考代码

Problem D. Escape Root

题目大意

思路

1. 守恒时间戳与碰撞性质推导

2. 树上启发式合并（Small-to-Large）

复杂度分析

参考代码