省赛前的刷题训练(三)

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

省赛刷题训练（三）

[Goldbach`s Conjecture](https://vjudge.net/contest/283110#problem/J)

LightOJ 1259

验证任何一个大于2的偶数都已可表示成两个素数的和。第一次只用了is[]数组，这样的话需要多找一些不必要的数对，同时也会超时。用了prime[]数组后，就可以只遍历素数对了。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000001;
bool is[maxn];
vector<int>prime;
int tot;
void Prime(){
    memset(is,0,sizeof(is));
    is[1] = 1;
    for(int i = 2; i < maxn; ++i)
    {
        if(!is[i])
        {
            prime.push_back(i);
            for(int j = i + i; j < maxn; j += i)
            {
                is[j] = 1;
            }
        }
    }
}
int main()
{
    int n,caser = 1, num;
    tot = 0;
    Prime();
    cin >> n;
    while(n--)
    {
        cin >> num;
         printf("Case %d: ",caser++);
        int sum = 0;
        for(int i = 0 ; prime[i] <= num / 2; ++i)
        {
            if(!is[num - prime[i]])
            {
                sum++;
            }
        }
        cout << sum << '\n';
    }
}

Number Sequence

POJ 1019

是一个思维题，我们需要记录的是每个组中有多少个数字，以及前i组中一共有多少个数字，当我们输入一个位置pos之后，可以判断出它在哪个组中，然后判断出它在这个组中的某个数字num当中，算到这，我们已经知道了在这个组中直到num一共有多少位数字sum，同时也知道了pos这个位置在这个组中的具体位置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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
using namespace std;

long long sum[35000],s[35000];
int init()
{
    s[1] = 1;
    sum[1] = 1;
    for(int i = 2; i <= 33001 ;++i)
    {
        s[i] = s[i - 1] + (int)log10(double(i)) + 1 ;    //第i组所包含的数字个数
        sum[i] = sum[i - 1] + s[i];               //前i组一共的数字个数
    }
}
int main()
{
    init();
    int t, n, i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int index;
        i = 1;
        while(sum[i] < n)
        {
            i++;
        }
        index = i;
        n -= sum[index - 1];
        int sum = 0, index1;
        for(i = 1; i <= index; ++i)
        {
            sum += (int)log10(i) + 1;
            if(sum >= n)
            {
                index1 = i;
                break;
            }
        }
        cout << (index1)/(int)pow(10, sum - n) % 10 << '\n';
    }
}

Proxy

山东省第三届省赛C题

反向建图，需要我们求出来在最短路径中离0点最近的点，同时下标最小。反向建图时，我们先保存一下与起点相连的点。最后求出最短路径之后，在验证一下这个点可不可以是最短路径上的点。明明记得反向建图，但是还是在add时没有写对，让我一度怀疑链式前向星的问题。注意输出-1的情况，同时求出的这个点恰好就是n + 1点，说明这个图中的最短路径只有 0 点和 n + 1点，因此就把此时的情况输出为0，剩下的就是普通情况了。

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
#include <bits/stdc++.h>
using namespace std;
struct node{
     int v,w,next;
}edge[40001];
const int inf = 0x3f3f3f3f;
int head[3001],vis[3001],dist[3001], n, m;
int tot;
int add(int u,int v,int w)
{
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int spfa(int s)
{
    dist[s] = 0;
    vis[s] = 1;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for(int k = head[u]; k != -1; k = edge[k].next)
        {
            int w = edge[k].w;
            int v = edge[k].v;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if(!vis[v])
                {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}
int main()
{
    int t, num[1003][2], u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        tot = 1;
        vector<int>V;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(dist,inf,sizeof(dist));
        memset(num,0,sizeof(num));
        scanf("%d %d",&n,&m);
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d %d",&u,&v,&w);
            add(v,u,w);
            if(u == 0)
            {
                V.push_back(v);
                num[v][0] = w;
            }
        }
        spfa(n + 1);
        if(dist[0] == inf)
        {
            cout << "-1" << '\n';
            continue;
        }
        int miner = inf;
        for(int i = 0; i < V.size() ; ++i)
        {
            if(dist[V[i]] + num[V[i]][0] == dist[0])
            {
                if(V[i] < miner)
                {
                    miner = V[i];
                }
            }
        }
        if(miner == n + 1)
            cout << 0 << '\n';
        else
            cout << miner << '\n';
    }
}

Stones

HDU 1896

扔石子游戏，只能扔奇数块的石头，在某一个位置可以扔那个位置上的石头，扔的距离由你输入的决定，一块石头扔出去之后会到达另一个位置。问最后石头到达的最远的位置是什么。优先队列模拟。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
struct node{
   int pos, dis;
   bool operator<(const node & a)const{
       if(a.pos != pos)
        return a.pos < pos;
       else
        return a.dis < dis;
   }
}a[300001];
priority_queue<node>Q;
int main()
{
    int t;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d %d",&a[i].pos , &a[i].dis);
            Q.push(a[i]);
        }
        int sum = -1;
        int counter = 1;
        while(!Q.empty())
        {
            if(counter % 2)
            {
                node A = Q.top();
                Q.push({A.pos + A.dis, A.dis});
                sum = max(sum, A.pos + A.dis);
                Q.pop();
                counter ++;
            }
            else{
                Q.pop();
                counter++;
            }
        }
        cout << sum << '\n';
    }
}