专栏文章

8-17暑假-S组-第四场 程皓楠总结

CCrash_Man_CHN
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioa2aqm
此快照首次捕获于
2025/12/02 15:49
3 个月前
此快照最后确认于
2025/12/02 15:49
3 个月前
查看原文

T1

错误原因

1.思路错误
其实本题是一道数学题，而我使用的是前缀和+枚举，我的思路是如果当前为0，那么和就是从1+2+…+n,若为1，那么和就是n+1+2+…+n,之后便是枚举 主要见代码

90pts TLE代码

CPP
#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

CPP
#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

CPP
#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函数，怎么写呢，这里给出伪代码
CPP
枚举所有种类的芒果数量
    如果只要取a[i]，那么拿a[i]份即可，若有多，则用x份即可，这里取min即可，然后用sum统计总和
若总和比总共要用的芒果还多，说明可行，return true,反之return false
这样这题就简单了，只需要判断特殊性质+二分答案即可

100pts code

CPP
#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 优先队列的代码也贴上来,以防正解过不了
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...