2020-08-02

拼多多笔试:

第一题略。

第二题: 模拟每个骰子的旋转，对每个状态分组即可。

#include <bits/stdc++.h>
using namespace std;

int v[7][7][7][7][7][7];
int cnt = 0;
bool vis[7];

void rotate(vector<int> a){
    if(v[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]]) return;
    v[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]] = cnt;
    int tmp = a[0];
    a[0] = a[5];
    a[5] = a[1];
    a[1] = a[4];
    a[4] = tmp;
    rotate(a);
    tmp = a[0];
    a[0] = a[4];
    a[4] = a[1];
    a[1] = a[5];
    a[5] = tmp;

    tmp = a[3];
    a[3] = a[4];
    a[4] = a[2];
    a[2] = a[5];
    a[5] = tmp;
    rotate(a);
    tmp = a[3];
    a[3] = a[5];
    a[5] = a[2];
    a[2] = a[4];
    a[4] = tmp;

}
void dfs(vector<int> a, int step){
    if(step==6){
        if(v[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]]) return;
        cnt++;
        rotate(a);
        return;
    }
    for(int i=1;i<=6;i++){
        if(vis[i]) continue;
        vis[i] = 1;
        a.push_back(i);
        dfs(a, step+1);
        a.pop_back();
        vis[i] = 0;
    }

}
int a[10];
map<int,int> m;
int ans[1000];
bool cmp(int a,int b){
    return a>b;
}
int main(){
    vector <int> b;
    dfs(b,0);
    int n;
    scanf("%d",&n);
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int i=0;i<6;i++){
            scanf("%d",&a[i]);
        }
        int cla = v[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]];

        if(m.count(cla)) {
            ans[cla]++;
        }else{
            m[cla] = 1;
            ans[cla]=1;
            cnt++;
        }
    }
    printf("%d
",cnt);
    sort(ans,ans+1000,cmp);
    for(int i=0;i<cnt;i++) printf("%d ",ans[i]);
}

第三题:

偏序问题

 实际上就是要你求， a集合{(X1,Y1), (X2,Y2), (Xn,Yn)} , b集合{(A1,B1), (A2,B2), (Am,Bm)} 中找到

min(Xi + Aj) subject. Yi+Bj<=T

思路是枚举a集合，将b集合按照 B 从小到大排序之后，使用一个MIN数组维护 bi ~ bm 中 A的最小值。

每次二分查找第一个大于等于 T-Yi 的数，然后查询当前的 MIN[i] 即可。

int MIN[100005];
int main(){

    int n,m,T;
    vector <pair<int,int> > a,b;
    vector <int >c;
    scanf("%d%d%d",&n,&m,&T);
    int ans = 1e9;
    if(T==0) ans = 0;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a.push_back({y,x});
        if(y>=T) ans = min(ans,x);
    }
    sort(a.begin(), a.end()); /// 按照
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        b.push_back({y,x});
        if(y>=T) ans = min(ans,x);
    }
    sort(b.begin(), b.end()); /// 按照美味值从小到大进行排序
    for(int i=0;i<m;i++) c.push_back(b[i].first);
    MIN[m-1] = b[m-1].second;
    for(int i=m-2; i>=0;i--){
        MIN[i] = min(MIN[i+1],b[i].second);
    }

    for(int i=0;i<n;i++){
        int need = T-a[i].first;

        int pos = lower_bound(c.begin(),c.end(),need) - c.begin();
        //printf("%d %d
",need, pos);
        if(pos < m){
            //printf("** %d %d
",a[i].first, MIN[pos]);
            ans = min(ans, a[i].second + MIN[pos]);
        }
    }
    if(ans==1e9) printf("-1");
    else printf("%d
",ans);
}