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

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

1049. Counting Ones (30)

2019-11-11 06:51:13
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

1. 原題: https://www.patest.cn/contests/pat-a-PRactise/1049

2. 思路:

題意:輸出從1~N之間的所有整數(shù)中含有1的總個(gè)數(shù)。思路:數(shù)學(xué)邏輯題。需要枚舉,歸納出規(guī)律。不易想出來(lái)。首先,從1直接數(shù)的方法有些傻,拋棄掉。那么如何處理呢?不妨站在全局進(jìn)行思考,我們無(wú)法準(zhǔn)確知道1會(huì)出現(xiàn)在哪一位。那為何我們不從每一位出現(xiàn)1的次數(shù)進(jìn)行累加不就是總次數(shù)呢。okay, 那么我們需要?dú)w納每一位出現(xiàn)1的次數(shù)是多少。假設(shè)我們現(xiàn)在計(jì)算百位上為1的次數(shù)。比如一個(gè)數(shù)12033.1. 若當(dāng)前位cur = 0, 顯然若百位為1,只與高位有關(guān)。比如 100~199, 1100~1199, 總數(shù)為12*100。即高位*位權(quán)。2. cur = 1, 如12133.顯然除了高位,還與低位有關(guān)。即12100~12133,低位有關(guān)時(shí)的總個(gè)數(shù)為 低位數(shù)+1.3. cur > 1, 如12233. 顯然與低位無(wú)關(guān)了,與高位及當(dāng)前位有關(guān),但可以把當(dāng)前位累計(jì)到高位上,即 總個(gè)數(shù)為 (高位+1)*位權(quán)。以上就是一個(gè)規(guī)律的展示。

3. 源碼(已AC):

#include<iostream>using namespace std;int main(void){	//freopen("in.txt", "r", stdin);	int N, sum = 0;	cin >> N;	int wgt = 1;//位權(quán)初始1,表示從個(gè)位開始		while (N / wgt != 0)	{		int left = N / (wgt * 10);//表示高位數(shù)		int cur = N / wgt % 10;//當(dāng)前位值		int right = N % wgt;//低位數(shù)值		if (cur == 0)//三種情況			sum += left * wgt;		else if (cur == 1)			sum += left * wgt + right + 1;		else			sum += (left + 1) * wgt;		wgt *= 10;//位權(quán)增加	}	cout << sum << endl;	return 0;}參考自: http://m.blog.csdn.net/article/details?id=38846057
發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 巴林左旗| 黄梅县| 稻城县| 河池市| 喀喇沁旗| 凤阳县| 商河县| 方城县| 龙口市| 曲阳县| 大洼县| 博白县| 洞头县| 三原县| 鞍山市| 平武县| 阿拉尔市| 福鼎市| 宜良县| 松桃| 胶南市| 娄烦县| 闸北区| 蛟河市| 吉林市| 从江县| 会东县| 灵山县| 六安市| 徐水县| 东丽区| 当雄县| 上饶县| 遂平县| 洱源县| 侯马市| 东乌珠穆沁旗| 阜新市| 乌兰察布市| 林周县| 沙洋县|