設(shè)index為當(dāng)前點,則index+k為終點。不難看出增量為這兩點之間的所有點的線段數(shù)之和再加1.數(shù)據(jù)范圍比較大,暴力會超時,所以用樹狀數(shù)組來求解。不會樹狀數(shù)組的話可以戳這里。~樹狀數(shù)組詳解~另外,一個凸n邊形,增量為k,和增量為(n-k)得到的結(jié)果相同,此處不再證明。#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <vector>#include <map>#include <iomanip>using namespace std;long long v[1000010];long long c[1000010];long long C(int i){ long long temp = 0; int index = i + 1 - (i&(-i)); while(index <= i) { temp+=v[index]; index++; } return temp;}long long SUM(int i){ long long s = 0; while(i>0) { s+=c[i]; i -= (i&(-i)); } return s;}void Update(int i,int add,int SIZE){ while(i<=SIZE) { c[i] += add; i += (i&(-i)); }}int main(){ int n,k; while(cin>>n>>k) { memset(v,0,sizeof(v)); k=min(k,n-k); for(int i=1; i<=n; i++) { if(i == 1||i == k+1) v[i] = 1; else v[i] = 0; c[i] = C(i); } cout<<"2"; int index = k+1; long long tempsum = 2; for(int i=2; i<=n; i++) { if(index+k>n) { tempsum += SUM(n) - SUM(index); tempsum += SUM((index+k)-n-1); tempsum++; Update(index,1,n); index = (index+k)-n; Update(index,1,n); } else { tempsum += SUM(index+k-1) - SUM(index); tempsum++; Update(index,1,n); index = (index+k); Update(index,1,n); } cout<<" "<<tempsum; } cout<<endl; }}
新聞熱點
疑難解答