这一场是在 2019-11-24 13:30 CST 开始的。
Team Round第一次选到多校，解了IEC三道题，三道题rank跨越在147—-406。我们解题较慢+罚时多。总的来说是挺符合队伍现状的，这样做一次尝试可能是一种好事。
有几个点这次特别有感触
我又双叒叕像以前一样在卡题时候给队友读算法名字，这真的真的真的是一种很糟糕的习惯，谢谢队友不杀之恩，我在今后练习中一定要注意这个点。
在卡题我瞎bb算法名称时候dqy说了这些：你说这个算法，你要怎么处理。你说线段树，你可以跟我说怎么维护，怎么处理，什么时候query，不要老是突然蹦出来算法名字，你要落实到代码上，你不会写，我帮你写，可你要告诉我你的想法，怎么一步步处理。看到题目，理解题目，转化题意，建立模型，落实代码。
在卡题我瞎bb算法名称时候wqr翻白眼。。。
还有一个点被一些我自己认为这个题目的性质所迷惑，，，，，这个就很糟糕，，，，难顶
I - Block Breaker
按题意模拟，dfs
1 | /* _ _ _ |
E - Welcome Party
题意:
每个人有两个属性 ai 和 bi ，将人分为两类，使得 |$\max(a_i)$−$\max(b_i)$| 最小。
题解：
dqy写的，他可能是这样处理的： 对 ai 排序，枚举每一个 ai 作为 a 属性上限的时候的情况，显然比当前 ai 大的一定是 b ，然后可以选择在比他小的或者相等（不能是自己）中挑一个和 ai 最接近的且能称为最大值的。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
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 5e5+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
pll a[N];
set<ll> s1;
set<pll> S;
int32_t main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--){
S.clear();
s1.clear();
int n;
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i].fi>>a[i].se;
}
sort(a+1,a+1+n, greater<pll>());
for(int i = 1; i <= n; i++){
S.insert({a[i].se, i});
}
ll ans = inf;
for(int i = 1; i <= n; i++){
if(i==n){
ans = min(ans, abs(a[i].fi - *s1.rbegin()));
break;
}
int p;
if(s1.empty()) p = 0;
else {
p = *s1.rbegin();
ans = min(ans, abs(p-a[i].fi));
}
S.erase({a[i].se, i});
auto it = S.lower_bound(make_pair(a[i].fi, 0));
if(it != S.end()) {
ll a1 = (*it).fi;
if(a1 >= p) ans = min(ans, abs(a1 - a[i].fi));
}
if(it != S.begin()){
ll a2 = (*--it).fi;
if(a2 >= p) ans = min(ans, abs(a[i].fi-a2));
}
s1.insert(a[i].se);
S.insert({a[i].se, i});
}
cout<<ans<<endl;
}
return 0;
}
C - Valentine’s Day
题意：
有 n 个礼物，每个礼物有 Pi 的概率让女友开心，要选出一些礼物，最大化让女友开心恰好一次的概率，求这个概率。
思路：
拆一下$\prod$,遍历一次，取max，也有人说这有一个性质。（做的时候一直以为和0.5有关系，一直跳不出自己假想的性质，其实是不对的。）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 /************************************************
# @Author: miniLCT
# @DateTime: 2019-11-24 14:08:11
# @Description: You build it.You run it
# @More: If lots of AC,try BF,dfs,DP
***********************************************/
using namespace std;
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
/*void dabiao(double a, double b){
double ans = a+b-a*b*2;
printf("a ======= %.9f b ======== %.9f a+b-2*a*b ===== %.9f \n",a, b , ans );
}*/
double p[maxn],zcj[maxn], zb[maxn];
//zcj 都是不开心的 zb 那一次开心的
int main()
{
/*freopen("out.txt","w",stdout);
double x = 0.0, y = 0.0;
for(int i = 0; i <= 1e6;i += 1000){
for(int j = 0; j <= 1e6;j += 1000){
dabiao(x+1.0*i*(1e-6),y+1.0*j*(1e-6));
}
}*/
int t , n ;
scanf("%d",&t);
while(t--){
//memset(zcj , 0 ,sizeof (zcj));
//memset(zb , 0 , sizeof (zb));
scanf("%d",&n);
for(int i = 0; i <= n;i++){
zb[i] = zcj[i] = 0;
}
for(int i = 0; i < n;i++){
scanf("%lf",&p[i]);
}
sort(p,p+n,greater<double>());
/*for(int i = 0; i < n;i++){
cout << p[i] << endl;
}*/
if(p[0] == 1){
printf("%.10f\n", p[0]);
continue;
}
//reverse(p.begin(), p.end());
double ans = 0;
for(int i = 0 ; i < n;i++){
if(i == 0){
zcj[i] = 1 - p[i];
zb[i] = p[i] / (1-p[i]);
}else{
zcj[i] = zcj[i - 1] * (1 -p[i]);
zb[i] = zb[i-1] + p[i] / (1.0-p[i]);
}
ans = max(zcj[i] * zb[i], ans);
}
printf("%.10f\n", ans);
}
}
/******************************************************
stuff you should look for
* int overflow, array bounds
* special cases (n=1?), set tle
* do smth instead of nothing and stay organized
*******************************************************/
补题：
H - Coins
题意:
每一组两个硬币，分别价值 ai 、 bi ，每一组有三个选择：取 ai ，取 ai 和 bi ，不取，求恰好取 k(k$\in$1~2n) 个硬币的时候的最大价值。
题解：
贪心的思想，用线段树或者四个优先队列去维护。或者用决策单调性优化dp。
有很多优秀的做法：
n-2推得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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91//others
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MAXN = (int)2e6+7;
int a[MAXN],b[MAXN],c[MAXN];
priority_queue<pi> se[2],sb[2];
int ans[MAXN];
int mark[2][MAXN];
int main()
{
int T;
scanf("%d",&T);
while (T --) {
rep(i,0,1) {
while (!se[i].empty()) se[i].pop();
while (!sb[i].empty()) sb[i].pop();
}
int N;
scanf("%d",&N);
rep(i,0,5*N) mark[0][i] = mark[1][i] = ans[i] = a[i] = b[i] = 0;
rep(i,1,N) {
scanf("%d %d",&a[i],&b[i]);
c[i] = a[i]+b[i];
se[0].push(make_pair(a[i],i));
se[1].push(make_pair(a[i],i));
sb[0].push(make_pair(c[i],i));
sb[1].push(make_pair(c[i],i));
}
int f = 0,id,now1,now2;
pi tmp;
//1
tmp = se[1].top();
ans[1] = tmp.first;
mark[1][tmp.second] = 1;
se[1].push(make_pair(b[tmp.second],tmp.second+N));
rep(i,2,2*N) {
now1 = 0,now2 = 0;
pi s1,s2,s3;
while (!se[f].empty() && mark[f][se[f].top().second] == 1) se[f].pop();
while (!sb[f].empty() && mark[f][sb[f].top().second] == 1) sb[f].pop();
if (!se[f].empty()) {
s1 = se[f].top();se[f].pop();
while (!se[f].empty() && mark[f][se[f].top().second] == 1) se[f].pop();
if (se[f].empty()) {
se[f].push(s1);
}else {
s2 = se[f].top();se[f].pop();
now1 = (s1.first+s2.first);
}
}
if (!sb[f].empty()) {
s3 = sb[f].top();sb[f].pop();
now2 = s3.first;
}
if (now1 >= now2) {
ans[i] = ans[i-2] + now1;
int id1 = s1.second;
int id2 = s2.second;
mark[f][id1] = 1;
mark[f][id2] = 1;
se[f].push(make_pair(b[id1],id1+N));
se[f].push(make_pair(b[id2],id2+N));
if (now2) {
sb[f].push(s3);
}
}else {
ans[i] = ans[i-2] + now2;
mark[f][s3.second] = 1;
if (now1) {
se[f].push(s1);
se[f].push(s2);
}
}
f = f^1;
}
rep(i,1,2*N-1) printf("%d ",ans[i]);
printf("%d\n",ans[2*N]);
}
}