topcpder SRM 664 div2 A,B,C BearCheats ， BearPlays equalPiles ， BearSorts （映射）

时间：2022-04-06 11:15:42

A题，熊孩子测视力，水题，题意就是判断一下两个数对应位不相同的数字有多少个。

#include<bits/stdc++.h>

using namespace std;

class BearCheats{

    public:

         string eyesight(int A, int B){

            int digA[],digB[];

            int t = ;

            while(A){

                digA[t++] = A%;

                A/=;

            }

            for(int i = ; i < t; i++){

                digB[i] = B%;

                B/=;

            }

            int dif = ;

            for(int i = ; i < t; i++){

                if(digA[i]!=digB[i]) dif++;

            }

            if(dif<=) return "happy";

            else return "glasses";

         }

};

Pro A

B题，熊孩子合并石子，题意是给你三堆石子，每次可以选两个，设小的那堆石子数为X，大的那堆石子为Y，X变成2*X，Y变成Y-X。问最后可不可能使三堆石子数相同。

div2的数据，暴力dfs就过了。因为石子总数一定，状态可以只有两维。

给用数论的大神orz

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

bool vis[maxn][maxn];

bool dfs(int *dat)

{

    if(dat[] == dat[] && dat[] == dat[]) return true;

    int ndat[]= {dat[]<<,dat[]-dat[],dat[]};

    sort(ndat,ndat+);

    if(!vis[ndat[]][ndat[]] && ( vis[ndat[]][ndat[]] = true,dfs(ndat))) return true;

    ndat[] = dat[]<<; ndat[] = dat[]; ndat[] = dat[] - dat[];

    sort(ndat,ndat+);

    if(!vis[ndat[]][ndat[]] && ( vis[ndat[]][ndat[]] = true,dfs(ndat))) return true;

    ndat[] = dat[]; ndat[] = dat[]<<; ndat[] = dat[] - dat[];

    sort(ndat,ndat+);

    if(!vis[ndat[]][ndat[]] && ( vis[ndat[]][ndat[]] = true,dfs(ndat))) return true;

    return false;

}

class BearPlaysDiv2{

public:

    string equalPiles(int A, int B, int C){

        if( (A+B+C)/* != A+B+C ) return "impossible";

        int dat[] = {A,B,C};

        sort(dat,dat+);

        vis[dat[]][dat[]] = true;

        if(dfs(dat)) return "possible";

        else return "impossible";

    }

};

Pro B

C题，熊孩子排序，熊孩子乱搞了一个LESS函数，返回true和false的概率各占一半，问用一个排好序的序列经过sort以后得到给出序列的概率，其实就是问你比较次数。。。映射一下就完了。

举个栗子：比如要得到的序列是2，4，3，1。那么它和有序的映射是如左边所示，那么以原来的数字为key排序就得到了右边的映射，

topcpder SRM 664 div2 A,B,C BearCheats ， BearPlays equalPiles ， BearSorts （映射）

怎么得到原来的映射呢？只要反过来，以右边的val做为key,key变成val。在排序就得到原来的映射了（这也就是为什么原来的映射一定要是有序的原因）。这和我们原来的问题有什么关系呢？当然有，观察下面的key，

在这个反过来sort的过程中，下面的1 2 3 4变成了 2 4 3 1，正是我们要得到的序列。

类似思路的题：CDOJ 485

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

int a[maxn];

int t[maxn];

const double onecmp = log(0.5);

int times;

void merge_sort(int* a,int l,int r)

{

    if(r-l<=) return ;

    int mid = (l+r)>>;

    merge_sort(a,l,mid);

    merge_sort(a,mid,r);

    int i = l, j = mid, k =l,p;

    while(i < mid && j < r){

        if(times++,a[i]>=a[j]) t[k] = a[j++];

        else t[k] = a[i++];

        k++;

    }

    if(i == mid) for(p = j; p < r; p++) t[k++] = a[p];

    else for(p = i; p < mid; p++) t[k++] = a[p];

    for(k = l;k < r; k++) a[k] = t[k];

}

class BearSortsDiv2{

public:

    double getProbability(vector <int> seq){

        for(int i = ; i < seq.size(); i++){

            a[seq[i]-] = i;

        }

        times = ;

        merge_sort(a,,seq.size());//log(ans);double ans =

        return times*onecmp;

    }

}Bear;

/*

int main()

{

    freopen("in.txt","r",stdin);

    vector<int> s;

    int tmp;

    while(~scanf("%d",&tmp))

        s.push_back(tmp);

    double ans = Bear.getProbability(s);

    printf("%lf",ans);

    return 0;

}

*/

相关文章