srm 547

发表于   |   分类于   |  

250

Description

$1\le x\le 10^5, 1\le y\le 10^5,x,y\in N$,给定$w$,随机选$x,y$求$\sum sqrt((x-y)^2+w^2)$的期望

Solution

枚举$x-y$即可，注意细节即可

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct Pillars {
    double getExpectedLength(int w, int x, int y) {
         double ans = 0.0;
         if (x < y) swap(x, y);
         int del = x - y;
         for (int d = 1 - y; d <= 0; ++d) {
            ans += (double)(y + d) * sqrt(1.0 * d * d + w * w);
         }
         for (int d = 1; d <= del; ++d) {
            ans += (double)y * sqrt(1.0 * d * d + w * w);
         }
         for (int d = del + 1; d < x; ++d) {
            ans += (double)(x - d) * sqrt(1.0 * d * d + w * w);
         }
         return ans / x / y;
    }
};

500

Description

给定一个$h\times w(h,w\le 10^6)$的矩阵，数字为别为$0\sim h\times w - 1$，给定一个$sum(sum\le 10^{12})$，求最小面积的子矩形，使得和等于$sum$

Solution

考虑面积的上界$s$,$s\times (s-1) / 2\ge sum$，于是得到上界是$10^6$级别的，枚举$n$，复杂度为$N\times logN$,显然是可以接受的。
设矩阵最上角为$x$，根据等差数列求和，显然可以列出$x$和$sum$的关系，判断是否满足即可

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
struct RectangularSum {
    long long minimalArea(int height, int width, long long S) {
        int s;
        for (s = 1; (LL)s * (s - 1) / 2 <= S; ++s);
        int ans = 1e7;
        for (int n = 1; n <= s && n <= height; ++n)
            for (int m = 1; n * m <= s && m <= width; ++m) {
                if (S * 2 % n != 0) continue;
                LL t = S * 2 / n - (LL)(n - 1) * m * width;
                if (t < 0 || t & 1) continue;
                if (t % m != 0) continue;
                t = t / m + 1 - m;
                if (t < 0 || t & 1) continue;
                t /= 2;
                int y = t % width, x = t / width;
                if (x >= 0 && x + n - 1 < height && y >= 0 && y + m - 1 < width)    ans = min(ans, n * m);
            }
        return ans == 1e7 ? -1 : ans;
    }
};