当前位置：首页 > news >正文

AcWing 第71场周赛

news 来源：原创 2024/5/2 16:22:26

4621. 三个整数

题目
提交记录
讨论
题解
视频讲解

给定四个整数 a,b,c,d

，保证 a≤b≤c≤d

。

请你找到三个整数 x,y,z

，使得它们满足：

a≤x≤b

b≤y≤c
c≤z≤d
x+y>z

输入格式

共一行，四个整数 a,b,c,d

。

输出格式

共一行，三个整数 x,y,z

。

保证一定有解。

如果方案不唯一，则输出任意合理方案均可。

数据范围

所有测试点满足 1≤a≤b≤c≤d≤100

。

输入样例1：

1 3 5 7

输出样例1：

3 4 5

输入样例2：

1 5 5 7

输出样例2：

5 5 5

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int x,y,z;
    x=b,y=c,z=c;
    cout << x << ' ' << y << ' ' << z << endl;
    return 0;
}

4622. 整数拆分

题目
提交记录
讨论
题解
视频讲解

我们规定 f(x)

（x≥2）表示整数 x

的除本身之外的最大因数。

例如，f(6)=3

，f(25)=5，f(2)=1

。

现在，给定一个整数 n

，请你将其拆分为 k 份 n1,n2,…,nk（也可以不拆分，即 k=1

），要求：

n1+n2+…+nk=n

对于 1≤i≤k
，ni≥2
始终成立。
f(n1)+f(n2)+…+f(nk)

的值应尽可能小。

输出 f(n1)+f(n2)+…+f(nk)

的最小可能值。

输入格式

一个整数 n

。

输出格式

一个整数，表示 f(n1)+f(n2)+…+f(nk)

的最小可能值。

数据范围

前 4

个测试点满足 2≤n≤30。
所有测试点满足 2≤n≤2×109

。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

  * 关于偶数得哥德巴赫猜想：任何一个大于一个 2 得偶数都可以写为两个素数之和；
*
* 那么根据题目的意思：
* 如果n是素数，那么答案是1；
* 如果n是大于2的偶数，那么答案是2；
* 如果n是奇数，
*      且 n-2 是素数，那么答案是 2 (n == (n-2) + 2)；
*      如果 n-2 不是素数，那么答案是3 (n == (n-3) + 3);n-3是偶数

/**
 * 关于偶数得哥德巴赫猜想：任何一个大于一个 2 得偶数都可以写为两个素数之和；
 * 
 * 那么根据题目的意思：
 * 如果n是素数，那么答案是1；
 * 如果n是大于2的偶数，那么答案是2；
 * 如果n是奇数，
 *      且 n-2 是素数，那么答案是 2 (n == (n-2) + 2)；
 *      如果 n-2 不是素数，那么答案是3 (n == (n-3) + 3);n-3是偶数
*/


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool is_primer(int x)
{
    for(int i=2;i*i <= x;++i)
        if(x%i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;
    
    if(is_primer(n))
        puts("1");
    else if(n%2 == 0 || is_primer(n-2))
        puts("2");
    else
        puts("3");
    
    return 0;
}

4623. 买糖果

题目
提交记录
讨论
题解
视频讲解

个糖果店，围成一圈。

店铺按顺时针顺序从 1

到 n 编号，n 号店铺与 1

号店铺相邻。

第 i

号店铺的单个糖果售价为 ai

元。

李华拿着 T

元钱去购买糖果，具体购买过程如下：

初始时，他位于 1

号店铺。
如果他现有的钱足够在当前店铺购买一个糖果，他就会立即购买一个糖果，否则他将不会在当前店铺购买糖果。随后，不论他是否在当前店铺购买糖果，他都会按顺时针顺序前往下一个店铺。
他将不断重复过程 2

，直到剩余的钱在所有店铺都买不起糖果为止。

请问，最终李华一共购买到多少个糖果。

输入格式

第一行包含两个整数 n,T

。

第二行包含 n

个整数 a1,a2,…,an

。

输出格式

一个整数，表示一共购买到的糖果数量。

数据范围

前 6

个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×105，1≤T≤1018，1≤ai≤109

。

输入样例1：

3 38
5 2 5

输出样例1：

输入样例2：

5 21
2 4 100 2 6

输出样例2：

* 枚举一圈内所有可以从前到后顺序购买的糖果的总价格以及糖果的数量；如果当前这颗
* 糖果我们买不起，那么我们下一轮回来的时候照样买不起；一轮结束以后，用剩下的钱
* t 除以 sum，得到我们可以转 ans 圈，且这ans圈买的糖果总类是相同的；再用剩余的钱
* 减去买ans圈糖果所需的钱；如此循环下去，直到我们转一圈，一颗糖果都买不起的时候，
* 循环结束；

/**
 * 枚举一圈内所有可以从前到后顺序购买的糖果的总价格以及糖果的数量；如果当前这颗
 * 糖果我们买不起，那么我们下一轮回来的时候照样买不起；一轮结束以后，用剩下的钱
 * t 除以 sum，得到我们可以转 ans 圈，且这ans圈买的糖果总类是相同的；再用剩余的钱
 * 减去买ans圈糖果所需的钱；如此循环下去，直到我们转一圈，一颗糖果都买不起的时候，
 * 循环结束；
*/

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 2e5+10;
int a[maxn];

int main()
{
    int n;
    LL t; //t 要定义为 long long 
    scanf("%d%lld",&n,&t);
    
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    
    LL res = 0; //res 也要定义为 long long
    while(1)
    {
        LL sum = 0;
        int cnt = 0;
        for(int i=1;i<=n;++i)
            if(sum + a[i] <= t)
            {
                sum += a[i];
                ++cnt;
            }
            
        if(!sum) //转了一圈，但是一颗糖果都买不起，退出循环
            break;
            
        LL ans = t/sum; //能买得起的圈数,ans也需要定于成 long long
        res += ans*cnt; 
        t %= sum;
    }
    
    printf("%lld\n",res);
    return 0;
}