BUPT-2022-summer-6

发表于 | 分类于 |

校内最后一场

M(构造、位运算性质)

大致题意：给定n和m，再给定n个数，，其中每个数都>=0且<=且都不相同，由给定个数,对任意的i都满足:i⊕>i⊕(j为不等于i的任何数)，现给定n、m、y，求有多少种x数列满足条件

题解:观察i，可将个i分为前半部分与后半部分，且前半部分与后半部分对应位置的i仅最高位不同，前半部分最高位恒为1，后半部分最高位恒为0，易知：

  1. 若x中同时含有最高位为1和最高位为0的数，前半部分总是选择最高位为0的数，后半部分总是选择最高位为1的数，这样其异或后最高位才为1，而这是满足最大的前提条件
  2. 若x中只含有最高位为1或只含有最高位为0的数，以只含有最高位为1的情况举例，前半部分其异或后最高位都只能为0，而后半部分异或后最高位总是为1，又由于前半部分和后半部分对应位置的i仅最高位不同，故前半部分的y和后半部分对应位置的y总是相同，可递归到前半部分或后半部分解决

而题目给定了y，故首先判断前半部分和后半部分对应y值是否全都不同，若全都不同，则满足条件1，两部分再分别递归解决；若有相同的，则可能满足条件2，再进一步判断是否前半部分和后半部分对应y值都相同，若都相同，则递归到前半部分或后半部分解决问题，此时最高位取1或0都可以，故序列总数为前半部分的序列总数*2，若存在不同，则与上述条件相悖，故答案为0

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
#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 =  (1<<16)+5;
const ll mod = 1e9+7;
ll p[maxn];
ll tmp, T, n, m;
ll ans=1;
void solve(ll l,ll r)//11 00
{
    if(l==r)
    {
        return;
    }
    ll mid = (r + l) >> 1;
    bool flag = 0;
    for (ll i = l; i <= mid;i++)
    {
        if(p[i]!=p[mid+i-l+1])
        {
            flag = 1;
        }
    }
    if(!flag)//前后半相同
    {
        ans *= 2;
        ans %= mod;
        solve(l, mid);
        return;
    }
    //flag为1，存在不同
    for (ll i = l; i <= mid;i++)
    {
        if(p[i]==p[mid+i-l+1])
        {
            flag = 0;
            break;
        }
    }
    if(!flag)
    {
        ans = 0;
        return;
    }else
    {
        solve(l, mid);
        solve(mid + 1, r);
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> m >> n;
        for (ll i = 1; i <= (1 << (m));i++)
        {
            cin >> p[i - 1];
        }
        ans = 1;
        solve(0, (1 << (m)) - 1);
        cout << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

G(扫描线)

大致题意:给定n个矩形的坐标，求是否有矩形相交(包含不属于相交)

题解:算是扫描线的模板题吧，思路是先对横坐标离散化后用线段树维护横坐标区间和，扫描到下边时，查询下边横坐标范围内区间和是否大于0，若大于0，则存在至少一个矩阵其左下端点或右下端在该范围内，构成相交条件，更新时，若遇到下边，将左右端点的对应位置值+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
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 = 100005;
ll T, n;
struct node
{
    ll l, r, cnt;
};
ll num;
node tree[maxn << 3]; //左右端点+线段树，一共乘8
void build(ll l = 1, ll r = num, ll rt=1)
{
    tree[rt].cnt = 0;
    tree[rt].l = l, tree[rt].r = r;
    if(l==r)
    {
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
}
void pushup(ll rt)
{
    tree[rt].cnt = tree[rt << 1].cnt + tree[rt << 1 | 1].cnt;
}
ll query(ll ql,ll qr,ll l=1,ll r=num,ll rt=1)
{
    if(l>=ql&&r<=qr)
    {
        return tree[rt].cnt;
    }
    ll mid = (l + r) >> 1, ret = 0;
    if(l>qr||r<ql)
    {
        return 0;
    }
    if(ql<=mid)
    {
        ret += query(ql, qr, l, mid, rt << 1);
    }
    if(mid<qr)
    {
        ret += query(ql, qr, mid + 1, r, rt << 1 | 1);
    }
    return ret;
}
void update(ll x,ll val,ll l=1,ll r=num,ll rt=1)
{
    if(l==r&&r==x)
    {
        tree[rt].cnt += val;
        return;
    }
    ll mid = (l + r) >> 1;
    if(x<=mid)
    {
        update(x, val, l, mid, rt << 1);
    }else
    {
        update(x, val, mid + 1, r, rt << 1 | 1);
    }
    pushup(rt);
}
ll lsh[maxn << 1];
struct seg
{
    ll x1, x2;
    ll y;
    ll val;
    bool operator < (const seg&b)
    {
        return y < b.y;
    }
};
seg a[maxn<<1];
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        //ll x1, x2, y1, y2;
        for (ll i = 1; i <= n;i++)
        {
            cin >> a[i].x1 >> a[i].y>>a[i].x2 >> a[i + n].y;
            a[i].val = 1, a[i + n].val = -1;
            lsh[i] = a[i].x1;
            lsh[i + n] = a[i].x2;
        }
        sort(lsh + 1, lsh + 1 + 2 * n);
        num = unique(lsh + 1, lsh + 1 + 2 * n) - lsh - 1;
        for (ll i = 1; i <= n;i++)
        {
            a[i].x1 = lower_bound(lsh + 1, lsh + 1 + num, a[i].x1) - lsh;
            a[i].x2 = lower_bound(lsh + 1, lsh + 1 + num, a[i].x2) - lsh;
            a[i + n].x1 = a[i].x1, a[i + n].x2 = a[i].x2;
        }
        sort(a + 1, a + 1 + 2 * n);
        build();
        bool flag = 0;
        for (ll i = 1; i <= 2 * n;i++)
        {
            if(a[i].val==1)
            {
                if(query(a[i].x1+1,a[i].x2-1)>0)
                {
                    flag = 1;
                    break;
                }else
                {
                    update(a[i].x1, 1);
                    update(a[i].x2, 1);
                }
            }else
            {
                update(a[i].x1, -1);
                update(a[i].x2, -1);
            }
        }
        cout << (flag ? "1\n" : "0\n");
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

主要是对题设条件如何转化成线段树操作卡住了，扫描线算法应该以边为单位思考，两个矩形相交如何转化成两个下边的关系，两个下边的关系又如何转化成查询、更新操作

F(概率密度+树形dp)

被fft折磨了半天，再看这道题简直眉清目秀bushi

大致题意:给定包含n个节点(n<=300)的一颗树和其对应值(范围为1e9)，每个节点的值为0~内的任意一个数，现求该树能形成小顶堆的概率(即节点上的值严格小于其所有的子节点的值)

在场上的时候想了个离散化后直接树形dp，但是没考虑好，离散化后其实根本没法处理，是个很离谱的错解

正解思路:引入概率密度函数f(x)，即节点上的值为x的概率，此题中u节点若为叶子节点，显然f(x)=1/a[u]，0<=x<=a[u]时成立，而F(x)函数为f(x)的积函数,表示的是节点上的值小于等于x的概率(注意:该条件对任意的节点均成立)。

思考，除了叶子节点外，其他节点的f(x)如何考虑。显然，要根据树形dp转移，我们需要将上述条件加强。f(x)—节点上的值为x且子树满足小顶堆的概率，F(x)—节点上的值小于等于x且子树满足小顶堆的概率。

显然，对于非叶子节点u和其子节点v(有多个子节点，均是乘操作，为书写方便只取一个子节点),f(u,x)=1/a[u]*G(v,x),G(v,x)表示v节点的值大于x的概率。

如何求G(v,x)，显然要从F(v,x)入手，是1-F(v,x)?不，1实际上是F(v,a[v])，但很显然v节点的值的上界会收到其子节点的影响(必须比子节点小)，故取其所有子节点的a值最小值，与a[v]相比取最小值即为其新的上界。故G(v,x)=F(v,mn[v])-F[v,x]。

那么到此，此题基本结束，先求出本节点的f(x)，再积分得到F(x)，再通过上述计算得到G(x)，而最后的答案便是F(root,mn[root])，即G(root,x)的常数项。

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
#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 = 305;
const ll mod = 1e9 + 7;
ll tmp, T, n, m, s;
ll a[maxn + 5];
ll mn[maxn + 5];
ll quick(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;
}
ll inv(ll x)
{
    return quick(x, mod - 2);
}
struct Poly
{
    vector<ll> p;
};
Poly mul(const Poly &a, const Poly &b)
{
    Poly ret;
    ret.p.resize(a.p.size() + b.p.size() + 1,0);
    for (ll i = 0; i < (ll)a.p.size(); i++)
    {
        for (ll j = 0; j < (ll)b.p.size(); j++)
        {
            ret.p[i + j] = (ret.p[i + j] + a.p[i] * b.p[j]%mod) % mod;
        }
    }
    return ret;
}
ll cal(const Poly &a, ll x)
{
    ll ret = 0;
    for (ll i = (ll)a.p.size() - 1; i >= 1; i--)
    {
        ret = (ret + a.p[i] * quick(x, i)) % mod;
    }
    return (ret + a.p[0]) % mod;
}
Poly Int(const Poly &a)
{
    Poly ret;
    ret.p.resize(a.p.size() + 1, 0);
    for (ll i = 0; i < (ll)a.p.size(); i++)
    {
        ret.p[i + 1] = (a.p[i] * inv(i + 1)) % mod;
    }
    return ret;
}
vector<ll> g[maxn + 5];
Poly f[maxn + 5];
void dfs(ll x, ll fa)
{
    mn[x] = a[x];
    f[x].p.push_back(inv(a[x]));
    for (auto &e : g[x])
    {
        dfs(e, x);
        mn[x] = min(mn[e], mn[x]);
        f[x] = mul(f[x], f[e]);
    }
    f[x] = Int(f[x]);
    f[x].p[0] = cal(f[x], mn[x]);
    for (ll i = 1; i < (ll)f[x].p.size(); i++)
    {
        f[x].p[i] = -f[x].p[i];
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        ll b, p;
        // memset(dp, 0, sizeof(dp));
        for (ll i = 1; i <= n; i++)
        {
            cin >> b >> p;
            a[i] = b;
            if (p != 0)
            {
                g[p].push_back(i);
            }
            else
            {
                s = i;
            }
        }
        dfs(s, 0);
        cout << (f[s].p[0]+mod)%mod << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

复杂度分析:n个节点*n次mul操作，而mul操作是，故最后是