“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛
题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=6463
Problem Description
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
通常来说，题面短的题目一般都比较难，所以我要把题面写得很长很长。
鸽子数字由以下过程定义：从任何正整数开始，将数字替换为其各个数位的平方和，并重复该过程，直到该数字等于1。如果不能，则这个数字不是鸽子数。
例如7是鸽子数，因为7->49->97->130->10->1。（77=49,44+99=97,99+7*7=130…如此类推）
显然1是第一个鸽子数。
有Q个询问，每个询问给出一个数k，你需要输出第k个鸽子数。
Input
第一行一个Q，代表询问的个数（Q<=100000）
接下来Q行，每行一个数字k（k<150000）
Output
每行输出一个数，代表第k个鸽子数
Sample Input
2
1
2
Sample Output
1
7
一做题步骤：
- 看懂题意
- 分析题目，找到隐藏解题条件和方向，注意细节
- 考虑题目使用的算法和解题的思路
- 时间复杂度和算法优化，以及思路优化
- 检查，数组大小和初始化等细节
1 题意：
从任何正整数开始，将数字替换为其各个数位的平方和，并重复该过程，直到该数字等于1。如果不能，则这个数字不是鸽子数。
2.分析问题：
鸽子数一看就明白，但题目要我们找的是第几个鸽子数。
分析1：这是一个规律题，可以考虑是否可以找到它规律。
找规律的方式是打印出格子数或者是鸽子数的一些规律。
分析2：技巧优化，暴力枚举
3 题目使用的算法和解题的思路、
显然根据题目，不会是某一个已经学习的算法，这个是一个需要找出解题思路的题目；
解法思路1：
对于鸽子数，你可以打印每一次循环，是鸽子数和不是鸽子数的数的规律。
你会发现不是鸽子数的时候，每个数运算到一定步骤后都会算到一个数，然后都会走到同样的一步。所以这就是规律！！！！
不是鸽子数的数循环到89 就结束；是鸽子数就循环到1结束。
这样就不会2无限循环了。
解法思路2：
对于这个题目，就是对于一个不是鸽子数的数，平方和后，一定会重复出现某个数，我们用数组记录这个出现的数，然后下次循环到这个数说明此路不同。
对于所有算过的数都标记一下，判断是鸽子数的记录下来，
4.时间复杂度和算法优化
O(1000001*10)左右
5. 检查，数组大小和初始化等细节
题目中的鸽子数的数目，大概有100001多，数组要开大一点；
二 比赛后总结和提高：
- 考察算法
- 思维提升
- 不同解题思路
- 以后做这类题目的时候，应该怎么做
- 需要提高什么？
1.考察算法
无
2.思维提升
这个题目，需要捉住一个重点，数字替换为其各个数位的平方和，并重复该过程，直到该数字等于1。这个过程一开始不知道会不会产生规律，如果你有灵感你会决定不是鸽子数的时候会有走到一个相同的方向，就是每一次位数的平方得到的数字都会走到同一个数。
想不出的时候，敲代码模拟出是鸽子数的规律和不是鸽子数的规律。
这种题目往往需要从逆方向思考，找不是鸽子数的规律。
找规律，我们不仅仅是一个数一个数的规律，也可能是运算过程中的规律。
3.不同解题思路
直接找出运算规律，不找确定出某个值，将运算规律运用。
4.以后做这种题目
先逆方向去想这个问题。
每想法，就代码模拟。
5.需要提高
逻辑能力和逆向思考的能力。
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define ll long long
ll num[150010];
int cnt;
int main()
{
for(ll i=1;;i++)
{
ll mm=i;
while(mm!=1&&mm!=89)//规律
{
ll d=mm;
mm=0;
while(d!=0)
{
mm+=(d%10)*(d%10);
d/=10;
}
}
if(mm==1)
{
num[cnt++]=i;
if(cnt==150000)
break;
}
}
int q,k;
scanf("%d",&q);
while(q--)
{
scanf("%d",&k);
printf("%lld\n",num[k-1]);
}
return 0;
}
链接：http://acm.hdu.edu.cn/showproblem.php?pid=6467
已知
F(n)=∑i=1n(i×∑j=inCij)
求 F(n) mod 1000000007
Input
多组输入，每组输入占一行，包含一个整数n（1 <= n <= 1e18)。
数据不超过300000组。
Output
对于每组输入，输出一行，包括一个数代表答案。
Sample Input
5
100
Sample Output
129
660756544
找出它 的递推式 (n-1)*2^n+1;
然后注意它的数据很大，一般算肯定超时，所以要优化，用快速幂就可以。
附上求快速幂a^bmodc
int ans = 1;
a = a % c;
while(b>0){
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
printf("%d",ans);
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
#define ll long long
int main()
{
ll n,m;
ll mod=1000000007;
while(~scanf("%lld",&n))
{
m=n;
ll sum=1,a=2;
while(n!=0)
{
if(n%2==1)
sum=(sum*a)%mod;
n=n/2;
a=(a*a)%mod;
}
sum=(sum*(m%mod-1)%mod+1)%mod;
printf("%lld\n",sum);
}
}
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6468
zyb的面试
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 560 Accepted Submission(s): 202
Problem Description
今天zyb参加一场面试,面试官听说zyb是ACMer之后立马抛出了一道算法题给zyb:
有一个序列,是1到n的一种排列,排列的顺序是字典序小的在前,那么第k个数字是什么?
例如n=15,k=7, 排列顺序为1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9;那么第7个数字就是15.
那么,如果你处在zyb的场景下,你能解决这个问题吗?
Input
T组样例(T<=100)
两个整数n和k(1<=n<=1e6,1<=k<=n),n和k代表的含义如上文
Output
输出1-n之中字典序第k小的数字
Sample Input
1
15 7
Sample Output
15
Source
“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛
Recommend
liuyiding | We have carefully selected several similar problems for you: 6470 6469 6468 6467 6466
DFS+暴力；
题意是按字典序排序，在n-个中找出第m个数是什么；
按题意，可以很明显就可以知道
1 2
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
100 101 102 103 104 105 106 107 108 109
1000 1001
10000 …
100000 …
解题思路：如果它们之间用树状图表示，我们找字典序的第m小的数也就是从1 开始，向左儿子下面搜索到最后再返回，还有一个地方是，当搜到s>=m时我们就循环return ;结束,否则继续递推搜索，直到找到答案；
#include<stdio.h>
#include<iostream>
using namespace std;
int cc,an,n,m;
void dfs(int x)
{
if(cc>=m)
return ;
an=x;//从1 开始，
cc++;//每一次搜索；
for(int i=x*10;i<=x*10+9&&i<=n;i++)//每一增一层就是十倍，从左到右就是9 个，还要注意的一点是i<=n;不能超过所给的排序的数，
{
dfs(i);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
an=0;
cc=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=9&&i<=n;i++)//排序的数字很明显就只是1-9；
dfs(i);
printf("%d\n",an);
}
return 0;
}
另一种写法（先占坑，后再补）；
#include<stdio.h>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
ll arr[150000];
ll Pow10(ll a)
{
ll sum=1;
for(int i=1;i<=a;i++)
sum*=10;
return sum;
}
//ll Pow10[i*10];
ll haa(ll val)
{
ll tot=0;
while(val)
{
tot++;
val/=10;
}
return tot;
}
ll waha(ll val,ll n)
{
ll Presum=0;
ll Pretot=0;
ll mid=val;
ll top=0;
do{
arr[++top]=mid%10;
mid/=10;
}while(mid);
for(ll i=top;i;--i)
{
Presum=Presum*10+arr[i];//
Pretot+=Presum-Pow10(top-i);
if(i!=0)
Pretot++;
}
for(;;)
{
top++;
Presum*=10;
if(top<haa(n))
{
Pretot+=Presum-Pow10(top-1);
}
else if(top==haa(n))
{
Pretot+=min(Presum,n)-Pow10(top-1);//比较那个小，得出那个位数得排序数；
if(Presum>n)
Pretot++;
return Pretot;
}
else
return Pretot;
}
}
int main()
{
ll u,y;
int t;
while(t--){
scanf("%lld%lld",&y,&u);
printf("%lld\n",waha(u,y));
}
return 0;
}
Count
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 661 Accepted Submission(s): 258
Problem Description
Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.
Input
第一行输入一个T,表示有T组样例
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)
其中，T=104,n<=1018
Output
共T行,每行一个正整数表示所求的答案
Sample Input
5
3
6
9
12
15
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6470
Sample Output
31
700
7486
64651
527023
这道题比赛时超时，问了学长之后，学长交了我矩阵快速幂就AC了；
那现在我先来解决怎么堆出矩阵快速幂，首先就是要知道矩阵是什么，这个知识我就跳过。
我们有题意推出一个公式：F[n]=F[n-1]+2F[n-2]+nnn;
那么我们运用矩阵：
A =[F[n-1] F[n-2] n^3 nn n 1]; 然后在建一个矩阵
B= [1 1 0 0 0 0]
2 0 0 0 0 0
1 0 1 0 0 0
0 0 3 1 0 0
0 0 3 2 1 0
0 0 1 1 1 0
AB，根据矩阵相乘可以得C=[F[n] F[n-1] (n+1)^3 (n+1)(n+1) (n+1) 2]
则，我们可以利用快速幂得模板进行 运算
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=123456789;
const int NN=6;
struct gg
{
ll mm[NN][NN];
};
gg mmll(gg a,gg b)
{
gg ans;
for(int i=0;i<NN;i++)
{
for(int j=0;j<NN;j++)
{
ans.mm[i][j]=0;
for(int k=0;k<NN;k++)
{
ans.mm[i][j]+=a.mm[i][k]*b.mm[k][j]%mod;
ans.mm[i][j]%=mod;
}
}
}
return ans;
}
gg qiupow(gg a,ll b)
{
gg ans;
for(int i=0;i<NN;i++)
for(int j=0;j<NN;j++)
ans.mm[i][j]=0;
for(int i=0;i<NN;i++)
ans.mm[i][i]=1;
while(b)
{
if(b&1)
ans=mmll(ans,a);
a=mmll(a,a);
b/=2;
}
return ans;
}
int A[]={2,1,27,9,3,1};
int main()
{
gg B;//矩阵B；
B.mm[0][0]=1;B.mm[0][1]=1;B.mm[0][2]=0;B.mm[0][3]=0; B.mm[0][4]=0;B.mm[0][5]=0;
B.mm[1][0]=2;B.mm[1][1]=0;B.mm[1][2]=0;B.mm[1][3]=0; B.mm[1][4]=0;B.mm[1][5]=0;
B.mm[2][0]=1;B.mm[2][1]=0;B.mm[2][2]=1;B.mm[2][3]=0; B.mm[2][4]=0;B.mm[2][5]=0;
B.mm[3][0]=0;B.mm[3][1]=0;B.mm[3][2]=3;B.mm[3][3]=1; B.mm[3][4]=0;B.mm[3][5]=0;
B.mm[4][0]=0;B.mm[4][1]=0;B.mm[4][2]=3;B.mm[4][3]=2; B.mm[4][4]=1;B.mm[4][5]=0;
B.mm[5][0]=0;B.mm[5][1]=0;B.mm[5][2]=1;B.mm[5][3]=1; B.mm[5][4]=1;B.mm[5][5]=1;
ll t,n;
scanf("%lld",&t);
while(t--)
{
int a=0;
scanf("%lld",&n);
gg as=qiupow(B,n-2);//B的n-2次幂；
if(n==1)
{
printf("1\n");
continue;
}
if(n==2)
{
printf("2\n");
continue;
}
for(int i=0;i<NN;i++)
{
a+=(A[i]*as.mm[i][0])%mod;
}
printf("%lld\n",a%mod);
}
return 0;
}
