Counting Ones (30)

#include <iostream>

using namespace std;

int main()

{

int n,k=1,sum=0,curr,large,small=0;

cin>>n;

while(n>0)

{

curr=n%10;

large=n/10;

if(curr>1)

sum=sum+large*k+k;

else if(curr<1)

sum=sum+large*k;

else

sum=sum+large*k+small+1;

small=small+curr*k;     //记录一下低位，当 当前为为0时用

n=n/10;

k=k*10;

}

cout<<sum;

return 0;

}

#include <iostream>
using namespace std;
int main(){
    int n,a=1,ans=0;
    int left,now,right;
    cin>>n;
    while(n/a){
        left=n/a/10;  //当前位的高位数
        now=n/a%10;
        right=n%a;    //当前位的低位数
        if(now==0) ans+=left*a;                //高位为0到left-1，当前位为1时，每个带a个1
        else if(now==1) ans+=left*a+(right+1); //当前位为1时，还要加上高位为left时低位数个1
        else ans+=(left+1)*a;                  //当前位大于1时，高位0到left当前位为1，每个带a个1
        a*=10;
    }
    cout<<ans;
    return 0;
}

n=int(input())
res,t=0,1
while n//t:
    l,p,r=n//(t*10),n//t%10,n%t
    res+=l*t
    res+=t if p>1 else r+1 if p==1 else 0
    t*=10
print(res) 

#include <iostream>

using namespace std;

int main()
{     int n,w=1,result=0;     int x,y,z;     cin>>n;     while(n/w)     {         x = n/w/10;         y = n/w%10;         z = n%w;         if(y==0)             result += x*w;         else if(y==1)             result += x*w+z+1;         else             result += (x+1)*w;         w *= 10;     }     cout<<result<<endl;     return 0;
}

	

#include<bits/stdc++.h>
using namespace std;

int main() {
	int n,a=1,answer=0,left,now,right;
	cin>>n;
	while(n/a!=0) {
		left=n/(a*10);
		now=n/a%10;
		right=n%a;
		if(now==0) {
			answer+=left*a;
		} else if(now==1) {
			answer+=left*a+right+1;
		} else {
			answer+=(left+1)*a;
		}
		a*=10;
	}
	cout<<answer<<endl;
	return 0;
}

#include<iostream>
using namespace std;
int js(int n);
int num(int n,int m);
int main()
{
	int n,ans=0;
	cin >> n;
	int m = js(n);
	for (int i = 1; i <= m; i++) {
		ans += num(n, i);
	}
	cout << ans << endl;
	return 0;
}
int js(int n)
{
	int m = 0;
	if (n % 10 == 0) n++;
	while (n!=0)
	{
		m++;
		n /= 10;
	}
	return m;
}
int num(int n, int m)
{
	int m1 = (int)(pow(10.0, m));
	int m2 = (int)(pow(10.0, m-1));
	int m3 = (n % m1 + 1) - m2;
	if (m3 > m2)m3 = m2;
	if (m3 < 0)m3 = 0;
	return (n / m1)*m2 + m3;
}

#include<cstdio>
int n,Pow[21],ans=0,dp[21];
int dfs(int n){
	int cnt=0;
	while(n){
		cnt++;
		n/=10;
	}
	return cnt;
}
int main(){
	scanf("%d", &n);
	Pow[1]=1;
	for(int i=1;i<=19;i++){//当有位9时，1的总个数
		dp[i]=Pow[i]+dp[i-1]*10;
		Pow[i+1]=Pow[i]*10;//每次都要加翻10倍的1
	}
	while(n){
		int cnt=dfs(n),a;
		a=n/Pow[cnt];
		if(cnt>1)
			a==1 ? ans+=dp[cnt-1]+(n%Pow[cnt]+1) : ans+=a*dp[cnt-1]+Pow[cnt];//a>1时 要加满10的cnt次方个1
		else ans++;
		n=n%Pow[cnt];
	}
	printf("%d",ans);
	return 0;
}

//不会做，模仿大神们的。。。。
//分别找每一位上1的个数
//
//高n位*本位（比如百位就乘100）               （本位小于1） 
//高n位*本位（比如百位就乘100）+低n位+1          （本位等于1）
//高n位*本位（比如百位就乘100）+1*本位            （本位大于1）     
/*
想一想，也很容易想到为什么要去与1判断大小。假设数为23012，那么要判断百位上为1的个数，
可以知道百位前面两位00-22有23种情况，所以是23*100（后面两位的值任意，就是100种），
但当前面两位为23时，这时候百上还有没有可能为1呢？在这个例子中，百位上为0(小于1)，
因此不可能再出现1了，这时候就不加了。那么又比如说十位上为1，则是230*10+2+1,加一是为了保证个位为0也要算上。
注意：最高位前的高n位看作是0，最低位后的低n位也看做是0。
*/
/*
看到大神用数位dp，百度了半天才勉强看懂了代码，但是还不会写，先记下来学习一下吧，代码直接copy的
*/
/*
#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int count = 0;
	int tmp = 1;//开始为个位,tmp为数位（比如百位就为100）
	while (n / tmp) {
		int number = n;
		int low = number % tmp;
		int now = (n / tmp) % 10;//完美解决最高位最低位的边界问题!!!
		int high = (n / tmp) / 10;
		if (now < 1) {
			count += high * tmp;
		}
		else if (now == 1) {
			count += high * tmp + low + 1;//加一是为了算上0
		}
		else {
			count += high * tmp + tmp;
		}
		tmp *= 10;
	}
	//由于0算进去也不会影响1的值，因此这里不用管0。
	printf("%d", count);
}
*/

#include<iostream>
using namespace std; 
int num[12],dp[12][12]; //dp[i][j]表示每一个状态对应下“1”的数目
int dfs(int pos,int now,int limit){   //now表示当前位的前面的位中有几个1。      123
 if(pos==-1)return now;   
 int& ans=dp[pos][now];//引用类型，dp[i][j]表示当第i位前面有j个1的状态下有多少个“1”出现
 if(!limit&&ans!=-1)
  return ans;  
 ans=0;  
 int up=limit?num[pos]:9;   
 for(int i=0;i<=up;i++){   
  ans+=dfs(pos-1,i==1?now+1:now,limit&&i==up);  
 }  
 return ans; 
} 
int solve(int x){   
 int cnt=0;  
 while(x){   
  num[cnt++]=x%10;  
  x/=10;  
 }   
 return dfs(cnt-1,0,1);
} 
int main() {   
 int n;   
 scanf("%d",&n);
 memset(dp,-1,sizeof(dp)); 
 printf("%d\n",solve(n));
 return 0;
}

感谢第一位和第二位大佬写的思路，由此受到启发，发现此题是一个排列组合的数学题

#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;

int main() {
    int n = 0, left = 0, right = 0, cur = 0, k = 1, sum = 0, tem = 0, i = 0;
    cin >> n;
    while (n / k != 0) {
        tem = n / k;
        cur = tem % 10;//求出各部分的值
        left = tem / 10;
        right = n % (tem*(int)pow(10,i++));

        if (cur > 1) {
            sum = sum + (left+1) * k;
        }
        else if(cur < 1){
            sum = sum + left * k;
        }
        else {
            sum = sum + left * k + right + 1;
        }
        k *= 10;
    }
    cout << sum<<endl;
    system("pause");
    return 0;
}

	优雅解决 数位DP



	#include <bits/stdc++.h>



	using namespace std;



	intnum[12],dp[12][12];



	intdfs(intpos,intnow,intlimit){



	    if(pos==-1)returnnow;



	    int&ans=dp[pos][now];



	    if(!limit&&ans!=-1)returnans;



	    ans=0;



	    intup=limit?num[pos]:9;



	    for(inti=0;i<=up;i++){



	        ans+=dfs(pos-1,i==1?now+1:now,limit&&i==up);



	    }



	    returnans;



	}



	intsolve(intx){



	    intcnt=0;



	    while(x){



	        num[cnt++]=x%10;



	        x/=10;



	    }



	    returndfs(cnt-1,0,1);



	}



	intmain()



	{



	    intn;



	    scanf("%d",&n);



	    memset(dp,-1,sizeof(dp));



	    printf("%d\n",solve(n));



	    return0;



	}

#include <iostream>

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

int table[]={};//表太大了，这里省略，大家可以自己打出来

int ones(int x){
	int ans=0;
	while(x){
		if(x%10==1)ans++;
		x/=10;
	}
	return ans;
}

int query(int id){
	if(id==-1) return 0;
	else if(id==0) return 100000;
	else if(id==1) return 100001;
	else if(id==2) return 200000;
	else if(id==3) return 299999;
	else if(id==4) return 300000;
	else if(id==5) return 300001;
	else if(id==6) return 400000;
	else if(id==7) return 499999;
	else if(id==8) return 500000;
	else if(id==9) return 500001;
	else if(id==10) return 600000;
	else if(id==11) return 699999;
	else if(id==12) return 700000;
	else if(id==13) return 800000;
	return 0;
}

int main(){
	table[0]=0;
	for(int i=1;i<sizeof(table)/sizeof(int);i++){
		table[i]=table[i-1]+query(table[i]);
	}
	int n;
	scanf("%d",&n);
	int ans=table[n/200000];
	for(int j=n/200000*200000+1;j<=n;j++)
		ans+=ones(j);
	printf("%d\n",ans);
    return 0;
} 

#include <iostream>
#include <stdio.h>

using namespace std;

int main()
{
    int n; scanf("%d", &n);
    int ones = 0;
    for(int m=1; m<=n; m*=10) {
        ones += (n/m + 8)/10 *m + (n/m%10 == 1)*(n%m+1);
    }
    printf("%d", ones);
    return 0;
} 

//数num中1的个数