2021-08-14新高二一期暑假集训11

发表于

【2018年12月多校联合集训A组day1】欧拉回路

标签:

计算几何

思路:

欧拉定理 : 在简单多面体中，设顶点数为 VV, 棱数为 EE, 面数为 FF. 有 V−E+F=2V - E + F = 2 。

这个定理有个拓展叫欧拉示性数，可以用来解决在非简单多面体中的问题。但是我不会。

但是欧拉定理在多边形中是适用的，无论是否是简单多边形.

已知棱数，所以只要求出交点数，就可以求出面数了

Code:

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 <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const double eps = 1e-8;

int n;

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1;
}

struct Vector {
    double x, y;

    friend Vector operator + (Vector A, Vector B) {
        Vector C;
        C.x = A.x + B.x;
        C.y = A.y + B.y;
        return C;
    }

    friend Vector operator - (Vector A, Vector B) {
        Vector C;
        C.x = A.x - B.x;
        C.y = A.y - B.y;
        return C;
    }

    friend Vector operator * (Vector A, double c) {
        Vector C;
        C.x = A.x * c, C.y = A.y * c;
        return C;
    }

    friend bool operator < (Vector A, Vector B) {
        if (A.x == B.x) {
            return A.y < B.y;
        }
        else return A.x < B.x;
    }

    friend bool operator == (Vector A, Vector B) {
        return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0;
    }
};

double dot (Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}

double cross(Vector A, Vector B) {
    return A.x * B.y - A.y * B.x;
}

std::pair<bool, Vector> get_point(Vector p, Vector v, Vector q, Vector w) {
    if (fabs(cross(v, w)) < eps) return std::make_pair(0, (Vector){0, 0});
    Vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return std::make_pair(1, p + v * t);
}

double min(double a, double b) {
    return a < b ? a : b;
}

double max(double a, double b) {
    return a > b ? a : b;
}


bool Check(Vector x, Vector s, Vector t) {
    return dcmp(cross(s - x, t - x)) == 0 && dcmp(dot(s - x, t - x)) < 0;
}

bool ccheck(Vector a1, Vector a2, Vector b1, Vector b2)
{
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

Vector p[610];
Vector s[610], t[610];
std::vector<Vector> v;

int main() {
    while (scanf("%d", &n), n != 0) {
        v.clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
            v.push_back(p[i]);
        }
        --n;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (ccheck(p[i], p[i + 1], p[j], p[j + 1])) {
                    v.push_back(get_point(p[i], p[i + 1] - p[i], p[j], p[j + 1] - p[j]).second);
                }
            }
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int V = v.size();
        int E = n;
        for (auto w : v) {
            for (int i = 1; i <= n; ++i) {
                if (Check(w, p[i], p[i + 1])) ++E;
            }
        }
        std::cout << E - V + 2 << std::endl;
    }
    return 0;
}

【2018年12月多校联合集训A组day1】光线追踪

标签

线段树 + 计算几何

思路

发现一个长方形只有左边的边和下面的边是有用的，所以分别计算左边的边和下面的边。考虑左边的边，把每条边的端点和询问极角排序后离散化，显然最先碰到的障碍物是横坐标最接近 00 的，只需要区间取最小值和单点查询就行. 下面的边同理.

Code

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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define int long long

using namespace std;

const int N = 5e5 + 10;

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

struct Vector {
    int x, y;

    friend bool operator < (Vector A, Vector B) {
        return 1ll * A.x * B.y - 1ll * A.y * B.x > 0;
    }
    
    friend bool operator == (Vector A, Vector B) {
        return 1ll * A.x * B.y - 1ll * A.y * B.x == 0;
    }
};

int n;
pair<int, int> val[4 * N + 20];

struct Segementtree {

    Segementtree (int _n) {
        n = _n;
        std::fill(val, val + 4 * N + 1, make_pair(0x3f3f3f3f, 0));
    }

    void resize(int _n) {
        n = _n;
        std::fill(val, val + 4 * N + 1, make_pair(0x3f3f3f3f, 0));
    }

    pair<int, int> operator [] (int i) {
        return val[i];
    }

    void change(int x, int y, pair<int, int> v, int u = 1, int l = 1, int r = n) {
        if (x <= l && r <= y) return val[u] = min(val[u], v), void();
        int mid = (l + r) >> 1;
        if (x <= mid) change(x, y, v, ls(u), l, mid);
        if (y > mid) change(x, y, v, rs(u), mid + 1, r);
    }

    pair<int, int> query(int x, int u = 1, int l = 1, int r = n) {
        if (l == r) return val[u];
        pair<int, int> res = val[u];
        int mid = (l + r) >> 1;
        if (x <= mid) res = min(res, query(x, ls(u), l, mid));
        else res = min(res, query(x, rs(u), mid + 1, r));
        return res;
    }
};

int Q;
Vector tmp[N];
int tot;
Vector VL[N], VR[N], VX[N];
int op[N], l[N], r[N], u[N], d[N], x[N], y[N];
int pos[N], L[N], R[N], V[N];
int X[N];
pair<int, int> ansl[N], ansd[N];
map<int, int> Mapl, Mapd;

signed main() {
    scanf("%lld", &Q);
    for (int i = 1; i <= Q; ++i) {
        scanf("%lld", &op[i]);
        if (op[i] == 1) {
            scanf("%lld%lld%lld%lld", &l[i], &d[i], &r[i], &u[i]); 
            tmp[++tot] = Vector{l[i], d[i]};
            VL[i] = tmp[tot];
            tmp[++tot] = Vector{l[i], u[i]};
            VR[i] = tmp[tot];
        }
        else {
            scanf("%lld%lld", &x[i], &y[i]);
            tmp[++tot] = Vector{x[i], y[i]};
            VX[i] = tmp[tot];
        }
    }
    sort(tmp + 1, tmp + tot + 1);
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 1) {
            L[i] = std::lower_bound(tmp + 1, tmp + tot + 1, VL[i]) - tmp;
            R[i] = std::lower_bound(tmp + 1, tmp + tot + 1, VR[i]) - tmp;
            V[i] = l[i];
        }
        else {
            X[i] = std::lower_bound(tmp + 1, tmp + tot + 1, VX[i]) - tmp;
        }
    }
    Segementtree st(tot + 1);
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 1) {
            if (l[i] == 0) continue;
            st.change(L[i], R[i], make_pair(V[i], -i));
        }
        else {
            if (x[i] == 0) continue;
        ansl[i] = st.query(X[i]);
        }
    }
    tot = 0;
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 1) {
            tmp[++tot] = Vector{r[i], d[i]};
            VL[i] = tmp[tot];
            tmp[++tot] = Vector{l[i], d[i]};
            VR[i] = tmp[tot];
        }
        else {
            tmp[++tot] = Vector{x[i], y[i]};
            VX[i] = tmp[tot];
        }
    }
    sort(tmp + 1, tmp + tot + 1);
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 1) {
            L[i] = lower_bound(tmp + 1, tmp + tot + 1, VL[i]) - tmp;
            R[i] = lower_bound(tmp + 1, tmp + tot + 1, VR[i]) - tmp;
            V[i] = d[i];
        }
        else {
            X[i] = lower_bound(tmp + 1, tmp + tot + 1, VX[i]) - tmp;
        }
    }
    st.resize(tot + 1);
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 1) {
            if (d[i] == 0) continue;
            st.change(L[i], R[i], make_pair(V[i], -i));
        }
        else {
            if (y[i] == 0) continue;
            ansd[i] = st.query(X[i]);
        }
    }
    for (int i = 1; i <= Q; ++i) {
        if (op[i] == 2) {
            if (1ll * ansl[i].first * y[i] == 1ll * x[i] * ansd[i].first) {
                printf("%lld\n", max(-ansl[i].second, -ansd[i].second));
            }
            else if (1ll * ansl[i].first * y[i] < 1ll * x[i] * ansd[i].first) {
                printf("%lld\n", -ansl[i].second);
            }
            else {
                printf("%lld\n", -ansd[i].second);
            }
        }
    }
    return 0;
}
/*                                                                                    
                *.                                                                                   
    .@@^       =@/                   .@@ .\@@]              .@@]]]]]]]]].     .@@        =@.=@\
      \@@` =@@@@@@@@@@@@^            .@@    ,/              .@@[[[[[[[[[`  ]]]]@@]]]`    =@. .[.     
       ,[. =@^        =@^  ,@@@@@@@@@@@@@@@@@@@@@@    /@@@@@@@@@@@@@@@`       .@@    @@@@@@@@@@@@    
           =@@@@@@@@@@@@^     ,\     .@@`     ,`      @@^           =@^       .@@    @@  =@^ ,].     
   .@@@@^  =@^        =@`     ,@@\   .@@@`  ,@@/.     @@@@@@@@@@@@@@@@^   =@@@@@@@@@O@@  ,@^.@@.     
      =@^  =@\]]]]]]]]]]]       \@/  .@@@@]@@/.       @@^           =@^     /\ =@^   @@ .`@@@@`      
      =@^  =@^        .@@         .]@@@@ \@@.         @@@@@@@@@@@@@@@@^     @@ =@\]]`@@@@`=@@..@@    
      =@^  =@^        .@@      ]@@@/`.@@  ,@@\`              @@^           .@@ =@^..,@@` /@@@^,@^    
      =@^  =@@@@@@@@@@@@@  ,@@@@[    .@@    ,@@@\. @@@@@@@@@@@@@@@@@@@@@@^ =@@@/@^     /@@. \@@@`    
    ,@@\@@],[`         ..   [.       =@@       [@/           @@^          .@@.\@@\].                 
    \/   ,[@@@@@@@@@@@@@@@`      =@@@@@`                     @@^          ,@`    [[\@@@@@@@@@@@@/    
                                                                                                        
*/

【2018年12月多校联合集训A组day1】是否

标签

期望 + 计数

思路

有一个很简单的想法，每次选择时，如果 YESYES 多就回答 YESYES, NONO 多就回答 NONO ， 一样多时随便猜。

有一个性质：至少答对 max(n,m)max(n,m) 个问题。因为如果答对，答对题数 +1+1, 如果没有答对，答对题数不变，但是另一种答案的数量会减小，考虑最惨的情况，每次都猜错，到最后一定剩下全是 YesYes 或全是 NoNo，然后回答就行

剩下的只用考虑剩下的 YesYes 和 NoNo 相等的情况，这时只能猜, 有 12\frac{1}{2} 的概率猜对.

把祂转化成一个格路计数问题，从 (0,0)(0, 0) 走到 (n,m)(n, m), 每次可以向上走或向右走，求期望经过 y=xy=x 多少次. 考虑 y=xy=x 上每个点的贡献，答案显然是 ∑i=1min⁡(n,m)(2ii)(n−i+m−in−i)(n+mn)\frac{\sum_{i=1}^{\min(n,m)}\tbinom{2i}{i}\tbinom{n - i + m - i}{n - i}}{\tbinom{n + m}{n}} ， 然后乘上 12\frac{1}{2} 再加上 max(n,m)max(n, m) 就行.

Code

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
#include <iostream>
#include <cstdio>
#define int long long

const int N = 1000010;
const int mod = 998244353;
int n, m;
int fac[N], inv[N], ifac[N];

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}

int C(int n, int m) {
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

signed main() {
    std::cin >> n >> m;
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    for (int i = 2; i <= n + m; ++i) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        fac[i] = fac[i - 1] * i % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    int ans = 0;
    for (int i = 1; i <= min(n, m); ++i) {
        ans = add(ans, C(2 * i, i) * C(n - i + m - i, n - i) % mod);
    }
    ans = ans * fac[m] % mod * fac[n] % mod * ifac[n + m] % mod * inv[2] % mod;
    std::cout << ans + max(n, m) << '\n';
    return 0;
}