专栏文章

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

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

文章操作

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

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

U562064 求和

这道题是一个数学题 比赛的时候想到有规律
毕竟题意 对于 100% 的数据范围， 满足 1≤t≤10 5 ,1≤n≤10 6 所以我先打了一个暴力代码再寻找规律

暴力50分核心代码如下

CPP
for(int i=0;i<=n;i++){
			for(int j=i;j<=n;j++){
				ans+=i+j;
				ans%=mod;
			}
		}
O(t*n *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

代码如下

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

代码如下

CPP
#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]的和

代码如下：

CPP
#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 芒果分类

此题比赛的代码
CPP
#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的数组
而我确实因为写贪心得不偿失 一分没拿到
这道题正解思路是二分+鸽巢原理

正解代码如下

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

综上

比赛我该拿的分没拿 数据范围要注意
没合理分配时间
暴力分没拿满

评论

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

正在加载评论...