25来追梦-暑假-S组-第四场补题

· · 个人记录

U562064 求和

这道题是一个数学题 比赛的时候想到有规律

毕竟题意 对于 100% 的数据范围， 满足 1≤t≤10 5 ,1≤n≤10 6 所以我先打了一个暴力代码再寻找规律

暴力50分核心代码如下

for(int i=0;i<=n;i++){
            for(int j=i;j<=n;j++){
                ans+=i+j;
                ans%=mod;
            }
        }

O(tn n) 这里暴力可以得知要算ans+=i到n的和+(i~n)*i i到n的和可以用高斯公式 可以省下一个循环

时间复杂度为O（n*t）

高斯公式 首相加末项的和*项数/2

可是有个细节要注意

本题需要取mod

mod的性质

（a+b）%mod=（a%mod+b%mod）%mod （+ - *）

可（a/b）mod就不能满足上述公式

所以本题取mod 可以每算完一次再取mod 过程取mod 有风险 以免过程中爆掉 需要开long long

代码如下

#include<bits/stdc++.h>
using namespace std;
int t;
#define int long long 
const int mod=998244353;
int ans=0;
signed main(){
    cin>>t;
    while(t--){
        int n,ans=0;
        cin>>n;
        for(int i=0;i<=n;i++){
            ans+=(i+n)*(n-i+1)/2+(n-i+1)*i;
            ans%=mod;
        }
        ans%=mod;
        cout<<ans<<'\n';
    }
    return 0;
}

可是O（t*n）还是超时了 只能拿到90分 所以还有最后的优化

课上优化

每个数字 i 一共会被使用 n+2 次

所以可以转化成(n+2)×(n)×(n+1)/2

O（t）

代码如下

#include<bits/stdc++.h>
using namespace std;
int t;
#define int long long 
const int mod=998244353;
int ans=0;
signed main(){
    cin>>t;
    while(t--){
        int n,ans=0;
        cin>>n;
        ans+=(n+2)*n*(n+1)/2;
            ans%=mod;

        ans%=mod;
        cout<<ans<<'\n';
    }
    return 0;
}

U560342 热量计算

这道题比赛的时候没时间打暴力

主要是比赛的时候题意理解错了

误以为是合并连续的两个的果汁

所以把它的解法写成石子合并了

这道题其实故意误导我们

其实推出来可以得知不管什么顺序合并都是一样的

例如：3 a b c

①a b + (a + b) c = a b + a c + b * c

②a c + (a + c) b = a b + a c + b * c

③b c + (b + c) a = a b + a c + b * c

所以每个数只能搭配一次 可以直接按固定顺序遍历合并

计算公式：

a[j]*a[i]的和

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=1e9+7;
const int maxn=2e5+7;
int a[maxn];
int n,op;
int cal(int x){
    return x*(x-1)/2;   
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>op;
        int tmp=0;
        int ans=0;
        int sum=1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            ans+=tmp*a[i];
            tmp+=a[i];
            tmp%=mod;
            ans%=mod;
        }
        cout<<ans<<" ";
        for(int i=2;i<=n;i++){
            int x=cal(i);
            x%=mod;
            sum*=x;
            sum%=mod;
        }
        if(op==0){
            sum=0; 
        }
        cout<<sum<<'\n';
    }
    return 0;
}

U558044 芒果分类

此题比赛的代码

#include<bits/stdc++.h>
using namespace std;

int n;
const int maxn=1e3+10;
int a[maxn];
int k;
int ans=0;
bool flag=1;
bool vis[maxn];
int main(){
//  freopen("T3.in","r",stdin);
//  freopen("T3.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans+=a[i];
        if(a[i]!=1){
            flag=0;
        }
    }
    if(k==1){
        cout<<ans<<'\n';
        return 0;
    }
    /*
    5 3
    1 1 1 1 1
    */
    if(flag){
        cout<<n/k<<endl;
        return 0;
    }
    ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(a[i]<a[j])swap(a[i],a[j]);
        }
    }
//  for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        int tmp=0;
        bool r=0;
        for(int j=1;j<=n;j++){
            if(a[j]>0){
                a[j]--;
                vis[j]=1;
                tmp++;
            }
            if(tmp==k){
                ans++;
                tmp=0;
                r=1;
                break;
            }
        }
        if(r==0){
            for(int j=1;j<=n;j++){
                if(vis[j]==1){
                    a[j]++;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

代码0分意料之外 比赛的时候我先看了特殊样例

发现有样例k=1 证明每个种类的一个都可以打包成一个礼包

所以输入a[i]的时候可以ans累加a[i]

当k==1时输出ans

还有一个特殊样例a[i]都等于1

证明每k个就能组成一个礼包

所以当a[i]都等于1时 输出[n/k]就行了

后面我拿了样例分之后尝试贪心 可是时间复杂度O(n的平方)

我就将数组从原本的5e5+10大小开成1e3+10

不然太大就内存就爆了

可是贪心是假解

并且前面的特殊样例数组大小都是5e5的数组

而我确实因为写贪心得不偿失 一分没拿到

这道题正解思路是二分+鸽巢原理

正解代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=5e5+7;
int a[maxn];
int ans=0;
int n,k;
bool check(int x){
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=min(a[i],x);
    }
    return sum>=x*k;
}
signed main(){
    int l=-1;
    int r=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        r+=a[i];
    } 
    r/=k;
    r++;
    while(l+1<r){
        int mid=(l+r)/2;
        if(check(mid))
        {
            l=mid; 
        }else {
            r=mid;
        }
    }
    cout<<l<<'\n';
    return 0;
}

综上

比赛我该拿的分没拿 数据范围要注意

没合理分配时间

暴力分没拿满