小米OJ TCO 预选赛

其实粗粮OJ比赛时间一直都很友好,就是题目太少,只有三题,而且质量都不咋地。

题目链接:https://code.mi.com/contest/list/view?id=13


A:

讲那么多,答案就是k/2。

队友1分48秒切掉的题目……手速帝啊。

太水就不贴代码了。

B:

这道题题面错漏百出,以下面为准:

给定xOy平面上的n个整点,每对点(x1,y1),(x2,y2)可以确定一个矩形:矩形左上角点为(min(x1,x2),max(y1,y2)),矩形右下角点为(max(x1,x2),min(y1,y2))。于是可以得到n*(n-1)/2个矩形。

随机取出不同的矩形,问覆盖面积的期望值,输出答案mod 1e9+7意义下的逆元。

因为只有一千个点,离散化+O(n^2)统计完事了。

小米OJ TCO 预选赛
 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson curpos<<1
15 #define rson curpos<<1|1
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const ll mod = 1e9 + 7;
21 const int maxn = 1e3 + 10;
22 
23 pair<ll, ll> a[maxn], reg[maxn];
24 ll cnt[maxn][maxn], s[maxn][maxn];
25 vector<ll>vx, vy;
26 int n, m;
27 
28 inline ll cal(ll lx, ll ly, ll rx, ll ry) {
29     return 1LL * abs(rx - lx) * abs(ry - ly) % mod;
30 }
31 
32 inline ll qp(ll a, ll b) {
33     ll res = 1LL;
34     while (b) {
35         if (b & 1) res = res * a % mod;
36         a = a * a % mod;
37         b >>= 1;
38     }
39     return res;
40 }
41 
42 inline ll inv(ll a) {
43     return qp(a, mod - 2);
44 }
45 
46 inline void add(ll &a, const ll &b) {
47     a += b;
48     if (a >= mod) a -= mod;
49 }
50 
51 int main() {
52     cin >> n;
53     rep1(i, 1, n) {
54         cin >> a[i].first >> a[i].second;
55         vx.pb(a[i].first); vy.pb(a[i].second);
56     }
57     sort(vx.begin(), vx.end());
58     sort(vy.begin(), vy.end());
59     vx.erase(unique(vx.begin(), vx.end()), vx.end());
60     vy.erase(unique(vy.begin(), vy.end()), vy.end());
61     rep1(i, 1, n) {
62         reg[i].first = lower_bound(vx.begin(), vx.end(), a[i].first) - vx.begin();
63         reg[i].second = lower_bound(vy.begin(), vy.end(), a[i].second) - vy.begin();
64     }
65     memset(cnt, 0, sizeof(cnt));
66     rep1(i, 1, n) {
67         rep1(j, i + 1, n) {
68             int lx = min(reg[i].first, reg[j].first);
69             int rx = max(reg[i].first, reg[j].first);
70             int ly = min(reg[i].second, reg[j].second);
71             int ry = max(reg[i].second, reg[j].second);
72             cnt[lx][ly]++; cnt[rx][ry]++;
73             cnt[lx][ry]--; cnt[rx][ly]--;
74         }
75     }
76     rep0(i, 1, vy.size()) add(cnt[0][i], cnt[0][i - 1]);
77     rep1(i, 1, vx.size()) {
78         add(cnt[i][0], cnt[i - 1][0]);
79         rep1(j, 1, vy.size()) {
80             add(cnt[i][j], cnt[i - 1][j]);
81             add(cnt[i][j], cnt[i][j - 1]);
82             add(cnt[i][j], mod - cnt[i - 1][j - 1]);
83         }
84     }
85     ll fm = n * (n - 1) / 2, ans = 0LL;
86     fm = inv(fm * (fm - 1) % mod);
87     rep0(i, 0, vx.size() - 1) {
88         rep0(j, 0, vy.size() - 1)
89         if (cnt[i][j] > 1LL) {
90             ll tmp = cal(vx[i + 1], vy[j + 1], vx[i], vy[j]);
91             ans = (ans + tmp * (1LL * cnt[i][j] * (cnt[i][j] - 1) % mod)) % mod;
92         }
93     }
94     printf("%lld\n", ans * fm % mod);
95     return 0;
96 }
View Code

C:

连胡老师都不会做的神仙题,溜了 (

小米OJ TCO 预选赛

上一篇:appium 学习教程


下一篇:appium-ios 日常定位方法