BUPT-2022-summer-2

发表于 | 分类于 |

A(数据结构:区间更新、查询最值线段树)

大致题意：给定n个闭区间，求两个点，使包含这两个点的总数最多

题解:

很明显是离散化后用数据结构维护，想了个先找被包含区间数最大的点，去掉该点后找第二个点的错误贪心

正解:首先，我们规定，选取的第一个点始终位于第二个点的左侧。

离散化后将所有区间按左端点从大到小排列，再从大到小用i枚举点，将所有左端点大于i的区间加入，记录此时的最大值作为f[i]，则此时f[i]表示不包含左端点小于等于i的区间的情况下，能找到一个点，满足包含这个点的最多的区间数。

当所有区间都加入后，用i遍历所有点，f[i]+包含i的区间总数则为可能答案

证明:包含i的区间总数很好理解，即枚举第一条直线的位置，而f[i]则表示消除包含该条直线后的区间后，第二条直线能达到的最大区间数（其他区间要么对答案根本没贡献—完全位于i点左侧，要么包含i)

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
ll n, m, T;
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
struct node
{
    ll leftx, lefty, rightx, righty;
    friend bool operator<(node &a, node &b)
    {
        return a.righty < b.righty;
    }
};
node a[100005];
ll tmp;
ll lsh[200005];
const ll maxn = 200005;
ll num;
ll ans[200005];
struct seg_node
{
    ll val;
    ll lazy;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = max(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void pushdown(ll rt, ll ln, ll rn)
{
    if (segtree[rt].lazy)
    {
        segtree[rt << 1].lazy += segtree[rt].lazy;
        segtree[rt << 1 | 1].lazy += segtree[rt].lazy;
        segtree[rt << 1].val +=  segtree[rt].lazy;
        segtree[rt << 1 | 1].val +=  segtree[rt].lazy;
        segtree[rt].lazy = 0;
    }
}
void build(ll left = 1, ll right = num, ll rt = 1)
{
    segtree[rt].lazy = 0;
    if (left == right)
    {
        segtree[rt].val = 0;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
ll part_query(ll l, ll r, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val; //+segtree[rt].lazy;
    }
    if (l > right || r < left)
    {
        return 0;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    return max(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}
void part_update(ll l, ll r, ll value, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        segtree[rt].val += value;
        segtree[rt].lazy += value;
        return;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    if (l <= mid)
    {
        part_update(l, r, value, left, mid, rt << 1);
    }
    if (r > mid)
    {
        part_update(l, r, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        //ll ans = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].leftx >> a[i].lefty >> a[i].rightx >> a[i].righty;
            lsh[i] = a[i].righty;
            lsh[i + n] = a[i].lefty;
        }
        sort(lsh + 1, lsh + 1 + 2 * n);
        // memset(tree, 0, sizeof(tree));
        num = unique(lsh + 1, lsh + 1 + 2 * n) - lsh - 1;
        for (ll i = 1; i <= n; i++)
        {
            a[i].lefty = lower_bound(lsh + 1, lsh + 1 + num, a[i].lefty) - lsh;
            a[i].righty = lower_bound(lsh + 1, lsh + 1 + num, a[i].righty) - lsh;
        }
        sort(a + 1, a + 1 + n);
         //reverse(a + 1 + n, a + 1);
         //cout << a[n].righty << "!!!\n";
        // build(1, num, 1);
        build(1,num,1);
        ll now = n;
        for (ll i = num; i >= 1; i--)
        {
            while (now>=1&&a[now].righty > i)
            {
                part_update(a[now].righty, a[now].lefty, 1,1,num,1);
                now--;
            }
            ans[i] = part_query(i, num,1,num,1);
        }
        while (now >= 1)
        {
            part_update(a[now].righty, a[now].lefty, 1,1,num,1);
            now--;
        }
        ll mx = 0;
        for (ll i = 1; i <= num; i++)
        {
            ans[i] += part_query(i, i,1,num,1);
            mx = max(ans[i], mx);
        }

        cout << mx << "\n";

#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

这个线段树写法是硬改的。。不怎么优雅，而且常数很大

B(图论、Floyd)

题意:给定m个物品，n个人对所有物品进行喜好度分级(可能多个物品同一级)，先规定d(x,y)为比起y更喜欢x的人数，现有路径,满足条件d(t,t+1)>d(t+1,t)(即路径中相邻两项中，比起右项更喜欢左项的人数要严格大于比起左项更喜欢右项的人数)，在所有d(t,t+1)中，取最小值作为S(x,y)的预备值，在所有预备值中，取最大值作为S(x,y)，若不存在路径，则规定S(x,y)=0,若S(x,y)>=S(y,x)，当y为除了x的任意值时，都成立，则输出x，要求找出所有x(m<500,n<500)

题解:

图论题，用d[x,y]存储比起y更喜欢x的人数后，将所有不能形成路径的d消去(避免影响后续计算)，类似Floyd算法，规定dp[k,x,y]表示x、y之间路径不包含编号超过k的节点时，S(x,y)的最大值，当k=0时，dp[0,x,y]=d[x,y]/(前提是d[x,y]有意义，即能形成路径)，之后枚举k进行计算，得到S值，再枚举所有S值得到答案。

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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 505;
const ll INF = 0x7fffffff;
ll T, n, m;
//ll S[maxn][maxn];
ll d[maxn][maxn];
ll a[maxn];
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> m >> n;
        /*if(m==1)
        {
            cout << "\n";
            continue;
        }*/
        memset(d, 0, sizeof(d));
        //memset(S, 0, sizeof(S));
        for (ll i = 1; i <= n;i++)
        {
            for (ll j = 1; j <= m;j++)
            {
                cin >> a[j];
                if(a[j]==0)
                {
                    a[j] = INF;
                }
                for (ll k = 1; k < j;k++)
                {
                    if(a[j]!=0&&a[j]<a[k])
                    {
                        d[j][k]++;
                    }else if(a[k]!=0&&a[k]<a[j])
                    {
                        d[k][j]++;
                    }
                }
            }
        }
        for (ll i = 1; i <= m;i++)
        {
            for (ll j = 1; j < i;j++)
            {
                if(d[i][j]==d[j][i])
                {
                    d[i][j] = 0;
                    d[j][i] = 0;
                }else if(d[i][j]>d[j][i])
                {
                    d[j][i] = 0;
                }else if(d[i][j]<d[j][i])
                {
                    d[i][j] = 0;
                }
                d[i][i] = 0;
            }
        }
        for (ll k = 1; k <= m;k++)//类似Floyd
        {
            for (ll i = 1; i <= m;i++)
            {
                for (ll j = 1; j <= m;j++)
                {
                    d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
                }
            }
        }
        for (ll i = 1; i <= m;i++)
        {
            bool flag = 1;
            for (ll j = 1; j <= m;j++)
            {
                if(i==j)
                {
                    continue;
                }
                if(d[i][j]<d[j][i])
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
            {
                cout << i << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

E(二分+贪心)

题意:给定n组数据(x,y)，根据题意求出误差最小值

题解:小数二分误差值，check使用贪心

check具体流程:将所有点按x坐标从左到右排好之后，先找到pos满足pos前的所有值都小于等于给定值，之后到达第二阶段；易知同一分段内的最大值最小值之差不能大于2给定值，根据最大最小值更新第二阶段可能的最小值，直至不满足条件，将其作为pos；之后所有点都归为第三个分段，而第三个分段满足的条件是:1.最大值、最小值之差不能大于2给定值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
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 3e5 + 5;
ll n;
const ll INF = 0x7fffffff;
const double eps = 1e-2;
struct node
{
    ll x;
    ll y;
    friend bool operator < (node&a,node&b)
    {
        return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
    }
};
node a[maxn];
bool check(double err)
{
    ll pos = 1e9 + 5;
    ll id1=1, id2;
    for (ll i = 1; i <= n;i++)//1 1 1 2 2
    {
        if(abs(a[i].y)>err)
        {
            pos = a[i].x-1;
            break;
        }
        if(i!=n&&a[i].x!=a[i+1].x)
        {
            id1 = i + 1;
        }
    }
    if(pos==-1)
    {
        //cout << "1!!\n";
        return false;
    }
    if(pos==1e9+5)
    {
        return true;
    }
    ll mx = -1e9-5, mn = 1e9+5;
    ll pos2 = 1e9 + 5;
    double val2;
    for (ll i = id1; i <= n;i++)
    {
        if(a[i].y>mx||a[i].y<mn)
        {
            if(2*err<max(a[i].y,mx)-min(a[i].y,mn))
            {
                pos2 = a[i].x - 1;
                val2 = min(mx - err, mn + err);
                //val2 = max(val2, 1.0*0);
                //cout << i << "debug!!\n";
                break;
            }else
            {
                mx = max(mx, a[i].y);
                mn = min(mn, a[i].y);
            }
        }
        if(i!=n&&a[i].x!=a[i+1].x)
        {
            id2 = i + 1;
        }
    }
    if(pos2==pos)
    {
        //cout << val2<<"!"<<"!"<<"!\n";
        return false;
    }
    if(pos2==1e9+5)
    {
        return true;
    }
    mx = -1e9 - 5, mn = 1e9 + 5;
    for (ll i = id2; i <= n;i++)
    {
        mx = max(mx, a[i].y);
        mn = min(mn, a[i].y);
    }
    if(1.0*(mx-mn)>2*err)
    {
       // cout << "3!!\n";
        return false;
    }
    if(1.0*mn+err<val2||1.0*mn+err<0)
    {
       // cout << "3!!\n";
        return false;
    }
    return true;
}
int main()
{
    ll T = 1;
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        double l = 0, r;
        for (ll i = 1; i <= n;i++)
        {
            scanf("%lld %lld", &a[i].x, &a[i].y);
            r = max(abs(1.0*a[i].y), r);
        }
        //r = INF;
        sort(a + 1, a + 1 + n);
        double mid;
        while(r-l>eps)
        {
            mid = (r + l) / 2;
            //cout << mid << "\n";
            if(check(mid))
            {
                r = mid+1e-3;
            }else
            {
                l = mid-1e-3;
            }
        }
        printf("%.1lf",(r + l) / 2);
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}