2022牛客寒假算法基础集训营

2022牛客寒假算法基础集训营

2022牛客寒假算法基础集训营1

A 九小时九个人九扇门

题目大意解法/思路代码 B 炸鸡块君与FIFA22C Baby's first attempt on CPUD 牛牛做数论

题目大意解法/思路

A 九小时九个人九扇门

题目链接

题目大意

给你n个数，你可以选择任意个数相加求数字根（将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于10为止）。问你最后组成1~9的方案数。

解法/思路

首先一个数的数字根就是对这个数取余9的结果(结果为0时，数字根为9).
证明：一个数的数字根就是这个数取余9

设数x=abcd(a,b,c,d分别为千,百,十,个位上的数)
则	x=a*1000+b*100+c*10+d
		x%9=(a*1000+b*100+c*10+d)%9
		x%9=a%9+b%9+c%9+d%9
		x%9=(a+b+c+d)%9
又因为a+b+c+d就是数x的数字根。
则说明取余9不影响数的数字根
例如14和5同余9.就说明14和5的数字根相同。又因为小于10的数的数字根为本身
则一个数的数字根即为这个数对9取余(结果为0的时候,数字根为9).

使用的算法：简单dp，类似于01背包的变形，求方案数。
定义状态：f(i,j)代表前i个数组成数字根为j的方案数
状态转移方程：

f(i,(j+a[i])%9)+=f(i-1,j)
f(i,j)+=f(i-1,j)
f(i,a[i])+=1

代码

#include 
using namespace std;
#define int long long
const int N=1e5+10;
const int p=998244353;
int a[N];
int dp[N][20];//dp[i][j]表示前i个数根为j的个数
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]%=9;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=9;j++)
        {
            dp[i][(j+a[i])%9]=(dp[i][(j+a[i])%9]+dp[i-1][j])%p;
        }
        for(int j=0;j<=9;j++)
        {
            dp[i][j]=(dp[i][j]+dp[i-1][j])%p;
        }
        dp[i][a[i]]++;
    }
    for(int i=1;i<=9;i++)
    {
        cout< 
B 炸鸡块君与FIFA22 
还不会…
 
C Baby’s first attempt on CPU 
还没补题…
 
D 牛牛做数论 
题目链接
 
题目大意 
定义H(x)=φ(x)/x
其中φ(x)就是欧拉函数
给你一个数n，让你求
1.2~n中H(x)取最小值的时候，x的值(如果有多个取最小的x)
2.2~n中H(x)取最大值的时候，x的值(如果有多个取最大的x)
 
解法/思路 
首先需要知道的是欧拉函数就是对于一个正整数n，小于n且和n互质的正整数(包括1)的个数，记作φ(n).
 欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)
 其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
 
 
则H(n)=(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)
H(n)=((p1-1)/p1)((p2-1)/p2).....
其中p1, p2……pn为n的所有质因数，n是不为0的整数。
 
因为H(2)=1/2 H(3)=2/3 H(5)=4/5…H(x)=(x-1)/x 这里的x为质数
 所以x是越大的质数则说明H(x)的值越大。
 可以很容易发现H(x)的最大值就是x取小于等于n的最大质数。
 证明：
 
假设H(x)的最大值不是x取小于等于n的最大质数p
则当p 
结论
 最小的值就是前面尽可能多的质数相乘
 最大的值就是小于等于n的最大质数
 
#include 
using namespace std;
#define int long long
const int N=1e5+10;
int a[30]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73};
int x[30];
void init()
{
    int s=1,n=20;
    for(int i=1;i<=15;i++)
    {
        s*=a[i];
        x[i]=s;
    }
}
bool prime(int x)
{
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return 0;
    }
    return 1;
}
signed main()
{
    init();
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if(n==1) {cout<<-1<=1;i--)
        {
            if(x[i]<=n)
            {
                cout<=1;i--)
        {
            if(prime(i))
            {
                cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714026.html