BUPT_2022_summer_1

发表于 | 分类于 |

F(数据结构:点更新、查询最值线段树)

给定N个正整数，N<=400000，数字会重复，但每个数都小于等于N，求字典序最小的A、B满足：该数列中含有A、B、A、B子序列(不一定连续)

题解:第一眼能猜到是个数据结构题，但不会推(

思路1：A、B、A、B，是一个交错结构，可以先想查询ABA子序列，则只需要知道下一个A的位置(预处理中能得到)，在两个位置之间查询最小值即为B，可在NlogN内完成，如果替换成ABAB的情况，则我们需要保证查询到的最小值B，其在两个A的间隔之后，仍存在一个B，很麻烦。

故转化思路，在遍历到时，将其看作B，查询BAB中的A，而A是遍历到之前插入线段树的，故在两个B之前必定存在一个A

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
#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 int maxn = 400005;
const int INF = 0x3f3f3f;
int tmp;
int n;
int a[400005];
int nxt[400005];
int lst[400005];
struct seg_node
{
    int val;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = min(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void build(ll left = 1, ll right = n, ll rt = 1)
{
    if (left == right)
    {
        segtree[rt].val = INF;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
void point_update(int point, int value, int left = 1, ll right = n, ll rt = 1)
{
    if (left == right)
    {
        segtree[rt].val = min(segtree[rt].val, value);
        return;
    }
    int mid = (left + right) >> 1;
    if (point <= mid)
    {
        point_update(point, value, left, mid, rt << 1);
    }
    else
    {
        point_update(point, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}
int part_query(int l, int r, int left = 1, int right = n, int rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val;
    }
    if (l > right || r < left)
    {
        return INF;
    }
    int mid = (left + right) >> 1;
    return min(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}

int main()
{
    n = read();
    memset(lst, 0, sizeof(lst));
    memset(nxt, 0, sizeof(nxt));
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    for (int i = n; i >= 1; i--)
    {
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    build(1, n, 1);
    int tmp, A = INF, B = INF;
    for (int i = 1; i <= n; i++)
    {
        if (nxt[i] == 0)
        {
            continue;
        }
        tmp = part_query(i+1, nxt[i]-1);
        if (tmp != INF)
        {
            if (tmp < A)
            {
                A = tmp;
                B = a[i];
            }
            else if (tmp == A)
            {
                B = min(B, a[i]);
            }
        }
        point_update(nxt[i], a[i]);
    }
    if (A == INF || B == INF)
    {
        write(-1);
        putchar('\n');
    }
    else
    {
        write(A);
        putchar(' ');
        write(B);
        putchar('\n');
    }
    return 0;
}

思路2：题目要求字典序最小，故我们找出满足题目条件的A，在A之间再找B，略复杂

G(数学、排列组合计数问题)

题意:给定RxC的方格，给定整数K(1<=K<=R*C)，在方格上找到N个矩形，满足所有矩形的共有区域的格数大于等于K，求矩形有多少种摆放方式(注意:矩形的顺序也有影响)

题解:预处理出共有区域大小刚好为i的摆放方式，最后枚举i从K到MAX的和

问题:如何预处理以至于不漏、不重复?可以看出共有区域必定是个矩形，故我们从矩形的row和column两方面考虑，若i块矩形，其row的位置有m种可能，column的位置有n种可能，则一共有m*n种摆放方式。故我们只需处理出共有区域的row的长度为1~R时，其所对应的可能数，column的长度从1~C，其所对应的可能数，最后汇总答案即可。

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
#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 mod = 1e9 + 7;
ll T, n, r, c, k;
ll pr[5005], pc[5005];
ll p[5006];
ll ksm(ll x, ll y)
{
    if (x == 0)
    {
        return 0;
    }
    ll ret = 1;
    while (y)
    {
        if (y & 1)
        {
            ret = (ret * x) % mod;
        }
        x = (x * x) % mod;
        y /= 2;
    }
    return ret;
}
void pre()
{
    ll cnt;
    for (ll len = 1; len <= r; len++)
    {
        cnt = 0;
        for (ll l = 1; l + len - 1 <= r; l++)
        {
            cnt += (p[l] - p[l-1])* (p[r - (l + len - 1) + 1] - p[r - (l + len - 1)]) % mod;
            // cout << cnt << "!!\n";
            cnt %= mod;
        }
        pr[len] = cnt;
        // cout << "pr" << len << "==" << pr[len] << "\n";
    }
    for (ll len = 1; len <= c; len++)
    {
        cnt = 0;
        for (ll l = 1; l + len - 1 <= c; l++)
        {
            cnt += (p[l]-p[l-1]) * (p[c - (l + len - 1) + 1] - p[c - (l + len - 1)]) % mod;
            cnt %= mod;
        }
        pc[len] = cnt;
        // cout << "pc" << len << "==" << pc[len] << "\n";
    }
}
int main()
{
    T = 1;
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> r >> c >> k;
        for (ll i = 0; i < 5005; i++)
        {
            p[i] = ksm(i, n);
        }
        pre();
        ll ans = 0;
        for (ll i = 1; i <= r; i++)
        {
            for (ll j = 1; j <= c; j++)
            {
                if (i * j >= k)
                {
                    ans += pr[i] * pc[j];
                    ans %= mod;
                }
            }
        }
        cout << (ans+mod)%mod << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

D(环型贪心、二倍环展开)

题意:给定N个数组成的圆环，求将圆环上的数分割成K组后，每组的OR值的AND值最大

题解:位运算很容易想到从高到低位考虑，当第i位为1的数不足k个，或将其分为k组的分法与更高位的分法相悖时，第i位对答案没有贡献。

我们就考虑1位时，很明显若当前位出现1时，将其划分到一组，最后看能划分出的组数大于等于k，即存在答案

而若考虑2位时，先将最高位按上述处理，若最高位对答案有贡献，则当前位和最高位都为1时，才将其划分到一组，最后也是看划分出的组数是否大于等于k

环问题，则将其转化成2n的序列，则划分出的组数要大于等于2k-1(将环变成二倍环，展开后最多减少1个组数，即2k-1满足条件—如果不扩展成二倍环，无法区分最后组数是否收到展开的影响而-1)

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
#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 = 100005;
ll tmp;
ll n, m, T, k;
ll a[1000005];
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> k;
        for (ll i = 1; i <= n;i++)
        {
            cin >> a[i];
            a[i + n] = a[i];//将环展开
        }
        ll ans = 0;
        for (ll i = 30; i >= 0;i--)//从高位枚举到低位贪心
        {
            ll cnt = 0, tmp = 0;
            for (ll j = 1; j <=2* n;j++)
            {
                tmp |= a[j];
                if(((ans|(1<<i))&(tmp))==(ans|(1<<i)))//此时的值满足成组条件
                {
                    cnt++;
                    tmp = 0;//重置
                }
            }
            if(cnt>=2*k-1)
            {
                ans |= (1 << i);
            }
        }
        cout << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}