8-F. fLIP (通过人数 19/48)#

题目描述#

给定一个 $N \times M$ 的网格，初始全为白色。每次操作可以选择一行或一列，将该行或该列的所有方格颜色反转（白变黑，黑变白）。问是否可能通过任意次操作，使得网格中恰好有 $K$ 个黑色方格。如果可以，输出 Yes，否则输出 No。

输入格式#

$N \ M \ K$

$1 \le N, M \le 1000$
$0 \le K \le N \times M$

题解#

首先需要想到，操作结果仅于行操作和列操作的操作次数有关而与顺序无关。举个例子，假设我们某次方案摁下了第2，5，6行的按钮，那把它换成摁下1，3，4行的按钮结果也完全一样；列的操作也是同理。因此我们根本不需要复杂的数学推导，只需要暴力枚举行操作和列操作的次数。

计算变成黑色的方格数也很简单，减去行和列的交叉覆盖的方格数量即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
void work() {
9
  int n, m, k;
10
  cin >> n >> m >> k;
11
  rep(i, 0, n) {
12
    rep(j, 0, m) {
13
      if((i * m + j * n - 2 * i * j) == k) {
14
        cout << "Yes" << endl;
15
        return;
16
      }
17
    }
18
  }
19
  cout << "No" << endl;
20
  return;
21
}
22
signed main() {
23
  ios::sync_with_stdio(0);
24
  cin.tie(0);
25
  cout.tie(0);
26
  int t = 1;
27
//  cin >> t;
28
  while (t--) {
29
    work();
30
  }
31
  return 0;
32
}

7-D. Two Alpinists (通过人数 16/43)#

题目描述#

有 $N$ 座山排成一行，高度为 $h_i$ 。 Takahashi 从西向东走，Aoki 从东向西走。对于每座山 $i$ ，Takahashi 记录了到达该山时的历史最高高度 $T_i$ ，Aoki 记录了到达该山时的历史最高高度 $A_i$ 。已知记录序列 $T$ 和 $A$ ，求可能的山峰高度序列的数量，对 $10^9 + 7$ 取模。

输入格式#

$N$ $T_1 \ T_2 \ \dots \ T_N$ $A_1 \ A_2 \ \dots \ A_N$

$1 \le N \le 10^5$
$1 \le T_i, A_i \le 10^9$
$T_i \le T_{i+1}$
$A_i \ge A_{i+1}$

题解#

乍一看是一个动态规划，实际手模一遍样例就能发现是简单的乘法原理题。

不难发现：

如果 $T_i > T_{i-1}$ ，说明第 $i$ 座山的高度必须恰好是 $T_i$
如果 $A_i > A_{i+1}$ ，说明第 $i$ 座山的高度必须恰好是 $A_i$

遍历每座山进行分类讨论：

同时满足必须等于 $T_i$ 且必须等于 $A_i$ ：若 $T_i \ne A_i$ ，则无解
仅有必须等于 $T_i$ ：此时需要满足 $T_i \le A_i$ （因为 $h_i \le A_i$ ），否则无解
仅有必须等于 $A_i$ ：此时需要满足 $A_i \le T_i$ （因为 $h_i \le T_i$ ），否则无解
没有强制等于的限制：此时 $h_i$ 可以是 $[1, \min(T_i, A_i)]$ 范围内的任意整数。方案数为 $\min(T_i, A_i)$

最终答案为所有山峰可能方案数的乘积。时间复杂度 $O(N)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 2e5 + 5;
8
int a[N];
9
int b[N];
10
const int mod = 1e9 + 7;
11
void work() {
12
  int n;
13
  cin >> n;
14
  rep(i, 1, n) cin >> a[i];
15
  rep(i, 1, n) cin >> b[i];
16
  int ans = 1;
17
  rep(i, 1, n){
18
    bool f1 = (a[i] > a[i - 1]);
19
    bool f2 = (b[i] > b[i + 1]);
20
    if(f1 && f2){
21
      if(a[i] != b[i]) {
22
        cout << 0 << endl;
23
        return;
24
      }
25
    } else if(f1){
26
      if(a[i] > b[i]){
27
        cout << 0 << endl;
28
        return;
29
      }
30
    } else if(f2){
31
      if(a[i] < b[i]){
32
        cout << 0 << endl;
33
        return;
34
      }
35
    } else{
36
      ans = ans * (min(a[i], b[i])) % mod;
37
    }
38
  }
39
  cout << ans << endl;
40
  return;
41
}
42
signed main() {
43
  ios::sync_with_stdio(0);
44
  cin.tie(0);
45
  cout.tie(0);
46
  int t = 1;
47
//  cin >> t;
48
  while (t--) {
49
    work();
50
  }
51
  return 0;
52
}

8-D. Time Gap (通过人数 7/48)#

题目描述#

有 $N+1$ 个人（包括 Takahashi），他们所在的城市之间存在时差。两个城市之间的时差定义为：若 A 城市 0 点时 B 城市为 $d$ 点，则时差为 $\min(d, 24-d)$ 。现在第 $i$ 个人与 Takahashi 的时差为 $D_i$ ，Takahashi 现在在0点，你需要为其他 $N$ 个人分配具体的时间（ $d$ 或 $24-d$ ），使得任意两人之间时差的最小值 $s$ 最大化。求 $s$ 的最大值。

输入格式#

$N$ $D_1 \ D_2 \ \dots \ D_N$

$1 \le N \le 50$
$0 \le D_i \le 12$

题解#

~~二分答案诈称题干~~

首先我们容易发现：

如果某个 $D_i$ 出现的次数 $\geq 3$ ，那么根据鸽巢原理，必然有两个人的时间相同，此时最小时间差一定为 0。
特殊地，时差为 $0$ 和时差为 $12$ 的点仅有一个，所以如果出现次数超过 1 次，最小时间差也为 0。

排除上面情况后，一定存在一种方案使得最小时间差大于 0，此时我们考虑：

如果一个时差 $D_i$ 出现了 2 次，那么为了使间隔不为 0，必须一个取 $D_i$ ，另一个取 $24-D_i$ 。因此这两个位置已经可以确定了。
如果 $D_i$ 只出现 1 次且不是 0 或 12，那么它可以取 $D_i$ 或 $24-D_i$ 。由于我们无法判断哪个更优，直接暴力出奇迹就好了，枚举所有有可能的时间点（其实就两个）后计算最小值就好了。由于最多只有 12 个时差给我们暴力选择，因此不可能超时

代码实现时，我们用v1记录已经确定的时间点，用v2记录需要暴力选择的时差，dfs 以v1为起始状态，每次 push_back一个v2的状态即可。当 dfs 深度为v2的长度时，表明所有不确定的时间点都已经枚举完了，直接计算最小时差即可。

DFS 的复杂度为 $O(2^{12})$ ，计算最小间隔需要排序复杂度 $O(N \log N)$ 。总复杂度约为 $O(2^{12} \cdot N \log N)$

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
#define rep(i, f, l) for(int i(f); i <= l; ++i)
6
#define per(i, f, l) for(int i(f); i >= l; --i)
7
const int N = 66;
8
int a[N];
9
int n;
10
int tong[N];
11
int ans = 0;
12
vector<int> v1;
13
vector<int> v2;
14
void dfs(int x, vector<int> v) {
15
  if(x == v2.size()){
16
    sort(v.begin(), v.end());
17
    int mi = 24 - v[v.size() - 1];
18
    for(int i = 1; i < v.size(); ++i){
19
      mi = min(mi, v[i] - v[i - 1]);
20
    }
21
    ans = max(ans, mi);
22
    return;
23
  }
24

25
  v.push_back(v2[x]);
26
  dfs(x + 1, v);
27
  v.pop_back();
28

29
  v.push_back(24 - v2[x]);
30
  dfs(x + 1, v);
31
  v.pop_back();
32
}
33

34
void work() {
35
  cin >> n;
36
  rep(i, 1, n) {
37
    cin >> a[i];
38
    tong[a[i]]++;
39
  }
40
  tong[0]++;
41
  rep(i, 0, 12){
42
    if(tong[i] >= 3) {
43
      cout << 0 << endl;
44
      return;
45
    }
46
  }
47
  if(tong[0] >= 2 || tong[12] >= 2) {
48
    cout << 0 << endl;
49
    return;
50
  }
51
  rep(i, 0, 12){
52
    if(tong[i] == 2){
53
      v1.push_back(i);
54
      v1.push_back(24 - i);
55
    }
56
    if(tong[i] == 1){
57
      if(i == 12 || i == 0){
58
        v1.push_back(i);
59
      } else{
60
        v2.push_back(i);
61
      }
62
    }
63
  }
64

65
  dfs(0, v1);
66
  cout << ans << endl;
67
  return;
68
}
69
signed main() {
70
  ios::sync_with_stdio(0);
71
  cin.tie(0);
72
  cout.tie(0);
73
  int t = 1;
74
//  cin >> t;
75
  while (t--) {
76
    work();
77
  }
78
  return 0;
79
}

わたしの部屋

8-F. fLIP (通过人数 19/48)#

题目描述#

输入格式#

题解#

7-D. Two Alpinists (通过人数 16/43)#

题目描述#

输入格式#

题解#

8-D. Time Gap (通过人数 7/48)#

题目描述#

输入格式#

题解#