OI
11 minutes read (About 1670 words)

20161109测试总结

T1

神奇的平衡三进制…
不懂为什么要转成三进制(好慢)。
直接预处理 $3$ 的幂和幂的前缀和，那么当 $x < 0$ 时，先输出 $T$，当$x>0$时，先输出$1$，当 $x = 0$ 时直接输出 $0$。最高位最多为 $maxDigit = \left \lceil \log_3x \right \rceil$，我们可以与 $3^{maxDigit}-sum[maxDigit-1]$ 比较，然后调整 $maxDigit$，然后向前枚举每一位，确定每一位的值就好了。

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
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <cmath>
#include <ctime>
#include <queue>
#include <string>
#include <cstdlib>
#include <iomanip>
using namespace std;

bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    x = 0, iosig = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = 1;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
typedef long double ld;
ld powVal[40], sum[40];
inline void init() {
    powVal[0] = 1, sum[0] = 1;
    for (int i = 1; i < 40; i++)
        powVal[i] = powVal[i - 1] * 3, sum[i] = sum[i - 1] + powVal[i];
    /*#ifdef DBG
    for (int i = 0; i < 40; i++)
        cerr << setprecision(19) << powVal[i] << " " << sum[i] << "\n";
    #endif*/
}
int q;
long long x;
const ld LOG_3 = log(3);
template<class T>
inline T abs(T x) {
    return x < 0 ? -x : x;
}
inline void calculate(ld &x, int &digit) {
    /*#ifdef DBG
    cerr << "now x ===> " << x << "\n";
    #endif*/
    if (digit) {
        if (x - (powVal[digit] - sum[digit - 1]) >= 0 && x - (powVal[digit] + sum[digit - 1]) <= 0) x -= powVal[digit], cout << "1";
        else if (x + (powVal[digit] + sum[digit - 1]) >= 0 && x + (powVal[digit] - sum[digit - 1]) <= 0) x += powVal[digit], cout << "T";
        else cout << "0";
    } else {
        if (x < 0) cout << "T";
        else if (x > 0) cout << "1";
        else cout << "0";
    }
    digit--;
}
inline void solve() {
    read(x);
    /*#ifdef DBG
    cerr << "solve " << x << "\n";
    #endif*/
    if (x == 0) {
        cout << "0\n";
        return;
    }
    ld num = x;
    int maxDigit = ceil(log(abs(num)) / LOG_3);
    if (num < 0) {
        cout << 'T';
        if (num + powVal[maxDigit] - sum[maxDigit - 1] > 0) maxDigit--;
        num += powVal[maxDigit];
    } else {
        cout << "1";
        if (num - powVal[maxDigit] + sum[maxDigit - 1] < 0) maxDigit--;
        num -= powVal[maxDigit];
    }
    maxDigit--;
    /*#ifdef DBG
    std::cerr << "num ==> " << num << " Digit ==> " << maxDigit << "\n";
    #endif*/
    for (int i = 0, r = maxDigit; i <= r; i++)
        calculate(num, maxDigit);
    cout << "\n";
}
int main() {
    init();
    read(q);
    while (q--)
        solve();
    return 0;
}

T2

又是windows评测，卡T了…

题解没开读入优化T了，23333…

贪心，考虑每次选取权值最大的切，直接排序，线性扫一遍就好了。

注意乘起来会大于long long，可以用long double神奇的实现$O(1)$计算

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
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <cmath>
#include <ctime>
#include <queue>
#include <string>
#include <cstdlib>
#include <iomanip>
using namespace std;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
inline char read() {
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline void read(T& x) {
    for (ioc = read(); !isdigit(ioc); ioc = read());
    x = 0;
    while (ioc == '0') ioc = read();
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
}
const int MAXN = 1e6;
const int mod = 1e9 + 7;
int x[MAXN + 10], y[MAXN + 10];
int n, m;
long long ans;
int sumx, sumy;
struct Data {
    int w;
    bool isx;
    inline bool operator < (const Data &x) const {
        return w > x.w;
    }
} data[MAXN * 2 + 10];
typedef long long ll;
const int sig = 2e9;
inline ll mul(ll a, ll b, ll c) {
    a %= c, b %= c;
    return c <= sig ? (a * b % c + c) % c : (a * b - (ll)(a / (long double)c * b) * c + c) % c;
}
inline void add(ll &a, ll b) {
    a += b;
    if (a > mod) a -= mod;
}
int maxnm;
long long ansVal = LONG_LONG_MAX;
inline void solveRand() {
    register int range = n + m - 2;
    maxnm = max(n, m);
    ans = 0;
    sumx = sumy = 1;
    for (int i = 1; i <= range; i++) {
        if (data[i].w == data[i + 1].w)
            if (rand() & 1) swap(data[i], data[i + 1]);
        Data *x = &data[i];
        if (x->isx) {
            add(ans, mul(x->w, sumy, mod));
            sumx++;
        } else {
            add(ans, mul(x->w, sumx, mod));
            sumy++;
        }
    }
    ansVal = min(ansVal, ans);
}
inline void solve() {
    register int range = n + m - 2;
    maxnm = max(n, m);
    ans = 0;
    sumx = sumy = 1;
    for (int i = 1; i <= range; i++) {
        Data *x = &data[i];
        if (x->isx) {
            add(ans, mul(x->w, sumy, mod));
            sumx++;
        } else {
            add(ans, mul(x->w, sumx, mod));
            sumy++;
        }
    }
    ansVal = min(ansVal, ans);
}
inline bool cmp(const Data &a, const Data &b) {
    return a.w < b.w;
}
int main() {
    read(m), read(n);
    if (n + m <= 11) {
        int pos = 1;
        for (int i = 1; i < m; i++)
            read(data[pos].w), data[pos++].isx = 1;
        for (int i = 1; i < n; i++)
            read(data[pos++].w);
        sort(data + 1, data + pos, cmp);
        register long long ans = LONG_LONG_MAX;
        do {
            sumx = sumy = 1;
            register long long sum = 0;
            for (int i = 1; i < pos; i++) {
                if (data[i].isx)
                    add(sum, mul(data[i].w, sumy, mod)), sumx++;
                else add(sum, mul(data[i].w, sumx, mod)), sumy++;
            }
            ans = min(ans, sum);
        } while (next_permutation(data + 1, data + pos, cmp));
        cout << ans;
    } else {
        for (int i = 1; i < m; i++) read(x[i]);
        for (int i = 1; i < n; i++) read(y[i]);
        for (int i = 1; i < n; i++)
            data[i].isx = 0, data[i].w = y[i];
        for (int i = 0; i < m - 1; i++)
            data[i + n].isx = 1, data[i + n].w = x[i + 1];
        sort(data + 1, data + n + m);
        solve();
        cout << ansVal;
    }
    return 0;
}

T3

此题与斗地主如出一辙…

首先可以发现所有的可能状态只有几万种，所以我们可以预处理所有转移，对于每个状态，我们记录它当前是谁先手及先手的输赢。如果后继状态中有一个状态是输，那么当前状态就是赢，否则当前状态就是输。
根据将、帅互吃的规则，有些状态可以 $1$ 步确定输赢。

整个过程可以用类似拓扑排序的做法来进行，对于拓扑排序无法确定的那些状态，必然存在环，也就是平局。

对于输者最大化步数，赢者最小化步数，我们可以发现 $BFS$ 恰好满足这个条件。

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
139
#include <bits/stdc++.h>
using namespace std;
const int delta1[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
const int delta2[8][2] = {-2, -1, -2, 1, -1, -2, -1, 2, 1, -2, 1, 2, 2, -1, 2, 1};
const int MAXI = 90;
const int MAXJ = 9;
const int MAXK = 9;
struct Node {
    int degree;
    bool flag;
    int step;
    vector<Node *> edge;
    inline void addEdge(Node *x) {
        degree++;
        x->edge.push_back(this);
    }
} nodes[MAXI + 1][MAXJ][MAXK][2];
inline bool valid(const int x, const int y) {
    return x >= 0 && x <= 9 && y >= 0 && y <= 8;
}
inline bool equals(const int x1, const int y1, const int x2, const int y2) {
    return x1 == x2 && y1 == y2;
}
inline void init() {
    for (register int i = 0; i <= MAXI; i++) {
        for (register int j = 0; j < MAXJ; j++) {
            for (register int k = 0; k < MAXK; k++) {
                Node *cur1 = &nodes[i][j][k][0], *cur2 = &nodes[i][j][k][1];
                register int xi = i / MAXJ, yi = i % MAXJ, xj = j / 3 + 7, yj = j % 3 + 3, xk = k / 3, yk = k % 3 + 3;
                if (equals(xi, yi, xj, yj) || equals(xi, yi, xk, yk))
                    continue;
                if (i != MAXI) {
                    for (register int d = 0; d < 8; d++) {
                        register int xi1 = xi + delta2[d][0], yi1 = yi + delta2[d][1];
                        if (equals(xi1, yi1, xk, yk)) {
                            cur1->flag = true;
                            break;
                        }
                    }
                }
                if (yj == yk && (yi != yj || xi < xk || xi > xj))
                    cur1->flag = true;
                if (!cur1->flag) {
                    if (i != MAXI) {
                        for (register int d = 0; d < 8; d++) {
                            register int xi1 = xi + delta2[d][0], yi1 = yi + delta2[d][1];
                            int tmp[2] = {xi + delta2[d][0] / 2, yi + delta2[d][1] / 2};
                            if (valid(xi1, yi1) && !equals(xi1, yi1, xj, yj) && !equals(tmp[0], tmp[1], xj, yj) && !equals(tmp[0], tmp[1], xk, yk))
                                cur1->addEdge(&nodes[xi1 * 9 + yi1][j][k][1]);
                        }
                    }
                    for (register int d = 0; d < 4; d++) {
                        register int xj1 = xj + delta1[d][0], yj1 = yj + delta1[d][1];
                        if (xj1 >= 7 && xj1 <= 9 && yj1 >= 3 && yj1 <= 5 && !equals(xj1, yj1, xi, yi))
                            cur1->addEdge(&nodes[i][(xj1 - 7) * 3 + (yj1 - 3)][k][1]);
                    }
                }
                if (yj == yk && (yi != yj || xi < xk || xi > xj))
                    cur2->flag = true;
                if (!cur2->flag) {
                    for (register int d = 0; d < 4; d++) {
                        register int xk1 = xk + delta1[d][0], yk1 = yk + delta1[d][1];
                        if (xk1 >= 0 && xk1 <= 2 && yk1 >= 3 && yk1 <= 5)
                            cur2->addEdge(&nodes[equals(xk1, yk1, xi, yi) ? 90 : i][j][xk1 * 3 + yk1 - 3][0]);
                    }
                }
            }
        }
    }
    queue<Node *> q;
    for (register int i = 0; i <= MAXI; i++) {
        for (register int j = 0; j < MAXJ; j++) {
            for (register int k = 0; k < MAXK; k++) {
                for (register int l = 0; l <= 1; l++) {
                    Node *x = &nodes[i][j][k][l];
                    if (x->flag) {
                        x->step = 1;
                        q.push(x);
                    }
                }
            }
        }
    }
    while (!q.empty()) {
        Node *v = q.front();
        q.pop();
        if (v->flag) {
            for (vector<Node *>::iterator it = v->edge.begin(); it != v->edge.end(); it++) {
                Node *u = *it;
                if (u->step) continue;
                if(!--u->degree) {
                    u->flag = false;
                    u->step = v->step + 1;
                    q.push(u);
                }
            }
        } else {
            for (vector<Node *>::iterator it = v->edge.begin(); it != v->edge.end(); it++) {
                Node *u = *it;
                if (u->step) continue;
                u->flag = true;
                u->step = v->step + 1;
                q.push(u);
            }
        }
    }
}
inline void solve() {
    int x1, x2, x3, y1, y2, y3, l;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> l;
    register int i = x1 * 9 + y1, j = (x2 - 7) * 3 + (y2 - 3), k = x3 * 3 + (y3 - 3);
    Node *cur = &nodes[i][j][k][l ^ 1];
    if (!l) {
        if (!cur->step)
            cout << "Lucky guy!\n";
        else if (cur->flag)
            cout << "Lucky guy!\n";
        else cout << "Lose in " << cur->step << " steps T.T!\n";
    } else {
        if (!cur->step)
            cout << "Lucky guy!\n";
        else if (cur->flag)
            cout << "Lose in " << cur->step << " steps T.T!\n";
        else cout << "Lucky guy!\n";
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}
20161110测试总结
KMP 算法学习笔记

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

×