【LGR-208-Div.3】洛谷基础赛 #18 &「WPOI」Round 2 纷飞的樱花雨题解

^羽然_ · 2024-11-23 17:37:09 · 题解

对于这道题目，我的建议是：不用管下面那个形式化玩意儿（别因为那玩意儿没看懂就卡那儿了奥）。还有，那个交换是任意两朵都能交换，不是相邻的交换。

根据题面，我们可以进行以下分类讨论：

如果 k=0，那么我们可以直接得出，这组数据的观赏度可以直接按照题面中“每朵樱花掉落后，樱花掉落的总观赏度会增加这朵樱花及之前所有已经掉落的樱花的美丽度的最大值”这句话来模拟！

就像这样：

for(int i=1;i<=n;i++)
{
    int a;
    cin>>a;
    maxx=max(maxx,a);
    ans+=maxx;
}

如果 n=2 的话，观赏度就和 a_1 是否大于 a_2 （下标从 1 开始）和 k 的奇偶性有关了：

如果 a_1>a_2，那么我们可以得到：当 k 是奇数时，观赏度为 a_1+a_2，否则观赏度为 2\times a_1；否则：当 k 是奇数时，观赏度为 2\times a_2，否则观赏度为 a_1+a_2。

至于上面这个怎么出来的，很简单，我们可以结合样例解释中的情况，进而推导。

最后一种情况就更简单了，直接把这 n 个数里的最大值搞出来然后乘 n。

于是，我写出了：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int maxx=0;
        int ans=0;
        if(k==0)
        {
            for(int i=1;i<=n;i++)
            {
                int a;
                cin>>a;
                maxx=max(maxx,a);
                ans+=maxx;
            }
        }
        else
        {
            if(n==2)
            {
                int a,b;
                cin>>a>>b;
                if(a>b)
                {
                    if(k%2==1)
                    {
                        cout<<a+b;
                    }
                    else
                    {
                        cout<<a*2;
                    }
                }
                else
                {
                    if(k%2==0)
                    {
                        cout<<a+b;
                    }
                    else
                    {
                        cout<<b*2;
                    }
                }
                cout<<endl;
                continue;
            }
            else
            {
                for(int i=1;i<=n;i++)
                {
                    int a;
                    cin>>a;
                    maxx=max(maxx,a);
                }
                ans=maxx*n;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

结果：https://www.luogu.com.cn/record/190571256

喜提爆零。。。

那为什么会爆零呢？我们来看一下数据：

【数据规模与约定】

对于 100\% 的数据， 1 \le T \le 500 ， 2 \le n \le 10^5 ， 0 \le k \le 10^9 ， \sum n \le 10^6 ，\color{red} 1 \le a_i \le 10^9 。

注意被我加红的字，可以想象 10^9\times 10^5 的大小。。。

这玩意儿 int 开得下就怪了啊！！！

于是，我们得到了：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long t;
    cin>>t;
    while(t--)
    {
        long long n,k;
        cin>>n>>k;
        long long maxx=0;
        long long ans=0;
        if(k==0)
        {
            for(long long i=1;i<=n;i++)
            {
                long long a;
                cin>>a;
                maxx=max(maxx,a);
                ans+=maxx;
            }
        }
        else
        {
            if(n==2)
            {
                long long a,b;
                cin>>a>>b;
                if(a>b)
                {
                    if(k%2==1)
                    {
                        cout<<a+b;
                    }
                    else
                    {
                        cout<<a*2;
                    }
                }
                else
                {
                    if(k%2==0)
                    {
                        cout<<a+b;
                    }
                    else
                    {
                        cout<<b*2;
                    }
                }
                cout<<endl;
                continue;
            }
            else
            {
                for(long long i=1;i<=n;i++)
                {
                    long long a;
                    cin>>a;
                    maxx=max(maxx,a);
                }
                ans=maxx*n;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

提交！AC！