国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

Code Forces 755 D PolandBall and Polygon(思維+樹狀數(shù)組)

2019-11-08 03:10:25
字體:
供稿:網(wǎng)友

看原題請戳下面戳這里~~題目內(nèi)容什么的就不贅述了,看圖吧。設(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;	}}


發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 兴安盟| 丽江市| 南充市| 榆社县| 仪征市| 沈丘县| 余干县| 大理市| 界首市| 永登县| 伊金霍洛旗| 浮山县| 平江县| 重庆市| 德江县| 望城县| 武城县| 莲花县| 宜兰市| 大关县| 肇源县| 二手房| 长岛县| 西乡县| 英山县| 平凉市| 株洲县| 达拉特旗| 涟水县| 武山县| 恭城| 高尔夫| 独山县| 北海市| 夏津县| 台湾省| 清水河县| 沛县| 江西省| 安庆市| 扶绥县|