|
一，思路首先，我们可以注意到： $t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$
该题解待审........................................................................(剩余 242 个中英字符)
题目4320 bitset(位集)
2026-02-28 17:24:20
|
||||||||||||||||
|
|
以下提供三种模板供您选择，发布题解时请删除模板中提示语等多余文字。【模板一：多解法题解模板】一、 解法概览
二、 详细解析解法一：[名称，如：暴力搜索]
[简要说明核心思路]
[请点击上面 解法二：[名称，如：动态规划]
[简要说明核心思路]
[请点击上面 解法三：[名称，如：贪心算法]
[简要说明核心思路] [策略描述] [简要证明或说明]
[请点击上面 三、 对比总结
[各解法在时间和空间上的表现对比] 四、 推荐题目
【模板二：思维演进题解模板】一、 初始思路（第一反应）
[描述最初想到的方法] [分析该方法的缺陷] [基于缺陷提出的改进思路] 二、 优化过程版本1.0：基础实现
[描述基础版本的思路]
[请点击上面 [分析性能瓶颈] 版本2.0：算法优化
题目4320 bitset(位集)
2026-02-28 17:17:55
|
||||||||||||||||
|
|
一、 初始思路（第一反应）
[线段覆盖模板] 二、 优化过程
首先我们会发现$2$个性质：
2:此题即为求解小A可以到达的最大的线段中包含的关 该题解待审........................................................................(剩余 251 个中英字符)
题目3878 [省选 2023]火车站
2026-02-28 17:14:26
|
||||||||||||||||
|
|
首先：暴力！40分略，大家都会 但是 暴力的另一个用处：打表！为什么打表呢？因为$2≤n,k≤10^{12}$。 所以时间是O(1)。 要找数学规律。 打表：（输出的是没有被淘汰的人）
6 2 1 2 3 4 5 6 2 4 6 4
8 3 1 2 3 4 5 6 7 8 2 3 5 6 8 3 5 8 5 8 8
注意到：每次剩下人中第一个人是有规律的，而且到最后一定只剩一个人（也是当前剩余人中的第一个），更重要的是，这个人的编号就是我们求的答案！！!
设每次的第一个人依次是$x_1$,$x_2$,$x_3$,......,$x_m$。m是轮数。 则有$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$。 （这个需要自己找） 于是初始$x_1=1$ ，然后往后找。
#include<iostream>
using namespace std;
long long ans,n,k;//ans就是x
int main(){
scanf("%lld%lld",&n,&k);
ans=k;//前k个是依次作开头的，所以从k开始也一样
while(ans+(ans+k-2)/(k-1)<=n){
ans+=(ans+k-2)/(k-1);//套公式
}
printf("%lld",ans);//最后的开头就是最后一个人
return 0;
}
嗯。于是就过关了！But，洛谷上有个大佬出了个Hack，几乎把当时所有AC干成UAC了，这份代码也不例外。就是这个
1000000000000 10000000000
999999999907
会超时。 分块优化：于是我们继续想：每一轮都是一个人一个人淘汰的，所以我们对这一点进行优化…… 因为$x_i+\lceil \frac{x_i}{k-1} \rceil=x_{i+1}$ ，所以按$k-1$分块（$k-1$分母，按$x_i$与$k-1$的关系分块，这样每个块的跳跃次数都是一样的)，批量跳跃被淘汰数。
将整个数域$[1,n]$按每块$k−1$个数划分成若干块： 第 $1$ 块：$[1,k−1]$ 第 $2$ 块：$[k,2(k−1)]$ 第 $id$ 块：$[(id−1)(k−1)+1,id(k−1)]$ 同一区块内的被淘汰数，递推的步长$\lceil \frac{x_i}{k-1} \rceil$是固定的（等于块编号 $id$），因此可以批量计算该块内的所有被淘汰数，一次跳跃，无需逐个计算。
在第$id$块中，$\lceil \frac{x_i}{k-1} \rceil$（$x$ 属于第 $id$ 块），因此递推式简化为：$x_{next}=x+id$ 这意味着在第 $id$ 块中，被淘汰数是以$id$为步长递增的，可以直接计算出该块内最后一个被淘汰数，一次跳到下一块，大幅减少计算次数。
正片开始#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll n,k;
ll x=1,last_val;//x为当前待检查的被淘汰数，初始为第一个被淘汰数x1=1
//last_val是当前块中最后被淘汰的数（答案），不断更新，最终输出
int main(){
scanf("%lld%lld",&n,&k);
while(x<=n){
ll id=(x-1)/(k-1)+1;//是当前x所在块的编号
ll end=min(n,(k-1)*id);//当前块的末尾
x+=((end-x)/id+1)*id;//直接跳到当前块的末尾或跳出当前块
last_val=x-id;//计算当前块最后一个淘汰的数，也可能是所有之中的最后一个淘汰的数（即答案）
}
printf("%lld",last_val);
return 0;
}
OK
题目4322 [常州市赛 2025] 金币
评论
2026-02-28 14:42:32
|
||||||||||||||||
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19651912
大意 现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件： $$1 \leq i + j \leq R,i \geq j \geq 1$$ 使对方无法操作者即为胜者。
思路 我们首先考虑这个玩意的 $SG$ 函数，太坑了，你们可以手动的模一下。 我们来假设 $R = 5$ 的情况，首先 $SG(0) = 0$，$SG(1) = 1$，$SG(2) = 2$，但是我们发现，当 $i = 3$ 的时候，能取的只有 $1, 2$，取这两坨只会把必胜态留给对面，那这个时候的 $SG(3) = 0$，那再看 $SG(4) = 1$，然后 $SG(5) = 0$，当 $i \ge R$ 的时候 $SG(i) = 0$，这是显然的。 我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 $i \le \lfloor \frac{R}{2} \rfloor$ 的时候，$SG(i) = i$，实际上就是简单的 Nim 博弈，但是一旦到达 $\lfloor \frac{R}{2} \rfloor + 1$，则 $SG(\lfloor \frac{R}{2} \rfloor + 1) = 0$，这是巧合吗？显然不是，但是只有这一个转折点吗？ 我赛时最初的思路是 $SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}$，可是真的对吗？不难发现当 $R = 100$ 时，转折点在 $\lfloor \frac{R}{2} \rfloor + 1 = 51$，但是当 $i = 76$ 的时候呢？我们只能取 $24$，也就是只能取到 $[52, 75]$ 这个区间，而这个区间的 $SG$ 是 ${1, 2, 3, \cdots 24}$，所以 $SG(76) = 0$，所以我刚刚的结论是错误的，继续向后模拟，发现在 $SG(89) = 0$，不难发现，什么时候等于 $0$ 呢，我们设 $pos$ 表示上次的位置，那么有： $$nxt = \lfloor \frac{pos + R}{2} \rfloor + 1$$ 这个说明了，我们的 $SG$ 是一段一段的，最多有 $\log$ 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，$\mathcal{O}(1)$ 处理询问即可。
代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 64;
ll R, lst[MAXN], val[MAXN];
int cnt;
inline ll Xor(ll n){
switch(n % 4){
case 1:
return n - 1;
case 2:
return 1;
case 3:
return n;
default:
return 0;
}
}
void init(ll x){
cnt = 0;
lst[0] = 0;
ll now = x / 2 + 1;
val[0] = Xor(now);
while(now < x){
lst[++ cnt] = now;
ll nxt = (now + x) / 2 + 1;
val[cnt] = val[cnt - 1] ^ Xor(nxt - now);
now = nxt;
}
}
ll ask(ll p){
int idx = upper_bound(lst, lst + cnt + 1, p) - lst - 1;
return (idx ? val[idx - 1] : 0) ^ Xor(p - lst[idx] + 1);
}
int main(){
// freopen("orange.in", "r", stdin);
// freopen("orange.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
int T; cin >> T;
while(T --){
string op; cin >> op;
if(op == "change"){
cin >> R; init(R);
}
else{
int n; cin >> n;
ll ans = 0;
while(n --){
ll l, r; cin >> l >> r;
ans ^= ask(r) ^ ask(l - 1);
}
cout << (ans ? "1" : "0");
}
}
return 0;
}
题目4321 这是一道橙题
 4
评论
2026-02-28 13:32:57
|
||||||||||||||||
|
|
更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19648636
大意 区间加，求 $a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$ 的值。
思路 对于这个指数塔，非常逆天，我们首先想到的肯定的是与降幂有关的内容，也就只有欧拉定理了，由于 $p$ 并非是质数，我们需要用扩展欧拉定理，那么什么是欧拉定理和扩展欧拉呢？ $\varphi(n)$ 就表示小于等于 $n$ 与 $n$ 互质的数的个数，$\varphi(1) = 1, \varphi(p) = p - 1$，这里的 $p$ 是质数。那么 $\phi(n)$ 应该怎么算呢？我们由素数分解定理，就可以有这样的公式： $$n \prod_{p | n} (1 - \frac{1}{p})$$ 这个过程我们是可以用线性筛预处理这个 $\varphi(n)$ 的。 好的，预处理讲完了，接下来讲欧拉定理，当 $\gcd(a, m) = 1$，那么 $a ^ {\varphi(m)} \equiv 1 \pmod m$，这个在模数为质数的时候就可以快速降幂，但是要是不是质数呢？没事，我们有扩展欧拉定理，其内容如下： $$a ^ b \equiv \begin{cases} a ^ {b \pmod{\varphi(m)}} & \gcd(a, m) = 1 \\ a ^ b & \gcd(a, m) \neq 1, b < \varphi(m) \\ a ^ {b \pmod{\varphi(m)} + \varphi(m)} & \gcd(a, m) \neq 1, b \ge \varphi(m) \end{cases} \pmod{m}$$ 好了，知道了这些，我们回到这个题目，对于这个指数塔，其指数一直取 $\varphi$ 显然最后会变成 $1$，那么要取多少次呢？我们想想对于 $\varphi(2 ^ k)$ 来说，其等于 $2 ^ {k - 1}$，对于质数是 $p - 1$，其如果是质数就减去一变成偶数，然后就会很快变小。 那么我们这个题直接写递归的话，递归层数最多就是 $\log$ 的层级，我们为了维护区间加和单点查询，我们直接用个树状数组维护即可，在递归的过程中，不断判断模数是否为 $1$，注意快速幂的地方，也要改一下。
代码
#include<iostream>
using namespace std;
#define int long long
const int MAXN = 2 * 1e7 + 5;
int a[MAXN], n, m;
int pri[MAXN], phi[MAXN], tot = 0;
int sum[MAXN];
bool vis[MAXN];
void init(){
phi[1] = 1;
for(int i = 2;i < MAXN;i ++){
if(!vis[i]){
phi[i] = i - 1;
pri[++ tot] = i;
}
for(int j = 1;j <= tot && i * pri[j] < MAXN;j ++){
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
// for(int i = 1;i < 5;i ++){
// cout << phi[i] << ' ';
// }
}
int lowbit(int x){
return x & -x;
}
void add(int x, int k){
while(x <= n){
sum[x] += k;
x += lowbit(x);
}
}
int ask(int x){
int res = 0;
while(x){
res += sum[x];
x -= lowbit(x);
}
return res;
}
int qpow(int a, int b, int p){
int res = 1;
bool flag = 0;
if(a >= p){
flag = 1;
a %= p;
}
while(b){
if(b & 1) res = res * a;
if(res >= p){
res %= p;
flag = 1;
}
a = a * a;
if(a >= p){
a %= p;
flag = 1;
}
b >>= 1;
}
return flag ? res + p : res;
}
int solve(int l, int r, int p){
int val = a[l] + ask(l);
if(p == 1) return 1;
if(l == r){
if(val >= p) return val % p + p;
else return val;
}
int cnt = solve(l + 1, r, phi[p]);
return qpow(val, cnt, p);
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
init();
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i <= m;i ++){
int op, l, r, x;
cin >> op >> l >> r >> x;
if(op == 1) add(l, x), add(r + 1, -x);
else cout << solve(l, r, x) % x << '\n';
}
return 0;
}
题目4228 [Ynoi Easy Round 2016] Nephren Ruq Insania
4
评论
2026-02-28 13:31:34
|