TopCoder 636 B 【暴力】

我就是我 2022-08-13 06:29 147阅读 0赞

题意：给出一个排列，其中的一些数字不小心给擦掉了。但是知道这个序列满足 i < j && a\[ i \] < a\[ j \] 的元素对有n个，然后让你求还原这个排列之后有几个排列是满足条件的

分析：很简单很暴力，暴力填入擦掉的值，然后看有多少对元素，然后比较就好。

代码：

#include <cstdlib>
    #include <cctype>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <iostream>
    #include <sstream>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <fstream>
    #include <numeric>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stdexcept>
    #include <functional>
    #include <utility>
    #include <ctime>
    using namespace std;
    
    #define PB push_back
    #define MP make_pair
    
    #define REP(i,n) for(i=0;i<(n);++i)
    #define FOR(i,l,h) for(i=(l);i<=(h);++i)
    #define FORD(i,h,l) for(i=(h);i>=(l);--i)
    
    typedef vector<int> VI;
    typedef vector<string> VS;
    typedef vector<double> VD;
    typedef long long LL;
    typedef pair<int,int> PII;
    
    
    class SortishDiv2
    {
            public:
            int ways(int sortedness, vector <int> seq)
            {
                int ans = 0;
                int vis[200],dis[200];
                int pps[200];
                memset(vis,0,sizeof(vis));
                memset(dis,0,sizeof(dis));
                for(int i=0;i<seq.size();i++)
                {
                    dis[seq[i]]=1;
                    if(seq[i]==0)
                    {
                        vis[i]=1;
                        continue;
                    }
                    for(int j=i+1; j<seq.size();j++)
                    {
                        if(seq[i]==0)
                            continue;
                        if(seq[i]<seq[j])
                            ans++;
                    }
                }
                sortedness -= ans;
                int count = 0;
                vector<int> cc,wei;
                for(int i=1;i<=seq.size();i++){
                    if(dis[i]==0){
                        cc.push_back(i);
                    }
                    if(vis[i-1])
                        wei.push_back(i-1);
                }
                if(cc.size()==0)
                    return sortedness==0;
                do
                {
                    ans = 0;
                    for(int i=0;i<seq.size();i++)
                        pps[i] = seq[i];
                    for(int i = 0;i<wei.size();i++)
                    {
                        for(int k=0;k<seq.size();k++)
                        {
                            if(pps[k]==0)
                                continue;
    
                            if(k>wei[i] && pps[k]>cc[i] || k<wei[i] && pps[k]<cc[i]){
                                ans++;
                            }
                        }
                        pps[wei[i]]=cc[i];
                    }
                    if(ans == sortedness)
                        count++;
                }while(next_permutation(cc.begin(),cc.end()));
                cc.clear();
                wei.clear();
                return count;
            }
    };
    
    int main()
    {
        freopen("Input.txt","r",stdin);
            SortishDiv2 a;
            int n;
            vector<int> v;
            while(~scanf("%d",&n))
            {
                for(int i=0;i<n;i++)
                {
                    int x;
                    scanf("%d",&x);
                    v.push_back(x);
                }
                cout<<a.ways(n,v)<<endl;
                v.clear();
            }
            return 0;
    }