给你两个数字x、y，每次可以对x在2进制下，任意的相邻的3个位置进行操作，使得中间的位置上的数字不变，两侧的两个位置上的数字交换。
问最少操作多少次，可以使得x变成y。
签到题，对奇数位和偶数位分类讨论即可。若x和y的奇数位和偶数位上1的数量不同，则无解；否则一定有解，且ans就是1的位置之差。
1mszs在计算ans的时候，枚举偶数位时，手误打成了odd.size()，然后WA了一发不知道为啥。lincong接手代码之后，找到问题并修正后AC。
有n堆石子，保证相邻两堆不等。A和B玩游戏，轮流从这n堆中，任意拿走一颗石子，但需要保证拿走第k堆的一颗石子后，第k堆的石子数量不能和它相邻的两堆相等。无法拿石子者输，问谁能赢？
显然，石子数量的单调性不会发生改变，所以能拿走的石子数量就是：保证序列单调性不变的前提下，尽量多的减少序列的值。
那么，我们只需找到序列的极小值和极大值的位置，先将所有的极小值都设为0，然后从极小值的位置开始向两边走，令每一个数等于前一个数+1，这样就可以在保证序列单调性不变的前提下，使得序列的值最小。
特殊地，极大值的位置会被走到2次，那么将极大值设为两次走到时的最大值即可。
最后，我们只需计算一下修改后的数列与原先的数列的差，这个差值就是能拿走的石子数num。如果num是奇数，则A赢，否则B赢。
给你n个数，每次操作可以让这n个数+1，问最少操作多少次，可以使得这n个数的gcd>1。
注意到，每次操作不会改变这n个数之间的差值，因此如果这n个数的gcd>1，那么它们的差值的gcd也必然>1。
因此，我们只需计算一下这n个数的差值的gcd，若gcd等于1，则无解（这n个数都等于1时除外）；若gcd>1，就枚举这n个数，用gcd的因子来计算操作次数，找到最小的那个即可。
代码如下：
ll ans=2e15,tot=0;
for(ll i=2;i*i<=p;i++)//p是这n个数的差值的gcd
if(p%i==0)
ys[++tot]=i,ys[++tot]=p/i;//ys数组记录gcd的因数
if(!tot) ys[++tot]=p;
for(int i=0;i<a.size();i++)//枚举这n个数
for(int j=1;j<=tot;j++)//枚举每一个因数
{
if(a[i]%ys[j]==0) ans=0;
else ans=min(ans,ys[j]-a[i]%ys[j]);//计算操作次数
}
特殊地，当这n个数全部相等时，如果这n个数都等于1，那么操作1次即可；如果这n个数都>1，那么无需任何操作。
由于H题从头调到尾都没能调出来，所以3题滚粗。
lincong补了AHL题。
给你两个长度一样的字符串s、t，构造一个字符串str，使得str与s对应位置字母不同的数量，等于str与t对应位置字母不同的数量（若有多个str满足题意，输出字典序最小的那个）。
一开始lincong以为是个简单的贪心，先将目标字符串全部置为a，然后从后向前替换，结果交上去WA了才意识到事情并没有那么简单。
后来手算了几组数据，发现这种情况没有考虑到：
aab
bba
如果直接贪心的话，会输出aca，但是显然正确答案是abc。相当于本来t串中的a就少，还要扔掉那个a换成c，但是接下来再给一个b就可以直接抹平s和t的差距，同时还能保证字典序最小。
考虑这种情况的存在，lincong就想着是不是得从前向后替换，然后发现不知怎样判断一个位置是否应该修改，最后一直调到VP结束也没能调出来。
VP结束后，lincong补题时发现，确实是应该正着构造，但是得开一个sum数组来记录每个位置向后最多可以调整的数量，这样就可以很好地解决VP时遇到的问题。
具体来说，我们正向构造，对于每一个位置，在保证后面可以调整回来的前提下（通过sum数组来判断），优先考虑a，接着考虑b，最后考虑其他字母。
代码如下：
string work(string s,string t)
{
string q;//构造的字符串q
int n=s.size();
sum[n]=0;
for(int i=n-1;i>=0;i--)
{
sum[i]=sum[i+1];
if(s[i]!=t[i]) sum[i]++;//计算每个位置最多可以调整的数量
}
int cnt=0;//same(q,s)-same(q,t),构造第i位的时候必须保证abs(cnt)<=sum[i+1]
for(int i=0;i<n;i++)
{
if(s[i]==t[i]||abs(cnt)<sum[i+1])//s与t字符相同or后面可以调整回来
{
q+='a';
if(s[i]=='a'&&t[i]!='a') cnt++;//与s相同的变多了,并且可以保证abs(cnt)<=sum[i+1]
if(s[i]!='a'&&t[i]=='a') cnt--;//与t相同的变多了,并且可以保证abs(cnt)<=sum[i+1]
continue;
}
char c=min_char(s[i],t[i]);//计算与s[i]和t[i]都不相同的第一个字符
if(c=='a')
{
if(abs(cnt)<=sum[i+1]) q+='a';//后面可以调整回来,优先考虑a,此时cnt不发生变化
else if(cnt>0) q+=t[i],cnt--;//后面调整不回来了,且现在与s相同的更多,所以放一个和t一样的
else q+=s[i],cnt++;//后面调整不回来了,且现在与t相同的更多,所以放一个和s一样的
}
else if(c=='b')
{
if((s[i]=='a'&&cnt<sum[i+1])||(t[i]=='a'&&cnt>-sum[i+1]))//后面可以调整回来,优先考虑a
{
q+='a';
if(s[i]=='a') cnt++;
else cnt--;
}
else if(abs(cnt)<=sum[i+1]) q+='b';//后面可以调整回来,接着考虑b
else//后面调整不回来了
{
if(s[i]=='a') q+=t[i],cnt--;//此时一定是cnt>sum[j+1]
else q+=s[i],cnt++;//此时一定是cnt<-sum[j+1]
}
}
else
{
if((s[i]=='a'&&cnt<sum[i+1])||(t[i]=='a'&&cnt>-sum[i+1]))//后面可以调整回来,优先考虑a
{
q+='a';
if(s[i]=='a') cnt++;
else cnt--;
}
else if((s[i]=='b'&&cnt<sum[i+1])||(t[i]=='b'&&cnt>-sum[i+1]))//后面可以调整回来,接着考虑b
{
q+='b';
if(s[i]=='b') cnt++;
else cnt--;
}
else q+=c;//后面调整不回来了
}
}
return q;
}
给定两个线段，颜色分别为白色和黑色，现在问你在二维平面坐标系中，只能看到白色线段的区域面积是多少？
计算几何，主要是分类讨论，情况较多，需要注意优先级。
首先，根据两条线段是否相交，可以分出两种情况：
一、两条线段相交，此时可分为两种情况：
1.交点在端点上，此时ans为inf。
2.交点不在端点上，此时ans为0。
二、两条线段不相交，此时又可分为两种情况：
1.黑色线段与白色线段的延长线相交，此时ans为0。
2.黑色线段与白色线段的延长线不相交，此时取两个线段端点之间的连线，根据连线有无交点再分成两种情况：
(1)有交点。若交点在白色线段一侧，则ans为该点与白色线段构成的三角形的面积；若交点在黑色线段一侧，则ans为inf。
(2)无交点，即连线平行，此时ans为inf。
特殊地，当白色线段退化成点时，ans为0；当黑色线段退化成点时，ans为inf。
有两个序列a、b，将他们合并成一个序列c，要求是不打乱a、b序列原来的相对顺序，且使得i * ci之和最小。
若a和b均为单调不增的序列，那么用类似归并排序的方式，每次取a和b中的较大值，贪心地合并即可。
因此，现在的目标是将a和b转化为单调不增的序列，这里采取的方法是自我合并。
显然，我们可以将连续的一段进行合并，那么该如何判断一个数应该合并到前面，还是后面呢？
假设x、y已经合并，那么考虑一个独立的数z，若z向前合并，则形成了xyz；若z向后合并，则形成了zxy，这两种合并方式的差为x+y-2z。
那么，我们只需比较z和(x+y)/2的大小即可，若z较大，那么z应该向前合并；否则z应该向后合并。
将这一理论推广到整个序列，我们只需比较相邻两个”块“的均值，若后面的”块“的均值较大，则应该合并到前面的”块“中（一开始”块“的数量为n，且所有”块“的大小均为1）。这样合并之后，我们就可以保证a、b序列单调不增，且满足i * ci之和最小。
具体见代码：
struct node
{
int sum,siz;
bool operator>(const node x)const
{
return sum*x.siz>siz*x.sum;
}
node operator+(const node x)const
{
return (node){sum+x.sum,siz+x.siz};
}
};
int a[maxn],b[maxn];
node s1[maxn],s2[maxn];
int work()
{
int n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
int tot1=0,tot2=0;
for(int i=1;i<=n;i++)
{
s1[++tot1]=(node){a[i],1};
while(tot1>1&&s1[tot1]>s1[tot1-1])
s1[tot1-1]=s1[tot1-1]+s1[tot1],tot1--;
}
for(int i=1;i<=m;i++)
{
s2[++tot2]=(node){b[i],1};
while(tot2>1&&s2[tot2]>s2[tot2-1])
s2[tot2-1]=s2[tot2-1]+s2[tot2],tot2--;
}
int i=1,j=1,k=1,ans=0;
int pos1=1,pos2=1;
while(i<=tot1&&j<=tot2)
{
if(s1[i]>s2[j])
{
int l=pos1,r=pos1+s1[i].siz-1;
while(l<=r) ans+=a[l++]*k,k++;
i++,pos1=r+1;
}
else
{
int l=pos2,r=pos2+s2[j].siz-1;
while(l<=r) ans+=b[l++]*k,k++;
j++,pos2=r+1;
}
}
while(i<=tot1)
{
int l=pos1,r=pos1+s1[i].siz-1;
while(l<=r) ans+=a[l++]*k,k++;
i++,pos1=r+1;
}
while(j<=tot2)
{
int l=pos2,r=pos2+s2[j].siz-1;
while(l<=r) ans+=b[l++]*k,k++;
j++,pos2=r+1;
}
return ans;
}