头像

陈平安




在线 


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

陈平安
58分钟前
/*
思路:
    由算数基本定理,任意一个大于1的整数都可以分解为若干个质数相乘
    形式为N=p1^a1*p2^a2*p3^a3·····
    又结合题目,发现只要每一个数后面的数是前面的数的倍数,且该倍数是质数时,长度最大,因为如果倍数是合数
    那么就可以再分,使长度更长
    那么长度最长可以是a1+a2+a3+····+an
    且排列方式的种数是(a1+a2!+a3!+···+an!)/a1!/a2!/···/an!      因为有一种质因数可能有多个
    那么排列方式就可能重复,所以不可以算重复的部分。(注意:阶乘可能会爆int,所以要用long long)
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=(1<<20)+10;
int primes[N],cnt;
bool st[N];
int minp[N];
int n;
int sum[N];
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])  minp[i]=i,primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;

            minp[primes[j]*i]=primes[j];
            if(i%primes[j]==0)  break;
        }
    }
}
int main()
{
    get_primes(N-1);
    while(cin>>n)
    {
        int k=0,total=0;
        while(n>1)
        {
            int p=minp[n];
            sum[k]=0;
            while(n%p==0)
            {
                n/=p;
                sum[k]++;
                total++;
            }
            k++;
        }
        ll res=1;
        for(int i=1;i<=total;i++)   res*=i;
        for(int i=0;i<k;i++)
            for(int j=1;j<=sum[i];j++)
                res/=j;
        printf("%d %lld\n",total,res);
    }
    return 0;
}


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

陈平安
11小时前
/*
思路:
        将所有数按照从小到大的顺序排序之后
        每两个数之间的差值其实就是公差d的倍数,又因为需要满足题目条件
        所以所有两个数之间的差值的最大公约数其实就是公差d,求出d之后等差数列的数目就很好求了
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,INF=1e9;
int n;
int a[N];
int d;
int maxv=-INF,minv=INF;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        maxv=max(maxv,a[i]);
        minv=min(minv,a[i]);
    }
    sort(a,a+n);
    d=0;
    for(int i=1;i<n;i++)    d=gcd(d,a[i]-a[i-1]);
    if(d==0)    cout<<n;
    else        cout<<(maxv-minv)/d+1;

    return 0;
}


活动打卡代码 AcWing 1247. 后缀表达式

陈平安
16小时前
/*
思路:
    如果没负号,则全部式子相加就是最大值
    如果含有负号,式子可以转化为bi-(a1+a2-a3)   相当于可以把负号转化为正号,但是必须有一个负号,一个正号,
    减去最小值,加上最大值,加上剩余所有数,就是最大值
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010;
int a[N];
ll res;
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    int k=n+m+1;
    for(int i=0;i<k;i++)    scanf("%d",&a[i]);
    if(!m)
    {
        for(int i=0;i<k;i++)    res+=a[i];
    }
    else
    {
        sort(a,a+k);
        res=a[k-1]-a[0];
        for(int i=1;i<k-1;i++)  res+=abs(a[i]);
    }
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 1239. 乘积最大

陈平安
17小时前
/*
思路:
    分情况讨论,一定要讲究不重不漏的原则
    1.k==n    全部相乘
    2.k<n   
    (1)当k是偶数,可以分为以下两种情况:
                负数有偶数个——>负数选偶数个,正数选偶数个                          ——>最大值一定为正
                负数有奇数个——>因为k<n,负数选偶数个,一定可以选偶数个整数,满足k个数——>最大值一定为正
    (2)当k是奇数,可以分为以下两种情况:
                全是负数    ——>全部选                                              ——>最大值一定为负
                至少有一个正数——>选最大的正数,则问题转化为(1)                   ——>最大值一定为正
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010,Mod= 1000000009;
ll res;
int a[N];
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);
    int l=0,r=n-1;
    res=1;
    int sig=1;
    if(k%2)
    {
        res=a[r--];
        if(res<0)   sig=-1;
        k--;
    }
    while(k)
    {
        ll x=(ll)a[l]*a[l+1],y=(ll)a[r]*a[r-1];
        if(x*sig>y*sig)
        {
            res=x%Mod*res%Mod;
            l+=2;
        }
        else
        {
            res=y%Mod*res%Mod;
            r-=2;
        }
        k-=2;
    }
    printf("%lld\n",res);
    return 0;
}


活动打卡代码 AcWing 1235. 付账问题

陈平安
20小时前
/*
思路:
    分两种情况:
    1.每个人携带的钱数都大于所有一共需要付的总钱数的平均数,则每个人付平均数,可以是标准差为0,最小
    2.有人携带的钱数小于平均数
        方法:(1)将所有人携带的钱数排序
               (2) 从前往后枚举:
               剩余的钱数的平均值就是该人应该付的钱数
               如果该人拥有的钱数小于剩余的所有钱数的平均值,付他(她)拥有的钱数,更新剩余的钱数。
               如果该人拥有的钱数大于等于剩余的所有钱数的平均值,付平均值的钱数,更新剩余的钱数即可。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=500010;
int a[N];
double s;
int n;
double res;
int main()
{
    scanf("%d%lf",&n,&s);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);
    double avg=s/n;
    for(int i=0;i<n;i++)
    {
        double cur=s/(n-i);
        if(a[i]<cur)    cur=a[i];
        res+=(cur-avg)*(cur-avg);
        s-=cur;
    }
    printf("%.4lf",sqrt(res/n));
    return 0;
}



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

陈平安
23小时前
/*
思路:
    通过转化,可以将与圆相关的问题转化成区间选点问题,使每一个区间至少含有一个点
    区间选点问题方法:
    1.将所有区间按照右端点进行排序
    2.(1)上一个包含点的区间的右端点大于枚举的区间的左端点,不进行操作,枚举下一个区间
      (2)上一个包含点的区间的右端点小于枚举的区间的左端点,更新lst,并更新答案res,使res++
贪心问题最重要部分:证明
    cnt:算法得到的可行解      opt:最优解
    一定有:opt<=cnt;
    又因为:必然存在cnt个不相交区间,每一个区间至少选一个点,至少选cnt个点
            即证明所有可行解opt>=cnt
    所以证明:cnt=opt,即证明算法的准确性
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1010;
int n,d;
int res;
int cnt;
struct Seg
{
    double l,r;
    bool operator<(const Seg&s)const
    {
        return r<s.r;
    }
}seg[N];
int main()
{
    scanf("%d%d",&n,&d);
    bool failed=false;
    double last=-1e20;
    for(int i=0;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        double len=sqrt(d*d-y*y);
        if(y>d)
        {
            failed=true;
            break;
        }
        else
        {
            seg[cnt++]={x-len,x+len};
        }
    }
    sort(seg,seg+cnt);
    if(failed)
    {
        printf("-1\n");
        return 0;
    }
    else
    {
        for(int i=0;i<cnt;i++)
        if(last<seg[i].l)
        {
            res++;
            last=seg[i].r;
        }
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 122. 糖果传递

/*
思路:
        建立数学模型环:
        a1-x1+xn=avg
        a2-x2+x1=avg
        a3-x3+x2=avg
        ············
        an-xn+xn-1=avg
        之后推出公式,本质还是中位数。
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1000010;
ll a[N];
ll c[N];
ll res;
ll sum;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)  
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    ll avg=sum/n;
    c[n]=avg-a[1];
    for(int i=n-1;i>=1;i--)
    {
        c[i]=c[i+1]-a[i]+avg;
    }
    sort(c+1,c+1+n);
    for(int i=1;i<=n;i++)
        res+=abs(c[i]-c[n/2+1]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

/*
思路:
        排序之后
        A[i]<A[i+1]
        A[0]<A[1]<A[2]·····
        分组来看
        (|A[0]-c|+|A[n-1]-c|)+(|A[1]-c|+|A[n-2]-c|)+·······
        货仓在中间,此时每一组均取最小值,则整个式子取最小值
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N];
int n;
ll res;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    sort(a,a+n);
    int x=a[n/2];
    for(int i=0;i<n;i++)   res+=abs(a[i]-x);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1055. 股票买卖 II

/*
贪心:
        局部最优
贪心最重要的部分: 
        如何证明:局部最优——>全局最优(如何证明局部最优一定可以达到全局最优)
本题思路:
        每一种天数跨度大于1的方案,都可以拆分成相邻两天的股票购买方案
        例如: 1,x,7
        加入1买7卖是一种最优购买方案,那么一定有1<=x<=7,那么7-1=x-1+7-x;
        因为如果x不在这个范围的话,1买7卖就不是最优方案了,不符合题意
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int n;
int sum;
int res;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=2;i<=n;i++)
    {
        if(a[i]>a[i-1])
            sum+=a[i]-a[i-1];
    }
    cout<<sum;
    return 0;
}


活动打卡代码 AcWing 1207. 大臣的旅费

/*
思路:
    求树的直径
    先用任意一点x,找到距离该点最远的点y,那么y一定是直径的一个端点
    再寻找距离y最远的点,y到该点的距离即为直径
*/

用vector存图

DFS

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100010;
struct Edge
{
    int id,w;
};
vector<Edge>h[N];
int n;
int d[N];
bool st[N];
void dfs(int u,int farther,int distance)
{
    d[u]=distance;
    st[u]=true;
    for(auto node:h[u])
    {
        //if(node.id!=farther)  //防止多余遍历
        if(!st[node.id])
        {
            dfs(node.id,u,distance+node.w);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    }
    dfs(1,-1,0);
    memset(st,0,sizeof st);
    int u=1;
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
        {
            u=i;
        }
    dfs(u,-1,0);
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
        {
            u=i;
        }
    u=d[u];
    printf("%lld\n",10*u+(ll)(u+1)*u/2);
    return 0;
}

BFS

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100010;
int n;
struct Edge
{
    int id,w;
};
vector<Edge>h[N];
int d[N];
int q[N];
void bfs(int u)
{
    memset(d,-1,sizeof d);
    d[u]=0;
    int hh=0,tt=-1;
    q[++tt]=u;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<h[t].size();i++)
        {
            int id=h[t][i].id,w=h[t][i].w;
            if(d[id]==-1)
            {
            d[id]=d[t]+w;
            q[++tt]=id;
            }
        }
        // for(auto node:h[t])
        // {
        //     if(d[node.id]==-1)
        //     {
        //         d[node.id]=d[t]+node.w;
        //         q[++tt]=node.id;
        //     }
        // }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        h[a].push_back({b,c});
        h[b].push_back({a,c});
    }
    int u=1;
    bfs(1);
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
            u=i;
    bfs(u);
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
            u=i;
    u=d[u];
    printf("%lld\n",10*u+(ll)(u+1)*u/2);
    return 0;
}

用邻接表存图

DFS

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx,w[N*2];
int n;
int d[N];
int q[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int distance)
{
    d[u]=distance;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(d[j]==-1)
        {
            d[j]=d[u]+w[i];
            dfs(j,d[j]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int u=1;
    memset(d,-1,sizeof d);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
            u=i;
    memset(d,-1,sizeof d);
    dfs(u,0);
    for(int i=1;i<=n;i++)
    {
        if(d[i]>d[u])
            u=i;
    }
    u=d[u];
    printf("%lld\n",10*u+(ll)(u+1)*u/2);
    return 0;
}

BFS

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx,w[N*2];
int n;
int d[N];
int q[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int u)
{
    memset(d,-1,sizeof d);
    d[u]=0;
    int hh=0,tt=-1;
    q[++tt]=u;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                d[j]=d[t]+w[i];
                q[++tt]=j;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int u=1;
    bfs(1);
    for(int i=1;i<=n;i++)
        if(d[i]>d[u])
            u=i;
    bfs(u);
    for(int i=1;i<=n;i++)
    {
        if(d[i]>d[u])
            u=i;
    }
    u=d[u];
    printf("%lld\n",10*u+(ll)(u+1)*u/2);
    return 0;
}