2022寒假集训1 A题（动态规划），H题，C题（模拟），D题（数论），F题

2022寒假集训1 A题（动态规划），H题，C题（模拟），D题（数论），F题 前言

要学习的思路：A（dp方案数计算）、H（从a的数字入手）；

要记住的结论：A（%9的结论）、D（欧拉数个数+素数）；

普通的警醒：C，F；

A题 

​​​​​​​​九小时九个人九扇门

【记录一下自己的错误】：

1. 结论是：数字的所有位加一起，最后的结论是这个数字%9；

大概是因为数字x的所有数加在一起如果等于9的话就刚好%9==0，那么x-1加在一起就等于8，也刚好%9==8……

2.思路是dp【第几个人】【能开的门的编号】；

        2.1把 第i-1个人（已经包括i-1个人之前的了） 开1~9门的 方案数都接到 第i个人这里；

        2.2因为第i个人的加入，开第(a[i]%9)门的方案数增加了一个；

        2.3灵活使用第i人，看看能不能去开其他门；

        【注意是前一个状态量的方案数加到当前状态量的方案数】 

        【不

要像2.2一样额外加1！！！！！！！！】（问为什么的话自己掰手指算一下！！！）

 d[i][(j+a[i])%9]=(d[i][(j+a[i])%9]+d[i-1][j])%mod;

3.最后注意9%9==0，所以开第九扇门的方案数是在dp【n】【0】里面的；

【当然也可以普通地（a[i]-1）%9+1，这样的话mod取值就是1~9了】

A题代码：（2.3代码前面的if-continue其实是不需要的。。。）

#include 
using namespace std;
long long d[100005][10]={0};
long long a[100005];
const int mod=998244353;
int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){  
        for(int j=0;j<=8;j++)d[i][j]=d[i-1][j];
        d[i][a[i]%9]=(d[i][a[i]%9]+1)%mod;
        for(int j=0;j<=8;j++){
            if(!d[i-1][j])continue;
            d[i][(j+a[i])%9]=(d[i][(j+a[i])%9]+d[i-1][j])%mod;
        }
    }
         for(int j=1;j<=8;j++){cout< 

H题 
牛牛看云
 
n(3≤n≤10E6)，​​​​​​​​(0≤​​​​​​​​≤1000)
 
单纯记录一下自己的代码和同学的代码（2种方法）；
 
我的代码：
 
        缺点：时间复杂度高，debug时间对我来说太长了（这也太数学了orz……）；
 
        优点：如果a是10E9的话大概也能跑；
 
#include 
using namespace std;
inline int read(){//快读
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
long long s=0;
int a[1000004];
int sum[1000004];
int main() {
  int n;n=read();
    for(int i=1;i<=n;i++){a[i]=read();}//读入
    sort(a+1,a+1+n);//从小到大排序
    for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}//前缀和
    s=0;//求和初始化
    for(int i=1;i<=n;i++){   
        s+=abs(2*a[i]-1000);//先加上自己
        int j=lower_bound(a+i+1,a+n+1,1000-a[i])-a;//找到绝对值由递增转向递减的地方
         s+=(1000)*(j-i-1)-a[i]*(j-1-i)-(sum[j-1]-sum[i])-1000*(n-j+1)+a[i]*(n-j+1)+(sum[n]-sum[j-1]);
    }
//通过数学公式求整个区间段的和
    cout< 
 
同学的代码：
 
根据小于等于1000的范围，计算​​​​​​​重复的个数，然后加上每个搭配组合之后的值；
 
#include
using namespace std;
int main(){
    long long ans=0,n;
    long long cnt[1005]={0};
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        cnt[a]++;
    }
    for(long long i=0;i<=1000;i++)
        for(long long j=i;j<=1000;j++){
            if(i==j)ans+=(abs(i+j-1000))*(cnt[i]+1)*cnt[i]/2;
            //因为自己也要计算一次，所以是(cnt[i]+1)*cnt[i]/2
            else ans+=(abs(i+j-1000))*(cnt[i]*cnt[j]);
        }
    cout<
 

C题（简单模拟） 
Baby's first attempt on CPU
 不应该因为  标题是英文+题目太长  就不去做的orz
 
#include
using namespace std;
int a[105];int b[105];int c[105];int l[105];
int main()
{
    int n;int s=0;
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];}
    for(int i=1;i<=n;i++){
        if(a[i]==1){l[i]=3;}
        if(b[i]==1){if(l[i]+l[i-1]<2){l[i]=2-l[i-1];}}
        if(c[i]==1){if(l[i]+l[i-1]+l[i-2]<1){l[i]=1;} }
    }
    for(int i=1;i<=n;i++){s+=l[i];}
    cout< 

D题（欧拉数知识点） 
欧拉数： 是满足且gcd(x,y)=1的y的个数；
 
也就是说，质数的欧拉数个数 是 质数自己-1，而合数的因数个数越多，欧拉数越少
 
同时又因为唯一分解定理：
 
任何一个大于1的整数n都可以分解成若干个素因数的连乘积，如果不计各个素因数的顺序，那么这种分解是惟一的，即若n>1，则有上图公式；
 
 因此 找小于且离n最近的欧拉数最少的合数 就是把 质数都乘起来；
 
代码部分：
 
筛素数——埃氏筛法O(nlog(logn))、欧拉筛O(n)、Miller-Rabin素性检验算法(不会)
 
【而且这道题前两个筛法都不用写，检验是否为素数用普通的根号内的检验就可以了orz】
 
#include
using  namespace std;
bool j(int n){
    if(n==2)return 0;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return 1;
    }
    return 0;
}
int prime[] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23,29};
int main()
{
    int T;cin>>T;
    while(T--){
       int a,sum=1,i;
        cin>>a;if(a==1){cout<<-1<<'n';continue;}
        for(i=1;(long long)sum*prime[i]<=a;i++)sum*=prime[i];//找到了拥有欧拉数最少的那个数
        while(j(a))a--;cout< 
F题（普通模拟） 
#include 
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int a[100004];
int main() {
    int T;T=read();
    while(T--){
        int ans=0;
        int n,m;n=read();m=read();int dd=0,xx=0,cnt1=0,cnt2=0;
        for(int i=0;i=m)dd++;else xx++;
        }
        if(dd<=xx){cout<<-1< 
 
					
										


					

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