网易互娱服务端4a题解(cpp)

阿已经连续微众拼多多网易互娱快乐ak了 希望周一能拿到美团oc结束0offer悲剧
t4 简单分析可知是一个有向无环图 可以通过构建一个连接全部节点的虚节点进行队列优化的BFS

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 100
using namespace std;
vector<int>G[maxn];
void addedge(int l,int r){
    G[l].push_back(r);
}
int boxes[100][3];
int main(){
    int boxesRowLen;
    cin >> boxesRowLen;
    for(int i = 0; i < boxesRowLen; i++){
        cin >> boxes[i][0] >> boxes[i][1] >> boxes[i][2];
        addedge(0,i+1);
    }
    for(int i = 0; i < boxesRowLen; i++){
        for(int j = 0; j < boxesRowLen; j++){
            if(boxes[i][0] < boxes[j][0] && boxes[i][1] < boxes[j][1] && boxes[i][2] < boxes[j][2]) {
                addedge(i+1,j+1);
            }
         }
    }
    queue<int>que;
    bool inq[maxn];
    memset(inq,0,sizeof(inq));
    int dist[maxn];
    memset(dist, -1, sizeof(dist));
    dist[0] = 0;
    que.push(0);
    int ans = 0;
    while(!que.empty()) {
        int k = que.front();
        inq[k] = 0;
        que.pop();
        for(int i = 0; i < G[k].size(); i++){
            int v = G[k][i];
            if(dist[v] == -1 || dist[v] < dist[k] + 1){
                dist[v] = dist[k]+1;
                ans = max(ans,dist[v]);
                if(!inq[v]){
                    inq[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    cout << ans;
}

t3 恶心lenDFS 就正常暴搜 我在最后10min才发现新选择的节点还要对其依赖进行放置，并确保没和不喜欢的放在一起，改了7min差3min就***叹人生的时候莫名其妙过了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#define maxn 9
#define maxm 9
#define maxx 52
using namespace std;
bool hate[maxx][maxx];
bool lov[maxx][maxx];
char nam[maxx];
int pick[maxm][maxn];
bool vis[maxx];
int n,m;
inline int toid (int i, int j){
    return i*m + j;
}
bool flg = 0;
void DFS(int tm,int tn){
    if(flg)
    return;
    if(tn == n){
        flg = 1;
        //cout << "adsdasdasdas";
        return;
    }
    if(pick[tm][tn] == -1){
        for(int i = 0; i < m; i++){
            int t = toid(tn,i);
            if(!vis[t]) {
                bool flgg = 1;
                for(int j = 0; j < tn; j++){
                    int c = pick[tm][j];
                    if(hate[c][t]){
                        flgg = 0;
                        break;
                    }
                }
                queue<int>que;
                que.push(t);
                queue<int>quee;
                while(!que.empty()){
                    int k = que.front();
                    que.pop();
                    for(int j = 0; j < n; j++){
                        if(pick[tm][j] == -1)
                        continue;
                    int c = pick[tm][j];
                    if(hate[c][k]){
                        flgg = 0;
                        break;
                    }
                }
                for(int j = 0; j < maxx; j++){
                    if (j == t)
                    continue;
                    if(lov[t][j]){
                        if(!vis[j] && pick[tm][j/m] == -1){
                            que.push(j);
                            quee.push(j);
                            pick[tm][j/m] = j;

                        } else if(pick[tm][j/m] == j){
                            continue;
                        }else{
                            flgg = 0;
                        }
                    }
                }

                }

                if(flgg){
                    vis[t] = 1;
                    pick[tm][tn] = t;
                    if(tm == m-1)
                    DFS(0,tn+1);
                    else
                    DFS(tm+1,tn);
                    if(flg)
                    return;
                    vis[t] = 0;
                    pick[tm][tn] = -1;
                }
                while(!quee.empty()){
                    int k = quee.front();
                    quee.pop();
                    pick[tm][k/m] = -1;
                    vis[k] = 0;
                }
            }
        }
    }else{
        if(tm == m-1)
            DFS(0,tn+1);
        else
            DFS(tm+1,tn);
    }
    return;
}
int main(){

    cin >> n >> m;
    memset(pick,-1,sizeof(pick));
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j++) {
            int c = toid(i,j);
            cin >> nam[c];
        }
    }
    int ai,aj,bi,bj;
    char c;
    while(cin >> ai >> aj >> c >> bi >> bj) {
        if(ai == 0)
        break;
        if(c == 'N'){
            int ta = toid(ai-1,aj-1), tb = toid(bi-1,bj-1);
            //cout << "hate" << nam[ta] << " " << nam[tb] << endl;
            hate[ta][tb] = 1;
            hate[tb][ta] = 1;
        }
        if(c == 'Y'){
            int ta = toid(ai-1,aj-1), tb = toid(bi-1,bj-1);
            //cout << "love" << nam[ta] << " " << nam[tb] << endl;
            lov[ta][tb] = 1;
            lov[tb][ta] = 1;
        }
    }
    queue<int>que;
    for(int i = 0; i < m; i++){
        que.push(i);
        vis[i] = 1;
        pick[i][0] = i;
        while(!que.empty()){
            int k = que.front();
            que.pop();
            for(int j = 0; j < m*n; j++){
                if(lov[k][j] && !vis[j]){
                    pick[i][j/m] = j;
                    vis[j] = 1;
                    que.push(j);
                }
            }
        }
    }
    /*for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j ++) {
            cout<<pick[i][j] << " ";
        }
        cout <<endl;
    }*/
    DFS(0,1);
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++) {
            cout<< nam[pick[i][j]];
        }
        cout <<endl;
    }
}

t2 把两个数组从小到大排序一下，对员工技能熟练度从小到大遍历 同时使用一个指针来找到可以被当前员工完成的全部任务的个数k，然后就1(k1-i1+1)(k2-i2+1)..... 就出来了
一开始完全没思路 后来看着看着数据觉得 333 321 = 6有点奥妙重重 然后就想出来了

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 100000
using namespace std;
int t[maxn],c[maxn];
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    for(int i = 0; i < n; i++){
        cin >> c[i];
    }
    long long m;
    cin >> m;
    int j = 0;
    long long ans = 1;
    sort(t,t+n);
    sort(c,c+n);
    for(int i = 0; i < n; i++){
        while(j < n && c[j] <= t[i])
        j++;
        if(c[j] > t[i] || j == n)
        j--;
        //cout  << j+1-i<<endl;
        ans*=(j+1-i);
        ans%=m;
    }
    cout << ans;
}

t1 简单字符串操作 写的时候因为今天一天就睡了4个小时 出现了无数的bug 希望能赶紧被给个offer 焦虑的天天睡不着可太难受了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
    string num1,num2;
    cin >> num1 >> num2;
    //num1 = "";
    //num2 = "";
    int num1pos = num1.size();
    for(int i = 0; i < num1.size(); i++){
        if(num1[i] == '.') {
            num1pos = i;
            break;
        }
    }
    int num2pos = num2.size();
    for(int i = 0; i < num2.size(); i++){
        if(num2[i] == '.') {
            num2pos = i;
            break;
        }
    }
    string num1r = "";
    if(num1pos != num1.size())
    num1r = num1.substr(num1pos+1,num1.size() - num1pos);
    string num2r = "";
    if(num2pos != num2.size())
    num2r = num2.substr(num2pos+1,num2.size() - num2pos);
    string num1l = num1.substr(0,num1pos);
    string num2l = num2.substr(0,num2pos);
    //cout << num1l << endl << num1r << endl << num2l << endl << num2r<<endl;
    if(num1r.size() < num2r.size()){
        string k = num2r;
        num2r = num1r;
        num1r = k;
    }
    //cout << num1r << endl;
    int jin = 0;
    for(int i = num1r.size() - 1; i >= 0; i--){
        if( i < num2r.size() ){
            int k = num2r[i] + num1r[i] + jin;
            k -= 96;
            jin = k/9;
            k = k%9;
            num1r[i] = k+'0';
        }
    }
    if(num1l.size() < num2l.size()){
        string k = num1l;
        num1l = num2l;
        num2l = k;
    }
    for(int i = 0; i < num1l.size(); i++){
        if(i < num2l.size() || jin != 0){
            int k = num1l[num1l.size() - i -1] - 48 + jin;
            if(i < num2l.size())
            k += num2l[num2l.size() - i -1] - 48;
            jin = k/9;
            k = k%9;
            num1l[num1l.size() - i -1] = k+'0';
        }
    }
    string c = "";
    if(jin != 0)
    c += "1";
    c+=num1l;
    if(num1r.size()){
        c+=".";
        c+=num1r;
    }
    cout << c;
}