C

平面上有两个圆半径分别为r1,r2和若干点,求覆盖所有点的最小$r_1^2 + r_2^2$

暴力
我们很容易知道了两个圆上都至少有一点(否则不能更优),所以我们将点分别按照与两个圆的距离排序,然后再求另一个圆覆盖剩下的点的最小半径。

复杂度$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define P(x) ((x)*(x))
const int maxn = 2010;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int n;

struct Point{
int id;
LL x,y;
} p1[maxn],p2[maxn],p,q;

LL val[maxn];

LL dis(Point a,Point b)
{
return P(a.x - b.x)+P(a.y - b.y);
}

bool cmp1(const Point a,const Point b)
{
return dis(a,p) < dis(b,p);
}

bool cmp2(const Point a,const Point b)
{
return dis(a,q) < dis(b,q);
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %lld %lld %lld %lld",&n,&p.x,&p.y,&q.x,&q.y);
for(int i=0;i<n;++i)
{
scanf("%lld %lld",&p1[i].x,&p1[i].y);
p2[i].x = p1[i].x; p2[i].y = p1[i].y;
p1[i].id = p2[i].id = i;
}
sort(p1,p1+n,cmp1);
sort(p2,p2+n,cmp2);

LL ans = INF;

for(int i=0;i<n;++i)
{
val[p2[i].id] = dis(p2[i],q);
}
for(int i=-1;i<n;++i)
{
LL r1 = 0,r2 = 0;
if(i!=-1) r1 = dis(p1[i],p);
for(int j=i+1;j<n;++j)
{
r2 = max(r2,val[p1[j].id]);
}
ans = min(ans,r1+r2);
// printf("%lld %lld\n",r1,r2);
}

for(int i=0;i<n;++i)
{
val[p1[i].id] = dis(p1[i],p);
}
for(int i=-1;i<n;++i)
{
LL r1 = 0,r2 = 0;
if(i!=-1) r2 = dis(p2[i],q);
for(int j=i+1;j<n;++j)
{
r1 = max(r1,val[p2[j].id]);
}
ans = min(ans,r1+r2);
// printf("%lld %lld\n",r1,r2);
}

printf("%lld\n",ans);
return 0;
}

D

给三个点,用一条折线(每条线段平行于坐标轴)将他们连起来,问这条折线最少由几条线段构成

特判
注意下面这种情况比较特殊

$$
..X \\
.X. \\
X..
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL x[3],y[3];

int solve()
{
if(x[0] == x[1] && x[1] == x[2]) return 1;
if(y[0] == y[1] && y[1] == y[2]) return 1;
if(x[0] == x[1])
{
int mn = min(y[0],y[1]),mx = max(y[0],y[1]);
if(!(mn < y[2] && y[2] < mx)) return 2;
}
if(x[0] == x[2])
{
int mn = min(y[0],y[2]),mx = max(y[0],y[2]);
if(!(mn < y[1] && y[1] < mx)) return 2;
}
if(x[2] == x[1])
{
int mn = min(y[2],y[1]),mx = max(y[2],y[1]);
if(!(mn < y[0] && y[0] < mx)) return 2;
}
if(y[0] == y[1])
{
int mn = min(x[0],x[1]),mx = max(x[0],x[1]);
if(!(mn < x[2] && x[2] < mx)) return 2;
}
if(y[0] == y[2])
{
int mn = min(x[0],x[2]),mx = max(x[0],x[2]);
if(!(mn < x[1] && x[1] < mx)) return 2;
}
if(y[2] == y[1])
{
int mn = min(x[2],x[1]),mx = max(x[2],x[1]);
if(!(mn < x[0] && x[0] < mx)) return 2;
}
return 3;
}

int main()
{
//freopen("test.txt","r",stdin);
for(int i=0;i<3;++i) scanf("%lld %lld",x+i,y+i);
printf("%d\n",solve());
return 0;
}

E

给一个序列,每次查询给出l,r,问[l,r]内有多少区间满足异或和为k

莫队
我们记录前缀和,每次转移的时候即加上或减去该位置对应的前缀和(注意L对应其上一个位置),新增异或和为k的区间个数即 cnt[pre[x]^k]
复杂度$O(n\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
int n,m,k,B,a[maxn];
int cnt[1 << 20];
LL pre[maxn],ans[maxn],cur;

struct Res{
int l,r;
int id;
bool operator<(const Res& rhs) const
{
if(l/B == rhs.l/B) return r < rhs.r;
else return l < rhs.l;
}
} q[maxn];

void add(int x)
{
cur += cnt[pre[x]^k];
++cnt[pre[x]];
}

void del(int x)
{
--cnt[pre[x]];
cur -= cnt[pre[x]^k];
}

void solve()
{
memset(cnt,0,sizeof cnt);
int L = 1,R = 0;
++cnt[0];
cur = 0;
for(int i=0;i<m;++i)
{
while(L < q[i].l) del((L++)-1);
while(L > q[i].l) add((--L)-1);
while(R < q[i].r) add(++R);
while(R > q[i].r) del(R--);
ans[q[i].id] = cur;
}
for(int i=0;i<m;++i) printf("%lld\n",ans[i]);
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<n;++i) scanf("%d",a+i+1);
pre[0] = 0;
for(int i=1;i<=n;++i) pre[i] = pre[i-1]^a[i];
for(int i=0;i<m;++i) scanf("%d %d",&q[i].l,&q[i].r),q[i].id = i;
B = sqrt(m) + 1;
sort(q,q+m);
solve();
return 0;
}