AtCoder Regular Contest 092

签到，二分图模板题，时间复杂度O(nlogn)

题意

给两个长度为N序列a，b,求所有数(ai + bj)的异或和，i,j∈[0,n) （n<=2e5）

分析

首先要知道异或(^)运算符合交换律，暴力n^2会炸

按位算贡献，考虑ai+bj的第k位对答案的贡献，首先可以明确地一点是ai/bj高于第k为上的对答案的第k位没有影响，先把ai和bj分别mod2^(k+1)

现在考虑ai+bj第k位1的情况(ai、bj < 2^(k+1) ) 令T=2^k

1、 T <= ai+bj < 2*T (即和的第k为1，第k+1为不能为1)

2、3*T <= ai+bj <= 4*T (即和的第k+1为1且第k位也为1)

所以我们可以固定一个且二分另一个算对答案的贡献

时间复杂度O(29*nlogn)

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

const int maxn = 200005;

int a[maxn], b[maxn], aa[maxn], bb[maxn];
int n;

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d", &b[i]);
    }
    int answer=0;
    for(int i=0;i<=28;i++){
        for(int j=1;j<=n;j++){
            aa[j]=a[j]%(1<<(i+1));
            bb[j]=b[j]%(1<<(i+1));
        }
        sort(bb+1,bb+n+1);
        int t=(1<<(i));
        int sum=0;
        for(int j=1;j<=n;j++){
            int p1=lower_bound(bb+1,bb+n+1,t-aa[j])-bb;
            int p2=lower_bound(bb+1,bb+n+1,2*t-aa[j])-bb;
            int s1=lower_bound(bb+1,bb+n+1,3*t-aa[j])-bb;
            int s2=lower_bound(bb+1,bb+n+1,4*t-aa[j])-bb;
            sum+=(p2-p1)+(s2-s1);
        }
        if(sum&1)
        answer+=(1<<i);
    }
    printf("%d
", answer);
    return 0;
}

View Code

E - Both Sides Merger 推结论

题意

给出一个长度为N的数列a，有两个操作，每次操作选择一个数，使得其最终只剩下一个数：
1、选择左端/右端，删去这个数
2、选中中间任意的一个数，将其值替换为其左右两边的数之和，然后删去其左右两边的数。
问现在要求使得最终的值尽可能大，求最大的值以及操作次数，选数方案（即每次选择的数所在位置）

分析

很直观的可以看出最后的答案是这个序列的子集

性质：

设最终的答案为answer $x (x = a_{i 1} + a_{i 2} + a_{i 3} + \dots \dots + a_{i k})$

$x (x = a_{i 1} + a_{i 2} + a_{i 3} + \dots \dots + a_{i k})$

但要注意整个序列全是负数的情况

输出方案：麻烦的是每次删除一个数序列的下标都发生变化，但分析可知，两个偶数/奇数之间有奇数个数，我们可以不断去取中点进行替换，直至全部取完

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

const int maxn = 1e3+2;

int n;
int a[maxn];
ll sum[3];
vector<int>answer;
vector<int>q;
int main()
{
    scanf("%d", &n);
    bool flag=true;
    sum[2]=-1000000002;
    int p;
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        if(a[i]>0)
        {
            flag=false;
            int h=i%2;
            sum[h]+=a[i];
        }
        else if(flag)
        {
            if(a[i]>sum[2])
            {
                p=i;
                sum[2]=a[i];
            }
        }
    }
    if(flag)
    {
        printf("%lld
%d
", sum[2],n-1);
        for(int i=n;i>p;i--)
        {
            printf("%d
",i);
        }
        for(int i=1;i<p;i++)
        {
            printf("%d
", 1);
        }
    }
    else
    {

        printf("%lld
", max(sum[0],sum[1]));
        if(sum[0]>sum[1])
        {
            for(int i=2;i<=n;i+=2)
            {
                if(a[i]>0)
                {
                    q.push_back(i);
                }
            }
        }
        else
        {
            for(int i=1;i<=n;i+=2)
            {
                if(a[i]>0)
                {
                    q.push_back(i);
                }
            }
        }

        for(int i=n;i>q.back();i--)
        {
            answer.push_back(i);
        }
        for(int i=int(q.size())-1;i>0;i--)
        {
            int mid=(q[i]+q[i-1])/2;
            int sz=(q[i]-q[i-1])/2;
            for(int j=0;j<sz;j++)
            {
                answer.push_back(mid-j);
             //   cout<<mid-j<<endl;
            }
        }
        for(int i=1;i<int(q[0]);i++)
        {
            answer.push_back(1);
        }
        printf("%d
", int(answer.size()));
        for(int i=0;i<int(answer.size());i++)
        {
            printf("%d
", answer[i]);
        }
    }
    return 0;
}

View Code

F - Two Faced Edges

题意

给出一个有向图，对每条边都做一次询问：
反转这条边后，对原图的强连通分量是否有影响？（点的个数 $N \leq 1000$

$N \leq 1000$