2024.02.19 测试

cloud2764scallop_eve · 2024-02-19 17:30:30 · 个人记录

Before writing

All the problems in 2024.02.18 测试 and 2024.02.19 测试 in here: link

T1 素数

Link

• gxyzoj: #3598 素数
• Luogu: UVA1210 连续素数之和
• UVa: 1210 - Sum of Consecutive Prime Numbers

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2 + 3 + 5 + 7 + 11 + 13, 11 + 13 + 17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given positive integer.

Interpretation

有些正整数可以用一个或多个连续质数的和来表示。一个给定的正整数有多少个这样的表示形式？例如，整数 53 有两个表示形式：5 + 7 + 11 + 13 + 17 和 53。整数 41 有三个表示 2 + 3 + 5 + 7 + 11 + 13、11 + 13 + 17 和 41。整数 3 只有一个表示，即 3。整数 20 没有这样的表示。请注意，和必须是连续的质数，因此 7 + 13 和 3 + 5 + 5 + 7 都不是整数 20 的有效表示形式。求方案数。

简述：有一些正整数能够表示为一个或连续多个素数的和。那么给定一些正整数，求有多少种这样的表示。

Solution

预处理出数据范围内的所有素数，再进行枚举即可。

code

Search with O(\frac{n^2}{2})

#include <bits/stdc++.h>
#define maxn 31767
using namespace std;
namespace A_prime {
    int n;
    int prime[maxn + 5], now;
    bool vis[maxn + 5];
    void get_prime() {
        for (int i = 2; i <= maxn + 1; i++) {
            if (!vis[i]) prime[++now] = i;
            for (int j = 1; j <= now && prime[j] * i <= maxn + 1; j++) {
                vis[prime[j] * i] = 1;
                if (i % prime[j] == 0) break;
            }
        }
    }
    void solve() {
        ios::sync_with_stdio();
        cin.tie(0);
        get_prime();
        while (cin >> n) {
            if (n == 0) return ;
            int cnt = 0;
            for (int i = 1; i <= now; i++) {
                int t = prime[i];
                if (t == n) {
                    cnt++;
                    break;
                }
                for (int j = i + 1; j <= now; j++) {
                    t += prime[j];
                    if (t < n) continue;
                    if (t > n) break;
                    cnt++;
                    break;
                }
            }
            cout << cnt << '\n';
        }
    }
}
int main() {
    A_prime::solve();
    return 0;
}

Preprocessing and search with O(1) (by @No0Chenquanlin %%%)

#include <bits/stdc++.h>
#define N 32780
using namespace std;
long long prm[N], tot;
bool vis[N];
void solve() {
    for (int i = 2; i <= 32767; i++) {
        if (!vis[i])
            prm[++tot] = i;
        for (int j = 1; j <= tot; j++)
            if (i * prm[j] <= 32767)
                vis[i * prm[j]] = true;
    }
}
long long sum[N];
long long mp[N];
int main() {
    solve();
    for (int i = 1; i <= tot; i++)
        sum[i] = sum[i - 1] + prm[i];
    for (int i = 1; i <= tot; i++)
        for (int j = i; j <= tot; j++)
            if (sum[j] - sum[i - 1] <= 32767)
                mp[sum[j] - sum[i - 1]]++;
    int x;
    while (scanf("%d", &x) && x) 
        printf("%d\n", mp[x]);
    return 0;
}

T2 晨练

Link

gxyzoj: #3599 晨练
Luogu: P1353 [USACO08JAN] Running S

Description

小 Y 打算通过锻炼来培养自己的运动细胞，他选择的运动方式是每天进行 N 分钟 (1 \le N \le 10000)。

在每分钟的开始，小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地，如果小 Y 选择在第 i 分钟内跑步，他可以在这一分钟内跑 (1 \le D_i \le 1000) 米，并且他的疲劳度会增加 1。不过，无论何时小 Y 的疲劳度都不能超过 M(1<=M<=500)。如果小 Y 选择休息，那么他的疲劳度就会每分钟减少 1，但他必须休息到疲劳度恢复到 0 为止。在疲劳度为 0 时休息的话，疲劳度不会再变动。晨跑开始时，小 Y 的疲劳度为 0。还有，在 N 分钟的锻炼结束时，小 Y 的疲劳度也必须恢复到 0，否则他将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下，小 Y 最多能跑多少米。

Solution

30 pts

暴力枚举哪天跑或者直接休息。

code

没有。

100 pts

设 f_{i, j} 表示到第i天疲劳度为j的最优解。

转移方程如下：

code

#include <bits/stdc++.h>
#define N 10000
#define M 500 //6
#define int long long
using namespace std;
namespace No0bxy_zx {
    int n, m, a[N + 5];
    int dp[N * 2 + 5][M + 5];
    void solve() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        dp[1][1] = a[1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= min(i, m); j++) {
                if (j == 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]); //一直休息
                else dp[i + j][0] = max(dp[i + j][0], dp[i][j]); //从i天开始休息
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[i + 1]); //不休息
            }
        }
        cout << dp[n][0] << '\n';
    }
}
signed main() {
    No0bxy_zx::solve();
    return 0;
}

T3 奇怪的桌子

Link

gxyzoj: #3600 奇怪的桌子

Description

小 H 有一张奇怪的矩形桌子，他能在桌子上的格子内画点，一个格子最多只能画一个点。这个桌子是 N \times M 的，现在小 H 想知道有多少种不同的放法能使得桌子上每个 N \times N 的正方形内恰好有 K(0 \le K \le N^2) 个点。

小 H 智商有限，所以他希望你能帮他解决这个问题。因为方案数可能有很多，所以你只需要输出方案数除以 1000000007 (10^9 + 7) 的余数。

Solution

10 pts

暴力枚举哪些位置放。

code

没有。

20 pts

另外 20\%：n = m，所以答案即为 C_{n \times m}^k。

神奇的小现象：由于数据中存在恰好 ans = C_{n^2}^k 的测试点，所以输出 C_{n^2}^k 会获得 10 \sim 40 pts 不等的得分（大概是 40 pts）。

code by @dingzibo_______

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef long long LL;
const int Maxn = 2e5 + 5;
const int Mod = 1e9 + 7;

int n, m, k;

struct pian1 {
    int ans = 0;
    int a[15][15];
    bool check() {
        for(int x = 1; x <= m - n + 1; x++) {
            int cnt = 0;
            for(int i = 1; i <= n; i++) {
                for(int j = x; j <= x + n - 1; j++) {
                    cnt += a[i][j];
                }
            }
            if(cnt != k) return 0;
        }
        return 1;
    }
    void Dfs(int x, int y) {
        if(x == n && y == m) {
            if(check()) {
                ans = (ans + 1) % Mod;
            }
            return ;
        }
        if(y == m) {
            a[x + 1][1] = 0, Dfs(x + 1, 1);
            a[x + 1][1] = 1, Dfs(x + 1, 1);
            a[x + 1][1] = 0;
        }
        else {
            a[x][y + 1] = 0, Dfs(x, y + 1);
            a[x][y + 1] = 1, Dfs(x, y + 1);
            a[x][y + 1] = 0;
        }
    }
}p1;

struct pian2 {
    int f[Maxn], g[Maxn];
    int qpow(int a, int b) {
        int res = 1;
        while(b) {
            if(b & 1) {
                res = (res * a) % Mod;
            }
            a = (a * a) % Mod;
            b >>= 1;
        } 
        return res;
    }
    void init() {
        f[0] = g[0] = 1;
        for(int i = 1; i < Maxn; i++) {
            f[i] = (f[i - 1] * i) % Mod;
            g[i] = (g[i - 1] * qpow(i, Mod - 2)) % Mod;
        }
    }
    int getc(int n, int m) {
        if(n < m) return 0;
        return f[n] * g[n - m] % Mod * g[m] % Mod;
    }
}p2; 

signed main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    if(n == m) {
        p2.init();
        cout << p2.getc(n * m, k);
    }
    else{
        p1.Dfs(1, 0);
        cout << p1.ans;
    }
    return 0;
}

100 pts

对于第 i 列，可以发现所有 i\%n 为相同值的，放的个数一定是相同的。