E. 双生双宿之错

题目简介：

给定一个数组，每次操作可以使得一个元素加1或者减1，问最小操作几次可以变成双生数组。

双生数组：元素种类数为2、且出现次数相同。

思路：

首先来了解一下中位数定理，即数轴上的一组数字到该组数字中位数的距离和最小

引申到本题，我们只需要将数组排序，将前半部分元素变成前半部分的中位数，后半部分元素变成后半部分的中位数。注意需要特判这两个中位数相等的情况，解决方案是要么将前半部分变成中位数减1，要么将后半部分变成中位数加1，枚举这两种方案分别统计取最优。

#include<bits/stdc++.h>
#define LL long long
#define N 100010
using namespace std;
int t,n,a[N];
LL check(int mid1,int mid2)
{
    LL i=1,cnt=0;;
    for(i;i*2<=n;i++)
        cnt+=abs(a[i]-mid1);
    for(i;i<=n;i++)
        cnt+=abs(a[i]-mid2);
    return cnt;
}
int main()
{
    cin>>t;
    while(t--)
    {
        LL ans=INT_MAX;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        int mid1,mid2;                //mid1为前半部分中位数，mid2为后半部分中位数
        if(n%4==0)                    //对于中位数的求法分类
            mid1=(a[n/4]+a[n/4+1])/2,mid2=(a[n/4+n/2]+a[n/4+n/2+1])/2;
        else
            mid1=a[(n/2+1)/2],mid2=a[((n/2+1)/2)+n/2];
        if(mid1==mid2)                 //当中位数相同时，枚举两种方案求最优解
        {
            ans=check(mid1-1,mid2);
            ans=min(ans,check(mid1,mid2+1));
        }
        else
            ans=check(mid1,mid2);
        cout<<ans<<endl;
    }
    return 0;
}

M. 数值膨胀之美

题目简介：

给定一个数组，可以选择一个区间将所有元素乘2，问操作后的最小极差。

思路：

显然，我们至少应当让最小值扩大一倍，其次考虑扩大区间，使最小值到次小值的区间扩大一倍……最小值到次次小值。此过程可以通过维护区间的两个端点 和 来实现，当我们需要翻倍的区间增大的时候（比如从最小值到次小值），只需要将 向左移动或者将 向右移动，直到包含当前需要选择的元素。

例如假设当前翻倍的区间为 [6,8] 即 ， 。下一个待翻倍的最小值位置在 11 ，这时我们需要将第 9,10,11 这三个数同时翻倍，即 ， 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{		//num为数组的值，id为下表
	int num,id;
}a[100010];
int b[100010];
int n;
bool cmp(node a,node b)
{
	return a.num<b.num;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].num;
		a[i].id=i;
        b[i]=a[i].num;
    }
    sort(a+1,a+n+1,cmp);
    a[n+1].num=INT_MAX;		//设定哨兵，防止越界
    int l=a[1].id,r=a[1].id;		//初始的区间只包含最小值
    int ma=max(a[1].num*2,a[n].num);		//ma为数组当前状态的最大值
    int res=ma-min(a[1].num*2,a[2].num);		//rse为数组当前状态的极差
    for(int i=2;i<=n;i++)		//从最小值开始遍历，不断扩大区间
    {
        while(a[i].id<l)		//如果下一个待翻倍的最小值在左边，则从左边扩大区间
        {
            l--;
            ma=max(ma,b[l]*2);
        }
        while(a[i].id>r)		//如果下一个待翻倍的最小值在右边，则从右边扩大区间
        {
            r++;
            ma=max(ma,b[r]*2);
        }
        res=min(res,ma-min(a[1].num*2,a[i+1].num));//更新极差 min(最小值*2,未翻倍的最小值)
    }
    cout<<res;
}

J. 硝基甲苯之袭

题目简介：

给定一个数组，问有多少对元素满足

gcd:最大公约数 xor:按位异或运算

思路：

对于一个数而言，它和任意一个数的 一定是它的某个因子。那么本题可以通过枚举每个元素 的每个因子 ,作为它和其他元素的“假想gcd”，然后我们去检测 是不是等于真正的 即可。如果确实相等，那么证明 就是真正是 ，我们直接用map计算 出现的次数。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,a[200005];
LL ans;
map<int,int> p;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=a[i]/j;j++)
        {
            if(a[i]%j==0)		//找出a[i]的因数j
            {
                if(j==__gcd(a[i],a[i]^j)) ans+=p[a[i]^j];
                if(a[i]/j!=j&&a[i]/j==__gcd(a[i],a[i]^(a[i]/j))) ans+=p[a[i]^(a[i]/j)];
            }
        }
    }
    cout<<ans/2;
    return 0;
}

H. 井然有序之窗

题目简介：

给定每个元素允许出现的区间，构造一个排列，使得每个元素都在一个指定的区间内。

思路：

我们先将所有区间排序，用一个优先队列来维护“可选的区间右端点”。当我们指定某个区间为 的时候，我们首先将所有以 为左端点的区间加入优先队列，然后尽量选择目前最小的那个右端点即可。

#include<bits/stdc++.h>
#define N 100010
using namespace std;
typedef pair<int,int> pll;
priority_queue< pll,vector<pll>,greater<pll> > k;
int ans[N],n;
struct node{		//数字b的可选区间为[l,r]
    int l,r,b;
}a[N];
bool cmp(node a,node b)
{
	if(a.l==b.l) return a.r<b.r;
    else return a.l<b.l;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
        a[i].b=i;
    }
    sort(a+1,a+n+1,cmp);
    int cnt=1;
    bool flag=false;
    for(int i=1;i<=n;i++)		//遍历下标，查找第i个数字能填多少
    {
        while(a[cnt].l==i)		//所有左端点取到l的数入队
        {
            k.push({a[cnt].r,a[cnt].b});
            cnt++;
        }
        if(k.size() && k.top().first>=i)		//若数字存在，取出右端点最小的数
        {
            pll res=k.top();
            k.pop();  
            ans[res.second]=i;          
        }
        else		//数字不存在，无解
        {
            cout<<-1;
            flag=true;
            break;
        }
        
    }
    if(!flag)
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
    return 0;
}

完结撒花