List Reshape

题目大意

将一组数分成若干组按特定格式输出。

如输入：

4

[3, 1, 4, 1, 5, 9, 2, 6]

2 4

[998, 244, 3, 5, 3]

5 1

[1, 1, 2, 3, 5, 8, 13, 21, 34]

1 9

[2, 3, 5, 7, 11, 13, 17, 19, 23]

3 3

输出：
[[3, 1, 4, 1], [5, 9, 2, 6]]

[[998], [244], [3], [5], [3]]

[[1, 1, 2, 3, 5, 8, 13, 21, 34]]

[[2, 3, 5], [7, 11, 13], [17, 19, 23]]

解题思路

先读入整行到字符串，然后取出里面所有数，模拟按照题意格式输出即可。

参考代码

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<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=1;

const int N=5e5+10;
int x,y;
string s;
int a[N];
void solve(){
    getline(cin,s);

    getline(cin,s);
    int m=s.size();
    cin>>x>>y;
    int x=-1;
    int n=0;
    for(int i=0;i<m;i++){
        if(s[i]>='0'&&s[i]<='9'){
            if(x==-1){
                x=s[i]-'0';
            }else{
                x=x*10+s[i]-'0';
            }
        }else{
            if(x!=-1){
                a[n++]=x;
                x=-1;
            }
        }
    }
    cout<<'[';
    for(int i=0;i<n;i+=y){
        if(i!=0){
            cout<<", ";
        }
        cout<<'[';
        for(int j=i;j<i+y;j++){
            cout<<a[j];
            if(j!=i+y-1){
                cout<<", ";
            }
        }
        cout<<']';
    }
    cout<<']';
    cout<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Shortest path

题目大意

给你一个数n，初始值为1，每次可以对他进行 乘2/乘3/加1 三种操作之一，问最小操作次数。

解题思路

由于从1到n的情况数比n到1多的多，所以我们考虑从n向1搜索，但肯定不能完全暴力。

可以发现，除以2或除以3的操作比减1进行的贡献要优的多。我们应考虑将减1作为该数不能整除2或整除3时来使用这一操作。

这里采用记忆化搜索，能有效降低时间复杂度。

时间复杂度：

参考代码

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
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=1;
int ans=1e18;
int n;

unordered_map<int,int> mp;

int dfs(int n){
    if(n==1) return 0;
    if(mp[n]) return mp[n];
    int res1=2e18,res2=2e18;
    if(n>=2){
        res1=n%2+1+dfs(n/2);
    }
    if(n>=3){
        res2=n%3+1+dfs(n/3);
    }
    int res=min(res1,res2);
    return mp[n]=res;
    
}

void solve(){
    ans=1e18;
    cin>>n;
    
    cout<<dfs(n)<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}