头像

噩梦齋纂




离线:14天前


最近来访(29)
用户头像
夜寐
用户头像
宋老虎
用户头像
侦察连王有胜
用户头像
学到世界末日那天
用户头像
yxc
用户头像
sdsds001
用户头像
风沙
用户头像
龙城柳月
用户头像
不开心
用户头像
石洛飞
用户头像
王小王
用户头像
KuiHunter
用户头像
年少纵马且长歌
用户头像
看不到我
用户头像
Apocalypse_3
用户头像
杨大鑫_ωノ
用户头像
一条秋刀鱼.

新鲜事 原文

噩梦齋纂
3个月前
AcWing《暑假每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/1934/group_buy/71978/, 6.18-6.20限时狂欢,全场6折起!


活动打卡代码 AcWing 3417. 砝码称重

噩梦齋纂
5个月前
统计最小的数量和最大的数量,统计能够构成的所有数量,然后进行输出
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110,M=2000010,B=M/2;
bool f[N][M];
int w[N];
int n,m;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]),m+=w[i];//统计砝码重量的总个数

    f[0][B]=true;//第一个肯定是能够构成的
    for(int i=1;i<=n;i++)
    for(int j=-m;j<=m;j++)
    {
        f[i][j+B]=f[i-1][j+B];
        if(j-w[i]>=-m)f[i][j+B]|=f[i-1][j-w[i]+B];
        if(j+w[i]<=m)f[i][j+B]|=f[i-1][j+w[i]+B];
    }
    int res;
    for(int j=1;j<=m;j++)
     if(f[n][j+B])res++;
     printf("%d",res);
     return 0;
}



活动打卡代码 AcWing 3416. 时间显示

噩梦齋纂
5个月前
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
LL n;
int main(){
    scanf("%lld",&n);
    n=n/1000;//毫秒化成秒
    n=n%86400;//除去所有的够一天的天数
    int h=n/3600;//整除后的就是小时的
    n=n%3600;//除去小时候剩下的
    int m=n/60;//整除60的是分钟
    int s=n%60;//除以60后剩下的
    printf("%02d:%02d:%02d",h,m,s);//格式化输出
    return 0;
}


活动打卡代码 AcWing 1296. 聪明的燕姿

噩梦齋纂
5个月前
算术基本定理

N = P1^a1 * P2^a2 * … * Pn^an
则N的约数个数为(a1+1)(a2+1)…(an+1)

假设N的一个约数为D

D = P1^b1 * P2^b2 * … * Pn^bn
其中bi可以取到0,范围是0<= bi <= ai

因为只有和N的质因数一一对应一定能得到约数
因为bi可以从0取到ai,那么每一个bi就有(ai+1)种选法

约数的个数就是每个bi对应多少种选法相乘
即约数个数就为(a1+1)(a2+1)…(an+1)

约数之和S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个怎么理解呢

因为每一个约数为D = P1^b1 * P2^b2 * … * Pn^bn

那么S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

这个公式的意思就是从每个括号里面取出来一个数然后相乘,就能得到一个约数Di
然后所有的约数Di相加就得到约数之和S

举个例子
对于S = 42来说,42对应的结果里面有一个为20,20 = (1 + 2 + 4 + 5 + 10 + 20)
20 = 2^2*5
对于两个质因数2和5来说
2可以取0,1,2次,5可以取0,1次
所以S = (1+2+2^2)(1+5) = 42

继续分析
所以我们最暴力的想法一定就是枚举了,比如对一个数S
枚举从1到S-1的所有数的约数,再判断他们的约数和是否等于S

但是这么做显然会超时,因为1 <= S <= 2*10^9

这个时候我们就可以观察我们的约数和的公式
S = (1+p1+p1^2+…+p1^a1)(1+p2+p2^2+…+p2^a2)…(1+pn+pn^2+…+pn^an)

假设这个时候有一个约数和S满足(1+2)(1+2+2^2)(1+2+2^2+…+2^k)
3x5x9x17x33x65x129 = 635037975 就已经接近1e9的量级了,可见符合条件的项不会很多

那么这个时候我们就可以用dfs进行搜索,看我们能不能得到符合条件的(1+pk+pk^2+…+pk^ak)能够使得
S能够整除,即S % (1+pk+pk^2+…+pk^ak) == 0
然后S /= (1+pk+pk^2+…+pk^ak),再dfs到下一层

应该先从小到大枚举P

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=50000;
int primes[N];
int cnt;
bool st[N];
int ans[N],len;
void get_prime(int n){
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
bool is_prime(int n){
    if(n<N)return !st[n];
    for(int i=0;primes[i]<=n/primes[i];i++)
    if(n%primes[i]==0)return false;
    return true;
}
void dfs(int last,int prod,int s){//枚举的上一个质数last,当前的数prod,
//s除去前面的所有因子后剩下的数
    if(s==1){
        ans[len++]=prod;
        return ;//递归的出口
    }
    if((s-1>(last<0?1:primes[last]))&&is_prime(s-1))
        ans[len++]=prod*(s-1);

    for(int i=last+1;primes[i]<=s/primes[i];i++)
    {
        int p=primes[i];
        for(int j=1+p,t=p;j<=s;t*=p,j+=t)
        if(s%j==0)dfs(i,prod*t,s/j);
    }
}
int main(){
    get_prime(N-1);
    int s;
    while(cin>>s){
        len=0;
        dfs(-1,1,s);
        cout<<len<<endl;//表示有len个等的人

        if(len){
            sort(ans,ans+len);//答案从小到大排序
            for(int i=0;i<len;i++)
            cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1295. X的因子链

噩梦齋纂
5个月前
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=(1<<20)+10;
int primes[N],minprimes[N];//质数函数,统计所有质数
int cnt;//统计素数个数的下标
bool st[N];//判重
int fact[30],sum[N];//数据范围内最大的个数和其中的和
typedef long long LL;
 void get_prime(int n){
     for(int i=2;i<n;i++)
     {
         if(!st[i]){primes[cnt++]=i;
         minprimes[i]=i;
         }
         for(int j=0;primes[j]*i<n;j++)//j用来遍历质数数组,从质数数组的0下标开始
         {
             st[primes[j]*i]=true;
             minprimes[primes[j]*i]=primes[j];//合数primes[j]*i的最小质因数就
             //是primes[j]
             if(i%primes[j]==0)break;
         }
     }
 }
int main(){
    get_prime(N-1);
    int x;

    while(scanf("%d",&x)!=-1){//scanf读入多组数据的做法
       int k=0;//表示x的因子链的下标
          int tot=0;//统计因子序列的总个数;
         while(x>1){
        int p=minprimes[x];//取出x的从最小因子开始的因子串
          fact[k]=p;
           sum[k]=0;

        while(x%p==0)
        {  
            x/=p;//去掉该因子,求其他因子
            sum[k]++;//表示每个因子使用的次数
            tot++;
        }
        k++;
    }
      LL res=1;
     for(int i=1;i<=tot;i++)res*=i;//统计总的列的阶乘
     for(int i=0;i<k;i++)
     for(int j=1;j<=sum[i];j++)
      res/=j;//除去每次使用次数的阶乘,计算后面的排列种数(即最大序列个数)

      printf("%d %lld\n",tot,res);
    }
    return 0;
}

线性筛法求素数

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=(1<<20)+10;
int primes[N];//存储素数
int cnt;//统计素数个数的下标
bool st[N];//判重数组
void get_prime(int n){
    for(int i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++)//j用来遍历质数数组,从质数数组的0下标开始
        {
            st[primes[j]*i]=true;//合数primes[j]*i的最小质因数就是primes[j]
            if(i%primes[j]==0)break;

        }
    }
}
int main(){
    int n;
    cin>>n;
    get_prime(n);
    for(int i=0;i<cnt;i++)
    cout<<primes[i]<<" ";
    return 0;
}


活动打卡代码 AcWing 1246. 等差数列

噩梦齋纂
5个月前

等差数列的处理,特殊的等差数列,常数列的处理

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100010;
int a[N];
int n;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}//欧几里的算法,求最大公因数/辗转相除法,进行递归求解,将数除到0
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    sort(a,a+n);
    int d=0;
    for(int i=1;i<n;i++)
    d=gcd(d,a[i]-a[0]);//求公差

    if(!d)printf("%d",n);//细节,常数列,如果公差为零,最短只能为n,所以要进行特判
    else{
    int t=a[n-1]-a[0];
    int len=t/d+1;//等差数列的项数,末项减首项加一
    printf("%d",len);}
    return 0;
}



噩梦齋纂
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

int main()
{
    unordered_map<string, int> hash = {
        {"Bessie", 0},
        {"Elsie", 0},
        {"Daisy", 0},
        {"Gertie", 0},
        {"Annabelle", 0},
        {"Maggie", 0},
        {"Henrietta", 0},
    };

    int n;
    cin >> n;

    while (n -- )
    {
        string name;
        int x;
        cin >> name >> x;
        hash[name] += x;
    }

    vector<int> q;
    for (auto& [k, v]: hash) q.push_back(v);
    sort(q.begin(), q.end());

    q.erase(unique(q.begin(), q.end()), q.end());
    if (q.size() == 1) puts("Tie");
    else
    {
        int x = q[1];
        string name;
        int cnt = 0;

        for (auto& [k, v]: hash)
            if (v == x)
            {
                name = k;
                cnt ++ ;
            }

        if (cnt > 1) puts("Tie");
        else cout << name << endl;
    }

    return 0;
}


活动打卡代码 AcWing 3490. 小平方

噩梦齋纂
5个月前
double 类型的不能够做取余运算,但是余数肯定不会是小数,所以在取余的时候进行一次强制类型转换将double转换成int进行比较
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int res;
double n;
int main(){
    scanf("%lf",&n);
    for(int i=1;i<n;i++)
    {    int y=(i*i)%(int)n;///
        if(y<(n/2))res++;
        else continue;
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 3496. 特殊年份

噩梦齋纂
5个月前

取数位时 (1)取模是除去前面的数 (2)除是出去后面的数

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int res;
bool check(int x){
    int g,s,b,q;
     g=x%10;
     s=x%100/10;
     b=x%1000/100;
     q=x/1000;
     if((q==s)&&(g==b+1))return true;
     else return false;
}
int main(){
    int n=5;
    while(n--){
        int x;
        scanf("%d",&x);
        if(check(x))res++;
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 112. 雷达设备

噩梦齋纂
5个月前

题目中的是求圆的范围,情况比较复杂,利用已知条件,将圆的范围问题一维话后,进行区间问题的判断

贪心策略:

(1)利用结构体记录左右端点表示区间
(2)将区间进行排序,从小到大遍历区间
(3)如果上一个点(最后一次选的,第一次是区间最左边的点,及负无穷)不在区间内,就选择右端点,(在不在区间内是和左端点比较)
(4)如果在这个区间内,就跳过,处理下一个端点

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1010;
struct segment {
    double l,r;
    bool operator <(const segment &t) const {
        return r<t.r;
}}seg[N];//自定义区间结构体,可以表示区间的左右端点,同时重载小于号,由右端点决定
int n,d;
int main(){
    scanf("%d%d",&n,&d);
    bool failed=false;
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(y>d)failed=true;//判断不可能的情况,因为雷达必须在x轴上
        else {
            double len=sqrt(d*d-y*y);//勾股定理计算
            seg[i]={x-len,x+len};
        }
    }

    if(failed)puts("-1");
    else{
        sort(seg,seg+n);
        int cnt=0;
        double last=-1e20;//第一个区间必须增加雷达
        for(int i=0;i<n;i++){
        if(last<seg[i].l){//如果上一个区间的最后一个点不在当前区间内,就要新增一个雷达
            cnt++;
            last=seg[i].r;
        }}
        printf("%d",cnt);
    }

    return 0;
}