OI
10 minutes read (About 1551 words)

20160910测试

T1

这本来是一道水题,八个方向暴力枚举,判断一下边界就行(其实不判断边界也行),谨以此题爆 $0$ 警示自己不能再把 $n,m$ 看反……
另外此题有许多同学在 linux 下 WA,*注意 windows 下的换行符为 \r\n *,不要只 getchar() 一次,注意单独处理…

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
#include <bits/stdc++.h>
using namespace std;
char mp[2050][2050];
char outmp[2050][2050];
int n, m;
inline char getcnt(int x, int y) {
    register int cnt = 0;
    if (x - 1 > 0 && y - 1 > 0)
        if (mp[x - 1][y - 1] == '*') cnt++;
    if (y - 1 > 0)
        if (mp[x][y - 1] == '*') cnt++;
    if (x + 1 <= n && y - 1 > 0)
        if (mp[x + 1][y - 1] == '*') cnt++;
    if (x - 1 > 0)
        if (mp[x - 1][y] == '*') cnt++;
    if (x + 1 <= n)
        if (mp[x + 1][y] == '*') cnt++;
    if (x - 1 > 0 && y + 1 <= m)
        if (mp[x - 1][y + 1] == '*') cnt++;
    if (y + 1 <= m)
        if (mp[x][y + 1] == '*') cnt++;
    if (x + 1 <= n && y + 1 <= m)
        if (mp[x + 1][y + 1] == '*') cnt++;
    return '0' + cnt;
}
int main() {
    freopen("mine.in", "r", stdin);
    freopen("mine.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (register int i = 1; i <= n; i++) cin >> mp[i] + 1;
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= m; j++) {
            if (mp[i][j] == '.')
                outmp[i][j] = getcnt(i, j);
            else
                outmp[i][j] = mp[i][j];
        }
    }
    for (register int i = 1; i <= n; i++) cout << outmp[i] + 1 << "\n";
    return 0;
}

T2

又一水题,此题同连线游戏,只需计算斜率,单独考虑分母为 $0$ 的情况,扔进 set 里就完事.

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
set<double> lines;
struct point {
    int x, y;
} points[500];
inline double getK(const point& a, const point& b) {
    register double x = b.x - a.x, y = a.y - b.y;
    if (x == 0) return INF;
    return (double)y / x;
}
int n;
int main() {
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (register int i = 0; i < n; i++) cin >> points[i].x >> points[i].y;
    for (register int i = 0; i < n; i++)
        for (register int j = i + 1; j < n; j++)
            lines.insert(getK(points[i], points[j]));
    cout << lines.size();
    return 0;
}

T3

此题数据范围坑人,应用二分套二分才能过,然而数据太水,普通二分也能过,我还是太zz了,竟然以为二分是错的,幸好我的骗分算法神奇地跑满了……
骗分的大概思路就是先算出 $mid=sum[n]/3$,然后找到使第一块的和恰好大于 $mid$ 的位置 $pos$,记录 $pos-1,pos-2,pos+1$ 四个位置,分别以这四个位置同前方法找出使第二块恰好大于 $mid$ 的位置,也记录四个,然后计算出 $ans$

骗分(100分)

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
using namespace std;
#define IO_L 1048576
char _buf[IO_L], *S, *Ts, IO_c, IO_signum;
inline char read() {
    if (S == Ts) {
        Ts = (S = _buf) + fread(_buf, 1, IO_L, stdin);
        if (S == Ts) return EOF;
    }
    return *S++;
}
inline bool read(int &x) {
    IO_signum = false;
    for (IO_c = read(); IO_c < '0' || IO_c > '9'; IO_c = read()) {
        if (IO_c == -1) return false;
        if (IO_c == '-') IO_signum = true;
    }
    x = 0;
    while (IO_c == '0') IO_c = read();
    for (;; IO_c = read()) {
        if (IO_c < '0' || IO_c > '9') break;
        x = (x << 3) + (x << 1) + (IO_c ^ '0');
    }
    if (IO_signum) x = -x;
    return true;
}
#define in(x, y) read(x), read(y)
int n, arr[5000500];
long long ans = 9223372036854775807LL, tmp;
long long sum[5000500];
long long mid;
int main() {
    freopen("divide.in", "r", stdin);
    freopen("divide.out", "w", stdout);
    read(n);
    for (register int i = 1; i <= n; i++)
        read(arr[i]), sum[i] = sum[i - 1] + arr[i];
    if (n < 100) {
        for (register int i = 1, range = n - 1; i < range; i++)
            for (register int j = i + 1; j < n; j++)
                tmp = max(sum[i], sum[j] - sum[i]),
                tmp = max(tmp, sum[n] - sum[j]), ans = min(ans, tmp);
        cout << ans;
    } else {
        mid = sum[n] / 3;
        int pos11, pos12, pos13, pos14, pos21, pos22, pos23, pos24, pos25,
            pos26, pos27, pos28, pos211, pos221, pos231, pos241, pos251, pos261,
            pos271, pos281;
        for (register int pos1p = 1; pos1p <= n; pos1p++) {
            if (sum[pos1p] > mid) {
                pos11 = pos1p - 1, pos12 = pos1p, pos13 = pos1p - 2,
                pos14 = pos1p + 1;
                break;
            }
        }
        for (register int i = pos11 + 1; i <= n; i++) {
            if (sum[i] - sum[pos11] > mid) {
                pos21 = i - 1, pos22 = i, pos211 = i - 2, pos221 = i + 1;
                break;
            }
        }
        for (register int i = pos12 + 1; i <= n; i++) {
            if (sum[i] - sum[pos12] > mid) {
                pos23 = i - 1, pos24 = i, pos231 = i - 2, pos241 = i + 1;
                break;
            }
        }
        for (register int i = pos13 + 1; i <= n; i++) {
            if (sum[i] - sum[pos13] > mid) {
                pos25 = i - 1, pos26 = i, pos251 = i - 2, pos261 = i + 1;
                break;
            }
        }
        for (register int i = pos14 + 1; i <= n; i++) {
            if (sum[i] - sum[pos14] > mid) {
                pos27 = i - 1, pos28 = i, pos271 = i - 2, pos281 = i + 1;
                break;
            }
        }
        tmp =
            max(max(sum[pos11], sum[pos21] - sum[pos11]), sum[n] - sum[pos21]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos11], sum[pos211] - sum[pos11]),
                  sum[n] - sum[pos211]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos11], sum[pos22] - sum[pos11]), sum[n] - sum[pos22]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos11], sum[pos221] - sum[pos11]),
                  sum[n] - sum[pos221]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos12], sum[pos23] - sum[pos12]), sum[n] - sum[pos23]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos12], sum[pos231] - sum[pos12]),
                  sum[n] - sum[pos231]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos12], sum[pos24] - sum[pos12]), sum[n] - sum[pos24]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos12], sum[pos241] - sum[pos12]),
                  sum[n] - sum[pos241]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos13], sum[pos25] - sum[pos13]), sum[n] - sum[pos25]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos13], sum[pos251] - sum[pos13]),
                  sum[n] - sum[pos251]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos13], sum[pos26] - sum[pos13]), sum[n] - sum[pos26]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos13], sum[pos261] - sum[pos13]),
                  sum[n] - sum[pos261]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos14], sum[pos27] - sum[pos14]), sum[n] - sum[pos27]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos14], sum[pos271] - sum[pos14]),
                  sum[n] - sum[pos271]),
        ans = min(ans, tmp);

        tmp =
            max(max(sum[pos14], sum[pos28] - sum[pos14]), sum[n] - sum[pos28]),
        ans = min(ans, tmp);
        tmp = max(max(sum[pos14], sum[pos281] - sum[pos14]),
                  sum[n] - sum[pos281]),
        ans = min(ans, tmp);
        cout << ans;
    }
    return 0;
}

正解

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
#include <bits/stdc++.h>
#define LL long long
#define abs(x) ((x) > 0 ? (x) : -(x))
using namespace std;

const int N = 5000000 + 9;

int arr[N], n, l, r, mid, vout, sum[N];

inline int read() {
    char c = getcharR();
    int ret = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0') ret = ret * 10 + c - '0', c = getchar();
    return ret * f;
}

inline bool judge(int sta) {
    int t1 = upper_bound(sum + 1, sum + n + 1, sta) - sum - 1;
    int t2 = upper_bound(sum + t1 + 1, sum + n + 1, sta + sum[t1]) - sum - 1;
    return sum[n] - sum[t2] <= sta;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) arr[i] = read(), sum[i] = sum[i - 1] + arr[i];
    r = sum[n];
    l = r / 3;
    while (l <= r) {
        mid = l + r >> 1;
        if (judge(mid))
            r = mid - 1, vout = mid;
        else
            l = mid + 1;
    }
    cout << vout;
    return 0;
}

T4

这是一道神奇的 dp,其实就是补刀,(此题真的可以暴搜…),$f[i][j][k]$ 表示第 $i$ 个兵时轮到 $j$ 以前有 $k$ 轮空闲时的最大金钱,那么就很容易得出一个状态转移方程:$f[i][1][k + 1] = \max(f[i][1][k + 1], f[i][j][k]) (j = 0)$,$j \neq 0$ 时,暴力计算得钱与不得钱的情况即可。

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;
int f[105][2][1005], val[105], w[105], n, p, q;
inline void init() {
    freopen("thd.in", "r", stdin);
    freopen("thd.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> p >> q >> n;
    for (register int i = 1; i <= n; i++) cin >> val[i] >> w[i];
    memset(f, -1, sizeof(f));
    f[1][0][0] = 0;
}
inline int dp() {
    init();
    register int ans = 0;
    for (register int i = 1; i <= n + 1; i++) {
        for (register int j = 0; j <= 1; j++) {
            for (register int k = 0; k <= 1000; k++) {
                if (f[i][j][k] == -1) continue;
                ans = max(ans, f[i][j][k]);
                if (!j)
                    f[i][1][k + 1] = max(f[i][1][k + 1], f[i][j][k]);
                else {
                    for (register int t = 0, *ptr; t <= (val[i] - 1) / q; t++)
                        if ((val[i] - t * q) <= (t + k)*p)
                            ptr = &f[i + 1][1][k + t - ((val[i] - t * q - 1) / p + 1 )], *ptr = max(*ptr, f[i][j][k] + w[i]);
                    f[i + 1][0][k + ((val[i] - 1) / q)] = max(f[i + 1][0][k + ((val[i] - 1) / q)], f[i][j][k]);
                }
            }
        }
    }
    return ans;
}
int main() {
    cout << dp();
    return 0;
}
20160916测试
OI 模板总结

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×