京东笔试9/16

t1 求站在某级台阶上最多可以高过多少人

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <unordered_map>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define se second
#define fi first
typedef vector<ll> VLL;
typedef vector<int> VI;
#define lowbit(x) ((x)&(-(x)))

int main() {
    ll n, m, H; cin >> n >> m >> H;
    vector<ll> heights(n);
    rep(i, 0, n) cin >> heights[i];
    vector<ll> stages(n);
    rep(i, 0, n) cin >> stages[i];
    vector<ll> nums(m);
    ll max_num = 0;
    rep(i, 0, m) { cin >> nums[i]; max_num = max(max_num, nums[i]); }
    ll cnt = 0;
    rep(i, 0, n) {
        if (H+max_num > heights[i]+nums[stages[i]-1])
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

t2，问删除树中的叶子结点，先删除者是否可以先删除x号结点，一开始理解错了题意，其实就是算从这个点出发的边的数量和剩余边的数量的关系。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <unordered_map>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define se second
#define fi first
typedef vector<ll> VLL;
typedef vector<int> VI;
#define lowbit(x) ((x)&(-(x)))
#define bitcnt(x) (__builtin_popcountll(x))

int main() {
    ll t; cin >> t;
    rep(i, 0, t) {
        ll n, x; cin >> n >> x;
        vector<vector<ll>> edges(n-1, vector<ll>(2));
        unordered_map<ll, vector<ll>> edge_map;
        rep(j, 0, n-1) {
            cin >> edges[j][0] >> edges[j][1];
            edge_map[edges[j][0]].push_back(edges[j][1]);
            edge_map[edges[j][1]].push_back(edges[j][0]);
        }
        int cnt = edge_map[x].size();
        if (cnt == 1) cout << "win" << endl;
        else cout << ((((n-1-cnt)%2 == 1)^(cnt%2 == 1))? "win":"lose") << endl;
    }
    return 0;
}

t3 问x如何操作可以变成y，可以对x的操作为：1. 增加t，其中t是2的幂且t&x!= 0; 2.减小t，其中t是2的幂且t&x!= 0。

注意到每次对x操作不会增加其中1的数量，只会减少或者不变，所以可以利用这个写循环。

从highbit出发，贪心就好了，一开始写的从lowbit出发贪心，但是从lowbit贪心会引发进位的问题，比如x=3,y=6

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <unordered_map>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define se second
#define fi first
#define lowbit(x) ((x)&(-(x)))
#define bitcnt(x) (__builtin_popcountll(x))

ll highbit(ll x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x - (x>>1);
}

int main() {
    ll x, y; cin >> x >> y;
    if (bitcnt(x) < bitcnt(y)) {
        cout << -1 << endl;
        return 0;
    }
    string s;
    ll cnt = 0;
    while(bitcnt(x) >= bitcnt(y) && x != y) {
        while(highbit(x) == highbit(y)) {
            x -= highbit(x);
            y -= highbit(y);
        }
        while(highbit(x) > highbit(y)) {
            cnt++; s += ("- "+to_string(highbit(x))+"\n");
            x -= highbit(x);
        }
        while(highbit(x) < highbit(y)) {
            cnt++; s += ("+ "+to_string(highbit(x))+"\n");
            x += highbit(x);
        }
    }
    if (x == y) {
        cout << cnt << endl;
        cout << s;
    } else {
        cout << -1 << endl;
    }
    return 0;
}