头像

名叫邱的女孩

小学五年级




离线:10小时前



请问:
我在CSP-J复赛中考好一点,应该学习哪些课程,做哪些题?(AcWing上面的)



活动打卡代码 AcWing 867. 分解质因数

#include <iostream>
#include <cstdio>

using namespace std;

void f(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            int s=0;
            while(x%i==0) x/=i,s++;
            printf("%d %d\n",i,s);
        }

    }
    if(x>1) printf("%d 1\n",x);
}

int main()
{
    int n;

    scanf("%d",&n);

    while(n--)
    {
        int x;
        scanf("%d",&x);

        f(x);

        printf("\n");
    }

    return 0;
}



#include <iostream>
#include <cstdio>

using namespace std;

bool f(int x)
{
    if(x==1) return false; 

    for(int i=2;i<=x/i;i++)
        if(x%i==0) return false;
    return true;
}

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

    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);

        if(f(x)) printf("Yes\n");
        else printf("No\n");
    }
}



题目描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 v[i,j],价值是 w[i,j],其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

每组数据第一行有一个整数 S[i],表示第 i 个物品组的物品数量;
每组数据接下来有 S[i] 行,每行有两个整数 v[i,j],w[i,j],用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<v[i,j],w[i,j]≤100

样例

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例:
8

解析

  • 这道题和01背包差不多

  • 对于每组s个物品,有s+1种选法:f[j]=max(f[j],f[j-v[0]]+w[0],f[j-v[1]]+w[1],…,f[j-v[s]]+w[s])就是说可以不选(选0个),选1个,选2个…选s个

  • 所以,我们先循环枚举所有体积,再循环枚举所有选择,最后得出状态转移方程:f[j]=max(f[j],f[j-v[k]]+w[k]),其中k是枚举所有选择中的循环变量


C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int v[105],w[105],f[105];

int main()
{
    int n,m; //输入物品组数与背包容量

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        int s;
        scanf("%d",&s); //输入第i个物品组的物品数量

        for(int j=1;j<=s;j++) scanf("%d%d",&v[j],&w[j]); //输入每个物品的体积和价值

        //接下来是处理过程

        for(int j=m+1;j>=1;j--) //枚举所有体积
            for(int k=1;k<=s;k++) //枚举所有选择
                if(j>=v[k]) //必须要满足,否则下面的下标减出来是负数
                    f[j]=max(f[j]/*不选*/,f[j-v[k]]+w[k]/*选*/);
    }
    printf("%d",f[m]);

    return 0;
}

如果觉得我的题解写得还不错的话,就点个赞吧



活动打卡代码 AcWing 9. 分组背包问题

#include <iostream>
#include <cstdio>

using namespace std;

int v[105],w[105],f[105];

int main()
{
    int n,m; //输入物品组数与背包容量

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        int s;
        scanf("%d",&s); //输入第i个物品组的物品数量

        for(int j=1;j<=s;j++) scanf("%d%d",&v[j],&w[j]); //输入每个物品的数量

        //接下来是处理过程

        for(int j=m+1;j>=1;j--) //枚举所有体积
            for(int k=1;k<=s;k++) //枚举所有选择
                if(j>=v[k]) //必须要满足,否则下面的下标减出来是负数
                    f[j]=max(f[j]/*不选*/,f[j-v[k]]+w[k]/*选*/);
    }
    printf("%d",f[m]);

    return 0;
}



题目描述

一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动。

他要从网格的左上角进,右下角出。

每穿越中间1个小方格,都要花费1个单位时间。

商人必须在(2N-1)个单位时间穿越出去。

而在经过中间的每个小方格时,都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。

请问至少需要多少费用?

注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。

输入格式
第一行是一个整数,表示正方形的宽度N。

后面N行,每行N个不大于100的整数,为网格上每个小方格的费用。

输出格式
输出一个整数,表示至少需要的费用。

数据范围
1≤N≤100

样例

输入样例:
5
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33
输出样例:
109
样例解释
样例中,最小值为109=1+2+5+7+9+12+19+21+33。

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int a[110][110],f[110][110]; //a表示原数组,b表示答案数组

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

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);

    f[1][1]=a[1][1]; //别忘了初始化,第1个格子的费用就是本身

    int ans=0;

    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++)
            f[i][j]=1000000001; //把除第一个点以外的每个点设为无穷大

    for(int i=2;i<=n;i++) f[1][i]=1000000001;

    for(int j=2;j<=n;j++) f[j][1]=1000000001;

    for(int j=0;j<=n;j++) f[0][j]=1000000001;

    for(int i=0;i<=n;i++) f[i][0]=1000000001;

    for(int j=0;j<=n+1;j++) f[n+1][j]=1000000001;

    for(int i=0;i<=n+1;i++) f[i][n+1]=1000000001;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1 && j==1 ) continue;

            int minn1=min(f[i][j+1],f[i][j-1]);
            int minn2=min(f[i-1][j],f[i+1][j]);

            f[i][j]=min(minn1,minn2)+a[i][j];
        }
    }

    printf("%d",f[n][n]);

    return 0;

}


新鲜事 原文

2020年的CSP题目什么时候出来


新鲜事 原文

普及组CSP-J2020题目:(网址) file:///C:/Users/Administrator/Documents/Tencent%20Files/515441863/FileRecv/CSP-J2.pdf


题目讨论 AcWing 5. 重名了

  • 这道题的两个V好像重名了



题目描述

小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。

问小明有多少种买书方案?(每种书可购买多本)

输入格式
一个整数 n,代表总共钱数。

输出格式
一个整数,代表选择方案种数。

数据范围
0≤n≤1000

样例

输入样例1:
20
输出样例1:
2
输入样例2:
15
输出样例2:
0
输入样例3:
0
输出样例3:
1

解析

本来很恐惧这道题结果5分钟就写完了~
此题是一个完全背包问题,言简意赅,题意容易理解
为什么是完全背包呢?因为每本书有多个,题目说的很清楚
* 可以把总钱数n看成背包的容积,每本书的价钱看成每个物体的价值

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

int v[5],f[1010];

int main()
{
    v[1]=10;
    v[2]=20;
    v[3]=50;
    v[4]=100;

    int n;
    scanf("%d",&n); //输入总钱数

    f[0]=1;

    for(int i=1;i<=4;i++)
    {
        for(int j=v[i];j<=n;j++)
            f[j]+=f[j-v[i]];
    }

    printf("%d",f[n]);

    return 0;
}