題目鏈接：點擊查看

題目大意：我們在玩一個游戲，屏幕上有一個數字，我們設這個數字為x，初始值為2，我們一開始的等級是k，我們每一次可以有兩種操作：

加法：可以讓x加上k

開根號：可以讓x開根號，并且等級變為k+1，但前提必須滿足：

x是完全平方數

根號x必須是k+1的倍數

現在給出一個n，問從1級開始升到n級的過程中，每升一級所需要執行多少次加法操作

題目分析：這個題看過網上的分析后知道了是一個構造題，雖然知道了是構造，但我自己還是構造不出來嗷。。是我太菜了

首先我們抽象一下，也就是關于每個數在可以開根號的時候所滿足的一些條件：

因為每一級的起始值x在經過上一級開根號的操作后，已經滿足了當前的x是當前等級k的倍數，而且每次加法操作后加的都是k，所以可以保證這個數一直都是k的倍數

根號x是k+1的倍數，那么x是(k+1)*(k+1)的倍數

綜上所述，我們可以構造每一級在開根號前的數為k*(k+1)*(k+1)，但因為涉及到遞推需要開根號，所以我們多乘上一個k能夠簡化計算，所以最終我們構造為：k*k*(k+1)*(k+1)，那么這個數開根號后為k*(k+1)，所以令k=k-1，就得到了當前第k層中的

起始x為：k*(k-1)

終止x為：k*k*(k+1)*(k+1)

這樣我們一共經過了（k*k*(k+1)*(k+1)-k*(k-1)）/k次加法操作，化簡一下就是k*(k+1)*(k+1)-(k-1)

注意一下，因為第一關的起始x為2，不滿足剛才構造的k*(k-1)，所以記得特判一下就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { // freopen("input.txt","r",stdin);int n;scanf("%d",&n);for(int i=1;i<=n;i++)if(i==1)printf("2\n");elseprintf("%lld\n",1LL*i*(i+1)*(i+1)-(i-1));return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 715A Plus and Square Root(思维+构造)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。