srm 552

发表于   |   分类于   |  

250

Description

定义大小为$N$的三角形, 是由若干个等大的圆形构成的, 高度和底宽为$N$,三角形的每个圆染三种颜色$r,g,b$,相接触的圆不能染同种颜色,问有$R$个$r$颜色的球, $G$个$g$颜色的球和$B$个$b$颜色的球, 最多能染多少个大小为$N$的三角形

Solution

稍加分析可以发现，每个三角形三个颜色的球要不是$x,x,x$,要不是$x,x,x+1$这种形式。先考虑$mod3=0$的情况，直接计算即可，$mod3=1$时，先当他们都相同，二分答案，然后check一下多出来的是否可以多出个数。

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
#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;
vector<LL> a;
struct FoxPaintingBalls {
    long long theMax(long long R, long long G, long long B, int N) {
        if (N == 1) return R + G + B;
        a.pb(R), a.pb(G), a.pb(B);
        sort(a.begin(), a.end());
        LL tot = (LL)N * (N + 1) / 2;
        LL x = tot / 3;
        if (tot % 3 == 0) return a[0] / x;
        LL ll = 0, ans = 0, rr = a[0] / x;
        while (ll <= rr) {
            LL mid = (ll + rr) >> 1ll;
            LL r = R - mid * x, g = G - mid * x, b = B - mid * x;
            if (r + g + b >= mid) {
                ans = mid;
                ll = mid + 1;
            }
            else rr = mid - 1;
        }
        return ans;
    }
};

500

Description

大小为$n\times m(n,m<30)$的矩阵, 有$L,P,.,$三种格子, 画两个互不相交的矩形, 使两个矩形$L$和$P$的差不超过$D$, 问这两个矩形最多能包含的$L$和$P$的和。

Solution

考虑一定存在一个分界线将其分为两个矩阵，先暴力$N^6$处理所有分界线，比如$l[i][j]表示第i列左边差为j的最大的花的和$，然后枚举两个矩形内部的差，再枚举分界线，暴力$N^5$计算即可。

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
#include <bits/stdc++.h>//enum
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;
const int N = 35;
int L[N][N * N + 1000], R[N][N * N + 1000], D[N][N * N + 1000], U[N][N * N + 1000];
inline void gao(int &x, int y) {
    if (x < y)  x = y;
}
struct FoxAndFlowerShopDivOne {
    int theMaxFlowers(vector <string> s, int maxDiff) {
        memset(L, 0xc0, sizeof(L));
        memset(R, 0xc0, sizeof(R));
        memset(U, 0xc0, sizeof(U));
        memset(D, 0xc0, sizeof(D));
        int n = s.size(), m = s[0].size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) 
                for (int k = i; k < n; ++k)
                    for (int l = j; l < m; ++l) {
                        int suml = 0, sump = 0;
                        for (int p = i; p <= k; ++p)
                            for (int q = j; q <= l; ++q) {
                                suml += s[p][q] == 'L';
                                sump += s[p][q] == 'P';
                            }
                        int sum = suml + sump, dif = suml - sump + 1000;
                        gao(D[i][dif], sum);
                        gao(R[j][dif], sum);
                        gao(U[k][dif], sum);
                        gao(L[l][dif], sum);
                    }
        for (int i = 1; i < n; ++i) 
            for (int j = 0; j < N * N + 1000; ++j)
                U[i][j] = max(U[i][j], U[i - 1][j]);
        for (int i = n - 2; i >= 0; --i)
            for (int j = 0; j < N * N + 1000; ++j)
                D[i][j] = max(D[i][j], D[i + 1][j]);
        for (int j = 1; j < m; ++j)
            for (int k = 0; k < N * N + 1000; ++k)
                L[j][k] = max(L[j][k], L[j - 1][k]);
        for (int j = m - 2; j >= 0; --j)
            for (int k = 0; k < N * N + 1000; ++k)
                R[j][k] = max(R[j][k], R[j + 1][k]);
        int ans = -1;
        for (int i = -n * m; i <= n * m; ++i)
            for (int j = -n * m; j <= n * m; ++j) {
                for (int h = 0; h < n - 1; ++h) 
                    if (abs(i + j) <= maxDiff)  ans = max(ans, U[h][i + 1000] + D[h + 1][j + 1000]);
                for (int l = 0; l < m - 1; ++l)
                    if (abs(i + j) <= maxDiff)  ans = max(ans, L[l][i + 1000] + R[l + 1][j + 1000]);
            }
        return ans;
    }
};