美团笔试3.13（C++）

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int st[105][105];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            cin>>st[i][j];
        }
    }
    int maxSum = max(n,m);
    for(int i = 1;i <= maxSum; ++i ) {
        for (int j=1;j<=maxSum;++j) {
            if (i == j) break;
            swap(st[i][j],st[j][i]);
        }
    }
    for(int i = 1;i<=m;++i) {
        for (int j = 1;j<n;++j) {
            printf("%d ",st[i][j]);
        }
        printf("%d\n",st[i][n]);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
using namespace std;
stack<char>st1,st2;
string getStringFromSt() {
    string s;
    while(st2.size() > 1 && st2.top() == '0') {
        st2.pop();
    }
    while (!st2.empty()) {
        s += st2.top();
        st2.pop();
    }
    return s;
}
string ans[1020];
int sum = 0;
void getAns() {
    string s = getStringFromSt();
    if(s.size() != 0) {
        ans[sum++] = s;
    }
}
bool cmp(string string1,string string2) {
    if (string1.size() == string2.size()) {
        return string1 < string2;
    } else {
        return string1.size() < string2.size();
    }
}
int main() {
    char str[2000];
    cin>>str;
    int len = strlen(str);
    for (int i = 0;i<len;++i) {
        st1.push(str[i]);
    }
    while(!st1.empty()) {
        if (st1.top() <= '9' && st1.top() >= '0') {
            st2.push(st1.top());
        } else if(!st2.empty()){
            getAns();
        }
        st1.pop();
    }
    getAns();
    sort(ans,ans + sum,cmp);
    for (int i=0;i<sum;++i) {
        cout<<ans[i] <<'\n';
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;
const int maxn = 1e5 + 7;
struct node {
    int val,sum;
    bool operator<(const node&c)const{
        if(c.sum==sum){
            return val>c.val;
        }
        else{
            return sum < c.sum;
        }
    }
};
map<int,int>mp;
set<node>valSet;
int s[maxn];
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    int p;
    node tmp;
    for (int i = 1;i<=n;++i) {
        scanf("%d",&s[i]);
        p = s[i];
        tmp.sum = mp[p];
        tmp.val = p;
        if(tmp.sum > 0) {
            valSet.erase(valSet.find(tmp));
        }
        tmp.sum++;
        mp[p]++;
        valSet.insert(tmp);
        if (i > m) {
            tmp.val = s[i - m];
            tmp.sum = mp[s[i - m]];
            valSet.erase(valSet.find(tmp));
            tmp.sum--;
            mp[s[i-m]]--;
            if (tmp.sum > 0) {
                valSet.insert(tmp);
            }
        }
        if (i >= m) {
            tmp = *--valSet.end();
            printf("%d\n",tmp.val);
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;
const int maxn = 1e5 + 7;
vector<int>edges[maxn];
long long posVal[maxn];
long long dp[maxn][3][3];
void dfs(int u,int fa) {
    
    long long sumIfChoose = 0;
    long long minNumIfChoose = posVal[u];
    for(int v:edges[u]) {
        if(v == fa) continue;
        dfs(v,u);
        sumIfChoose += dp[v][0][0];
        minNumIfChoose = min(minNumIfChoose,dp[v][0][1]);
    }
    dp[u][1][0] = dp[u][1][0] + sumIfChoose;
    dp[u][1][1] = minNumIfChoose;

    long long sumIfNoChoose = 0;
    long long minNUmIfNoChoose = 1e9+7;
    for(int v:edges[u]) {
        if(v == fa) continue;
        if (sumIfNoChoose < sumIfChoose - dp[v][0][0] + dp[v][1][0]) {
            sumIfNoChoose = sumIfChoose - dp[v][0][0] + dp[v][1][0];
            minNUmIfNoChoose = dp[v][1][1];
        } else if (sumIfNoChoose == sumIfChoose - dp[v][0][0] + dp[v][1][0]){
            minNUmIfNoChoose = min(minNUmIfNoChoose,dp[v][1][1]);
        }
        sumIfNoChoose = max(sumIfNoChoose,sumIfChoose - dp[v][0][0] + dp[v][1][0]);
    }
    dp[u][0][0] = sumIfNoChoose;
    dp[u][0][1] = minNUmIfNoChoose;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i<=n; ++i) {
        scanf("%lld",&posVal[i]);
        dp[i][0][1] = 1e9+7;
    }
    int u,v;
    for(int i=1;i<=m;++i) {
        scanf("%d %d",&u,&v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    dfs(1,0);
    printf("%lld %lld\n",max(dp[1][1][0],dp[1][0][0]),min(dp[1][0][1],dp[1][1][1]));
    return 0;
}