T1 5050. 排序
签到题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <iostream>
using namespace std;
#include <algorithm>
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int tt;
cin>>tt;
while(tt--){
int k;
cin>>k;
string s;
cin>>s;
sort(s.begin(),s.end());
cout<<s<<"\n";
}
}
|
T2 5051. 翻转
题意：有一个\(1\sim n\) 的排列，现在求是否找得到一个区间使得\([l,r]\) 里的数字反转后让数组变成\(1,2，..，n\)
思路：找到第一个\(a[i]≠i\) 的点，并且\(i\) 在\(a[j]\) ，找到这个\(j\) 并翻转\([i,j]\) ，如果翻转后符合就是这个，否则无解。证明：如果翻转这个区域后仍然不符合，说明这个区间是错的，但不翻转这个区间，\(i\) 就永远回不到他原本争取的位置，所以不翻转这个区间也是错的，故只有这个解。
代码：
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
37
38
39
40
41
|
#include <iostream>
using namespace std;
#include <algorithm>
const int N=1e4+7;
int a[N];
int ansl,ansr;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(a[i]!=i){
for(int j=1;j<=n;j++){
if(a[j]==i){
if(j>i){
ansl=i,ansr=j;
}
else ansl=j,ansr=i;
break;
}
}
}
}
int l=ansl,r=ansr;
while(l<r){
int t=a[l];
a[l]=a[r];
a[r]=t;
l++;
r--;
}
for(int i=1;i<=n;i++)if(a[i]!=a[i-1]+1){
cout<<"0 0";
return 0;
}
cout<<ansl<<" "<<ansr;
return 0;
}
|
T3 5052. 排列
题意：已知，\(a1,a2,…,an\) 是 \(1∼n\) 的全排列中字典序第 kk 个排列。
请你判断，一共有多少个整数 \(x\)同时满足以下所有条件：
- \(1≤x≤n\)
- \(x\) 的十进制表示不含 4和 7 以外的数字。
- \(a_x\) 的十进制表示不含 4 和 7 以外的数字。
思路：首先\(x\) 枚举只含\(4,7\) 的数字很容易，然后判断\(x\le n\) 也很容易，再看看\(k\) 是不是合法的，由于直接求阶乘再比较不可行，由于只关注\(n!\) 与\(k\) 的大小，所以可以先线性求\(n!\) ，如果过程中大于了\(k\) 就是合法的，否则就是不合法的。
\(n\) 的全排列有\(n!\) 种，现在的瓶颈就在于求第\(k\) 个全排列的做法，我们考虑第一位放\(1\) ，后面的\((n-1)\) 位可以有\((n-1)*(n-2)*(n-3)..=(n-1)!\) 种选择，如果\(k>(n-1)!\) ，说明放\(1\) 的字典序中前面的数都没有大于\(k\) ，考虑放\(2\) ，则有\((n-2)!\) 种选择，以此类推，但这里求阶乘与\(k\) 的大小仍然用到了与前面相同的手法，以此类推。
这里介绍一个数学方法：康托展开 ，可以用这个公式获取第\(k\) 个排列，但仍然解决不了问题，因为\(n\) 的范围也非常大，如果强行套公式也过不了，容易发现我们的\(n\) 的排列的长度虽然巨大，但只关注第\(k\) 个的第\(x\) 位，而\(x ，也就是说我们关注的第\(x\) 位不会超过\(10^9\) ，我们如何快速找到第\(k\) 个排列的第\(j\) 位呢？
不难发现康托展开真正改变的是\(\exists v∈[1,n],fact(v)\le k\) 往后，例如\(n=3,k=1\) ，容易发现前几个排列为：\(1,2,3/,1,3,2,/2,1,3..\) ，所以只需要找到序列中第一个满足这个条件的\(v\) ，如果\(v\) 的位置大于了\(x\) ，说明\(a_x\) 不需要变（因为后面的字典序变化产生的不同结果已经超过了\(k\) 个），否则就从\(v\) 开始寻找第\(x\) 个位置的数字(这个应用已记录至组合数学那章)
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=20;
ll n,k;
ll ans=0;
ll fact(int n){
ll res=1;
for(int i=1;i<=n;i++){
res*=i;
if(res>k)return k+1;
}
return res;
}
int b[N];
int get(int x){ //获取第k位
int v=1,kk=k;
while(fact(v)<k)v++;//找到最后一个小于k的阶乘
if(x<=n-v)return x;
//由于(v)!是第一个大于k的
for(int i=1;i<=20;i++)b[i]=0;
for(int i=n-v+1;i<=n;i++) { //n-v就是他的正序位置 n-v+1就不大了
for(int j=1;j<=v;j++){ //枚举后v位
if(!b[j]){ //康托展开
ll p=fact(n-i); //第i个位置的阶乘是(n-i)!
if(p<kk)kk-=p;
else{
if(x==i)return j+(n-v);//增量加上基准位置
b[j]=1;
break;
}
}
}
}
return -1;
}
int check(int x){
string s=to_string(x);
for(int i=0;i<s.size();i++){
if(s[i]!='4'&&s[i]!='7')return false;
}
return true;
}
void dfs(ll x){//形参要用LL
if(x>n)return;
if(x&&check(get(x)))ans++;
dfs(x*10+7);
dfs(x*10+4);
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>k;
if(fact(n)<k){
cout<<"-1\n";
return 0;
}
dfs(0);
cout<<ans<<"\n";
}
|