省赛前的刷题训练(二)

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

省赛刷题训练（二）

Values whose Sum is 0

UVA 1152

一个简单的二分题目，将a数组和b数组排个序，c数组和d数组排个序，然后对第二个数组进行二分查找。这里要找的是个数，所以upper_bound和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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
int e[4001 * 4001],f[4001 * 4001];
int a[4001],b[4001],c[4001],d[4001];
int main()
{
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
        }
        int tot = 0;
        for(int i = 0 ; i < n; ++i)
        {
             for(int j = 0; j < n; ++j)
             {
                 e[tot++] = a[i] + b[j];
             }
        }
        tot = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0 ;j < n; ++j)
            {
                f[tot++] = c[i] + d[j];
            }
        }
        sort(e , e + tot);
        sort(f , f + tot);
        int sum = 0;
        for(int i = 0; i < tot; ++i)
        {
            int m = upper_bound(f , f + tot , -e[i]) - lower_bound(f ,f + tot, -e[i]);
            sum += m;
        }
        cout << sum << '\n';
        if(t)
            cout << '\n';
    }
}

Humble numbers

HDU 1058

再一次做感觉思路清晰了挺多，第一次做没有理解本质，再一次做的时候，想到每一个数其实都可以通过它前面的数字乘积得到。2 3 5 7作为乘积的一个参数，另一个参数就是前面已经出现过的数字。比如8，通过2 * 4得到，2是一个因子，4是因为前边已经出现过了。

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
#include <bits/stdc++.h>
using namespace std;
int a[10001];
int elect()
{
    int aa = 1, bb = 1, cc = 1, dd = 1;
    a[1] = 1;
    for(int i = 2; i <= 5842; ++i)
    {
        a[i] = min(2 * a[aa], min(3 * a[bb], min(5 * a[cc] , 7 * a[dd])));
        if(a[i] == 2 * a[aa])
         aa++;
        if(a[i] == 3 * a[bb])
        bb++;
        if(a[i] == 5 * a[cc])
            cc++;
        if(a[i] == 7 * a[dd])
            dd++;
    }
}
int main()
{
    int n;
    elect();
    while(scanf("%d" ,&n) != EOF && n)
    {
        if(n % 10 == 1 && n % 100 != 11)
        {
            printf("The %dst humble number is %d.\n",n,a[n]);
        }
        else if(n % 10 == 2 && n % 100 != 12)
        {
             printf("The %dnd humble number is %d.\n",n,a[n]);
        }
        else if(n % 10 == 3 && n % 100 != 13)
        {
            printf("The %drd humble number is %d.\n",n,a[n]);
        }
        else{
             printf("The %dth humble number is %d.\n",n,a[n]);
        }
    }
}

Train Problem I

HDU 1022

模拟火车的进出站。注意栈为空就要停止。

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
#include <bits/stdc++.h>
using namespace std;
struct node{
    string s;
}b[1001];
int main()
{
    int n;
    while(cin >> n)
    {
        stack<char>S;
        string s,s1;
        cin >> s;
        cin >> s1;
        int tot = 0;
        int ans = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            S.push(s[i]);
            b[ans++].s = "in";
            while(s1[tot] == S.top())
            {
                S.pop();
                tot++;
                b[ans++].s = "out";
                if(tot == s1.size() || S.empty())
                    break;
            }
        }
        if(S.size() == 0)
        {
            cout << "Yes." << '\n';
            for(int i = 0; i < ans; ++i)
            {
                cout << b[i].s << '\n';
            }
            cout << "FINISH" << '\n';
        }
        else{
            cout << "No." << '\n';
            cout << "FINISH" << '\n';
        }
    }
}

Prime Friend

HDU 3823

需要注意的是输入的A和B的大小关系不一定，素数打表范围要开的很大。第一次WA是因为没有搞懂什么是prime neighbor . 比如说输入2 和 4这两个数字，我们找到了1，因为1 + 2 和 1 + 4是素数，同时 3 和 5 还是素数相邻。 这样的话我们最终在枚举的时候，就枚举相邻的两个素数就行了，满足条件的话就输出对应的数字。而不是从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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20000001;
bool is[maxn];
int tot;
int prime[maxn];
void Prime()
{
    memset(is,0,sizeof(is));
    is[0] = is[1] = 1;
    tot = 0;
    for(int i = 2; i < maxn; ++i)
    {
        if(!is[i])
        {
            prime[tot++] = i;
            for(int j = i + i; j < maxn; j += i)
            {
                is[j] = 1;
            }
        }
    }
}
int main()
{
    Prime();
    int t,caser = 1,A,B;
    cin >> t;
    while(t--)
    {
        scanf("%d %d",&A,&B);
        if(A > B)
            swap(A,B);
        printf("Case %d: ",caser++);
        int flag = -1;
        for(int i = 0; i + 1 < tot; ++i)
        {
            if(prime[i + 1] - prime[i] == B - A && prime[i] >= A)
            {
                flag = prime[i] - A;
                break;
            }
        }
       cout << flag << '\n';
    }
}