[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZZvR6qJU-1639543248823)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639452312575.png)]
题意：
输出所有的二元组
<
a
i
,
a
j
>
思路：
可能这道题对于位运算大师没啥必要写，但我还是想记一下
只有两种情况， a i a_i ai 和 a j a_j aj 该位上都为 1 1 1 或者都为 0 0 0 才能满足限制条件。
如果均为 0 0 0 ，说明该位不存在，所以这种情况不存在
如果均为 1 1 1 ，说明此时 a i & a j > a i ⨁ a j a_i & a_j > a_i bigoplus a_j ai&aj>ai⨁aj ，之后取什么数都没关系了。并且在没有前导 0 0 0 的情况下（说人话就是正常情况），第一位必然均为 1 1 1 。
也就是说，如果两个数转化为二进制后，位数相同，这样首位均为 1 1 1 ，就能满足限制条件。如果位数不同，首位一个为 1 1 1 一个为 0 0 0 。这样第一位就不满足限制条件，直接舍弃。
题目转化为了求位数相同的对的个数。
ll n;
ll a[MAXN];
void solve()
{
//输入数据
n=read();
rep(i,1,n) a[i]=read();
//求二进制位数
rep(i,1,n)
{
ll tmp=a[i];
ll cnt=0;
while(tmp)
{
cnt++;
tmp/=2;
}
a[i]=cnt;
}
//排序后计算对数
sort(a+1,a+1+n);
ll r=1,l=1;
ll ans=0;
while(r<=n)
{
while(a[r]==a[l]&&r<=n) r++;
ans=ans+(r-l)*(r-l-1)/2;
l=r;
}
cout<
组合数+差分维护（数据结构）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C7aGludw-1639543248824)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639453012857.png)]
题意：
一共有
n
n
n 盏灯。每盏灯
a
i
a_i
ai 都有自己的开启时间
l
i
l_i
li 和
r
i
r_i
ri 。求有多少种方案，使得有
k
k
k 盏灯正好在某一时刻同时亮着。
思路：
最朴素的暴力。一次次枚举每盏灯的起始时间，在对应区间上加上他的贡献
1
1
1 。如果在某个点
i
i
i 使得
s
u
m
[
i
]
≥
k
sum[i] geq k
sum[i]≥k ，那么这盏灯对答案的贡献就累加
C
s
u
m
[
i
]
−
1
k
−
1
C_{sum[i]-1}^{k-1}
Csum[i]−1k−1 。
可是这样空间需要开
1
e
9
1e9
1e9 ，时间复杂度最坏情况下是
O
(
n
2
)
O(n^2)
O(n2) ，考虑进行优化。
需要用到区间求和，可以考虑使用差分维护。
差分数组的前缀和就是正常数组的端点值。对于本题，每次
[
l
,
r
]
[l,r]
[l,r] 的贡献
+
1
+1
+1 ，在差分中即可表示为
a
[
l
]
+
1
a[l]+1
a[l]+1 和
a
[
r
+
1
]
−
1
a[r+1]-1
a[r+1]−1 。因为需要求前缀和，因此必须保证数组是有序的。
这样左端点值为
1
1
1 ，右端点值为
−
1
-1
−1 ，然后将这两个新的二元组push到差分数组中。然后先根据端点的下标进行升序排序，再根据端点的值进行升序排序。（若降序排序会导致重复计算吧）。这样即可保证前缀和计算正确并且方案数的计算是不重不漏的。
接着扫一遍差分数组。定义一个变量
n
o
w
now
now 表示
[
1
,
i
]
[1,i]
[1,i] 的前缀和。如果当前点权为
1
1
1 表示有一盏新的灯亮起，那么就要计算他对答案的贡献
C
n
o
w
k
−
1
C_{now}^{k-1}
Cnowk−1 ；如果点权为
0
0
0 ，说明某一盏灯灭了，不统计贡献。接着维护前缀和。
struct node
{
ll id;
ll val;
}a[MAXN<<1];//差分
bool cmp(node a,node b)
{
if(a.id==b.id) return a.val
差分+思维(这场的出题人是多喜欢差分QAQ)
阿巴阿巴，是昨天那道求波峰波谷的 $hard $ $version $ 。新增了
q
q
q 次操作，调换
a
[
l
]
a[l]
a[l] 和
a
[
r
]
a[r]
a[r] 。对于每组样例，输出
q
+
1
q+1
q+1 次不同序列的最大战力。
这么看好像我的写法不是歪解，因为这个dp写不了
这样的差分太妙了太妙了太妙了太妙了
继续回到之前波峰波谷的思路上来，其实这就是一个求差分的过程。
以 1 2 5 4 3 6 7 这组样例来进行解释
差分数组
b
[
i
]
b[i]
b[i] 即可表示为 1 1 3 -1 -1 3 4
5-3+7 用差分的形式即可表示为
∑
i
=
1
3
b
[
i
]
−
∑
i
=
1
i
=
5
b
[
i
]
+
∑
i
=
1
7
b
[
i
]
sum_{i=1}^3{b[i]}-sum_{i=1}^{i=5}{b[i]}+sum_{i=1}^7{b[i]}
∑i=13b[i]−∑i=1i=5b[i]+∑i=17b[i]
化简即为
b
[
1
]
+
b
[
2
]
+
b
[
3
]
+
b
[
5
]
+
b
[
7
]
b[1]+b[2]+b[3]+b[5]+b[7]
b[1]+b[2]+b[3]+b[5]+b[7] ，即减去那些差分数组值为负数的情况。
因为最后一部分必然为波峰，一共有奇数个累加式相加，结合上面的例子应该能想清楚为什么是这个结果吧
如果答案由各段差分数组的值来累加得到，那么调换后就方便维护了。
每次先减去这两个位置上的数在差分意义上对答案的贡献（正数贡献即为本身，负数无贡献）；再加上调换位置后两个位置上的数在差分意义上对答案的贡献。
一共是
4
4
4 段，分别为
a
[
l
]
−
a
[
l
−
1
]
,
a
[
r
]
−
a
[
r
−
1
]
,
a
[
l
+
1
]
−
a
[
l
]
,
a
[
r
+
1
]
−
a
[
r
]
a[l]-a[l-1],a[r]-a[r-1],a[l+1]-a[l],a[r+1]-a[r]
a[l]−a[l−1],a[r]−a[r−1],a[l+1]−a[l],a[r+1]−a[r] 。
当
r
=
l
+
1
r=l+1
r=l+1 时，
a
[
l
+
1
]
−
a
[
l
]
a[l+1]-a[l]
a[l+1]−a[l] 和
a
[
r
]
−
a
[
r
−
1
]
a[r]-a[r-1]
a[r]−a[r−1] 其实是同一段，会重复计算。其实重复计算也没什么，因为后面也会重复加上他的贡献，但是因为贡献和正负有关，调换位置后正负又会变化，所以必须特判。
ll n,q;
ll a[MAXN];
ll ans;
void init()
{
ans=0,a[0]=0,a[n+1]=0;
}
void solve()
{
n=read(),q=read();
rep(i,1,n) a[i]=read();
init();
rep(i,1,n)//以差分的形式计算答案
{
ans+=max(a[i]-a[i-1],0ll);
}
cout<
伪博弈（水）
不放题面，又臭又长。
题意：
给出一个位数为
n
n
n 的数字。轮到
A
l
i
c
e
Alice
Alice 时标记奇数位上的数字 ，轮到
B
o
b
Bob
Bob 时标记偶数位上的数字。这样一直标记持续到还剩最后一个数。如果最后一个数为奇数，
A
l
i
c
e
Alice
Alice 获胜；如果是偶数，
B
o
b
Bob
Bob 获胜。
思路：
如果长度为奇数，最后一个被标记的数必然是奇数位上的数。只要这个未被标记数是奇数，
A
l
i
c
e
Alice
Alice 就能获胜。只要
A
l
i
c
e
Alice
Alice 能够保证留下一个奇数，
A
l
i
c
e
Alice
Alice 就能获胜。只要奇数位上有一个奇数，
A
l
i
c
e
Alice
Alice 就可以把它保留到最后并获胜。
长度为偶数的情况用
B
o
b
Bob
Bob 推类似。
char s[MAXN];
void solve()
{
//Raze 先手 奇数位置 ；Breach 后手 偶数位置
ll n,tmp;
n=read();
ll cnt1=0,cnt2=0;
cin>>s+1;
rep(i,1,n)
{
tmp=s[i]-'0';
if((i&1)&&(tmp&1)) cnt1++;
else if(!(i&1)&&!(tmp&1)) cnt2++;
}
int ans;
if((n&1)&&cnt1>0)
{
ans=1;
}
else if((n&1)&&cnt1==0)
{
ans=2;
}
else if(!(n&1)&&cnt2>0)
{
ans=2;
}
else if(!(n&1)&&cnt2==0)
{
ans=1;
}
debug(ans);
}
傻逼结论题
题面又臭又长并且题意不清，只放张图。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DCjFkoDT-1639543248824)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639469007028.png)]
这样的东西被叫做楼梯。可以看出这个楼梯的大小为
7
7
7 ，由
7
7
7 个正方形组成。
如果一个楼梯的大小为
m
m
m ，并且正好能由
m
m
m 个正方形组成，我们称之为完美阶梯。
现给出
n
n
n 个 大小为
1
×
1
1 times 1
1×1 的正方形，问通过这些正方形最多能够组成多少个 不同 的完美阶梯。
思路：
傻逼结论题。
大小为
1
,
3
,
7
,
15......
1,3,7,15......
1,3,7,15...... 的阶梯是构成完美阶梯的充分条件。
可以把一个完美阶梯看成三部分。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-n946BnPY-1639543248825)(C:UsersADguyAppDataRoamingTyporatypora-user-images1639469484935.png)]
设上一块完美阶梯的大小为
k
k
k 。则根据图显然可以得到当前这块完美阶梯的大小为
2
×
k
+
1
2times k+1
2×k+1
三部分组成的阶梯数量为
k
+
k
+
1
=
2
×
k
+
1
k+k+1=2times k+1
k+k+1=2×k+1 ，因此可以证明这是一块完美阶梯。
那么就枚举这些情况并计数就好了。
void solve()
{
ll n;
n=read();
int ans=0;
for(ll i=1;i*(i+1)/2<=n;i=i<<1|1)
{
ans++;
n-=(i+1)*i/2;
}
cout<
imes k+1$
三部分组成的阶梯数量为
k
+
k
+
1
=
2
×
k
+
1
k+k+1=2times k+1
k+k+1=2×k+1 ，因此可以证明这是一块完美阶梯。
那么就枚举这些情况并计数就好了。
void solve()
{
ll n;
n=read();
int ans=0;
for(ll i=1;i*(i+1)/2<=n;i=i<<1|1)
{
ans++;
n-=(i+1)*i/2;
}
cout< 
