T1

#题目描述 :

对于给定的一个正整数n, 判断n是否能分成若干个正整数之和 (可以重复) ,
其中每个正整数都能表示成两个质数乘积。

#输入描述:

第一行一个正整数 q,表示询问组数。
接下来 q 行,每行一个正整数 n,表示询问。

#输出描述:

q 行,每行一个正整数,为 0 或 1。0 表示不能,1 表示能。

#样例输入:

5
1
4
5
21
25

#样例输出:

0
1
0
1
1

#数据范围:

\(30\%\)的数据满足:\(q\leq20, n\leq20\)
\(60\%\)的数据满足:\(q\leq10000, n\leq5000\)
\(100\%\)的数据满足:\(q\leq10^5, n \leq 10^{18}\)

解题思路:

看到这个奇葩的数据范围,我先看到了\(100\%\)\(n \leq 10^{18}\)
然后我就不知道怎么想的,写了一个不知道能不能跑过60分的完全背包?

code:

#include <bits/stdc++.h>
#define N 5010
#define ll long long
#define M 1010
#define _ 0

using namespace std;
map<int, int> mp; bool vis[N], b[N];
int q, m, mx, mi = 99999999, cnt, tot;
int po[10000100], f[N], qust[N << 1], prime[N];

int read() {
    int s = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

void erlur(int s) {
    for (int i = 2; i <= s; i++) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++) {
            if (i * prime[j] > s) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

int main() {
    freopen("a.in", "r", stdin);
//  freopen("a.out", "w", stdout);
    q = read();
    for (int i = 1; i <= q; i++) {
        qust[i] = read();
        mx = max(mx, qust[i]);
    }
    erlur(mx);
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++) {
            int an = prime[i] * prime[j];
            if (!mp[an] && an <= mx)
                mp[an] = 1, po[++tot] = an, mi = min(mi, an);
        }
    cout << tot << "\n";
    for (int i = 1; i <= q; i++) {
        if (b[qust[i]]) cout << 1 << " ";
        else {
            memset(f, 0, sizeof(f));
            int flag = 0;
            for (int j = 1; j <= tot; j++)
                for (int k = po[j]; k <= qust[i]; k++) {
                    f[k] = max(f[k], f[k - po[j]] + po[j]);
                    if (f[k] == qust[i]) flag = 1;
                }
            if (flag) b[qust[i]] = 1, puts("1");
            else puts("0");
        }
    }
    return 0;
}

在打出来的时候尝试一下\(60\%\)的范围,结果发现自己的程序跑步过去,然后就把前\(1000\)个输了出来,然后发现除了前边的\(1,2,3,5,7,11\)之外所有的数都是1,只有这两个是0.

证明啊

\(n \leq 20\) 时, 只有\(1,2,3,5,7,11\)无解,其余均有解。
\(n > 20\) 时, 因为\(n = (n - 4) + 4 = (n-4) + 2 \ast 2\),而\((n-4)\)这个数\(\geq16\), 是一定有解的。
所以,我们证明了对于任意的正整数\(n\),只有\(n = 1,2,3,5,7,11\)时无解,其余均有解。

正解代码:

#include <bits/stdc++.h>
#define N 100010
#define M 1010
#define _ 0

using namespace std;
long long q, n;

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

int main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    q = read();
    for (int i = 1; i <= q; i++) {
        n = read();
        if (n == 1 || n == 2 || n == 3 || n == 5  || n == 7 || n == 11) puts("0");
        else puts("1");
    }
    return 0;
}

T2

01-26 15:01