A题题解

A题

A题描述

Eddy was a contestant participating in ACM ICPC contests. ACM is short for Algorithm, Coding, Math. Since in the ACM contest, the most important knowledge is about algorithm, followed by coding(implementation ability), then math. However, in the ACM ICPC World Finals 2018, Eddy failed to solve a physics equation, which pushed him away from a potential medal.

Since then on, Eddy found that physics is actually the most important thing in the contest. Thus, he wants to form a team to guide the following contestants to conquer the PACM contests(PACM is short for Physics, Algorithm, Coding, Math).

There are N candidate groups each composed of pi physics experts, ai algorithm experts, ci coding experts, mi math experts. For each group, Eddy can either invite all of them or none of them. If i-th team is invited, they will bring gi knowledge points which is calculated by Eddy’s magic formula. Eddy believes that the higher the total knowledge points is, the better a team could place in a contest. But, Eddy doesn’t want too many experts in the same area in the invited groups. Thus, the number of invited physics experts should not exceed P, and A for algorithm experts, C for coding experts, M for math experts.

Eddy is still busy in studying Physics. You come to help him to figure out which groups should be invited such that they doesn’t exceed the constraint and will bring the most knowledge points in total.

A输入描述

The first line contains a positive integer N indicating the number of candidate groups.

Each of following N lines contains five space-separated integer pi, ai, ci, mi, gi indicating that i-th team consists of pi physics experts, ai algorithm experts, ci coding experts, mi math experts, and will bring gi knowledge points.

The last line contains four space-separated integer P, A, C, M indicating the maximum possible number of physics experts, algorithm experts, coding experts, and math experts, respectively.

1 ≤ N ≤ 36
0 ≤ pi,ai,ci,mi,gi ≤ 36
0 ≤ P, A, C, M ≤ 36

A输出描述

The first line should contain a non-negative integer K indicating the number of invited groups.
The second line should contain K space-separated integer indicating the index of invited groups(groups are indexed from 0).

You can output index in any order as long as each index appears at most once. If there are multiple way to reach the most total knowledge points, you can output any one of them. If none of the groups will be invited, you could either output one line or output a blank line in the second line.

A输入1

A输出1

1
2

1
1

A输入2

1
2
3

1
2 1 1 0 31
1 0 2 1

A输出3

A题分析

AC代码A

#include <iostream>
using namespace std;
int dp[37][37][37][37];
bool ch[37][37][37][37][37];
int p[37], a[37], c[37], m[37], g[37];
bool path[37];
int main()
{
    int N, P, A, C, M;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d%d%d%d%d", p + i, a + i, c + i, m + i, g + i);
    scanf("%d%d%d%d", &P, &A, &C, &M);
    for (int i = 0; i < N; i++)
        for (int pi = P; pi >= p[i]; pi--)
            for (int ai = A; ai >= a[i]; ai--)
                for (int ci = C; ci >= c[i]; ci--)
                    for (int mi = M; mi >= m[i]; mi--)
                        if (dp[pi][ai][ci][mi] < dp[pi - p[i]][ai - a[i]][ci - c[i]][mi - m[i]] + g[i])
                        {
                            dp[pi][ai][ci][mi] = dp[pi - p[i]][ai - a[i]][ci - c[i]][mi - m[i]] + g[i];
                            ch[i][pi][ai][ci][mi] = true;
                        }
    int ans = 0;
    for (int i = N - 1; i >= 0; i--)
        if (ch[i][P][A][C][M])
        {
            path[i] = true;
            ans++;
            P -= p[i];
            A -= a[i];
            C -= c[i];
            M -= m[i];
        }
    printf("%d\n", ans);
    for (int i = 0; i < N; i++)
    {
        if (path[i])
            printf("%d\n", i);
    }
    return 0;
}

H题题解

H题

H题描述

Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem. diff-prime pairs problem is that given N, you need to find the number of pairs (i, j), where and are both prime and i ,j ≤ N. gcd(i, j) is the greatest common divisor of i and j. Prime is an integer greater than 1 and has only 2 positive divisors.

Eddy tried to solve it with inclusion-exclusion method but failed. Please help Eddy to solve this problem.

Note that pair (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.

H输入描述

Input has only one line containing a positive integer N.

1 ≤ N ≤ 1e7

H输出描述

Output one line containing a non-negative integer indicating the number of diff-prime pairs (i,j) where i, j ≤ N

H输入1

H输出1

H输入2

H输出2

H题分析

先找出区间[1,n]中的所有素数的个数ans,并标记
总数 = ans * (ans - 1);每一个素数与其他的素数两两配对
找出符合条件素数对的倍数

AC代码H

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000000 + 5;
bool prime[maxn];
int sum[maxn];

int main()
{
    int n;
    scanf("%d", &n);

    memset(prime, 1, sizeof prime);
    prime[1] = 0;
    for (int i = 2; i <= n; i++)
        if (prime[i])
            for (int j = 2; j * i <= n; j++)
                prime[j * i] = 0;

    long long ans = 0;

    for (int i = 2; i <= n; i++)
        if (prime[i])
            ans++, sum[i] = ans;

    ans = ans * (ans - 1);

    for (int i = n; i >= 3; i--)
    {
        if (prime[i])
        {
            int t = n / i;
            t--;
            sum[i]--;
            ans += (2 * t * sum[i]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}