A.Strange Functions
给你一个数n,求在1-n中g(x)的个数。其中g(x)=x/f(f(x)),然后f(x)是求x从个位往前数连续0的个数
输入样例
5
4
37
998244353
1000000007
12345678901337426966631415
输出样例
1
2
9
10
26
思路
找规律,你会发现
1-9 10-99 100-999 1000-9999 …
1 2 3 4 …
所以结果就是n的位数
然后我们就可以直接输入字符串,输出字符串长度就行了
(找规律) $O(1)$
C++ 代码
#include<iostream>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
string s;
cin>>s;
cout<<s.size()<<endl;
}
return 0;
}
B. Jumps
你在一个数轴上,位于坐标0,你可以进行两个操作
1.你可以往前跳k格(k=你这一步操作是第几步操作)
2.你可以往后跳1个
问:给你一个数x,你可以最少花几步到达
输入样例
5
1
2
3
4
5
输出样例
1
3
2
3
4
思路
当你走第k步后,你的坐标v恰好≥x时,可以分成两种情况
1.v-x>1,因为如果你一直往前跳,你分别跳1 2 3 4 5 6 7 8 9 …
你把其中任何一步换成-1，你最终到达的点就变成了v-2,v-3,v-4,v-5 … v-(k+1), 这其中必然有x,所以这种情况只需要走k步
2.v-x==1,根据上述情况分析,我们可以知道我们不能把k步中的任意一步换成-1，
使我们到达x,所以我们必须多走一步 需要走k-1步
分析完毕之后,我们就要去找k了,我这是用二分去找k,因为v=k*(k+1)/2具有单调性。
(二分) $O(log(n))$
C++ 代码
#include<iostream>
using namespace std;
int find(int x){
int l=1,r=x;
while(l<r){
int mid=(l+r)>>1;
if((long long)mid*(mid+1)>=2*x) r=mid;
else l=mid+1;
}
return l;
}
int main(){
int T;
cin>>T;
while(T--){
int x;
cin>>x;
int k=find(x);
int t=k*(k+1)/2;
if(t-x==1)cout<<k+1<<endl;
else cout<<k<<endl;
}
return 0;
}
后面的题明天再写 12.02
C. Ping-pong
Alice和Bob打乒乓,Alice先发球,发球和接球都会消耗一点体力,
Alice和Bob最开始有x点体力和y点体力。如果一个人不接球或者
没有体力接球就算他输。两个人都采取保证自己赢的次数最多情
况下,使对方赢的次数尽可能少的策略。
问:最后两人获胜的次数。
输入样例
3
1 1
2 1
1 7
输出样例
0 1
1 1
0 7
思路
从Alice的角度看,只要Bob接球,Alice就不接,直到Bob只剩
一点体力为止,Alice再接球,这样就可以赢的最多,赢x-1次。
从Bob的角度看,只要Alice每次发球后,我不接,直到Alice还
剩下最后一点体力为止,我在接球和发球,这样Bob就可以赢最
多y场比赛了。
综上,我们其实可以发现Bob和Alice的策略不矛盾，不会互相
影响,都可以成立.所以结果就是x-1和y.
$O(1)$
C++ 代码
#include<iostream>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int A,B;
cin>>A>>B;
cout<<A-1<<' '<<B<<endl;
}
return 0;
}
D.Sequence and Swaps
给你一个长度为n的数组，和一个数x，你可以选择数组中的某个
大于x的元素，将这个元素的值与x的值互换。
问最少需要做多少次这样的操作，才能使得数组为有序(从小到大)。
输入样例
6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324
输出样例
3
0
0
-1
1
3
算法1
(贪心) $O(n^2)$
从前往后遍历,如果我们遇到一个数>x,我们就将其与x交换,直到整个数组有序。
假如存在ai>x和aj>x,并且j>i,然后我们不将ai和x交换,而是将aj和x交换,那么
数组将变为....ai…x… ,则因为ai>x数组不是有序的,所以我们必须从前往后
遍历,不能跳过一些大于x的元素。
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=510;
int x,res,n;
bool solve(vector<int>& a){
res=0;
if(is_sorted(a.begin(),a.end()))
return true;
for(int i=0;i<n;i++)
if(a[i]>x){
swap(a[i],x);
res++;
if(is_sorted(a.begin(),a.end()))
return true;
}
return false;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>x;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
if(solve(a)) cout<<res<<endl;
else puts("-1");
}
return 0;
}
