多校联赛9补题

, ,
日常暴零~嘤嘤嘤~
2019-08-19

###1Rikka with Coin
####思路

首先 10 分的硬币最多只会用一个，如果用了两个，直接替换成一个 10 分一个 20 分一定不亏。
20 分的硬币最多只会用三个，如果用了四个，直接替换成一个 10 分两个 20 分一个 50 分一定不亏。
50分的硬币最多只会用一个，如果用了两个，直接替换成一个 50 分和一个一元一定不亏。
对于任何一种情况，重复使用上述规则一定会达到一个 分硬币最多一个， 分最多三个， 分最
多一个的情况，不会陷入重复甩锅的死循环。

关键：
贪心思想

####AC代码:

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
#include<bits/stdc++.h>
using namespace std;
#define maxn 110
typedef long long ll;
ll a[maxn];
ll n, num1 = 0, num2 = 0, num3 = 0;
ll check()
{
    bool flag;
    ll ret = 0;
    for(int p = 1; p <= n; p++)
    {
        flag = false;
        ll res = 1000000000;
        for(int i = 0; i <= num1; i++)
        {
            for(int j = 0; j <= num2; j++)
            {
                for(int k = 0; k <= num3; k++)
                {
                    ll ans = i * 10 + j * 20 + k * 50;
                    if(ans > a[p])
                        continue;
                    if((a[p] - ans) % 100 == 0)
                    {
                        flag = true;
                        res = min(res, (a[p] - ans) / 100);
                    }
                }
            }
        }
        if(flag)
            ret = max(ret, res);
        else
            break;
    }
    if(!flag)
        return -1;
    return ret;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        for(int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        ll num = 100000000000;
        bool flag = false;
        for(int i = 0; i <= 1; i++)
        {
            for(int j = 0; j <= 3; j++)
            {
                for(int k = 0; k <= 1; k++)
                {
                    num1 = i;
                    num2 = j;
                    num3 = k;
                    if(check() == -1)
                        continue;
                    else
                    {
                        flag = true;
                        num = min(num, num1 + num2 + num3 + check());//check()为100
                    }
                }
            }
        }
        if(flag)
            printf("%lld\n", num);
        else
            printf("-1\n");
    }
    return 0;
}

###2Rikka with Cake
####思路

题意：k条射线把平面分成多少个联通块？
思路：个数=交点数+1.先离散化
线段树或者树状数组的区间修改+单点查询

#####逆序对数

  • 逆序数

跟标准列相反序数的总和
2 4 3 1 5
4 之前有0个
3 之前有1个
1 之前有3个
5 之前有0个
所以逆序数就是1+3=4

  • 逆序对数

对于一个给定的数列,如果有i<j,且Ai>Aj,则称(i,j)为一逆序对.
要解决的问题是,给出一个数列,求出这个数列包含多少个逆序对。
例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,❤️,2><4,2><5,2>，共4个。

差不多的概念

#####离散化

二维坐标离散化模板

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
typedef pair<int, int> P;
vector<int> vx, vy;
vector<P> t[maxn], ask[maxn];
int T, n, m, k;

struct line
{
    int x, y;
    char dir;
} a[maxn];

void LiSanhua(line a[], int k)
{

    vx.clear();
    vy.clear();
    for(int i = 1; i <= k; i++)
        scanf("%d%d %c", &a[i].x, &a[i].y, &a[i].dir), vx.push_back(a[i].x), vy.push_back(a[i].y);//空格好评
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());//unique去重
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    n = vx.size() + 1;
    m = vy.size() + 1;
    for (int i = 1; i <= k; i++)
        a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin() + 1, a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin() + 1;
//    for (int i = 1; i <= k; i++)
//    {
//        printf(i == k ? "%d %d " : "%d %d\n", a[i].x, a[i].y);
//    }
}

####AC代码1(树状数组)

求交点数的话，离散化后，树状数组维护x坐标，将上下射线的+1和-1放到对应的y坐标，左右射线查询对应区间，按这样的做法，由y小到大扫一遍。复杂度O(k×log⁡(k))O(k \times \log(k))

自己写了一个
感觉要复习一下树状数组了

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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
#define debug(a) cout << "*" << a << "*" << endl
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;
class TA
{
private:
    int e[maxn];
    int len = maxn;
    int lowbit(int k)
    {
        return k & (-k);
    }
public:
    void add(int x,int v)													//区间更新
    {
        while(x <= len)
            e[x] += v,x += lowbit(x);
    }
    void init(int* getin,int _len)											//初始化
    {
        len = _len;
        for(int i = 1; i <= len; i ++)
            add(i,*(getin + i - 1));
    }
    void init_0()
    {
        len = maxn,memset(e, 0, sizeof(e));
    }
    int getsum(int x)														//询问
    {
        int sum = 0;
        while(x > 0)
            sum += e[x],x -= lowbit(x);
        return sum;
    }
}ta;

typedef pair<int, int> P;
vector<int> vx, vy;
vector<P> t[maxn], ask[maxn];
int T, n, m, k;

struct line
{
    int x, y;
    char dir;
} a[maxn];

bool cmp(line a, line b)
{
    return a.x < b.x;
}

void LiSanhua(line a[], int k)
{

    vx.clear();
    vy.clear();
    for(int i = 1; i <= k; i++)
        vx.push_back(a[i].x), vy.push_back(a[i].y);//空格好评
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());//unique去重
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    n = vx.size() + 1;
    m = vy.size() + 1;
    for (int i = 1; i <= k; i++)
        a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin() + 1, a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin() + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        ll ans = 0;
        cin >> n >> m >> k;
        for (int i = 1 ; i  <=  k; i++)
            cin >> a[i].x >> a[i].y >> a[i].dir;
        //离散化函数
        LiSanhua(a, k);
        //
        sort(a + 1, a + k + 1, cmp);
        
        ta.init_0();
        for (int i = 1; i <= k; i++)
        {
            if (a[i].dir == 'U')
            {
                ta.add(m, -1);
                ta.add(a[i].y, 1);
            }
            else if (a[i].dir == 'D')
            {
                ta.add(1, 1);
                ta.add(a[i].y + 1, -1);
            }
            else if (a[i].dir == 'L')
            {
                ans += ta.getsum(a[i].y);
            }
        }
        ta.init_0();
        for (int i = k; i >= 1; i--)
        {
            if (a[i].dir == 'U')
            {
                ta.add(m, -1);
                ta.add(a[i].y, 1);
            }
            else if (a[i].dir == 'D')
            {
                ta.add(1, 1);
                ta.add(a[i].y + 1, -1);
            }
            else if (a[i].dir == 'R')
            {
                ans += (ta.getsum(a[i].y));
            }
        }
        cout << ans + 1 << endl;
    }
    return 0;
}
//764MS	9340K

参考的大佬代码

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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description:
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 5;
class TA
{
private:
    int e[maxn];
    int len;
    int lowbit(int k)
    {
        return k & (-k);
    }
public:
    void add(int x,int v)													//区间更新
    {
        while(x <= len)
            e[x] += v,x += lowbit(x);
    }
    void init(int* getin,int _len)											//初始化
    {
        len = _len;
        for(int i = 1; i <= len; i ++)
            add(i,*(getin + i - 1));
    }
    void init_0()
    {
        len = maxn,memset(e, 0, sizeof(e));
    }
    int getsum(int x)														//询问
    {
        int sum = 0;
        while(x > 0)
            sum += e[x],x -= lowbit(x);
        return sum;
    }
}ta;

typedef pair<int, int> P;
vector<int> vx, vy;
vector<P> t[maxn], ask[maxn];
int T, n, m, k;

struct line
{
    int x, y;
    char dir;
} a[maxn];

void LiSanhua(line a[], int k)
{

    vx.clear();
    vy.clear();
    for(int i = 1; i <= k; i++)
        vx.push_back(a[i].x), vy.push_back(a[i].y);//空格好评
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());//unique去重
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    n = vx.size() + 1;
    m = vy.size() + 1;
    for (int i = 1; i <= k; i++)
        a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin() + 1, a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin() + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        ll ans = 0;
        cin >> n >> m >> k;
        for (int i = 1 ; i  <=  k; i++)
            cin >> a[i].x >> a[i].y >> a[i].dir;
        //离散化函数
        LiSanhua(a, k);
        for (int i = 0; i <= max(n, m); i++)
            t[i].clear(), ask[i].clear();

        for (int i = 1; i <= k; i++)
            if (a[i].dir == 'U')
                t[a[i].y].push_back(make_pair(a[i].x, 1));
            else if (a[i].dir == 'D')
                t[1].push_back(make_pair(a[i].x, 1)), t[a[i].y + 1].push_back(make_pair(a[i].x, -1));
            else if (a[i].dir == 'R')
                ask[a[i].y].push_back(make_pair(a[i].x, n - 1));
            else
                ask[a[i].y].push_back(make_pair(1, a[i].x));

        //树状数组操作
        ta.init_0();
        for (int i = 1; i <= m; i++)
        {
            for (int j = 0 ; j < t[i].size(); j++)
                ta.add(t[i][j].first, t[i][j].second);

            for (int j = 0; j < ask[i].size(); j++)
                ans += ta.getsum(ask[i][j].second) - ta.getsum(ask[i][j].first - 1);
        }
        cout << ans + 1 << endl;
    }
    return 0;
}
//764MS 12024K

####AC代码2(线段树)

由于是射线，因此容易知道每一次射线的相交都会使答案+1，考虑用线段树求解。按照起始点的x坐标对射线排序，对y轴坐标离散化，从左往右更新，遇到向上或者向下的射线，对线段树上的对应区间+1，遇到向左的射线，对线段树进行单点查询，答案加上查询结果。初始化线段树后，从右往左更新，处理向右的射线，其余不变。处理完毕后即可得到答案。由于只需要线段树中叶节点的值，因此可以不用pushUp函数。

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
/*************************************************************************
 > FileName:
 > Author:      Lance
 > Mail:        lancelot_hcs@qq.com
 > Date:        9102.1.8
 > Description: Discretization 离散化
 ************************************************************************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//add_stack
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <vector>
#include <cstdio>
#include <bitset>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const int eps = 1e-10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;//int2147483647//ll9e18//unsigned ll 1e19
const int maxn = 1e5 + 10;

typedef pair<int, int> P;
vector<int> vx, vy;
vector<P> t[maxn], ask[maxn];
int T, n, m, k;


int a_t[maxn];
struct node
{
    ll sum;
    ll lazy;

} A[maxn << 2];

void build(int u, int l, int r)
{
    A[u].lazy = 0;
    if (l == r)
    {
        A[u].sum = 0;//这里可以改为初始数组的
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid);
    build(2 * u + 1, mid + 1, r);
    A[u].sum = A[2 * u].sum + A[2 * u + 1].sum;//等价pushup操作
}

//下放操作，将当前的lazy下放
void pushdown(int u, int l,int  r)
{
    if (A[u].lazy == 0)
        return ;
    int mid = (l + r) / 2;
    A[u * 2].sum += A[u].lazy * (mid - l + 1);
    A[u * 2 + 1].sum += A[u].lazy * (r - mid);
    A[u * 2].lazy += A[u].lazy;
    A[u * 2 + 1].lazy += A[u].lazy;
    A[u].lazy = 0;
}

//l,r表示更新区间sl,sr一开始为1, n, u == 1

void add(int u, int sl, int sr, int l, int r, ll k)
{
    if (l > sr || r < sl)
        return ;
    if (l <= sl && r >= sr)
    {
        A[u].sum += k * (sr - sl + 1);
        A[u].lazy += k;
        return ;
    }
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    add(2 * u, sl, mid, l, r, k);
    add(2 * u + 1, mid + 1, sr, l, r, k);
    A[u].sum = A[u * 2].sum + A[u * 2 + 1].sum;
    return ;
}

ll query(int u, int sl, int sr, int l, int r)
{
    if (l > sr || r < sl)
        return 0;
    if (l <= sl && r >= sr)
        return A[u].sum;
    pushdown(u, sl, sr);
    int mid = (sl + sr) / 2;
    return (query(2 * u, sl, mid, l, r) + query(2 * u + 1, mid + 1, sr, l, r));
}


struct line
{
    int x, y;
    char dir;
    bool operator <(const line &A) const
    {
        return x < A.x;
    }
} a[maxn];

void LiSanhua(line a[], int k)
{

    vx.clear();
    vy.clear();
    for(int i = 1; i <= k; i++)
        vx.push_back(a[i].x), vy.push_back(a[i].y);//空格好评
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());//unique去重
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    n = vx.size() + 1;
    m = vy.size() + 1;
    for (int i = 1; i <= k; i++)
        a[i].x = lower_bound(vx.begin(), vx.end(), a[i].x) - vx.begin() + 1, a[i].y = lower_bound(vy.begin(), vy.end(), a[i].y) - vy.begin() + 1;
}


int main()
{
    scanf("%d", &T);
    while (T--)
    {
        ll ans = 0;
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= k; i++)
            scanf("%d%d %c", &a[i].x, &a[i].y, &a[i].dir);
        LiSanhua(a, k);
        build(1, 1, m);
        sort(a + 1, a + k + 1);
        for (int i = 1; i <= k; i++)
        {
            if (a[i].dir == 'U')
            {
                add(1, 1, m, a[i].y, m, 1);
            }
            else if (a[i].dir == 'D')
            {
                add(1, 1, m, 1, a[i].y, 1);
            }
            else if (a[i].dir == 'L')
            {
                ans += query(1, 1, m, a[i].y, a[i].y);
            }
        }
        build(1, 1, m);
        for (int i = k; i >= 1; i--)
        {
            if (a[i].dir == 'U')
            {
                add(1, 1, m, a[i].y, m, 1);
            }
            else if (a[i].dir == 'D')
            {
                add(1, 1, m, 1, a[i].y, 1);
            }
            else if (a[i].dir == 'R')
            {
                ans += query(1, 1, m, a[i].y, a[i].y);
            }
        }
        printf("%lld\n", ans + 1);
    }
    return 0;
}
//1076MS	13056K

###本文参考

大佬博客1
大佬博客2