数据结构和算法分析

AtCoder Beginner Contest 096/D

2018-05-08  本文已影响6人  不知名小号

题目链接

题意

要求找出n个素数,然后这n个素数里面任意5个数相加起来都是合数。

思路

打比赛的时候smc指挥我写了一个神奇的欧拉筛,然后我跟队友想了各种办法,dfs,爆搜都想了,但是当时并没有做出来。但是刚刚学长跟我说他看了题解,没想到思路这么巧妙!

正解是:找出n个个位数相同的素数就可以了,因为个位数相同,任意五个数相加起来的和的个位数就是一个合数。
甚至找出n个个位数都是1素数也可以,因为相加之后个位为5,肯定是合数。

代码如下

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define maxn 1000000
bool mark[maxn];
int pri[maxn];
//欧拉筛
void ola(){
    for (int i = 2; i * i < maxn; i++){
        for (int j = 2; j <= i; j++){
            mark[i * j] = 1;
        }
    }
    int t = 0;
    for (int i = 2; i < maxn; i++){
        if(!mark[i]){
            pri[t++] = i;
        }
    }
}

int main(int argc, char * argv[]) 
{
    int ans[11][100], cnt[11], flag, n; //cnt[i]记录了个位数为i的素数出现的次数
    ms(cnt);
    ms(mark);
    ola();
    cin >> n;
    for (int i = 0; i <= maxn; i++){
        int t = pri[i] % 10; //t为当前出现素数的个位数
        ans[t][cnt[t]] = pri[i];  //给对应的个位数数组放进当前素数
        cnt[t]++;
        if (cnt[t] >= n){ //如果某个个位数出现的次数超过n,则记录并停止循环
            flag = t;
            break;
        }
    }
    for (int i = 0; i < n; i++){
        if (!i) cout << ans[flag][i];
        else cout << " " << ans[flag][i];
    }
    cout << endl;
    return 0;
}

最后跑了几个样例发现素数中出现最多的个位数是3,所以可以直接统计个位数为3的素数就ok了,不用那么复杂。

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define maxn 1000000
bool mark[maxn];
int pri[maxn];
void ola(){
    for (int i = 2; i * i < maxn; i++){
        for (int j = 2; j <= i; j++){
            mark[i * j] = 1;
        }
    }
    int t = 0;
    for (int i = 2; i < maxn; i++){
        if(!mark[i]){
            pri[t++] = i;
        }
    }
}

int main(int argc, char * argv[]) 
{
    int ans[100], n;
    ms(mark);
    ola();
    cin >> n;
    int t = 0;
    for (int i = 0; i <= maxn && t < n; i++){
        if (pri[i] % 10 == 3) ans[t++] = pri[i];
    }
    for (int i = 0; i < n; i++){
        if (!i) cout << ans[i];
        else cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}

总结反思

当时思维僵化,没想到还有这么巧妙的思路,还想着要找出所有数,然后一遍一遍验证,真是too young!
跟两个队友的第一场网络赛训练,A了3道水题,还马马虎虎。

上一篇下一篇

猜你喜欢

热点阅读