srm 544

发表于   |   分类于   |  

275

Description

给你一些百分比，四舍五入之后，问原来可不可能是百分之百

Solution

数据范围非常小，暴力枚举分子分母到$1000$即可，做法很多。。。

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
#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 ElectionFraudDiv1 {
    int MinimumVoters(vector <int> percentages) {
        int n = percentages.size();
        for (int i = 1; i <= 1000; ++i) {
            bool f = 1;
            int l = 0, r = 0;
            for (int j = 0; j < n; ++j) {
                int x = percentages[j];
                bool ok = 0;
                for (int k = 0; k <= i; ++k) {
                    if ((int)((100.0000 / i * k) + 0.500005) == x) {
                        ok = 1;
                        l += k;
                        break;
                    }
                }
                for (int k = i; k >= 0; --k) {
                    if ((int)((100.0000 / i * k) + 0.500005) == x) {
                        ok = 1;
                        r += k;
                        break;
                    }
                }
                if (!ok)    f = 0;
            }
            if (f && l <= i && i <= r)  return i;
        }
        return -1;
    }
};

500

Description

给你一个$N\times M的$0/1$矩阵，你每次可以选一条最短路线的路线，把路线左下部$0/1$取反。问全矩阵变成$0$最少操作次数。

Solution

容易发现，每次最边界的是早晚都要取的，而且，$1$的边界线会逐渐变小。每次从上到下，找最右边界，翻转即可，数据范围很小，暴力即可，复杂度$O(N^2\times M^2)$

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
#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 FlipGame {
    int minOperations(vector <string> board) {
        int ans = -1;
        int n = board.size(), m = board[0].size();
        while (1) {
            ++ans;
            int last = -1;
            bool ok = 0;
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < m; ++j)
                    if (board[i][j] == '1') ok = 1;
            if (!ok)    break;
            for (int i = 0; i < n; ++i) {
                for (int j = last + 1; j < m; ++j)
                    if (board[i][j] == '1') {
                        last = j;
                    }
                for (int j = 0; j <= last; ++j) 
                    board[i][j] = (board[i][j] == '1') ? '0' : '1';
            }
        }
        return ans;
    }
};