国产探花免费观看_亚洲丰满少妇自慰呻吟_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ā)表
主站蜘蛛池模板: 宜昌市| 南郑县| 巴彦淖尔市| 平利县| 唐海县| 双牌县| 玉田县| 新民市| 新营市| 固镇县| 丹寨县| 定州市| 财经| 吴旗县| 平武县| 华宁县| 湘潭市| 孟州市| 武义县| 沁源县| 麟游县| 新蔡县| 银川市| 依安县| 南华县| 武安市| 宜川县| 大庆市| 衡阳市| 吉安县| 临武县| 临朐县| 永兴县| 右玉县| 买车| 盘锦市| 长沙县| 甘洛县| 广昌县| 启东市| 鱼台县|