其实粗粮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)统计完事了。
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 }
C:
连胡老师都不会做的神仙题,溜了 (