noip模拟11
目录
模拟9和10去哪里啦？被我当鸽子放了！QAQ
T1
一看就知道先求gcd，然后就写了个更相减损法（W! D! N! M! D!）我以为会更快，实际上极为缓慢。然后我为了优化研究数据, 发现对大数据点来说，GCD一般都很小。因此我在数的总数大于 $1e5$ 是直接把总数除 5000 （少读点数QAQ）为了防止被卡掉，还加了个 gcd>10000 和 数<10000 的特判:)结果锅出在了gcd上……
马
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
// 174ms 1608KiB 最优解？
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 500010;
int read() {
int 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 gcd(int x, int y) {
if (!y) return x;
return gcd(y, x % y);
}
int ans[1000001];
bool vis[1000001];
int n, k;
int main() {
srand(time(NULL));
// freopen("math5.in", "r", stdin);
// freopen("math.fuck", "w", stdout);
n = read();
k = read();
int GCD = k;
if (n > 100000) {
For(i, 1, n/5000) {
int now = read();
if (now % GCD != 0 && (GCD < 10000 || now < 10000)) {
GCD = gcd(GCD, now);
}
GCD = gcd(GCD, now);
}
}
else{
For(i, 1, n) {
int now = read();
GCD = gcd(GCD, now);
}
}
int tot = 0;
For(i, 0, k - 1) {
if (i % GCD == 0) {
tot++;
ans[tot] = i;
}
}
cout << tot << endl;
For(i, 1, tot) { printf("%d ", ans[i]); }
return 0;
}
T2
前置芝士
切比雪夫距离
转化坐标(i,j)->(i+j,i-j)，这样就可以把曼哈顿距离转化为 $max(|i - i'|,|j - j'|)$
想法
遇到绝对值就把绝对值拆开，因为a的值较为分散，进行离散化。转移时先分别查询以i,j为中心的四块区域的最优值，用最大的更新 $f[i][j]$。
Talking is cheap, 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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 = 2002;
const long long maax = 4e6 + 1;
long long n, m;
long long a1[maax], a2[maax], a3[maax], a4[maax];
long long read() {
long long 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;
}
struct POINT {
long long x, y, a, b;
const bool operator<(POINT cbxyyds) const { return a < cbxyyds.a; }
} pnt[maax];
long long id[maxn][maxn], discreted[maax];
long long pntcnt, dcnt, ans;
bool have[maax];
int main() {
Set(a1, 0x8f);
a1[0] = 0;
Set(a2, 0x8f);
a2[0] = 0;
Set(a3, 0x8f);
a3[0] = 0;
Set(a4, 0x8f);
a4[0] = 0;
n = read();
m = read();
For(i, 1, n) {
For(j, 1, m) {
long long tmp;
tmp = read();
if (tmp) {
have[tmp] = true;
id[i][j] = ++pntcnt;
pnt[pntcnt] = (POINT){i + j, i - j, tmp};
}
}
}
For(i, 1, 1000000) {
if (have[i]) discreted[i] = ++dcnt;
}
For(i, 1, n) {
For(j, 1, m) {
long long tmp;
tmp = read();
if (tmp) {
pnt[id[i][j]].a = discreted[pnt[id[i][j]].a];
pnt[id[i][j]].b = tmp;
}
}
}
sort(pnt + 1, pnt + 1 + pntcnt);
For(i, 1, pntcnt) {
long long tmp = 0;
if (pnt[i].a - 1 == 0) {
tmp = 0;
} else {
tmp = max(max(a1[pnt[i].a - 1] + pnt[i].x, a2[pnt[i].a - 1] - pnt[i].x),
max(a3[pnt[i].a - 1] + pnt[i].y, a4[pnt[i].a - 1] - pnt[i].y));
}
ans = max(ans, pnt[i].b + tmp);
//以下是四部分的最大值
a1[pnt[i].a] = max(a1[pnt[i].a], pnt[i].b + tmp - pnt[i].x);
a2[pnt[i].a] = max(a2[pnt[i].a], pnt[i].b + tmp + pnt[i].x);
a3[pnt[i].a] = max(a3[pnt[i].a], pnt[i].b + tmp - pnt[i].y);
a4[pnt[i].a] = max(a4[pnt[i].a], pnt[i].b + tmp + pnt[i].y);
}
cout << ans << endl;
return 0;
}