8-17暑假-S组-第四场 程皓楠总结
Crash_Man_CHN · · 个人记录
T1
错误原因
1.思路错误
其实本题是一道数学题，而我使用的是前缀和+枚举，我的思路是如果当前为0，那么和就是从1+2+…+n,若为1，那么和就是n+1+2+…+n,之后便是枚举 主要见代码
90pts TLE代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int mod=998244353;
int a[N],sum[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)
{
memset(sum,0,sizeof(sum));
int n;
cin>>n;
for(int i=1;i<=n;i++)a[i]=i%mod;
sum[1]=a[1];
for(int i=2;i<=n;i++)sum[i]=(sum[i-1]+a[i])%mod;
int ans=(sum[n]+n+sum[n])%mod,j=n-1;
for(int i=2;i<=n;i++)
{
ans+=((j*i%mod+(sum[n]-sum[i-1])%mod))%mod;
j--;
}
cout<<ans%mod<<"\n";
}
return 0;
} 因为会爆，所以我们要修改思路，要O(1)，而根据题目意思和样例解释，我们可以推出一个公式为：n(n+1)(n+2)/2
一定要取模！！！并且不要位置不要错！！！
100pts code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int mod=998244353;
int a[N],sum[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
cout<<(n*(n+1)*(n+2)/2)%mod<<"\n";
}
return 0;
} T2
考场骗了60分的特殊性质，其实要求出现了多少次很简单，因为通过乘法分配律可以得出怎么算都是一样的，所以我们可以得出要在x个数中选取两个合并，得出公式:x*(x-1)/2
最后求乘积,并且取模即可
100pts code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int a[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--)
{
int n,op;
cin>>n>>op;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int sum=0;
for(int i=1;i<n;i++)
{
sum+=(a[i]*a[i+1])%mod;//热量
a[i+1]=(a[i+1]+a[i])%mod;//体积
}
int ans=1;
for(int i=n;i>=2;i--)
{
int x=(i*(i-1))/2;
x%=mod;
ans*=x;
ans%=mod;
}
if(op==0)cout<<sum%mod<<" "<<0<<"\n";
else cout<<sum%mod<<" "<<ans<<"\n";
}
return 0;
}T3
这道题目居然用特殊性质+假解贪心居然能拿40分，真是奇迹
一眼二分答案，我考场也想了，
但是没多想就没写了，只写了假贪心和特殊性质，所以我们直接使用二分答案
为什么可以用二分答案？
因为有单调性，题目可以说明：如果可以打包出来val份大礼包，则小于val份一定可以打包出来
具体思路
首先讲check函数，怎么写呢，这里给出伪代码
枚举所有种类的芒果数量 如果只要取a[i]，那么拿a[i]份即可，若有多，则用x份即可，这里取min即可，然后用sum统计总和 若总和比总共要用的芒果还多，说明可行，return true,反之return false这样这题就简单了，只需要判断特殊性质+二分答案即可
100pts code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N],n,k;
bool check(int x)
{
int t=x*k;
int sum=0;
for(int i=1;i<=n;i++)sum+=min(a[i],x);
return sum>=t;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
int l=-1,r=0;
for(int i=1;i<=n;i++)cin>>a[i],r+=a[i];
if(k==1)
{
int sum=0;
for(int i=1;i<=n;i++)sum+=a[i];
cout<<sum;
return 0;
}
int fl=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)fl++;
}
if(fl==n)
{
cout<<n/k;
return 0;
}
r=r/k+1;
while(l+1<r)
{
int mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
cout<<l;
return 0;
}这里顺便把60pts 优先队列的代码也贴上来,以防正解过不了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],n,k;
priority_queue<int,vector<int>,less<int> > q;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
q.push(a[i]);
}
if(k==1)
{
int sum=0;
for(int i=1;i<=n;i++)sum+=a[i];
cout<<sum;
return 0;
}
int fl=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)fl++;
}
if(fl==n)
{
cout<<n/k;
return 0;
}
int ans=0;
while(q.size()>=k)
{
int x=k,y=1;
vector<int> v;
while(x--)
{
int t=q.top();
q.pop();
v.push_back(t);
}
ans++;
int len=v.size();
for(int i=0;i<len;i++)
{
if(v[i]-1>0)q.push(v[i]-1);
}
}
cout<<ans;
return 0;
}