顺丰笔试8月29日

第一题：字符串转化

字符串的驼峰表示法仅将除第一个单词外的单词首字母大小,例如：myName。而下划线表示法中所有单词小写，但是会用下划线隔开，例如my_name。给出n个字符串，若是驼峰表示法，将其转化为下划线表示法输出，若是下划线表示法则直接输出，否则输出"indistinct";

#include<bits/stdc++.h>  
using namespace std;  
int main() {  
    int n;  
    cin >> n;  
    string s;  
    for (int i = 0; i < n; i++) {  
        cin >> s;  
        if ((s[0] >= 'A' && s[0] <= 'Z') || s[0] == '_'){  
            cout << "indistinct"<<endl;  
            continue;  
        }  
        string res;  
        bool camel = false;  
        bool down = false;  
        bool next = false;  
        for (char c:s) {  
            if (c >= 'A' && c <= 'Z') {  
                char nc = c + 32;  
                res = res + '_' + nc;  
                camel = true;  
                continue;  
            }  
            if (c =='_') {  
                if (next) {  
                    camel = true;  
                }  
                down = true;  
                next = true;  
            }  
            else next = false;  
            res = res + c;  
        }  
        if ((camel && down) || next ) cout << "indistinct"<<endl;  
        else cout << res << endl;  
    }  
    return 0;  
}

需要排除_开头结尾、大写字母开头和连续下划线的特殊情况

第二题：排列房子

小岛上有n(n <= 15)间房子，每间房子都有着对应的价值，要求相邻两个房子的价值一定为整数倍(例如房子1的价值是2的倍数或房子2价值为1的倍数)，请问有多少种排列

#include<bits/stdc++.h>  
using namespace std;  
int main() {  
    int n;  
    cin >> n;  
    int h[18];  
    for (int i = 0; i < n; i++) {  
        cin >> h[i];  
    }  
    //使用状态压缩表示排布方法  
    // dp[i][j] i表示当前集合，j表示前一个房子  
    int dp[100005][15];  
    memset(dp, 0, sizeof(dp));  
    for (int i = 0; i < n; i++) {  
        int s = (1 << i);  
        dp[s][i] = 1;  
    }  
    for (int i = 1; i < (1 << n); i++) {  
        for (int j = 0; j < n; j++) {  
            if (i & (1 << j)) {  
                //枚举的dp[i][j]存在则找 dp[i - j][k],k则是与j满足条件的房子  
                for (int k = 0; k < n; k++) {  
                    if (((1 << k) & (i ^ (1 << j))) && (h[j] % h[k] == 0 || h[k] % h[j] == 0)) {  
                        dp[i][j] += dp[i ^ (1 << j)][k];  
                    }  
                }  
            }  
        }  
    }  
    int res = 0;  
    for (int i = 0; i < n; i++) {  
        res += dp[(1 << n) - 1][i];  
    }  
    cout << res;  
    return 0;  
}