9.20美团笔试-算法-4道AC Code

// A 
// 六位数字ABCDEF均不同，A不能为0, 算[n, m]之间满足AB + CD = EF的六位数有几个
// 暴力枚举 + check
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5+5;
const int inf = 1e7;
const ll mod = 1e9+7;

map<int, int> mp;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = 0;
    for(int i=n; i<=m; i++){
        int tmp = i;
        vector<int> v;
        int flag = 1;
        mp.clear();
        while(tmp){
            if(mp.count(tmp % 10) > 0){
                flag = 0;
                break;
            }
            mp[tmp%10] = 1;
            v.push_back(tmp%10);
            tmp /= 10;
        }
        if(!flag) continue;
//        FEDCBA
//        012345
        if(v[5] == 0) continue;
        if(v[5] * 10 + v[4] + v[3] * 10 + v[2] == v[1]*10 + v[0]){
            ans ++;
        }
    } 
    printf("%d\n", ans);
    return 0;
}

// B 
// 给图，O是得分，X是扣分，得分扣分仅一次，按照一个序列WASD四个方向走，问最后得分是多少
// 按照序列走就行，注意边界保持不动，得分扣分仅一次
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 505;
const int inf = 1e7;
const ll mod = 1e9+7;

string a[maxn];
string s;

int main(){
    int n, m, p, q;
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    cin >> s;

    int x = -1, y = -1;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(a[i][j] == 'S'){
                x = i;
                y = j;
                break;
            }
        }
        if(x != -1) break;
    } 

    int ans = 0;
    int dy[] = {-1, 0, 1, 0};
    int dx[] = {0, 1, 0, -1};
    map<char, int> dir;
    dir['A'] = 0;
    dir['W'] = 3;
    dir['D'] = 2;
    dir['S'] = 1;
    for(int i=0; i<s.size(); i++){
        int nx = x + dx[dir[s[i]]];
        int ny = y + dy[dir[s[i]]];
        if(nx >= n || nx < 0 || ny >=m || ny < 0 || a[nx][ny] == '#') continue;
        if(a[nx][ny] == 'O') ans += p;
        if(a[nx][ny] == 'X') ans -= q;
        a[nx][ny] = '+';
        x = nx;
        y = ny;    
//        cout<<i<<", "<<s[i]<<", "<<x<<", "<<y<<endl;
    }
    printf("%d\n", ans);
    return 0;
}


// C
// 字符串s和t，问t若是s的子串，则t在s中对应字母下标和最小是多少，下标从1开始
// 贪心 + 二分搜索
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5+5;
const int inf = 1e7;
const ll mod = 1e9+7;

string s, t;
vector<int> v[26];

/*
4 2
aaaa
aa
*/

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    cin >> s;
    cin >> t;
    for(int i=0; i<n; i++){
        v[s[i] - 'a'].push_back(i);
    }
    int idx = -1;
    long ans = 0;
    for(int i=0; i<m; i++){
        char c = t[i] - 'a';
        if(v[c].size() == 0 || v[c][v[c].size()-1] <= idx){
            printf("No\n");
            return 0;
        }
        else{
            int p = upper_bound(v[c].begin(), v[c].end(), idx) - v[c].begin();
            idx = v[c][p];
            ans += v[c][p] + 1;
        }
    }
    printf("Yes\n");
    printf("%ld\n", ans);
    return 0;
}

// D
// 求无根树最大最小权之差最大的子节点编号，若有多个返回编号最小的节点，子节点对应的子树节点数<=k
// dfs暴力计算每个子节点对应子树的大小，最大权，最小权即可
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
const int inf = 1e9 + 7;
const ll mod = 1e9+7;

int w[maxn];
int maxw[maxn];
int minw[maxn];
int cnt[maxn];
int mark[maxn];
vector<int> g[maxn];
int n, k, root;

void dfs(int u, int &ans){
    mark[u] = 1;
    for(int i=0; i<g[u].size(); i++){
        int v = g[u][i];
        if(mark[v]) continue;
        dfs(v, ans);
        cnt[u] += cnt[v];
        maxw[u] = max(maxw[u], maxw[v]);
        minw[u] = min(minw[u], minw[v]);
    }
    if(cnt[u] <= k && maxw[u] - minw[u] >= maxw[ans] - minw[ans]){
//        cout<<u<<", "<<cnt[u]<<", "<<maxw[u]<<", "<<minw[u]<<", "<<ans<<endl;
        if(maxw[u] - minw[u] > maxw[ans] - minw[ans] || u < ans){
            ans = u;
        }
    }
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
        maxw[i] = w[i];
        minw[i] = w[i];
        cnt[i] = 1;
        mark[i] = 0;
    }
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u); 
    }
    scanf("%d", &root);
    int ans = n+1;
    maxw[ans] = 0;
    minw[ans] = 0;
    cnt[ans] = n+1;
    dfs(root, ans);
    printf("%d\n", ans);
    return 0;
}