错位排列
这是一道水题，名字就直接告诉了题的内容和做题的方法，那么直接使用公式就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<bits/stdc++.h>
using namespace std;
long long fact[15];
inline void init(){
fact[0]=1;
for(int i=1;i<=12;i++)fact[i]=fact[i-1]*i;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
init();
long long res;
int n;
scanf("%d",&n);
res=fact[n];
double tmp=1;
for(int i=1;i<=n;i++){
tmp+=(pow(-1,i)/(fact[i]+0.0));
}
printf("%.0lf\n",res*tmp);
return 0;
}
|
计数器
大概就是统计1~n中每一个数字出现了多少次。有10^9的数量级，所以不可以枚举的。因此要采取把每一位的数字分开来进行计算，即分解每一位，然后这一位前面的数字乘以这一位的权值(它在十的第几位，权值就是十的第几次方)，如果说这一位数字大于我们统计的数字，那么还可以再加上一次权值，而如果等于，则应该加上它后面的位数组成的数字+1，+1是因为后面的组成的还有全0。比如2533，再统计5时，统计到第三位，因为这这一位等于5，后面的位数组成的数字是33，但是漏了2500，所以要+1(注意0要进行特殊的判定，因为0在最前面是不符合计数的规则的)。
那么代码如下
洛谷的链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include<bits/stdc++.h>
using namespace std;
int data[11];
void calc(int num,int tot){
int cnt=0,k=1,upp,low,now;
int tmp=tot;
while(k<=tot){
upp=tot/(k*10);
low=tot%k;
now=tmp%10;
cnt+=(upp*k);
if(now>num)cnt+=k;
if(now==num)cnt+=(low+1);
if(num==0)cnt-=k;
k*=10;
tmp/=10;
if(tmp<10&&num==0)break;
}
data[num]=cnt;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
memset(data,0,sizeof(data));
int n;
cin>>n;
for(int i=0;i<=9;i++){
calc(i,n);
}
for(int i=0;i<=9;i++)printf("%d\n",data[i]);
return 0;
}
|