CodeForces 755D PolandBall and Polygon —

　　每次连线，起点和终点之间，每一个被点亮的点，这些点都能连出去两条线，因此可以增加的块数+2（1这个点除外，因为只有连出的点没有连进的点），计算起点和终点之间有几个点被点亮即可，然后1这个点特判一下。感觉，可以用线段树维护。。不过这题还是有规律的，每转过一圈，两线之间的点数就会加1，然后O(n)扫一遍就行了。注意答案会爆int。

　　代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 1e6 + ;

 typedef long long ll;

 int n,k;

 int main()

 {

     cin >> n >> k;

     k = min(k,n-k);

     int add = ;

     int pos = ;

     ll have = ;

     for(int i=;i<=n;i++)

     {

         if(pos + k > n + )

         {

             add++;

             have += add;

             add++;

         }

         else have += add;

         pos += k;

         if(pos > n) pos -= n;

         cout << have << " ";

     }

     puts("");

     return ;

 }

巴特西

CodeForces 755D PolandBall and Polygon ——（xjbg）

最新文章

热门文章