阿里7.22笔试题

1.给一个n（<=10），按字典序输出1~n的排列。（要求排列中相邻数字绝对值不为1）

输入：

4
输出：
2 4 1 3
3 1 4 2

n<=10 直接暴力搞

vector ans;
int vis[11];
int n;
void dfs(int x,vi a){
    vis[x] = 1;
    a.push_back(x);
    if(a.size() == n) {vis[x] = 0; ans.push_back(a); return;}
    for(int i = 1; i <= n; i++){
        if(abs(x-i) != 1 && !vis[i]) dfs(i,a);
    }
    vis[x] = 0;
}
int main(){
    vector a;
    cin >> n;
    for(int i = 1; i <= n; i++)
        dfs(i,a);
    sort(ans.begin(),ans.end());
    for(auto c:ans) {
        for(int i = 0; i < n; i++) cout << c[i] << " \n"[i == n-1];
    }
}

2. 给一个n个数字（1e5）。求有多少个区间出现最多的数字的次数大m。
输入：
5 2
1 2 1 2 5
输出：
5
解释：区间[1,3][1,4][1,5][2,4][2,5]五个区间中最多的数字大于2。

枚举区间左端点。set维护一下出现最多的次数。

int main(){
    int n, m, r = 0;
    cin >> n >> m;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    long long ans=0;
    multiset<int> s;
    for(int i = 0; i < n; ++i){
        while(r < n && (s.empty() || -*s.begin() < m)){
            if(s.find(-c[a[r]]) != s.end()) s.erase(s.find(-c[a[r]]));
            ++c[a[r]];
            s.insert(-c[a[r]]);
            r++;
        }
        if(!s.empty() && -*s.begin() >= m)ans += (n-r+1);
        if(s.find(-c[a[i]]) != s.end()) s.erase(s.find(-c[a[i]]));
        c[a[i]]--;
        s.insert(-c[a[i]]);
    }
    cout << ans << endl;
}