AtCoder Regular Contest 092

C - 2D Plane 2N Points

---

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points. The coordinates of the i-th red point are (ai,bi), and the coordinates of the i-th blue point are (ci,di).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

• All input values are integers.
• 1≤N≤100
• 0≤ai,bi,ci,di<2N
• a1,a2,…,aN,c1,c2,…,cN are all different.
• b1,b2,…,bN,d1,d2,…,dN are all different.

---

Input

Input is given from Standard Input in the following format:

N
a1 b1
a2 b2
:
aN bN
c1 d1
c2 d2
:
cN dN

Output

Print the maximum number of friendly pairs.

---

Sample Input 1

Copy

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

Copy

2

For example, you can pair (2,0) and (4,2), then (3,1) and (5,5).

---

Sample Input 2

Copy

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

Copy

2

For example, you can pair (0,0) and (2,3), then (1,1) and (3,4).

---

Sample Input 3

Copy

2
2 2
3 3
0 0
1 1

Sample Output 3

Copy

0

It is possible that no pair can be formed.

---

Sample Input 4

Copy

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

Copy

5

---

Sample Input 5

Copy

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

Copy

4

---

这个题目的描述很简单，就是有A，B两个集合，你要找到两个集合最多匹配的个数，匹配的是B中的元素横纵坐标都是比A的大，这里采用二分，查询另一个分组是不是存在这样的元素，每次都选择与其最相近的元素

（相当于排序之后不够考虑一个坐标轴）

#include<bits/stdc++.h>
using namespace std;
#define Fi first
#define Se second
pair<pair<int,int> ,int>p[1005];
int n;
int main()
{
    cin>>n;
    for(int i=0; i<n+n; i++)cin>>p[i].Fi.Fi>>p[i].Fi.Se,p[i].Se=i>=n;
    sort(p,p+n+n);
    set<int> s;
    int ans=0;
    for(int i=0; i<n+n; i++)
        if(p[i].Se&&!(s.empty()||*s.begin()>p[i].Fi.Se))s.erase(--s.lower_bound(p[i].Fi.Se)),ans++;
        else if(!p[i].Se)s.insert(p[i].Fi.Se);
    cout<<ans;
}

D - Two Sequences

---

Time limit : 3sec / Memory limit : 256MB

Score : 500 points

Problem Statement

You are given two integer sequences, each of length N: a1,…,aN and b1,…,bN.

There are N2 ways to choose two integers i and j such that 1≤i,j≤N. For each of these N2 pairs, we will compute ai+bj and write it on a sheet of paper. That is, we will write N2 integers in total.

Compute the XOR of these N2 integers.

Definition of XOR

Constraints

• All input values are integers.
• 1≤N≤200,000
• 0≤ai,bi<228

---

Input

Input is given from Standard Input in the following format:

N
a1 a2 … aN
b1 b2 … bN

Output

Print the result of the computation.

---

Sample Input 1

Copy

2
1 2
3 4

Sample Output 1

Copy

2

On the sheet, the following four integers will be written: 4(1+3),5(1+4),5(2+3) and 6(2+4).

---

Sample Input 2

Copy

6
4 6 0 0 3 3
0 5 6 5 0 3

Sample Output 2

Copy

8

---

Sample Input 3

Copy

5
1 2 3 4 5
1 2 3 4 5

Sample Output 3

Copy

2

---

Sample Input 4

Copy

1
0
0

Sample Output 4

Copy

0

---

这个题目也是有点意思，题目还是很好懂的

就是给你A数组和B组数，A和B进行相加有n*n个结果，求这n*n结果的异或和

首先你要想n*n的运算肯定是爆炸的

a+b = a^b + (a&b)<<1

所以n为a次表示要进行n次异或，异或两次的值为0，所以n为奇数答案肯定有两个数组的异或和

然后将其划分为子问题，选取两个数的和最大值2^29

用位运算实现两数相加

int Add(int a,int b)
{
    return b?Add(a^b,(a&b)<<1):a;
}

 位运算实现两数相减

int MINUS(int a,int b)
{
    return b?MINUS(a^b,((a^b)&b)<<1):a;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N];
int main()
{
    int n,r=0;
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0; i<n; i++)cin>>b[i];
    if(n&1)
    {
        for(int i=0; i<n; i++)r^=a[i]^b[i];
    }
    for(int i=1<<29; i; i>>=1)
    {
        for(int j=0; j<n; j++)a[j]&=i-1;
        sort(a,a+n);
        for(int j=0; j<n; j++)
        {
            int t=lower_bound(a,a+n,i-(b[j]&(i-1)))-a;
            if((t&1)!=(n&1))r^=i;
        }
    }
    cout<<r;
    return 0;
}