2019 Multi-University Training Contest 10
2019-08-22 / Luo Jinrong   

进度

A B C D E F G H I J K
∅ ∅ √ ∅ ∅

1008. Coins

题意

有n堆硬币，每堆有2个硬币，每个硬币有面额，而且有拿的顺序，必须先拿第一个才能拿第二个。要从中取出$k(1\leq k\leq 2n)$个硬币的最大总值。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#pragma warning(disable:4996)
#include <bits/stdc++.h>

#define upf(i,a,n) for (int i=a;i<=n;i++)
#define drf(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const ll INF(0x3f3f3f3f);
const ll mod(998244353);
const int maxn(1e5 + 5);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int t, n;
struct group {
    ll a, b, sum;
}coins[maxn];
struct tmp2
{
    bool operator()(pair<int,int> a, pair<int,int> b)
    {
        return a.first < b.first;//大顶堆
    }
};
ll marked[maxn], f[maxn * 2];
priority_queue<pair<int, int>, vector<pair<int, int> >, tmp2 > q1, q2;
int main(){
#ifdef ACM_LOCAL
    freopen("acm.in", "r", stdin);
    freopen("acm.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    upf(_, 1, t) {
        cin >> n;
        while (!q1.empty())
            q1.pop();
        while (!q2.empty())
            q2.pop();
        upf(i, 0, n + 1)
            marked[i] = 0;
        upf(i, 1, n) {
            cin >> coins[i].a >> coins[i].b;
            coins[i].sum = coins[i].a + coins[i].b;
            q1.push(pair<int, int>{coins[i].a, i});
            q2.push(pair<int, int>{coins[i].sum, i});
        }
        f[0] = 0;
        f[1] = q1.top().first;
        int pos = q1.top().second;
        int ve = f[1];
        marked[pos]++;
        q1.pop();
        if (marked[pos] != 2)
            q1.push(pair<int, int> {coins[pos].b, pos});
        upf(i, 2, 2 * n) {
            //被整组取值，没有从q1中删除的值需要删除
            while (!q1.empty()) {
                if (marked[q1.top().second] == 2)
                    q1.pop();
                else
                    break;
            }
            int poss = q1.top().second;
            int value = q1.top().first;
            q1.pop();
            marked[poss]++;
            //整组被单个选择过,无法成组
            while (!q2.empty()) {
                if (marked[q2.top().second])
                    q2.pop(); 
                else
                    break;
            }
            pair<int, int> sm;
            if (!q2.empty()) {
                sm = q2.top();
            }
            else {
                sm.first = -INF;
            }
            if (marked[poss] == 1) {
                if (sm.first < coins[poss].sum) {
                    sm.first = coins[poss].sum;
                    sm.second = poss;
                }
            }
            if (sm.first > value + ve) {
                f[i] = f[i - 2] + sm.first;
                if (!q2.empty()) {
                    if (q2.top().first == sm.first)
                        q2.pop();
                }
                if (pos == poss) {
                    marked[pos] = 0;
                    marked[sm.second] = 2;
                    q1.push(pair<int, int>{coins[pos].a, pos});
                    q2.push(pair<int, int>{coins[pos].sum, pos});
                    ve = coins[sm.second].b;
                    pos = sm.second;
                    continue;
                }
                if (marked[pos] == 1) {
                    q1.push(pair<int, int>{coins[pos].a, pos});
                }
                else {
                    q1.push(pair<int, int>{coins[pos].b, pos});
                }
                if (marked[poss] == 1) {
                    q1.push(pair<int, int>{coins[poss].a, poss});
                }
                else {
                    q1.push(pair<int, int>{coins[poss].b, poss});
                }
                marked[pos]--;
                marked[poss]--;
                marked[sm.second] = 2;
                if (marked[pos] == 0) {
                    q2.push(pair<int, int>{coins[pos].sum, pos});
                }
                if (marked[poss] == 0) {
                    q2.push(pair<int, int> {coins[poss].sum, poss});
                }
                ve = coins[sm.second].b;
                pos = sm.second;
            }
            else {
                f[i] = f[i - 1] + value;
                if (marked[poss] == 1) {
                    q1.push(pair<int, int>{coins[poss].b, poss});
                }
                pos = poss;
                ve = value;
            }
        }
        upf(i, 1, 2 * n)
            cout << f[i] << " \n"[i == 2 * n];
    }
}

1003. Valentine’s Day

题意

有$n$个礼物挑任意个送女朋友，每个礼物有$p_i$的概率使女朋友开心，每个礼物让女朋友开心是独立的。问女朋友只开心一次的最大概率。

做法

根据概率从大到小遍历，记录前$i$个礼物只开心一次的概率$ans$和一次都不开心的概率$no$，到第$i+1$个礼物的时候如果$ans\times (1-p[i+1])+no\times p[i+1]>ans$就更新$ans$和$no$。

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
#include<bits/stdc++.h>
#define FIN freopen("./data.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e4+5);
ll T,n;
const double eps(1e-8);
double p[maxn],ans,no;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
    freopen("./1003.out","w",stdout);
#endif
    scanf("%lld",&T);
    for(int t=1;t<=T;t++){
        ans=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf",&p[i]);
            ans=max(p[i],ans);
        }
        sort(p+1,p+1+n);
        if(ans-0.5<eps){
            ans=p[n],no=1-p[n];
            for(int i=n-1;i>=1;i--){
                if(ans*(1-p[i])+no*p[i]>ans){
                    ans=ans*(1-p[i])+no*p[i];
                    no=no*(1-p[i]);
                }
            }
        }
        printf("%.12lf\n",ans);
    }
}

1009. Block Breaker

题意

有一个$n\times m$的格子平面，每个格子里面都有个砖块，每次询问敲掉$(x,y)$位置的砖块，当一个砖块x轴方向和y轴方向都至少有一个砖块不存在时，这个砖块也可以被敲掉。对于每次询问，输出这次敲掉了几个砖块。

做法

记录这个平面的状态，对于每次询问如果这个位置存在砖块就入队，每次出队敲掉一个砖块的时候，判断它周围四个能不能被敲掉，能敲掉就入队，进行bfs搜索。

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
#include<bits/stdc++.h>
#define FIN freopen("./data.in","r",stdin)
using namespace std;
const int maxn(3e3+5);
int T,n,m,q,mapp[maxn][maxn],ans,quu[maxn*maxn];
struct point{
    int x,y;
};
queue<point> que;
inline bool judge(int x,int y){
    if(x==0||x==n+1||y==0||y==m+1){
        return false;
    }
    if(mapp[x][y]&&(mapp[x+1][y]==0||mapp[x-1][y]==0)&&(mapp[x][y+1]==0||mapp[x][y-1]==0)){
        return true;
    }
    return false;
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
    freopen("./1009.out","w",stdout);
#endif
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%d%d%d",&n,&m,&q);
        for(int i=0;i<=n+1;i++){
            for(int j=0;j<=m+1;j++){
                mapp[i][j]=1;
            }
        }
        int x,y;
        while(q--){
            ans=0;
            scanf("%d%d",&x,&y);
            if(mapp[x][y]){
                mapp[x][y]=0;
                que.push({x,y});
            }
            while(!que.empty()){
                point tmp=que.front();
                ans++;
                que.pop();
                if(judge(tmp.x+1,tmp.y)){
                    mapp[tmp.x+1][tmp.y]=0;
                    que.push({tmp.x+1,tmp.y});
                }
                if(judge(tmp.x-1,tmp.y)){
                    mapp[tmp.x-1][tmp.y]=0;
                    que.push({tmp.x-1,tmp.y});
                }
                if(judge(tmp.x,tmp.y+1)){
                    mapp[tmp.x][tmp.y+1]=0;
                    que.push({tmp.x,tmp.y+1});
                }
                if(judge(tmp.x,tmp.y-1)){
                    mapp[tmp.x][tmp.y-1]=0;
                    que.push({tmp.x,tmp.y-1});
                }
            }
            printf("%d\n",ans);
        }
    }
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/22/2019-Multi-University-Training-Contest-10/