题目传送门

题目描述

你面前的黑板上写了 $[1,n]$ 中的所有正整数各一个。你的手里有一个计数器 $cnt$，初始为 $0$。

每次，你会选择黑板上最小的数 $x$（若有多个相同，只选择其中一个），并执行如下操作：

• 如果 $x=1$，那么直接将其从黑板上擦除；
• 否则，将 $cnt$ 加上 $(x\bmod 2)$ 的值，并擦除 $x$，然后写上两个 $\lfloor\frac{x}{2}\rfloor$。

请求出：当黑板上的数字全部被擦除时，$cnt$ 的值。

数据范围：$1\le n\le 10^9$。

解析

Update on 2025/8/11：同机房同学给出了一种极简做法，写在这里：

开始时，所有数的值之和为 $\displaystyle\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$。

记 $\text{highbit}(i)$ 为 $i$ 的二进制最高位的值，则 $Ans=\displaystyle\frac{n(n+1)}{2}-\sum_{i=1}^{n}\text{highbit}(i)$。

显然 $\displaystyle\sum_{i=1}^{n}\text{highbit}(i)=\sum_{j\ge 0,2^j\le n}\Big(\min(2^j,n-2^j\color{red}{+1})\times 2^j\Big)$。

然后算这个式子就可以了，时间复杂度 $\mathcal{O}(\log n)$。

Part 1

我们显然不能直接暴力枚举。

定义“初始数字”为在所有操作开始前，写在黑板上的数字。我们注意到，处理时，任意两个初始数字不互相影响。也就是说，我们可以假设开始前黑板上只有一个数字 $i$（$1\le i\le n$），记此时最终的 $cnt$ 为 $cnt_i$，则 $Ans=\displaystyle\sum_{i=1}^{n}cnt_i$。

Part 2

我们思考一下求 $cnt_i$ 的过程到底是在干什么。设当前 $i=x$。

我们实际在干这么一件事：

• 维护一个权值 $w$，初始 $w=2^0$（即 $1$）。
• 重复执行如下操作：
• • 如果 $x=1$，那么结束整个流程；
• • 否则，$cnt\leftarrow cnt+(x\bmod 2)\times w$，然后 $x\leftarrow\lfloor\frac{x}{2}\rfloor$，$w\leftarrow w\times 2$（也就是将 $x$ 右移一位，将 $w$ 左移一位）。

容易发现，在第 $j$ 次操作中，$w=2^{j-1}$，$(x\bmod 2)$ 的值对应初始 $x$ 中 $2^{j-1}$ 位置的值。这个结论在正解中有用，先记着。

这样我们就有时间复杂度 $\mathcal{O}(n\log n)$ 的做法了，但这还不够。

Part 3

我们把上面的过程改一下，不是枚举数而是枚举二进制位。

根据 Part 2 中我们得到的结论，我们容易得到：$2^{j-1}$ 位置对最终答案的贡献为 $(cnt_A-cnt_B)\times 2^{j-1}$，其中：

• $cnt_A$ 是 $[1,n]$ 中的所有整数中，二进制位中 $2^{j-1}$ 位置为 $1$ 的数的个数；
• $cnt_B$ 是 $[1,n]$ 中的所有整数中，以 $2^{j-1}$ 为二进制最高位的数的个数。

如何快速求出 $cnt_A$ 与 $cnt_B$ 呢？

我们记 $q=\displaystyle\bigg\lfloor\frac{x}{2^j}\bigg\rfloor$，$r=x\bmod 2^j$。

显然，如果 $q=0$，那么 $n$ 的最高位一定是 $2^{j-1}$。根据上面的式子，显然 $2^{j-1}$ 位置对答案的贡献为 $0$，因此我们只需循环到最大的 $j$ 使得 $2^j\le n$ 即可。

先记一个小结论：

$[1,2^j-1]$ 中有且只有 $[2^{j-1},2^j-1]$ 的 $2^{j-1}$ 位置为 $1$。

有了上面的限制，我们计算出的 $q$ 一定是正数，且显然有 $cnt_B=2^{j-1}$（理由：$2^j\le n$ 和上面的小结论）。我们只需考虑如何计算 $cnt_A$ 即可。

$cnt_A$ 分布在两部分中：被 $2^j$ 整除的部分（由 $q$ 代表）和整除完剩余的部分（由 $q$ 代表）。

• 对于每个整除产生的 $2^j$ 大小的块，根据上面的小结论，每个块对 $cnt_A$ 有恰好 $2^{j-1}$ 的贡献，因此这部分的总贡献就是 $q\times 2^{j-1}$；
• 对于剩余部分，还是根据上面的小结论，只有 $\ge 2^{j-1}$ 的部分会对 $cnt_A$ 有贡献，因此这部分的总贡献就是 $\max(0,r-2^{j-1}+1)$。

所以 $cnt_A=q\times 2^{j-1}+\max(0,r-2^{j-1}+1)$。

也就是说，第 $2^{j-1}$ 位对答案产生的贡献为 $\Big((q-1)\times 2^{j-1}+\max(0,r-2^{j-1}+1)\Big)\times 2^{j-1}$。

整合一下：(完全展开形式）

$$Ans=\displaystyle\sum_{j\gt 0,2^j\le n}\Bigg(2^{j-1}\times\bigg(\Big(\big\lfloor\frac{n}{2^j}\big\rfloor-1\Big)\times 2^{j-1}+\max\Big(0,(n\bmod 2^j)-2^{j-1}+1\Big)\bigg)\Bigg)$$

显然每一位的贡献可以时间复杂度 $\mathcal{O}(1)$ 完成，于是我们成功地把最终的时间复杂度降到了 $\mathcal{O}(\log n)$。

AC Code

按最终的式子计算就可以了，所以不展示。

乘法一定一定开 long long！！！ 不长记性

后记

感谢您的阅读！若有不妥之处还请批评指正！

题目传送门

题目描述

数轴上有 $n$ 个定点，其中点 $1$ 位于原点，点 $i(i\ge 2)$ 位于数轴上表示数 $x_i$ 的位置（$x_i\lt x_{i+1}$）。

这条数轴上还有 $m$ 条线段，第 $i$ 条线段的中点位于数轴上表示数 $z_i$ 的位置（$z_i$ 单调递增），从中点到线段两端点的距离都为 $l$（本题中，所有线段的 $l$ 都相同）。

对 $m$ 条线段进行 $d$ 次操作，第 $i$ 次操作将中点位于 $p_i$ 的一条线段移动至数轴上另一处，使得移动后线段的中点位置为 $r_i$（$p_i\neq r_i$）。保证移动前存在符合要求的线段，且移动后不会有其他线段的中点与该线段重合。

对于 $i=1,2,...,d$，输出执行第 $i$ 次操作之前，$n$ 个定点中被至少一条线段覆盖的点的数量（位于端点也算）。你还需要输出所有操作都完成后，$n$ 个定点中被至少一条线段覆盖的点的数量。

数据范围：$2\le n,m\le 5\times 10^5$，$1\le d\le 5\times 10^5$，$1\le l\le 10^9$，$0\lt x_i\le 10^9$，$0\le z_i,p_i,r_i\le 10^9$。

分析

注意到，题面中的操作很像扫描线中的“求线段长度并”的操作。那我们不妨就用扫描线的思想解决这道题。

显然，存在题目给定的数轴这一维和时间这一维。时间这一维由于题目的条件不用多加处理，因此我们只需处理数轴这一维。

开一棵线段树，区间对应题目中的定点区间。每次增加或删除一条线段就等价于增加或减少一次区间覆盖。

区间覆盖对应的线段树上操作是：如果当前节点表示的区间被修改区间完全包含，就直接执行覆盖/去覆盖的指令。否则向下递归，然后 Push_up。具体操作为：

• 每个节点维护该节点被完整覆盖的次数 $k$（初始为 $0$）和被覆盖的位置的个数 $sum$（初始也为 $0$），覆盖时把 $k$ 加上 $1$，去覆盖时把 $k$ 减去 $1$。
• 修改后，如果 $k=0$，叶子结点的 $sum$ 修改为 $0$，其他节点的 $sum$ 修改为两子节点的 $sum$ 之和；如果 $k\gt 0$，各节点的 $sum$ 修改为节点所对应的区间长度。(如果不注意加粗部分那么恭喜你数组越界了）

一个节点的 Push_up 的操作与修改后的操作一致。

初始时，二分（或使用 lower_bound 和 upper_bound 找出）线段左右端点的位置，如果存在受影响的位置（端点未越界且区间存在/右端点在左端点右边），那么就将对应的连续区间进行覆盖就可以了。

执行操作时，先删除线段，再添加线段，操作细节同初始时的操作。不要忘记输出初始时和结束时的答案哦！

建立线段树的时间复杂度是 $\mathcal{O}(n)$，初始覆盖及所有操作的总时间复杂度为 $\mathcal{O}((m+d)\log n)$，对于 4s 的时间限制还是绰绰有余的。

参考代码

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

#define N 500007

int n,x[N];//由于 Seg 函数，需要把 n 定义在全局

struct qwq{int l,r,k,sum;}t[N<<2];//线段树
#define L(u) u<<1
#define R(u) u<<1|1

inline void build(int u,int l,int r){//建树
    t[u]={l,r,0,0};
    if(l<r){
        int mid=(l+r)>>1;
        build(L(u),l,mid),build(R(u),mid+1,r);
    }
}

inline void Push_U(int u){//更新 sum
    if(t[u].k) t[u].sum=t[u].r-t[u].l+1;//被完整覆盖过
    else t[u].sum=t[L(u)].sum+t[R(u)].sum;//没被完整覆盖过
}

inline void Modify(int u,int l,int r,int val){
    if(l<=t[u].l&&t[u].r<=r){//完全包含
        t[u].k+=val;
        if(t[u].l==t[u].r) t[u].sum=min(t[u].k,1)*(t[u].r-t[u].l+1);//注意对叶子的特判（WA+RE*2）
        else Push_U(u);
        return;
    }
    int mid=(t[u].l+t[u].r)>>1;
    if(l<=mid) Modify(L(u),l,r,val);
    if(r>mid) Modify(R(u),l,r,val);
    Push_U(u);//更新当前节点
}

int l;//由于 Seg 函数，需要把 l 定义在全局，但线段树相关操作中存在以 l 命名的变量，故定义在此处

inline void Seg(int pos,int val){//线段覆盖/去覆盖
    int pl=lower_bound(x+1,x+n+1,pos-l)-x;//对应的区间左端点
    int pr=upper_bound(x+1,x+n+1,pos+l)-x-1;//对应的区间右端点
    if(pl<=pr) Modify(1,pl,pr,val);//如果区间合法，那么修改
}//左右端点别写反！！！

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

    int m,d;
    cin>>n>>m>>d>>l;
    for(int i=2;i<=n;i++) cin>>x[i];
    build(1,1,n);//别忘了建树！！
    while(m--){
        int z;
        cin>>z;
        Seg(z,1);
    }
    cout<<t[1].sum<<'\n';//初始答案
    while(d--){
        int p,r;
        cin>>p>>r;
        Seg(p,-1),Seg(r,1);//先删后加
        cout<<t[1].sum<<'\n';//操作后答案
    }

    return 0;
}

感谢您的阅读！

题目传送门

题目描述

给定一个长为 $n$ 的自然数数列 $a$ 和一个正整数 $k$，问最少修改 $a$ 中的多少个整数（修改后必须也为整数）能使整个序列的所有长为 $k$ 的区间的元素和都为偶数。

数据范围：$1\le k\le n\le 10^6$，$0\le a_i\le 10^9$。

分析

首先，因为我们只关心结果的奇偶，所以我们可以直接将数列转为 $0/1$ 序列（所有数对 $2$ 取模），并将求和改为求异或和。

然后，我们注意到，这个数列中 $[i,i+k-1]$ 这个区间内元素的异或和与 $[i+1,i+k]$ 这个区间内元素的异或和相等（都为 $0$）。将两式异或，得到 $a_i\oplus a_{i+k}=0$，即 $a_i=a_{i+k}$。所以我们得到一个重要结论：修改后的序列中，下标模 $k$ 相等的位置上的数，奇偶性一定相同。

因此，我们可以计算序列中下标模 $k$ 相等的数中有多少个 $0$（偶数）和多少个 $1$（奇数）。设下标取模后的结果为 $r$（我的代码中 $r$ 取 $1$ 到 $k$），则 $cnt_{r,0}$ 表示这些数中偶数的个数，$cnt_{r,1}$ 类似（奇数的个数）。

这样，我们就将问题转化为了下面这样：

有一个长为 $k$ 的数列，第 $i$ 个位置上填 $0$ 会有 $cnt_{i,\color{red}1}$ 的代价，填 $1$ 会有 $cnt_{i,\color{red}0}$ 的代价（注意下标，是要改成目标数的数的个数，而非目标数的个数），且只能填 $0$ 或 $1$ 中的一个，不能不填。要求所有位上的数的异或和为 $0$，求最小总代价。

显然，我们可以 DP 解决。

设 $dp_{i,0}$ 表示第 $i$ 位填 $0$ 在以 $i$ 结尾的前缀中的最小总代价（$dp_{i,1}$ 类似，表示第 $i$ 位填 $1$），则根据异或运算的定义，我们可以很容易地得出：

$$dp_{i,0}=\max(dp_{i-1,0}+cnt_{i,1},dp_{i-1,1}+cnt_{i,0})$$

$$dp_{i,1}=\max(dp_{i-1,1}+cnt_{i,1},dp_{i-1,0}+cnt_{i,0})$$

特别地，当 $i=1$ 时，$dp_{1,0}=cnt_{1,1}$，$dp_{1,1}=cnt_{1,0}$。（如果你忘记了这条然后交了一发，你就会被 Test #1 给 hack 掉）

最后我们输出 $dp_{k,0}$ 就结束了。（如果下标采用 $0$ 到 $k-1$，请注意你的 DP 起终点和输出内容）

输入+处理 $cnt$ 数组的时间复杂度为 $\mathcal{O}(n)$，DP 的复杂度也为 $\mathcal{O}(n)$，所以完全没有问题！

代码的具体实现在上文中讲得很清楚，因此不展示。

感谢您的阅读！

题目传送门

题意简述

你有 $n$ 项工作要做，第 $i$ 项工作需要连续的 $d_i$ 天去完成（同一天只能完成一项工作），而且最后一天不得晚于 $t_i$。问在开始所有工作之前，你最多能休息多久？

数据范围：$1\le n\le 10^6$，$1\le d_i,t_i\le 10^9$。保证所有任务都能够按时完成。

解析

简单的贪心。

秉承“能拖就拖”的原则，我们先按截止时间降序排列这些任务，然后从前往后扫，同时维护一个值 $Ans$（根据数据范围，该值初始值应不小于 $10^9$）。

对于每个 $i$，执行下面这个式子：

$$Ans\leftarrow\min(Ans,t_i)-d_i$$

为什么？

首先第 $i$ 项工作需要在第 $t_i$ 天及之前完成，所以开始时间肯定不晚于 $t_i-d_i+1$。

如果即便拖延到极致但有工作已经占了第 $t_i$ 天，那么只能再往前推，推到最后一个没有工作的日子为止（第 $Ans$ 天）。

最后直接输出 $Ans$ 就可以了。

快排时间复杂度 $\mathcal{O}(n\log n)$，扫任务时间复杂度 $\mathcal{O}(n)$，可以通过本题。

代码实现过程已在上文中完整给出，因此不展示。

感谢您的阅读！

题目传送门

题意简述

给定一棵 $n$ 个节点的，以 $1$ 为根的有根树，请按升序输出所有满足下面要求的正整数 $k$：

• 这棵树可以被划分为 $k$ 个节点数目相同的连通块。

数据范围：$2\le n\le 3\times 10^6$。

解析

首先，我们需要找出可能成为连通块节点数目的所有正整数，记为 $d$。

显然，$d$ 必须是 $n$ 的因数。

如果将这部分的复杂度压缩至根号，不要忘记将数组排好序！！ 我不会告诉你我为什么要提醒这一条

然后，降序枚举 $d$（对于 $1$ 和 $n$ 我们可以不经判断直接输出），判断树可否分为若干大小都为 $d$ 的连通块。

方法使用贪心，具体实现如下：

• 对整棵树进行 DFS，同时维护布尔值 $Ans$（初始为 $1$）。对每个节点记录在其子树中且与该节点位于同一连通块的节点数，保存为 $sz$ 数组。为表述方便，记每个连通块的大小为 $sz_0$（与当次的 $d$ 相等）。
• 搜索到节点 $u$ 时，如果 $Ans=0$ 那么将 $sz_u$ 归零后返回（避免无用初始化）。
• 如果 $Ans=1$，搜索 $u$ 的每个子节点 $v$。
• 返回时：

  • 如果 $sz_u\gt sz_0$，那么将 $Ans$ 设为 $0$ 并返回；
  • 如果 $sz_u=sz_0$，那么直接返回；
  • 如果 $sz_u\lt sz_0$，那么将 $sz_{fa_u}$ 加上 $sz_u$ 并返回（$fa_u$ 为 $u$ 的父亲）。
  • 无论哪种情况，返回前必须将 $sz_u$ 设为 $0$。

• 整棵树搜完后，判断 $Ans$ 是否仍然为 $1$。若是，则 $\frac{n}{sz_0}$ 为答案。

接下来证明这种方法的正确性。

假设这是我们第一次割下来的，大小为 $sz_0$ 的块。如果我们不割它，那么显然没有别的解法。所以，有块，一定割。

再假设在一棵子树中能割的块都割完了，但剩下的大小大于 $sz_0$。显然，如果各个子节点还能割的话一定就割了，所以现在各个子节点的 $sz$ 值均小于 $sz_0$。我们不能抛下任意一棵子树（否则大小就不等于 $sz_0$ 了），所以此时一定无解。那么对于大小小于 $sz_0$ 的 $sz$ 值，我们只能选择把这个节点的剩余连通部分交给父节点去割。

所以每次验证 $d$ 是否可行都需要一次 $\mathcal{O}(n)$ 的 DFS。那么 $n$ 的正整数因数个数到底有多少呢？

这个答案有个相当宽松的上界，$2\sqrt{n}$。但在 $n\le 3\times 10^6$ 的条件下，较大的 $n$ 显然不可能达到这个值。事实上，题目范围内含有最多正整数因子的数为 $2\ 882\ 880$，含有 $336$ 个因子。而题目的时间限制是 10 秒，所以我们的算法肯定可以通过！（亲测，当 $n=10^3$ 时，$\mathcal{O}(n^3)$ 的区间 DP 关同步流甚至跑不到 500ms）

参考代码

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

#define _ 507
int d[_];//存n的因子

#define N 3000007

int cnt,head[N];
struct qwq{int v,nxt;}edge[N];//链式前向星存边
inline void AddE(int u,int v){
    edge[++cnt]={v,head[u]};
    head[u]=cnt;
}

bool Ans;//是否有解
int sz[N];//剩余块大小

inline void dfs(int u,int fa,int sz0){
    sz[u]++;//自己也得算
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        dfs(v,u,sz0);
        if(!Ans) {sz[u]=0;return;}//记得归零
    }
    if(sz[u]>sz0) {sz[u]=0;Ans=0;return;}//记得归零
    if(sz[u]==sz0) {sz[u]=0;return;}//记得归零
    sz[fa]+=sz[u];sz[u]=0;//记得归零
}

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

    int n,m=0;
    cin>>n;
    for(int i=2;i*i<=n;i++)//根号判因数
        if(n%i==0){
            d[++m]=i;
            if(i*i!=n) d[++m]=n/i;
        }
    sort(d+1,d+m+1);//如果根号判因数一定要记得sort！！
    for(int i=2,a;i<=n;i++) cin>>a,AddE(a,i);//父节点到子节点

    cout<<1<<' ';//显然
    for(int i=m;i;i--){
        sz[0]=0,Ans=1;dfs(1,0,d[i]);//d为连通块大小
        if(Ans) cout<<n/d[i]<<' ';//输出的为连通块个数
    }
    cout<<n<<'\n';//显然

    return 0;
}

感谢您的阅读！