OI
8 minutes read (About 1219 words)

20161028测试总结

T1

T2、T3 AC的我T1爆0…
string.substr注意长度的判断，以免RE…
此题可以直接暴力计数，也可以用HashMap优化

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>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
__gnu_pbds::cc_hash_table<string, int> h;
string str;
char c;
int cnt;
long long ans;
int main() {
    while (cin.get(c)) {
        c = tolower(c);
        if (c >= 'a' && c <= 'z') str += c;
        else {
            if (!str.length()) continue;
            h[str]++, cnt++;
            str.clear();
        }
    }
    for (__gnu_pbds::cc_hash_table<string, int>::iterator it = h.begin(); it != h.end(); it++) {
        register int tmp = it->second;
        ans += (long long)tmp * tmp * tmp * tmp;
    }
    cout << ans << " " << cnt;
    return 0;
}

T2

这是一道极为简单的模拟题，但写起来就233了…

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
#include <bits/stdc++.h>
using namespace std;

const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
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 bool read(T& x) {
    iosig = false;
    for(ioc = read(); !isdigit(ioc); ioc = read()) {
        if(ioc == -1) return false;
        if(ioc == '-') iosig = true;
    }
    x = 0;
    while(ioc == '0') ioc = read();
    for(; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if(iosig) x = -x;
    return true;
}
struct Node {
    int t, s, f;
    bool flag;
    int end;
} people[5000];
int ans[5000];
inline bool check1(int x, int y){
    if (people[y].s <= people[x].f && people[y].f >= people[x].s) return true;
    return false;
}
inline bool check2(int x,int y){
    if(people[y].s >= people[x].f && people[y].f <= people[x].s) return true;
    return false;
}
inline bool check3(int i, int j) {
    return people[j].t + people[i].s - people[j].s == people[i].t;
}
inline bool check4(int i, int j) {
    return people[j].t + people[j].s - people[i].f <= people[i].t + people[i].f - people[i].s;
}
inline void addAns(int i, int j) {
    ans[i]++, ans[j]++;
} 
inline void solve(int n) {
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= n; j++) {
            
            if(i == j) continue;
            if(people[i].flag == people[j].flag) {
                if(!people[i].flag) {
                    if(check3(i, j) && check1(i, j))    
                        ans[i]++;
                
                } else { 
                    if(people[j].t - people[i].s + people[j].s == people[i].t && check2(i, j))  
                        ans[i]++;   
                }
            } else {
                if(!people[i].flag) {
/*case 1*/          if(people[j].s > people[i].f) {
                        if(people[j].f <= people[i].f && people[j].f >= people[i].s)
/*case 11*/                 if(check4(i, j) && people[j].end >= people[i].t + people[j].f - people[i].s)
                                addAns(i, j);
/*case 12*/             if(people[j].f <= people[i].f && people[j].f < people[i].s)
                            if(check4(i, j) && people[j].t + people[j].s - people[i].s >= people[i].t)
                                addAns(i, j);
/*case 2*/          } else {
                        if (people[j].s >= people[i].s && people[j].f < people[i].s)
                            if(people[i].t <= people[j].t + people[j].s - people[i].s && people[i].t + people[j].s - people[i].s >= people[j].t)
                                addAns(i, j); 
                        if (people[j].s >= people[i].s && people[j].f >= people[i].s)
                            if (people[i].t + people[j].f - people[i].s <= people[j].end && people[i].t + people[j].s - people[i].s >= people[j].t)
                                addAns(i, j);   
                    }
                }  
            }
        }
    }
    for (register int i = 1; i <= n; i++) cout << ans[i] <<" ";
}
int n;
int main() {
    read(n);
    for (register int i = 1; i <= n; i++) {
        read(people[i].t), read(people[i].s), read(people[i].f);
        people[i].end = people[i].t + abs(people[i].s - people[i].f);
        if(people[i].s < people[i].f) people[i].flag = false;
        else people[i].flag = true;
    }
    solve(n);
    return 0;
}

T3

我们可以考虑先按t和d分别排序，然后线性枚举t，将大于等于d的t和t对应的pos插进两颗权值线段树里，并给第二棵权值线段树加权为d，再打上左右儿子之和，这时我们只需要计算一下两颗权值线段树的根节点之差是否小于r，就能判断答案是否为0，对于不为0的情况，只需要恢复权值，在询问时递归减去加权的d就能得到答案。
注意sort的稳定性，我们还是用stable_sort吧

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
#include <bits/stdc++.h>
using namespace std;

const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
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 bool read(T& x) {
    iosig = false;
    for(ioc = read(); !isdigit(ioc); ioc = read()) {
        if(ioc == -1) return false;
        if(ioc == '-') iosig = true;
    }
    x = 0;
    while(ioc == '0') ioc = read();
    for(; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if(iosig) x = -x;
    return true;
}
struct Node1 {
    int t, pos;
    inline bool operator < (const Node1 &n) const {
        return t > n.t;
    }
};
struct Node2 {
    int d, r, pos;
    inline bool operator < (const Node2& n) const {
        return d > n.d;
    }
};
const int MAX = 200005;
typedef long long ll;
int n, m;
Node1 data1[MAX];
Node2 data2[MAX];
struct WeightSegmentTree {
    /*data1 -> d1 ------------------ data2 -> d2*/
    ll *SegmentTreeData1, *SegmentTreeData2;
    /*size > 2 ^ ? max(n, m)*/
    int size;
    /*d1 -> pos ----------------- d2 -> t*/
    void insert(int v, int l, int r, ll d1, ll d2) {
        
        if (l == r) {
            SegmentTreeData1[v] = d2;
            SegmentTreeData2[v] = 1;
            /*SegmentTreeData1[v] = 1;------
        ------SegmentTreeData2[v] = d2;*/
            return;
        }
        register int mid = (l + r) >> 1;
        if (d1 <= mid) insert(v << 1, l, mid, d1, d2);
        else insert(v << 1 | 1, mid + 1, r, d1, d2);
        SegmentTreeData1[v] = SegmentTreeData1[v << 1] + SegmentTreeData1[v << 1 | 1];
        SegmentTreeData2[v] = SegmentTreeData2[v << 1] + SegmentTreeData2[v << 1 | 1];
    }
    ll query(int v, int l, int r, ll d1, ll d2) {
        if (l == r) return l;
        
        register int mid = (l + r) >> 1;
        if (SegmentTreeData1[v << 1] - SegmentTreeData2[v << 1] * d2 >= d1)
            return query(v << 1, l, mid, d1, d2);
        else{
            /*d1 = SegmentTreeData1[v << 1] - SegmentTreeData2[v << 1] * d2*/
            d1 -= SegmentTreeData1[v << 1] - SegmentTreeData2[v << 1] * d2;
            return query(v << 1 | 1, mid + 1, r, d1, d2);
        }
    }
    /*--------d -> d--------*/
    ll getRootDelta(int d) {
        return SegmentTreeData1[1] - SegmentTreeData2[1] * d;
    }
    WeightSegmentTree(int n) : size(n << 2 | 1), SegmentTreeData1(new ll[n << 2 | 1]), SegmentTreeData2(new ll[n << 2 | 1]) {
        memset(SegmentTreeData1, 0, sizeof(ll) * size);
        memset(SegmentTreeData2, 0, sizeof(ll) * size);
    }
} *tree;
ll ans[MAX];
int main() {
    read(n), read(m);
    tree = new WeightSegmentTree(max(n, m) + 1);
    for (register int i = 1; i <= m; i++)
        read(data1[i].t), data1[i].pos = i;
    for (register int i = 1; i <= n; i++)
        read(data2[i].d), read(data2[i].r), data2[i].pos = i;
    stable_sort(&data1[1], data1 + m + 1), stable_sort(&data2[1], data2 + n + 1);
    for (register int i = 1, k = 1; i <= n; i++) {
        for (; data1[k].t >= data2[i].d && k <= m; k++)
            tree->insert(1, 1, m, data1[k].pos, data1[k].t);
        /*can not finish the work*/
        if (tree->getRootDelta(data2[i].d) < data2[i].r) ans[data2[i].pos] = 0;
        else ans[data2[i].pos] = tree->query(1, 1, m, data2[i].r, data2[i].d);
    }
    for (register int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}
20161101测试总结
20161026测试总结

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

×