目录：
数字统计问题
2011的倍数
最多约数问题
最大间隙问题
字典序问题
金币列阵问题
更新中......
问题 B: 数字统计问题（二）
时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 6
[提交] [状态] [讨论版] [命题人:admin]
题目描述
给定一本书，其中包含n页，计算出书的全部页码中用到了多少个数字0…9？页码从1开始
输入
一个整数n，代表页码总数。（0<=n<=109）
输出
十行，每行一个整数，分别表示0~9每个数字出现的次数
样例输入
11样例输出
1
4
1
1
1
1
1
1
1
1提示
注意！答案范围可能超过int存储范围。
【分析】
1. 暴力思路。枚举从1到n每一个数字，对于i，分解这个数字每一位，数一数即可。
2. 组合数学计数。考虑每一位放数字0~9，存在的数字数量。
比如n=12345，在中间那一个3的位置，
如果放1（小于3），那么种数=（12+1）*100，高位00~12，低位00~99
如果放3（等于3），那么种数=12*100+45+1，高位00~11，低位00~99，加上，高位12，低位00~45
如果放8（大于3），那么种数=12*100， 高位00~11，低位00~99
对于每一位，枚举放0~9，统计数量即可。
特别注意，上面的统计方法会统计前导0，最后要减掉带前导0的数量
【代码】
#include<stdio.h>
typedef long long ll;
ll cnt[10]={0};
ll bit[12];
int main()
{
int n,top=0;
scanf("%d",&n);
for(int i=0;i<12;i++) //预处理10的i次幂
bit[i]=(i==0?1:bit[i-1]*10);
for(int i=n;i;i/=10) //数一数数字n的长度
++top;
for(int i=top-1;i>=0;i--) //从高位向低位遍历
{
int pre=n/bit[i+1]; //获取高位数字
int up=n/bit[i]%10; //获取当前数字
int low=n%bit[i]; //获取低位数字
for(int j=0;j<10;j++) //枚举当前位放0~9
{
if(j<up) cnt[j]+=(pre+1)*bit[i]; //随意放
else if(j==up)cnt[j]+=pre*bit[i]+low+1; //高位小 + 高位相等时低位的数量
else if(j>up) cnt[j]+=pre*bit[i]; //比当前位时，高位只能小于pre
}
}
for(int i=top-1;i>=0;i--) //由于上面枚举0时，0会作为前导0，因此减掉个位前导0的次数
cnt[0]-=bit[i];
for(int i=0;i<10;i++)
printf("%lld\n",cnt[i]);
return 0;
}问题 D: 2011的倍数（二）
时间限制: 1 Sec 内存限制: 128 MB
提交: 9 解决: 6
[提交] [状态] [讨论版] [命题人:admin]
题目描述
给定一个正整数n，多少个1组成的整数可以被n整除？
输入
一个整数n（1<=n<=10^5）
输出
一个正整数，表示数字1的个数。如果无解，请输出-1
样例输入
2011样例输出
670【分析】
同余模定理：(a+b)%n=(a%n+b%n)%n; a*b%n=a%n*b%n
一般思路，暴力乘10再加1，直到模除2011等于0。但是数字太大时，C语言不提供大数存储。
令res表示答案，初始为1。状态转移：res=res*10+1，我们要求的是res%n的值，因此状态转移后，让res模除n，对结果是无影响的。
如何判断无解：用vis数组标记每个数字对模除n的余数是否出现过，如果出现过，再次碰到，说明形成了循环，永远找不到模除n等于0的数。
【代码】
#include<stdio.h>
bool vis[200000];
int main()
{
int n,p=1,ans=1;
scanf("%d",&n);
for(int i=0;i<200000;i++)
vis[i]=false;
while(p%n!=0)
{
if(vis[p])
{
ans=-1;
break;
}
vis[p]=true;
p=(p*10+1)%n;
ans++;
}
if(ans==-1)
printf("-1\n");
else
printf("%d\n",ans);
return 0;
}
问题 E: 最多约数问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 19 解决: 8
[提交] [状态] [讨论版] [命题人:admin]
题目描述
正整数 x 的约数是能整除x的正整数，其约数的个数记为div(x)，例如div(10)=4。设 a 和 b 是两个正整数，找出 a 和 b 之间(包含a,b)约数个数最多的数 x 的约数个数
输入
两个正整数a和b，（1<=a<=b<=105）
输出
一个正整数表示答案。
样例输入
1 36样例输出
9【分析】
对于一个数字x，求其因子个数，一般思路，循环1到n，只要模除等于0，即为因子，时间复杂度O(n)，优化思路：循环到1到sqrt(n)，因为对于x的因子a，若a<sqrt(n)，则必然存在b>sqrt(n)，使得a*b=n。若sqrt(n)恰好是个整数，也将是一个因子。时间复杂度O(sqrt(n))
循环a到b，找出最大因子数即可。总时间复杂度O(n*sqrt(n))
【代码】
#include<bits/stdc++.h>
using namespace std;
int get(int x)
{
int res=0;
for(int i=1;i*i<=x;i++)
{
if(x%i==0)res+=2;
if(i*i==x)res--;
}
return res;
}
int main()
{
int a,b,ans=0;
scanf("%d%d",&a,&b);
for(int i=a;i<=b;i++)
{
ans=max(ans,get(i));
}
printf("%d\n",ans);
}问题 F: 最大间隙问题
时间限制: 9 Sec 内存限制: 1024 MB
提交: 34 解决: 7
[提交] [状态] [讨论版] [命题人:admin]
题目描述
给定 n 个实数，求这n个实数在数轴上相邻2个数之间的最大差值，设计解最大间隙问题的线性时间算法（时间复杂度为O(n)）。
输入
第一行一个正整数n（2<=n<=2×107）
第二行n个实数，数据保证这些实数只有一位小数。
输出
一个实数，保留1位小数。
样例输入
5
2.3 3.1 7.5 1.5 6.3样例输出
3.2【分析】
鸽笼原理：将n个鸽子放到n+1个笼子里，不管怎么放，必然至少有一个笼子是空的。
对于输入的n个数字，找到最大值最小值，还剩下n-2个数字，将其放到n-1个区间里，则必然有空区间。
最大间隙一定出现在空区间附近。有可能多个空区间连在一起。
分块n-1个区间，每个区间存储区间内的最大值和最小值。
扫描放好的数轴，记录下最大的空隙即可。总时间复杂度O(3n)
【代码】
#include<bits/stdc++.h>
using namespace std;
const int N=2e7+5;
double Max[N],Min[N],a[N];
int n;
int main()
{
double mx=-1e16,mn=1e16;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf",&a[i]);
mx=max(mx,a[i]);
mn=min(mn,a[i]);
Max[i]=-1e16;
Min[i]=1e16;
}
if(mx==mn)
{
printf("0.0\n");
return 0;
}
double len=(mx-mn)/(n-1); //分成n-1段，每段长度len
for(int i=0;i<n;i++) //把n个数放进去
{
int pos=(a[i]-mn)/len;
Max[pos]=max(Max[pos],a[i]);
Min[pos]=min(Min[pos],a[i]);
}
double ans=0,last=mn;
for(int i=0;i<n;i++)if(Min[i]<1e15)
{
ans=max(ans,Min[i]-last);
last=Max[i];
}
printf("%.1f\n",ans);
}问题 G: 字典序问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 19 解决: 7
[提交] [状态] [讨论版] [命题人:admin]
题目描述
在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写字母组成。该字母表产生的升序字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表中产生的所有长度不超过6的升序字符串，计算它在字典中的编码。
1 | 2 | 3 | … | ab | ac |
a | b | c | | 27 | 28 |
输入
第一行一个整数T，表示测试组数。
接下来T行，每行一个长度不超过6的升序字符串（仅含小写字母）。
输出
输出T行，每行一个整数代表答案。
样例输入
2
a
b样例输出
1
2【分析】
注意是升序字符串。
可以先预处理一个数组 dp[i][j]，用它来表示 以字母 i 开头，长度为 j 的升序字符串有多少个。
求法：dp[i][0]=0, dp[i][1]=1是显然的，j 大于2时，dp[i][j]= dp[i+1][j-1]+dp[i+2][j-1]+...+dp['z'][j-1]；意思是将 i 作为首字母时，后面可以安排 j-1 个字母，且必须以大于 i 的字母开头。
设输入字符串为str，接下来我们数一数有多少串会出现在str前面即可。
可以发现，长度小于str的合法串都在str前面，直接累加一下总数即可，长度等于str的串，需要考虑每一个位置放什么。第一个位置放小于str[0]的字符，或放等于str[0]的字符，需考虑第二位，同样第二位可以放小于str[1]的字符，或等于str[2]的字符并继续考虑第三位。。。。
【代码】
#include<bits/stdc++.h>
typedef long long ll;
ll dp[26][10];
int main()
{
for(int i=25;i>=0;i--)
{
dp[i][1]=1;
for(int j=2;j<10;j++)
{
dp[i][j]=0;
for(int k=i+1;k<26;k++)
{
dp[i][j]+=dp[k][j-1];
}
}
}
int T;
char s[10];
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int n=strlen(s);
ll ans=1;
for(int i=0;i<26;i++)
for(int j=1;j<n;j++)
ans+=dp[i][j];
for(int i=0;i<n;i++)
{
int j=0;
if(i>0)j=s[i-1]-'a'+1;
for(;j<s[i]-'a';j++)
ans+=dp[j][n-i];
}
printf("%lld\n",ans);
}
}问题 H: 金币阵列问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 4 解决: 2
[提交] [状态] [讨论版] [命题人:manager]
题目描述
有m×n(m<=100,n<= 100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。
给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。
输入
输入的第1行有1个正整数k，表示有k组数据。每组数据的第1行有2个正整数m和n。以下的m行是金币阵列的初始状态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的m行是金币阵列的目标状态。
输出
按照输入数据的次序输出计算出的最少变换次数（规则1和2使用的次数之和）,相应数据无解时输出-1。
样例输入
4 3 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1
样例输出
2
【分析】
考虑第一列，其他任意一列都有可能作为第一列而获得最少变换次数，而想要去第一列，就必须变成和目标矩阵第一列相同。
这样就遍历到了所有情况。当第一列定下来后，第一列不符的位置所在行都要进行反转，然后第2~m列就只能进行列列交换了，扫描一下，遇到不行的列，就在后面找个行的换过来。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int src[120][120]; //原矩阵
int temp[120][120];
int aim[120][120]; //目标矩阵
int n,m; //行列
void swapCol(int u,int v) //对temp数组交换两列
{
for(int i=1;i<=n;i++)
swap(temp[i][u],temp[i][v]);
}
void changeRow(int x) //对temp数组翻转第x行
{
for(int j=1;j<=m;j++)
temp[x][j]^=1;
}
int checkCol(int x,int y) //检查temp第k列和aim的第p列是否相同
{
for(int i=1;i<=n;i++)
if(temp[i][x]!=aim[i][y])
return 0;
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&src[i][j]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&aim[i][j]);
}
int ans=INF;
for(int j=1;j<=m;j++) //枚举将第j列作为第一列
{
memcpy(temp,src,sizeof(src)); //把src复制到temp
int res=0;
if(j!=1)//交换两列
{
swapCol(1,j);
res++;
}
for(int i=1;i<=n;i++)
{
if(temp[i][1]!=aim[i][1]) //翻转第i行
{
changeRow(i);
res++;
}
}
for(int k=2;k<=m;k++) //考虑调整后面的列
{
if(!checkCol(k,k))
{
int p=k+1;
while(p<=m&&!checkCol(p,k))p++; //找到后面可以放在k处的拿过来。
if(p>m)
{
res=-1; //没有找到可以放在k列的列，因此这时无解
break;
}
else
{
swapCol(k,p);
res++;
}
}
}
if(res!=-1&&res<ans)
ans=res;
}
if(ans==INF)ans=-1;
printf("%d\n",ans);
}标签：数字,int,样例,金币,算法,2018,提交,习题,输入 From： https://blog.51cto.com/u_16125110/6369255