srm 558

发表于   |   分类于   |  

275

Description

懒得写了= =自己看吧。。。

Solution

直接dp即可，用二进制的小技巧表示相同颜色即可

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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N = 55, inf = 1e7;
int a[N], dp[N];
class Stamp {
    public:
        int getMinimumCost(string s, int A, int B) {
            int n = s.size();
            for (int i = 0; i < n; ++i) {
                if (s[i] == 'R')    a[i] = 1;
                if (s[i] == 'G')    a[i] = 2;
                if (s[i] == 'B')    a[i] = 4;
                if (s[i] == '*')    a[i] = 7;
            }
            int ans = inf;
            for (int l = 1; l <= n; ++l) {
                fill(dp, dp + n + 1, inf);
                dp[0] = 0;
                for (int i = 0; i < n; ++i) {
                    int now = 7;
                    for (int j = i; j < n; ++j) {
                        now &= a[j];
                        if (!now)   break;
                        int len = j - i + 1;
                        if (len >= l && dp[i] != inf)   dp[j + 1] = min(dp[j + 1], dp[i] + ((len + l - 1) / l) * B);
                    }
                }
                if (dp[n] != inf)   ans = min(ans, dp[n] + A * l);
            }
            return ans;
        }
};

550

Description

看图泥就懂题意了= =

Solution

首先枚举两个蓝色点，再枚举$B$点，复杂度可以接受
从小到大枚举$B$点时可以同时记录可以满足条件的$A$的个数，然后二分求出右面$C,D$的个数，统计即可

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
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
#define mp make_pair
#define pb push_back
#define F first
#define S second
class Ear {
    public:
        long long getCount(vector <string> redX, vector <string> blueX, vector <string> blueY) {
            string a, b, c;
            vector<int> r, bx, by;
            for (int i = 0; i < redX.size(); ++i)   a += redX[i];
            for (int i = 0; i < blueX.size(); ++i)  b += blueX[i];
            for (int i = 0; i < blueY.size(); ++i)  c += blueY[i];
            stringstream sa(a), sb(b), sc(c);
            int x;
            while (sa >> x) r.pb(x);
            while (sb >> x) bx.pb(x);
            while (sc >> x) by.pb(x);
            sort(r.begin(), r.end());
            LL ans = 0;
            int n = bx.size(), m = r.size();
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j) {
                    if (i == j) continue;
                    if (by[i] > by[j]) {
                        int tot = 0;
                        for (int k = 0; k < m; ++k) {
                            if (r[k] < bx[j]) {
                                int R = max(bx[i], bx[j]) + 1;
                                double x = 1e50;
                                if (bx[i] != bx[j]) {
                                    double k = (double)(by[i] - by[j]) / (bx[i] - bx[j]);
                                    x = bx[i] - (double)by[i] / k;
                                    R = max(R, (int)floor(x + 1e-6) + 1);
                                }
                                int RR = lower_bound(r.begin(), r.end(), R) - r.begin();
                                int LL = upper_bound(r.begin(), r.end(), bx[j]) - r.begin();
                                ans += 1ll * tot * (RR + m - LL * 2 - 1) * (m - RR) / 2;
                                if (r[k] < bx[i] && r[k] < x - 1e-6)    ++tot;
                            }       
                        }
                    }
                }
            return ans;
        }
};