noip模拟38
目录
死磕T1战术失败？
T1 a
一看到在矩阵上统计符合条件的子矩形个数就想到了前缀和，然后就不会了。剩下的3h想了从dp到线段树的各种方法就是没想到天天挂在嘴边（？）的双指针。如果是暴力 $O(n^2m^2)$ 铁定过不了，考虑如何降低复杂度。因为n最大仅为30,所以可以暴力枚举每个块的上下边界，而对于左右边界就使用双指针进行优化。找到第一个1的个数大于l的位置设为第一个指针（代码中为ll），最后一个1的个数小于r的位置设为第二个指针（代码中为rr）。等到写代码的时候会发现二维前缀和并不香，于是对其进行降维打击，使用一维前缀和，将在上边界和下边界之间的行拍成1行再求两个指针即（不）可。
TLE 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
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 50010;
const long long mod = 1e9 + 7;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, m;
int mat[31][maxn];
int qz[31][maxn];
int l, r;
int ans = 0;
void WinRAR(int up, int dn) {
int tmp[maxn] = {0};
For(kk, 1, m) {
For(i, up, dn) {
tmp[kk] += qz[i][kk];
}
}
int ll = 1, rr = 0;
For(i, 0, m) {
ll = 1, rr = 1;
while ((tmp[ll] - tmp[i] < l || ll <= i) && ll < m) ll++;
while (tmp[rr] - tmp[i] <= r && rr < m) rr++;
if (ll == i)
break;
if (tmp[rr] - tmp[i] > r) rr--;
if(tmp[ll] - tmp[i] >= l && tmp[rr] - tmp[i] <= r) {
ans += (rr - ll + 1) ;
}
}
}
int main() {
n = read<int>();
m = read<int>();
For(i, 1, n) {
char in[maxn];
scanf("%s", in + 1);
For(j, 1, m) {
mat[i][j] = in[j] - '0';
qz[i][j] = qz[i][j - 1] + mat[i][j];
}
}
l = read<int>();
r = read<int>();
For(i, 1, n) {
For(j, i, n) {
WinRAR(i, j);
}
}
cout << ans << endl;
return 0;
}
嗯？？怎么TLE了？接着优化！因为随着i向右移动，两个指针一定会单调右移，因此将初值放在外面即可。
Accepted 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
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 50010;
const long long mod = 1e9 + 7;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long n, m;
long long mat[31][maxn];
long long qz[31][maxn];
long long l, r;
long long ans = 0;
void WinRAR(long long up, long long dn) {
long long tmp[maxn] = {0};
For(kk, 1, m) {
For(i, up, dn) {
tmp[kk] += qz[i][kk];
}
}
long long ll = 1, rr = 1;
For(i, 0, m) {
while ((tmp[ll] - tmp[i] < l || ll <= i) && ll < m) ll++;
while (tmp[rr] - tmp[i] <= r && rr < m) rr++;
if (ll == i)
break;
if (tmp[rr] - tmp[i] > r) rr--;
if(tmp[ll] - tmp[i] >= l && tmp[rr] - tmp[i] <= r) {
ans += (rr - ll + 1) ;
}
}
}
int main() {
n = read<long long>();
m = read<long long>();
For(i, 1, n) {
char in[maxn];
scanf("%s", in + 1);
For(j, 1, m) {
mat[i][j] = in[j] - '0';
qz[i][j] = qz[i][j - 1] + mat[i][j];
}
}
l = read<long long>();
r = read<long long>();
For(i, 1, n) {
For(j, i, n) {
WinRAR(i, j);
}
}
cout << ans << endl;
return 0;
}
T2 b
官方题解：
这里记a的最大值为x。将问题转化为“对i∈[1,1e5]，求多少种选择方案使得 $gcd=i$ ”。继续转化为“对i∈[1,1e5]，求多少种选择方案使得 $i|gcd$ ”。这里可以 $O(x)$ 或直接暴力 $O(x;ln;x)$ 容斥回去。等价于“对i∈[1,1e5]，求多少种选择方案使得选的所有数均为 $i$ 的倍数”。 $O(n(m+x;ln;x))$ 处理出第 $i$ 行有多少个数是 $j$ 的倍数，记为 $cnt_{i,j}$ 。那么，共有 $\Pi^n_{i=1}(cnt_{i,j} + 1) − 1$ 种方案，使得选的所有数均为 $j$ 的倍数，这一步为 $O(nm)$ 。
还需要去重，去掉每个数×2及以上出现的个数，最后还要把个数乘上当前的数再加到ans里
Show you the 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
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 100010;
const long long mod = 1e9 + 7;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long n, m;
long long num[21][maxn];
long long cnt[21][maxn];
long long bkt[21][maxn];
long long sum[maxn];
int32_t main() {
n = read<long long>();
m = read<long long>();
long long maxx = 0;
For(i, 1, n) {
For(j, 1, m) {
num[i][j] = read<long long>();
bkt[i][num[i][j]]++;
maxx = max(maxx, num[i][j]);
}
}
For(i, 1, n) {
For(j, 1, maxn) {
for (long long mult = 1; mult * j <= maxn; mult++) {
cnt[i][j] += bkt[i][j * mult];
}
}
}
long long ans = 1;
Fordown(j, maxx, 1) {
sum[j] = 1;
For(i, 1, n) {
sum[j] *= (cnt[i][j] + 1);
sum[j] %= mod;
}
sum[j]--;
for (long long k = 2; k * j <= maxn; k++) {
sum[j] = (sum[j] - sum[k * j] + mod) % mod;
}
ans += sum[j] * j;
ans %= mod;
}
cout << ans - 1 << endl;
return 0;
}
T3 c
点分治题不会，尝试搞懂
std:
|
|