OI
7 minutes read (About 980 words)

20161112测试总结

T1

先判断负数个数的奇偶性，再处理能直接判断的情况，然后用 double 一乘一除判断就好了。
此题还可以用神奇的数学方法，我们可以把相乘看成 $log$ 相加，处理符号就好了。

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
#include <stack>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <string>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    iosig = 0, x = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = true;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
const int MAXN = 100010;
int t, n, m;
int alice[MAXN], bob[MAXN];
inline void solve() {
    fill(alice, alice + MAXN, 1);
    fill(bob, bob + MAXN, 1);
    register bool flagAliceZero = false, flagBobZero = false, flagAliceSum = false, flagBobSum = false;
    register int totAlice = 0, totBob = 0;
    double sum = 1;
    read(n);
    for (register int i = 1; i <= n; i++) {
        read(alice[i]);
        if (alice[i] == 0) flagAliceZero = true;
        if (alice[i] < 0) alice[i] = -alice[i], totAlice++;
    }
    read(m);
    for (register int i = 1; i <= m; i++) {
        read(bob[i]);
        if (bob[i] == 0) flagBobZero = true;
        if (bob[i] < 0) bob[i] = -bob[i], totBob++;
    }
    /*Alice->0  2 | totBob ==> Bob > 0*/
    if (flagAliceZero == true && (~totBob & 1)) {
        cout << "Alice\n";
        return;
    }
    /*Alice->0  2 ~| totBob ==> Bob < 0*/
    if (flagAliceZero == true && (totBob & 1)) {
        cout << "Bob\n";
        return;
    }
    /*Bob->0 2 | totAlice ===> Alice > 0*/
    if (flagBobZero == true && (~totAlice & 1)) {
        cout << "Bob\n";
        return;
    }
    /*Bob->0 2 ~| totAlice ===> Alice < 0*/
    if (flagBobZero == true && (totAlice & 1)) {
        cout << "Alice\n";
        return;
    }
    /*2 ~| totAlice ===> Alice < 0 2 | totBob ===> Bob > 0*/
    if ((totAlice & 1) && (~totBob & 1)) {
        cout << "Alice\n";
        return;
    }
    /*2 | totAlice ===> Alice > 0  2 ~| totBob ===> Bob < 0*/
    if ((~totAlice & 1) && (totBob & 1)) {
        cout << "Bob\n";
        return;
    }
    register int posAlice = 0, posBob = 0;
    while (posAlice <= n || posBob <= m) {
        while (posAlice <= n && sum <= 1e5) {
            posAlice++;
            sum = sum * double(alice[posAlice]);
        }
        while (posBob <= m && sum >= 1e-5) {
            posBob++;
            sum = sum / double(bob[posBob]);
        }
        if (posAlice > n) {
            flagAliceSum = true;
            break;
        }
        if (posBob > m) {
            flagBobSum = true;
            break;
        }
    }
    if (flagAliceSum == true) {
        while (posBob <= m) {
            sum /= bob[posBob];
            posBob++;
            if (sum < 1) break;
        }
    }
    if (flagBobSum == true) {
        while (posAlice <= n) {
            sum *= alice[posAlice];
            posAlice++;
            if (sum > 1) break;
        }
    }
    if ((~totAlice & 1) && sum >= 1) {
        cout << "Bob\n";
        return;
    }
    if ((~totAlice & 1) && sum < 1) {
        cout << "Alice\n";
        return;
    }
    if ((totAlice & 1) && sum >= 1) {
        cout << "Alice\n";
        return;
    }
    if ((totAlice & 1) && sum < 1) {
        cout << "Bob\n";
        return;
    }
}
int main() {
    read(t);
    while (t--)
        solve();
    return 0;
}

T2

$dp$，首先可以很简单地想出一个 $O(n^4)$ 的暴力 $dp$，然后我们可以用乘法分配率拆掉 $sum$，通过将两个序列的所有数 $-1$，就可以得到优化后的方程
$$f[i][j]=\min(f[i+1][j+1],f[i+1][j],f[i][j+1])$$，这样做时间复杂度为$O(n^2)$。
此题数据水，否则应用long long + 滚动数组

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
#include <stack>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <string>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    iosig = 0, x = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = true;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
template<class T>
inline T min(T a, T b, T c) {
    return std::min(std::min(a, b), c);
}
const int MAXN = 5100;
int a[MAXN], b[MAXN];
int f[MAXN][MAXN];
int l1, l2;
const int INF = INT_MAX;
inline void dp() {
    for (register int i = 0; i <= l1 + 1; i++)
        fill(f[i], f[i] + l2 + 2, INF);
    f[l1 + 1][l2 + 1] = 0;
    for (register int i = l1; i > 0; i--)
        for (register int j = l2; j > 0; j--)
            f[i][j] = min(f[i + 1][j + 1], f[i + 1][j], f[i][j + 1]) + a[i] * b[j];
}
int main() {
    read(l1), read(l2);
    for (register int i = 1; i <= l1; i++)
        read(a[i]), a[i]--;
    for (register int i = 1; i <= l2; i++)
        read(b[i]), b[i]--;
    dp();
    cout << f[1][1];
    return 0;
}

T3

我们可以推出一个式子$ans=\frac{n \times (n-1)}{2}-\sum\limits_{i=1}^{componentNumber}\frac{componentSize[i] \times (componentSize[i]-1)}{2}$，思考一下，这个式子为什么是对的？
然后 $tarjan$ 求桥就完了。

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
#include <stack>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <string>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <cstdlib>
using namespace std;
bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    iosig = 0, x = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = true;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
const int MAXN = 20010;
struct Node {
    int v, index;
    bool flag;
    Node(int v, int index) : v(v), index(index), flag(0) {}
};
vector<Node> edge[MAXN];
inline void addEdge(int u, int v) {
    edge[u].push_back(Node(v, edge[v].size()));
    if (u == v) edge[u].back().index++;
    edge[v].push_back(Node(u, edge[u].size() - 1));
}
int dfn[MAXN], low[MAXN], idx, inComponent[MAXN];
int componentSize[MAXN], componentNumber, ans;
stack<int> st;
inline void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    st.push(u);
    register int v;
    for (register int e = 0; e < edge[u].size(); e++) {
        Node *x = &edge[u][e];
        if (x->flag) continue;
        x->flag = true;
        edge[x->v][x->index].flag = true;
        v = x->v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!inComponent[v]) low[u] = min(low[u], low[v]);
    }
    if (dfn[u] == low[u]) {
        componentNumber++;
        do {
            v = st.top(), st.pop();
            componentSize[componentNumber]++;
            inComponent[v] = componentNumber;
        } while (v != u);
        ans -= componentSize[componentNumber] * (componentSize[componentNumber] - 1) >> 1;
    }
}
int n, m;
int main() {
    read(n), read(m);
    for (register int i = 0, u, v; i < m; i++)
        read(u), read(v), addEdge(u, v);
    ans = n * (n - 1) >> 1;
    for (register int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    cout << ans;
    return 0;
}
20161114测试总结
20161111练习总结

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

×