9/26蚂蚁笔试（没a）

t1：二分，但是注意直接算会爆ull，记得改用除法就可以过

#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
typedef vector<ll> VLL;
typedef vector<int> VI;
#define lowbit(x) ((x)&(-(x)))
#define bitcnt(x) (__builtin_popcountll(x))

int main() {
    ull m; cin >> m;
    ull n = 2*m-1;
    ull l = 1; ull r = n;
    while(l < r) {
        ull mid = (l+r)>>1;
        if ((2*m-1+mid)/mid < mid) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    if ((2*m-1+l)/l < l) {
        cout << l-1 << endl;
    } else {
        cout << l << endl;
    }
    return 0;
}

t2：还是二分

#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
typedef vector<ll> VLL;
typedef vector<int> VI;
#define lowbit(x) ((x)&(-(x)))
#define bitcnt(x) (__builtin_popcountll(x))

int main() {
    ll n; ll k; cin >> n >> k;
    string s; cin >> s;
    unordered_map<char, int> map;
    rep(i, 0, n) {
        map[s[i]-'a']++;
    }
    if (map.size() > k) { cout << -1 << endl; return 0; }
    int r = n; int l = 1;
    while(l < r) {
        int mid = (l+r)>>1;
        int sum = 0;
        for (auto&& it : map) {
            sum += (it.second+mid-1)/mid;
        }
        if (sum > k) {
            l = mid+1;
        } else {
            r = mid;
        }
    }
    cout << l << endl;
    return 0;
}

t3：写了快一个小时没a掉，我的思路是找出所有叶子结点，计算所有叶子结点间的距离，然后从所有叶子结点中选出2个距离最大的，分别标记一个颜色，然后再从剩下的叶子结点里选两个距离最大的，设置合适的颜色，重复这个步骤直到所有叶子结点都被标记。然后从所有叶子结点多头bfs，没有被染色的结点就被染色成bfs过来的上一个结点的颜色，只过了26+%

其实写完第一版代码就只剩10分钟了，第一次交过了20%，后来修了点bug多过了点，但是代码其实还没写完。不知道这种方法OK不OK，有没有大佬a了的看看解法，附题目

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#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
typedef vector<ll> VLL;
typedef vector<int> VI;
#define lowbit(x) ((x)&(-(x)))
#define bitcnt(x) (__builtin_popcountll(x))

void bfs(unordered_map<int, vector<int>> edge_map, int cur, vector<bool>& visited, vector<vector<int>>& distance, vector<int> leaves) {
    visited[cur] = true;
    if (edge_map[cur].size() == 1) return;
    rep(i, 0, edge_map[cur].size()) {
        int target = edge_map[cur][i];
        if (visited[target]) continue;
        bfs(edge_map, target, visited, distance, leaves);
        rep(j, 0, leaves.size()) {
            distance[cur][leaves[j]] = min(distance[cur][leaves[j]], 1+distance[target][leaves[j]]);
        }
    }
    return;
}

int main() {
    ll n; cin >> n;
    unordered_map<int, vector<int>> edge_map;
    vector<int> leaves;
    vector<vector<int>> distance(n+1, vector<int>(n+1));
    vector<bool> color(n+1);
    rep(i, 0, n-1) {
        int from, to; cin >> from >> to;
        edge_map[from].push_back(to);
        edge_map[to].push_back(from);
    }
    for (auto&& it : edge_map) {
        if (it.second.size() == 1) {
            leaves.push_back(it.first);
        }
    }
    for (int i = 0; i < leaves.size(); i++) {
        for (int j = 0; j < leaves.size(); j++) {
            if (i != j)
                distance[leaves[i]][leaves[j]] = n;
        }
    }
    vector<bool> visited(n+1);
    bfs(edge_map, 1, visited, distance, leaves);
    // 最大的直径一定在两个叶子结点间产生
    // 这两个一定要染成不同颜色
    // 计算所有叶子结点之间的距离
    // 确定所有叶子结点的颜色后，从每个叶子结点开始染色
    unordered_map<int, bool> colored; int left = n; queue<int> q; 
    while(left > n-leaves.size()) {
        pair<int, int> big_pair = make_pair(0, 0);
        for (int i = 0; i < leaves.size(); i++) {
            for (int j = i+1; j < leaves.size(); j++) {
                if (distance[leaves[j]][leaves[i]] > distance[big_pair.fi][big_pair.se] && !(colored[leaves[i]] && colored[leaves[j]]))
                    big_pair = make_pair(leaves[i], leaves[j]);
            }
        }
        if (colored[big_pair.fi]) { color[big_pair.se] = ~color[big_pair.fi]; q.push(big_pair.se); colored[big_pair.fi] = true; left--; }
        else if (colored[big_pair.se])  { color[big_pair.fi] = ~color[big_pair.se]; colored[big_pair.se] = true; left--; q.push(big_pair.fi); }
        else {
            color[big_pair.fi] = true; // true: R, false: B
            colored[big_pair.fi] = true; left--;
            colored[big_pair.se] = true; left--;
            q.push(big_pair.fi); q.push(big_pair.se);
        }
        
    }
    while(q.size() > 0) {
        int cur = q.front(); q.pop();
        for (auto next : edge_map[cur]) {
            if (colored[next]) continue;
            colored[next] = true;
            color[next] = color[cur];
            q.push(next);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << (color[i]?"B":"R");
    }
    cout << endl;
    return 0;
}

#蚂蚁笔试##蚂蚁#