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;
}
#蚂蚁笔试##蚂蚁#
