OI
7 minutes read (About 993 words)

20161101测试总结

T1

80分贪心

毫无正确性的贪心，直接统计小写变大写后的小写字母数。

正解

递推一下就行了，lsum表示小写字母的个数，usum表示大写字母的个数，$lsum = max(lsum, usum)$，那么 $ans = len - max(lsum, usum)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
char str[100010];
int len, usum, lsum;
inline bool isUpper(const char c) {
    return c >= 'A' && c <= 'Z';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> str;
    len  = strlen(str);
    for (int i = 0; i < len; i++) {
        if (isUpper(str[i])) usum++;
        else lsum = max(lsum, usum) + 1;
    }
    cout << len - max(lsum, usum);
    return 0;
}

T2

此题一看就可以离线搞莫队，由于$ a_{i} \leq 10 ^ {9} $，并且$ n \leq 10^{5} $，所以我们只需要判断100000一下的数据就行了，这时候我们就可以用一个桶，暴力莫队即可，故时间复杂度为$ O(n \sqrt{n}) $，稍微注意一下常数就好。

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
#include <bits/stdc++.h>
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;
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
}
int n, m;
struct Query {
    int l, r;
    int *ans;
    inline bool operator < (const Query& x) const {
        static int blockSize = floor(sqrt(n));
        if (l / blockSize == x.l / blockSize) return r < x.r;
        else return l / blockSize < x.l / blockSize;
    }
} Q[100010];
int a[100010];
int query[100010];
int times[100010];
inline int expandRight1(int l, int r) {
    register int tmp = 0;
    if (a[r] <= 100000) {
        times[a[r]]++;
        if (times[a[r]] == a[r]) tmp++;
        if (times[a[r]] == a[r] + 1) tmp--;
    }
    return tmp;
}
inline int expandRight2(int l, int r) {
    register int tmp = 0;
    if (a[r] <= 100000) {
        times[a[r]]--;
        if (times[a[r]] == a[r]) tmp--;
        if (times[a[r]] == a[r] - 1) tmp++;
    }
    return tmp;
}
inline int expandLeft1(int l, int r) {
    register int tmp = 0;
    if (a[l] <= 100000) {
        times[a[l]]++;
        if (times[a[l]] == a[l]) tmp++;
        if (times[a[l]] == a[l] + 1) tmp--;
    }
    return tmp;
}
inline int expandLeft2(int l, int r) {
    register int tmp = 0;
    if (a[l] <= 100000) {
        times[a[l]]--;
        if (times[a[l]] == a[l]) tmp--;
        if (times[a[l]] == a[l] - 1) tmp++;
    }
    return tmp;
}
int main() {
    read(n), read(m);
    for (register int i = 1; i <= n; i++)
        read(a[i]);
    for (register int i = 0, x, y; i < m; i++)
        read(Q[i].l), read(Q[i].r), Q[i].ans = &query[i];
    sort(Q, Q + m);
    register int l = 1, r = 0, ans = 0;
    for (register int i = 0; i < m; i++) {
        Query &q = Q[i];
        while (r < q.r) r++, ans += expandRight1(l, r);
        while (l > q.l) l--, ans += expandLeft1(l, r);
        while (r > q.r) ans -= expandRight2(l, r), r--;
        while (l < q.l) ans -= expandLeft2(l, r), l++;
        *q.ans = ans;
    }
    for (register int i = 0; i < m; i++)
        cout << query[i] << "\n";
    return 0;
}

T3

我们可以先按权值从大到小排序，然后依次枚举，计算加入这条边后图中有多少点对联通，更新答案；现在问题就变为了如何维护图，我们可以用并查集，如果两个端点在同一联通块中，点对数目不增加，反之，增加的点对为两个联通块的数目之积。

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
#include <bits/stdc++.h>
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;
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
}
struct DisjointSet {
    int *rank, *father, size;
    inline int get(int x) {
        register int p = x, i;
        while (p != father[p]) p = father[p];
        while (x != p) i = father[x], father[x] = p, x = i;
        return p;
    }
    inline void put(int x, int y) {
        x = get(x), y = get(y);
        if (rank[x] > rank[y]) father[y] = x;
        else {
            father[x] = y;
            if (rank[x] == rank[y]) rank[y]++;
        }
    }
    inline void init(int x) {
        rank[x] = 0, father[x] = x;
    }
    DisjointSet(int n) : rank(new int[n + 1]), father(new int[n + 1]), size(n + 1) {
        for (register int i = 1; i <= n; i++)
            father[i] = i;
    }
} *s;
struct Node {
    int u, v, w;
    Node(int u, int v, int w) : u(u), v(v), w(w) {}
    Node() {}
    inline bool operator < (const Node &n) const {
        return w > n.w;
    }
};
Node edge[100010];
int tot;
inline void addEdge(int u, int v, int w) {
    edge[++tot] = Node(u, v, w);
}
typedef long long ll;
const int mod = 1e9;
int n, m, cnt[100010];
ll sum, ans;
int main() {
    read(n), read(m);
    for (int i = 0, u, v, w; i < m; i++) {
        read(u), read(v), read(w);
        addEdge(u, v, w);
        sum += w;
        if (sum >= mod) sum -= mod;
    }
    sort(edge + 1, edge + tot + 1);
    s = new DisjointSet(n);
    fill(cnt + 1, cnt + n + 1, 1);
    for (int i = 1; i <= tot; ++i) {
        register int fa1 = s->get(edge[i].u), fa2 = s->get(edge[i].v);
        if (fa1 != fa2) {
            ans = (ans + (ll)cnt[fa1] * (ll)cnt[fa2] * sum) % (ll)mod;
            s->father[fa2] = fa1;
            cnt[fa1] += cnt[fa2];
        }
        sum -= (ll)edge[i].w;
    }
    cout << (ans % (ll)mod + (ll)mod) % (ll)mod;
    return 0;
}