https://codeforces.com/contest/1153
E. Serval and Snake
题意：交互题。给定一个n*n的网格，n小于1001，里面有一条链，可能是弯曲的，不超过2019次询问，每次询问对一个矩形，有几次经过这个矩形边界。求链的两个端点坐标。
二分
一个矩形如果包含了链的几个节点，那就可以看成这几个节点缩点了。原来是一条链，是一个欧拉路径，缩点后必定还是欧拉路径或欧拉回路。
如果矩形包含一个端点，则有奇数个度，如果包含两个或者0个，则有偶数个度。
考虑询问每一行，如果这一行包含一个端点，则有奇数度，确定行后二分确定列坐标。
如果两个端点在同一行，则无法得到结果。但是这两点就必定不在同一列了，所以再询问每一列，确定列后同样二分确定行坐标。因为知道是同一行了，所以只要二分一次就得到两个的行坐标了。
最差情况询问每一行每一列+一次二分，2010次。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
int qry(int x1, int y1, int x2, int y2) {
int res;
cout << "? " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
cin >> res;
return res;
}
void ans(int x1, int y1, int x2, int y2) {
cout << "! " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
exit(0);
}
int sol(int r) {
int L = 1, R = n;
while (L < R) {
int mid = (L + R) / 2;
if (qry(r, 1, r, mid) & 1)R = mid;
else L = mid + 1;
}
return L;
}
int sol2(int c) {
int L = 1, R = n;
while (L < R) {
int mid = (L + R) / 2;
if (qry(1, c, mid, c) & 1)R = mid;
else L = mid + 1;
}
return L;
}
int main() {
scanf("%d", &n);
int q = 0;
for (int i = 1; i <= n; i++) {
if (qry(i, 1, i, n) & 1) { q = i; break; }
}
if (q != 0) {
int x1 = q, y1 = sol(q);
for (int i = n; i >= 1; i--) {
if (qry(i, 1, i, n) & 1) { q = i; break; }
}
int x2 = q, y2 = sol(q);
ans(x1, y1, x2, y2);
}
else {
for (int i = 1; i <= n; i++) {
if (qry(1, i, n, i) & 1) { q = i; break; }
}
int x1 = sol2(q), y1 = q;
for (int i = n; i >= 1; i--) {
if (qry(1, i, n, i) & 1) { q = i; break; }
}
int x2 = x1, y2 = q;
ans(x1, y1, x2, y2);
}
return 0;
}
|
F. Serval and Bonus Problem
题意：给定一个范围 0 到 l 的 x 轴，要随机选出 n 个线段，它们的 2n 个端点分出 2n+1 个小间隔，求所有被至少 k 个线段覆盖的小间隔的长度和的数学期望。1≤k≤n≤2000,1≤l≤109
dp，数学期望
由于是完全随机的，所以每个小间隔的长度期望都相等，所以都是 2n+1l。那么只要求出每一个小间隔被覆盖 k 次的概率，再遍历所有小间隔，乘上长度再求和就是答案。
假设小间隔标号0到2n，点标号1到2n，则第 i 个间隔在第 i 和第 i+1 个点之间。
对于一个间隔，如果一条线段的左端点是这个间隔的左端点，则这个间隔被覆盖。
dp[i][j] 表示到前 i 个点，有 j 个点没有闭合的方案数。
对于点 i，它可以不闭合，则由 dp[i−1][j−1] 转移；也可以闭合，则前 i-1 个点有 j+1 个没闭合，点 i 可以和其中任一个闭合，由 dp[i−1][j+1]∗(j+1) 转移。
对于第 i 个间隔，没有闭合的点数 j 就是它被覆盖的次数。
前 i 个点中 j 个没闭合的点与后 2n-i 个点中 j 个没闭合的点配对，形成线段，那么还应该再反向求一个dp，再得到反向的 dp[2n−i][j]，但是要知道这是非常对称的，反向和正向是一样的，所以直接用正向的dp值即可。
还要注意前 j 个点和后 j 个点可以以任意顺序配对形成线段，所以还应该乘以 j 的全排列。
dp[2n][0] 就是2n个点全都闭合的方案数，也就是全部的方案数，也就是分母。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 1e6 + 10;
int n, k;
ll l, p[2020];
ll Pow(ll a, ll b) {
ll res = 1ll;
while (b) {
if (b & 1)res = res * a%mod;
a = a * a%mod;
b >>= 1;
}
return res;
}
ll dp[4020][2020], ans;
int main() {
scanf("%d%d%lld", &n, &k, &l);
p[0] = 1ll;
for (int i = 1; i <= n; i++)p[i] = p[i - 1] * i%mod;
dp[1][1] = 1ll;
for (int i = 2; i <= 2 * n; i++) {
for (int j = 0; j <= min(i, n); j++) {
dp[i][j] = dp[i - 1][j + 1] * (j + 1) % mod;
if (j > 0)dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
}
}
for (int i = 1; i < 2 * n; i++) {
for (int j = k; j <= min(i, n); j++) {
ans = (ans + dp[i][j] * dp[2 * n - i][j] % mod*p[j] % mod) % mod;
}
}
ans = ans * l % mod * Pow(2 * n + 1, mod - 2) % mod * Pow(dp[2 * n][0], mod - 2) % mod;
printf("%lld\n", ans);
return 0;
}
|
