关于站外题,求助大佬
  • 板块灌水区
  • 楼主xiaoyang111
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/9/9 19:17
  • 上次更新2023/11/2 21:49:00
查看原帖
关于站外题,求助大佬
890311
xiaoyang111楼主2023/9/9 19:17

题大概是这样的:给出 nn,求 a+b+c=na + b + c = n 中 a,b,ca,b,c 的方案数,a,b,ca,b,c 须满足 0<a<b<c≤n0 \lt a \lt b \lt c \leq n。保证 n≤1200n \le 1200。

由于我太卷了,从开始的 O(n2)O(n^2) 卷到了现在的 O(n)O(n),想问一下大佬可能做到时间复杂度为 O(1)O(1) 吗

先摆代码(我都不知道怎么卷出来的):

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	int n;
	cin >> n;
	int ans=0;
	for (int a=1;a<n/3;++a){
		ans+=ceil((n-a)/2.0)-1-a;
	}
	cout<<ans<<endl;
	return 0;
}

形象化的话答案就是:∑i=1n⌈(n−i)/2⌉−1−i\sum ^ {n} _ {i=1} \lceil {(n-i)/2} \rceil - 1 - i。

请求各位大佬解答,上面的代码能否做到 O(1)O(1) 级别qwq。

2023/9/9 19:17
加载中...