# 2019 HDU多校第十场

## Valentine’s Day

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Oipotato loves his girlfriend very much. Since Valentine’s Day is coming, he decides to buy some presents for her.

There are n presents in the shop, and Oipotato can choose to buy some of them. We know that his girlfriend will possibly feel extremely happy if she receives a present. Therefore, if Oipotato gives k presents to his girlfriend, she has k chances to feel extremely happy. However, Oipotato doesn’t want his girlfriend to feel extremely happy too many times for the gifts.

Formally, for each present i, it has a possibility of Pi to make Oipotato’s girlfriend feel extremely happy. Please help Oipotato decide what to buy and maximize the possibility that his girlfriend feels extremely happy for exactly one time.

InputThere are multiple test cases. The first line of the input contains an integer T (1≤T≤100), indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤10 000), indicating the number of possible presents.

The second line contains n decimals Pi (0≤Pi≤1) with exactly six digits after the decimal point, indicating the possibility that Oipotato’s girlfriend feels extremely happy when receiving present i.

It is guaranteed that the sum of n in all test cases does not exceed 450000.

OutputFor each test case output one line, indicating the answer. Your answer will be considered correct if and only if the absolute error of your answer is less than 10−6.

Sample Input

2
3
0.100000 0.200000 0.900000
3
0.100000 0.300000 0.800000

Sample Output

0.900000000000
0.800000000000

#### 记已经购买的礼物一次都不能让女朋友开心的概率为 s0，恰好开心一次的概率为 s1，再买一个概率为 p 的礼物会使 (s0, s1) → (s0p, s1 + (s0 − s1)p)。显然，当 s0 ≤ s1 时加入任何礼物都不会使答案变优。类似地，如果删除一个礼物之后 s0 ≤ s1，那么删除这个礼物不会使答案变得更差。因此，任意一个最优解对应的非空礼物集合 G 都满足 s0 ≤ s1，且该集合每个真子集均有 s0 > s1，也即 ∀T\$G,s1s0=Pp∈Tpp 1−p < 1。不难发现 p 1p 1−p 和 p 的单调性相同，因此，如果一个满足上述条件的非空礼物集合 G 不是由使女朋友开心概率最大的若干个礼物构成，那么可以把集合内概率最小的礼物 a 换成集合外概率最大的礼物 b，从而得到一个答案不会更劣的礼物集合 (G − {a}) ∪ {b}。设新集合中概率最小的礼物为 c，新集合的真子集 ((G − {a}) ∪ {b}) − {c} 可能不满足 s0 > s1，此时可以不断地删去集合中概率最小的礼物，直到该集合满足条件。这个过程不会使答案变劣，不断地替换和删除礼物可以得到最优解。最终的结论是，按照概率从大到小的顺序购买礼物直到 s0 ≤ s1 或者全部买完为止，即可得到一个最优解。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
double a;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
sort(a+1,a+1+n);
double p=0,z=1,su=0;
if(a[n]==1){
printf("%.12lf\n",1.0);
continue;
}
for(int i=n;i>=1;i--){
su+=a[i]/(1.0-a[i]);
z*=(1.0-a[i]);
if(su*z>p){
p=su*z;
}
}
printf("%.12lf\n",p);
}
return 0;
}


## Welcome Party

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

The annual welcome party of the Department of Computer Science and Technology is coming soon! Many students have been applying to show up at the welcome party, and every one of them can choose to sing a song or play crosstalk. This troubles the chief director a lot: how to arrange the program list, such that every student can have a chance to show up on the stage, and the satisfactory value of audiences is maximized?

To cope with this problem, the director proposes a model. In this model, every student has two attributes: the singing ability and crosstalking ability. The satisfactory value of audiences to singings is the maximum singing ability among all students that choose to sing a song; similarly, the satisfactory value to crosstalks is the maximum crosstalking ability among all students that choose play crosstalk. The strange thing is, the overall satisfactory value to the whole party is negatively related to the absolute difference between the satisfactory values to singings and crosstalks. The problem is, what is the minimum possible absolute difference between the satisfactory values of the two types of programs?

Note that:
– every student should choose exactly one type of programs to play;
– at least one student should sing a song, and at least one student should play crosstalk.

InputThe first line of input consists of a single integer T (1≤T≤70), the number of test cases.

Each test case starts with a line of a single integer n (2≤n≤100000), denoting the number of students applying to show up on the stage. Then follow n lines, each containing two integers x and y (0≤x,y≤1018), denoting the singing ability and crosstalking ability of a student.

It is guaranteed that the sum of n over all test cases never exceeds 1000000.

OutputFor each test case, output a single integer, denoting the minimum possible absolute difference between the satisfactory values of the two types of programs.

Sample Input

2
5
27 46
89 13
55 8
71 86
22 35
3
3 5
4 7
6 2

Sample Output

3
1

#### 称 i = arg maxi∈S xi 为 x 临界的，对 y 临界也类似定义。枚举 x 临界的下标 i，那么 j 可能成为 y临界的，当且仅当 yj ≥ max{yk : k 6= i, j, xk > xi}。将所有数对以 x 为关键字排序后，就可以用数据结构维护 y 并找出最接近 xi 的 yj，且 yj ≥ max{yk : k 6= i, j, xk > xi}，复杂度是 O(n log n)。

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
typedef long long ll;
struct node{
ll a,b;
int id;
bool operator < (const ll& y) const{
return b<y;
}
};
node a,b,c;
int cmp(const node& x,const node& y) {
if(x.a!=y.a) return x.a<y.a;
else return x.b>y.b;
}
int ccmp(const node& x,const node& y) {
if(x.b!=y.b) return x.b<y.b;
else return x.a<y.a;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i].a,&a[i].b);
a[i].id=i;
b[i]=a[i];
c[i]=a[i];
}
sort(b+1,b+1+n,cmp);
sort(c+1,c+1+n,ccmp);
ll suf=0;
ll ans=2e18+7;
for(int i=n;i>=1;i--){
ll tar=b[i].a;
ll tmp=b[i].b;
if(suf>=tar){
if(i!=n) ans=min(ans,abs(suf-tar));
}
else{
if(i!=n) ans=min(ans,abs(suf-tar));
int pt1=lower_bound(c+1,c+1+n,b[i].a)-c;
for(int j=max(1,pt1-5);j<=min(n,pt1+5);j++){
if(b[i].id!=c[j].id && c[j].b>=suf) ans=min(ans,abs(b[i].a-c[j].b));
}
}
suf=max(suf,tmp);
}
printf("%lld\n",ans);
}
return 0;
}


## Block Breaker

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Given a rectangle frame of size n×m. Initially, the frame is strewn with n×m square blocks of size 1×1. Due to the friction with the frame and each other, the blocks are stable and will not drop.

However, the blocks can be knocked down. When a block is knocked down, other remaining blocks may also drop since the friction provided by other remaining blocks may not sustain them anymore. Formally, a block will drop if it is knocked or not stable, which means that at least one of the left block and the right block has been dropped and at least one of the front block and the back block has been dropped. Especially, the frame can be regarded as a huge stable block, which means that if one block’s left is the frame, only when its right block has been dropped and at least one of the front block and the back block has been dropped can it drop. The rest situations are similar.

Now you, the block breaker, want to knock down the blocks. Formally, you will do it q times. In each time, you may choose a position (xi,yi). If there remains a block at the chosen position, you will knock it down; otherwise, nothing will happen. Moreover, after knocking down the block, you will wait until no unstable blocks are going to drop and then do the next operation.

For example, please look at the following illustration, the frame is of size 2×2 and the block (1,1) and (1,2) have been dropped. If we are going to knock the block (2,2), not only itself but also the block (2,1) will drop in this knocking operation.

You want to know how many blocks will drop in total in each knocking operation. Specifically, if nothing happens in one operation, the answer should be regarded as 0.

InputThe first line contains one positive integer T (1≤T≤10), denoting the number of test cases.

For each test case:

The first line contains three positive integers n,m and q (1≤n,m≤2000,1≤q≤100000), denoting the sizes in two dimensions of the frame and the number of knocking operations.

Each of the following q lines contains two positive integers xi and yi (1≤xi≤n,1≤yi≤m), describing a knocking operation.

OutputFor each test case, output q lines, each of which contains a non-negative integer, denoting the number of dropped blocks in the corresponding knocking operation.

Sample Input

2
2 2 3
1 1
1 2
2 2
4 4 6
1 1
1 2
2 1
2 2
4 4
3 3

Sample Output

1
1
2
1
1
2
0
1
11

#### BFS裸题

#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand()%x;}
int n,m;
struct node{
int x,y;
bool mk;
};
node a;
queue<int> qx,qy;
int bfs(int tx,int ty){
while(!qx.empty()) qx.pop(),qy.pop();
if(a[tx][ty].mk==0) return 0;
a[tx][ty].x=a[tx][ty].y=a[tx][ty].mk=0;
qx.push(tx);qy.push(ty);
int ret=0;
while(!qx.empty()){
int x=qx.front(),y=qy.front();qx.pop();qy.pop();
ret++;
for(int i=x-1;i>x-2 && i>=1;i--){
if(a[i][y].mk && a[i][y].y){
a[i][y].y=0;
if(a[i][y].x==0){
a[i][y].mk=0;
qx.push(i);qy.push(y);
}
}
else break;
}
for(int i=x+1;i<=n && i<x+2;i++){
if(a[i][y].mk && a[i][y].y){
a[i][y].y=0;
if(a[i][y].x==0){
a[i][y].mk=0;
qx.push(i);qy.push(y);
}
}
else break;
}
for(int i=y-1;i>=1 && i>y-2;i--){
if(a[x][i].mk && a[x][i].x){
a[x][i].x=0;
if(a[x][i].y==0){
a[x][i].mk=0;
qx.push(x);qy.push(i);
}
}
else break;
}
for(int i=1+y;i<=m && i<y+2;i++){
if(a[x][i].mk && a[x][i].x){
a[x][i].x=0;
if(a[x][i].y==0){
a[x][i].mk=0;
qx.push(x);qy.push(i);
}
}
else break;
}
}
return ret;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j].x=1,a[i][j].y=1,a[i][j].mk=1;
}
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
int cnt=bfs(x,y);
printf("%d\n",cnt);
}
}
return 0;
}