解题以及补题报告。
题目链接：Codeforces Round #645 (Div. 2)
需要注意一下奇数乘奇数的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, T;
int main() {
for (cin >> T; T--; ) {
cin >> n >> m;
if (n & 1 && m & 1) {
cout << min(n / 2 * m + (m + 1) / 2, m / 2 * n + (n + 1) / 2) << endl;
} else {
cout << (n * m / 2) << endl;
}
}
return 0;
}
|
先排序，然后从小到大枚举，考虑让 a[i] 值一样的同时入场，看能不能满足条件，样例 3 比较强，可以知道，如果每次只考虑一组 a[i] 值相同的全部入场也不能满足条件，但是加上后面值更大的入场或许就能满足了，因此如果加上 a[i] 这一组仍然不能满足，还需要一直向后扫描，直到全部扫描完所有 a[i] 。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, T;
int a[N];
int main() {
for (cin >> T; T--; ) {
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
int now = -1;
for (int i = 0; i < n; i++) {
while (a[i] > i + 1 && i < n) i++;
if (i == n) break;
now = i;
}
if (now == -1) puts("1");
else cout << now + 2 << endl;
}
return 0;
}
|
思维题啊，虽然看出来先右后下是最小值，先下后右得到了最大值，就是没看出来这个最值区间是连续的，那么只要求这个区间的大小即可，但求这个也比较思维。
将先右后下的直角修改成先下后右的直角，就能使得当前路径比上一个路径和大 $1$，这样一层一层修改，最终能达到，最大值路径（即一直往下再一直往右）。共修改了 $\Delta{x}\cdot\Delta{y}$ 次，就有了这么多不同的路径和，还需要加上没有修改过的最小的路径和，答案就是 $\Delta{x}\cdot\Delta{y}+1$
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <iostream>
using namespace std;
int a, b, c, d, T;
int main() {
for (cin >> T; T--; ) {
cin >> a >> b >> c >> d;
cout << 1ll * (a - c) * (b - d) + 1 << endl;
}
return 0;
}
|
贪心，双指针，前缀和。（双指针写炸了....另外还有各种细节错误
基于贪心，长度为 $x$ 的区间的右端点一定恰好是某一个月的结束的那天，否则，一定可以让这个区间向前平移，使得满足上述条件，从而使答案更优。首先 $d[\ ]$ 数组需要开两倍，复制一遍在后面，然后求 $d[i]$ 的前缀和 $sd[i]$，以及拥抱个数的前缀和 $s[i]$ 。然后我们枚举每一个月份 $i$ 作为结束月份（即 $x$ 区间的右端点），用 $j$ 指针表示 $x$ 区间左端点所在的月份，如果 $[j,i]$ 月份区间不够 $x$ 天，那么 $i$ 不断后移。然后更新对应的 $j$ 指针（就是这里写错了），如果 $[j+1,i]$ 月份区间的天数已经大于等于 $x$ 天了，那么 $j$ 后移动。通过这样双指针的移动，能保证 $x$ 区间的左端点一定在 $j$ 月份。因此计算这段区间的贡献就是：完整的 $[j+1,i]$ 月份的拥抱数量 + $j$ 月份月末连续的 $x-(sd[i]-sd[j])$ 天的拥抱数量。然后与答案取 $\max$ 即可。
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;
typedef long long LL;
const int N = 200010;
LL n, T, x;
LL d[N * 2];
LL s[N * 2];
LL sd[N * 2];
LL add(int i, LL cnt) {
LL right = d[i], left = right - cnt + 1;
return cnt * (left + right) / 2;
}
int main() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> d[i];
d[i + n] = d[i];
}
for (int i = 1; i <= 2 * n; i++) {
s[i] = s[i - 1] + d[i] * (d[i] + 1) / 2;
sd[i] = sd[i - 1] + d[i];
}
LL ans = 0;
for (int i = 1, j = 1; i <= 2 * n; i++) {
while (sd[i] - sd[j - 1] < x) i++;
while (sd[i] - sd[j] >= x) j++;
LL temp = s[i] - s[j] + add(j, x - (sd[i] - sd[j]));
ans = max(ans, temp);
}
cout << ans << endl;
return 0;
}
|