不正经题解 - 模拟

1

根据题意，我们逐天模拟，第 $i$ 天就在累计上加上 $i$ 直到累计超过 $k$，最后输出最后一天的日期即可。时间复杂度 $O(N)$，可以通过此题数据范围。

#include <cstdio>
using namespace std;
int main(){
	int ans=0,k,i;
	scanf("%d",&k);
	for(i=1;ans<k;i++)
		ans+=i;
	printf("%d",i-1);
	return 0;
}

2

根据等差序列求和公式，前 $n$ 天可以收到的经验值为 $\sum\limits_{i=1}^ni$，即为 $\dfrac{n(n+1)}2$。配合二分答案，check 的时间复杂度为 $O(1)$，二分的时间复杂度为 $O(\log N)$，我们实现了 $O(\log N)$ 的时间复杂度，可以通过 long long 数据范围。

#include <cstdio>
using namespace std;


int main(){
	int k;
	scanf("%d",&k);
	int l=0,r=1000,ans=1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(mid*(mid+1)>>1>=k) ans=r=mid;
        else l=mid;
    }
    printf("%d\n",ans);
	
	return 0;
}

3

我们发现，我们要求的就是关于 $n$ 的不等式 $\dfrac{n(n+1)}2\geq k$ 的最小整数解。解得：

$$n\geq\dfrac 12(\sqrt{8k+1}-1)\quad\text{and}\quad n\leq\dfrac 12(-\sqrt{8k+1}-1)$$

后者为负解集，舍去。答案即为 $\lceil\dfrac 12(\sqrt{8k+1}-1)\rceil$。时间复杂度 $O(1)$，配合高精度，可以通过极大的数据范围。

#include <cstdio>
#include <cmath>
using namespace std;


int main(){
	int k;
	scanf("%d",&k);
	printf("%d",(int)ceil((sqrt((k<<3)+1)-1)/2));
	
	return 0;
}