省赛前的刷题训练(一)

发表于 更新于 分类于 阅读次数：

省赛刷题训练（一）

非常可乐

临近比赛，不再学习新知识，把以前csdn上的题拿过来重新做一遍。

HDU 1495

寒假训练的一道题，拿出来重新做，思路很清晰了，就是因为细节问题改了几遍。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
struct node{
       int x,y,z,time;
};
int vis[101][101][101];
int bfs(int S,int N,int M)
{
    node A,B;
    queue<node>Q;
    Q.push({S,0,0,0});
    vis[S][0][0] = 1;
    while(!Q.empty())
    {
        A = Q.front();
        Q.pop();
        if((A.x == A.y && A.x == S / 2 && A.z == 0) || (A.x == A.z && A.x == S / 2 && A.y == 0) || (A.y == A.z && A.y == S / 2 && A.x == 0))
        {
            return A.time;
        }
        if(A.x > 0)
        {
            B.y = A.y + min(A.x, N - A.y);
            B.x = A.x - min(A.x, N - A.y);
            B.z = A.z;
            B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
        if(A.x > 0)
        {
            B.z = A.z + min(A.x, M - A.z);
            B.x = A.x - min(A.x, M - A.z);
            B.y = A.y;
             B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
        if(A.y > 0)
        {
            B.y = A.y - min(A.y, S - A.x);
            B.x = A.x + min(A.y, S - A.x);
            B.z = A.z;
             B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
        if(A.y > 0)
        {
            B.y = A.y - min(A.y, M - A.z);
            B.z = A.z + min(A.y, M - A.z);
            B.x = A.x;
            B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
         if(A.z > 0)
        {
            B.z = A.z - min(A.z, S - A.x);
            B.x = A.x + min(A.z, S - A.x);
            B.y = A.y;
             B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
         if(A.z > 0)
        {
            B.z = A.z - min(A.z, N - A.y);
            B.y = A.y + min(A.z, N - A.y);
            B.x = A.x;
             B.time = A.time + 1;
            if(!vis[B.x][B.y][B.z])
            {
                vis[B.x][B.y][B.z] = 1;
                Q.push(B);
            }
        }
    }
    return -1;
}
int main()
{
    int S,N,M;
    while(cin >> S >> N >> M)
    {
        memset(vis,0,sizeof(vis));
        if(S == 0 && N == 0 && M == 0)
            break;
        int c = bfs(S,N,M);
        if(c == -1)
            cout << "NO" << '\n';
        else
            cout << c << '\n';
    }
}

HDU 4006

The kth great number

运用multiset应该更简单一些，不用排序了，这里练习vector的用法。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
    int n,k,num;
    string s;
    while(cin >> n >> k)
    {
        vector<int>V;
        for(int i = 1 ; i <= n; ++i)
        {
            cin >> s;
            if(s[0] == 'I')
            {
                cin >> num;
                V.insert(lower_bound(V.begin(),V.end(),num), num);
            }
            else{
                cout << V[V.size() - k] << '\n';
            }
        }
    }
}

Color the ball

HDU 1556

好长时间没写线段树了，竟然连区间更新有个Pushdown都忘记了，好歹看了一眼模板又想起来了。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int tree[400001];
int addmark[400001];
void pushdown(int node,int begin,int end)
{
    if(addmark[node] == 0)
        return;
    int mid = (begin + end) / 2;
    addmark[node << 1] += addmark[node];
    addmark[node << 1|1] += addmark[node];
    tree[node << 1] += addmark[node] * (mid - begin + 1);
    tree[node << 1|1] += addmark[node] * (end - mid);
    addmark[node] = 0;
}
void update(int node,int begin ,int end,int l ,int r ,int k)
{
    if(l > end || r < begin)
        return;
    if(l <= begin && r >= end)
    {
        tree[node] += k;
        addmark[node] += k;
        return;
    }
    pushdown(node,begin,end);
    int mid = (begin + end) / 2;
    update(node << 1, begin , mid, l, r, k);
    update(node << 1|1, mid + 1, end, l ,r ,k);
    tree[node] = tree[node << 1] +  tree[node << 1|1];
}
int query(int node,int begin,int end,int pos)
{
    if(pos > end || pos < begin)
        return 0;
    if(pos == begin && begin == end)
    {
        return tree[node];
    }
    pushdown(node,begin,end);
    int sum = 0;
    int mid = (begin + end) / 2;
    sum += query(node << 1,begin ,mid, pos);
    sum += query(node << 1|1,mid + 1,end,pos);
    return sum;
}
int main()
{
    int n;
    while(cin >> n && n)
    {
        int l, r;
        memset(tree,0,sizeof(tree));
        memset(addmark,0,sizeof(addmark));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d %d",&l,&r);
            update(1,1,n,l,r,1);
        }
        for(int i = 1; i <= n; ++i)
        {
            printf("%d%c",query(1,1,n,i),i == n ? '\n' : ' ');
        }
    }
}

Can you find it?

HDU 2141

再次做二分的题，第一次优化到n^2log(n)果然超时，因为我只是排了第三个数字的顺序。第二次把第一个和第二个数组的和放到一个数组里，再用二分。（可我竟然把a数组和b数组接连放到一个数组里，佩服我自己。在CSDN中用的是标准的二分，这里直接用的lower_bound函数

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int main()
{
    int a[501],b[501],c[501],L,N,M,num,k, caser = 1;
    int d[505*505];
    while(scanf("%d %d %d",&L,&N,&M) != EOF)
    {
        int tot = 0;
        for(int i = 0; i < L; ++i)
        {
            scanf("%d",&a[i]);
        }
        for(int i = 0; i < N; ++i)
        {
            scanf("%d",&b[i]);
        }
        for(int i = 0; i < M; ++i)
        {
            scanf("%d",&c[i]);
        }
        for(int i = 0; i < L; ++i)
        {
            for(int j = 0; j < N; ++j)
            {
                d[tot++] = a[i] + b[j];
            }
        }
        sort(d , d + tot);
        scanf("%d",&num);
        printf("Case %d:\n",caser++);
        while(num--){
        scanf("%d",&k);
        int flag = 0;
        for(int i = 0; i < M; ++i)
        {
            int num1 = k - c[i];
            int m = lower_bound(d, d + tot, num1) - d;
            if(d[m] == num1)
                flag = 1;
        }
        if(flag == 1)
            printf("YES\n");
        else
            printf("NO\n");
        }
    }
}