ACM暑期集训Day3题解

ACM暑期集训Day3题解

地址

集训赛地址:https://vjudge.net/contest/384707

A 简单数论

#1 思路

这道题方法挺多,说一说贪心做法,从左到右遍历数组,当前下标元素满足条件(a[i]*2>=a[i+1])就累加长度,如果不满足则更新长度最大值,并另起一段。来证明一下这个做法:

  • 正确性:因为数组内元素是单调递增的,所以如果当前下标元素不满足条件,后面的元素也一定不会满足条件。
  • 最优性:显然最优。

#2 程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int a[200005];

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    for (int i=1;i<=n;i++)
        cin>>a[i];

    int cnt=1,maxn=0;
    for (int i=1;i<n;i++)
    {
        if (2*a[i]>=a[i+1]) cnt++;
        else
        {
            maxn=max(maxn,cnt);
            cnt=1;
        }
    }

    cout<<max(maxn,cnt)<<'\n';
    return 0;
}

B 超简单数论

#1 思路

一道真数论题。先来看看LCM的公式:

$LCM(a,b)=a*b/GCD(a,b)$

然后我们把它推广到三个数:

$LCM(a,b,c)=LCM(LCM(a,b),c)=LCM(a*b/GCD(a,b),c)=a*b*c/(GCD(a,b)*GCD(a*b/GCD(a,b),c))=a*b*c/(GCD(a,b)*GCD(LCM(a,b),c))=a*b*c/(GCD(a,b)*LCM(GCD(a,c),GCD(b,c))=a*b*c*GCD(a,b,c)/(GCD(a*b)*GCD(a,c)*GCD(b,c))$

可以看出a,b,c三个数的最小公倍数取决于a,b,c的乘积,a与b、a与c、b与c的最大公约数和a与b与c的最大公约数。那么要使得LCM(a,b,c)最大,有两个方面:

  • 使a*b*c的大小尽可能的大。
  • 使得三个数两两的GCD尽可能的小,或者说互质
  • 三个数两两互质,那么这三个数的GCD必为1

想明白了之后,我们肯定选的三个数是n,(n-1),(n-2),来考虑下使得三个数两两互质:

  • 如果我们有两个整数n和m(n>m),它们的GCD为k,则k必然也是n-m的约数。
  • 那么相邻的两个数必定互质(差为1),当一个数n为奇数时n和n-2必定互质,当n不被3整除时n和n-3必定互质。
  • 当n为奇数时,此时LCM(n,n-1,c)=n*(n-1)*(n-2),这绝对是最大。
  • 当n为偶数时,此时n和n-2不互质,LCM(n,n-1,c)=n*(n-1)*(n-2)/2,不确定是不是最大的值
  • 考虑取小一点的数,但也不知道哪个好一点,先把它列出来吧
  • n,(n-1),(n-3)
  • (n-1),(n-2),(n-3)
  • 比较一下三个的乘积n*(n-1)*(n-3)>=(n-1)*(n-2)*(n-3)
  • 消去n-1,并分解$n^2-3n>=n^2-5n+6$
  • 得n>=3,所以n,(n-1),(n-3)比(n-1),(n-2),(n-3)要优先选择选
  • (n-1)*(n-2)*(n-3)>n*(n-1)*(n-2)/2(可以证明)
  • 然而如果n能被3整除,此时n和n-3不互质,那就只能选择(n-1),(n-2),(n-3)

整个题目的思路就是这样,比赛时写的快暴毙了,各位太巨了。

程序1(C++)

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n;
    cin>>n;

    if (n<3)
        cout<<n<<'\n';
    else if (n%2)
        cout<<n*(n-1)*(n-2)<<'\n';
    else
    {
        if (n%3)
            cout<<n*(n-1)*(n-3)<<'\n';
        else cout<<(n-1)*(n-2)*(n-3)<<'\n';
    }

    return 0;
}

C 超超简单数论(补)

D 超超超简单数论(补)

E 超超超超简单数论

#1 思路

一道最短路模板题,数据范围来说Floyd,Dijsktra和SPFA都可以过。当然要注意的是这道题是无向带权图,所以要双向建边,我就是这样浪费了十几分钟,做之前一定要看清楚是什么类型的图。

#2 程序1

#include<bits/stdc++.h>
using namespace std;
#define INS(x) (x).begin(),(x).end()

struct Edge
{
    int v;
    int w;
    int next;
}edge[10005];
 
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;    //优先队列相当于二叉堆
int head[205];
int cnt;
bool vis[205];
int F[205];
 
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
 
int main()
{
    int n,m;

    while (cin>>n>>m&&n&&m)
    {
        cnt=0;
        for (int i=1;i<=n;i++) F[i]=INT_MAX;    //初始化
        memset(edge,0,sizeof(edge));
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
    
        F[1]=0;
        q.push(make_pair(0,1));
        while (!q.empty())  
        {
            int x=q.top().second;
            q.pop();    //在判断之前先pop
            if (vis[x]) continue;
            vis[x]=1;
 
            for (int i=head[x];i;i=edge[i].next) 
            {
                if(F[edge[i].v]>F[x]+edge[i].w)
                {
                    F[edge[i].v]=F[x]+edge[i].w;
                    q.push(make_pair(F[edge[i].v],edge[i].v));
                }
            }
        }
 
        cout<<F[n]<<'\n';
        while (!q.empty()) q.pop();
    }
    return 0;
}

F 超超超超超简单数论(补)

G 超超超超超超简单数论(补)

H 超超超超超超超简单数论(补)

I 超超超超超超超超简单数论(补)

总结

我某了🙃。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。