教育场 = 教你编程的场次 or 教你做人的场次? 比赛时完成前4题. E题是一个需要一点小技巧/脑洞的数学题, F的标签是 data structures, geometry, 好像是在凸壳上搞事, 至今只有一人AC. 由于是unrated, 右边栏没有下降的分值表影响心情, 又由于是教育场, 不分pretest和system test, 状态稍微好一些. 题解: 5/6 为了节省版面, 下面的代码把宏和using指令省略了.
A. New Bus Route
数轴上有n个不同的点, 给出它们的坐标, 求两点间最小距离和距离最小的点的对数. 距离定义为坐标之差的绝对值. (2≤n≤2*10^5, -109≤ai≤109)
距离最小的两点一定是相邻的, 排序即可.
const int N = 2e5;
int a[N];
int main()
{
int n;
cin >> n;
Rep (i, 0, n) cin >> a[i];
sort(a, a+n);
int mn = 2e9 + 1, cnt = 0;
Rep (i, 1, n) {
if (a[i] - a[i-1] < mn) {
mn = a[i] - a[i-1];
cnt = 0;
}
if (a[i] - a[i-1] == mn)
++cnt;
}
cout << mn << " " << cnt << endl;
return 0;
}B. Counting-out Rhyme
n个小朋友从1开始编号围成一圈, 进行k轮游戏. 一开始1是领袖. 第i轮, 领袖顺时针数的第ai个人 (包括自己) 离开, 并钦定离开者的下一位当领袖. 求每轮离开的人的编号. (2≤n≤100, 1≤k≤n-1, 1≤ai≤10^9)
教育场不求题目新颖, 而要凸显教育意义. 本题即约瑟夫问题的变种. 由于n很小, 模拟即可, 但是ai可以很大, 所以对圈内人数取个模.
const int N = 100;
int a[N], pre[N + 1], nxt[N + 1];
int main()
{
int n, k;
cin >> n >> k;
Rep (i, 0, k) cin >> a[i];
For (i, 1, n) {
pre[i] = i-1;
nxt[i] = i+1;
}
pre[1] = n;
nxt[n] = 1;
int s = 1;
Rep (i, 0, k) {
a[i] %= n-i;
while (a[i]--)
s = nxt[s];
printf("%d%c", s, " \n"[i == k-1]);
nxt[pre[s]] = nxt[s];
pre[nxt[s]] = pre[s];
s = nxt[s];
}
return 0;
}C. Divide by Three
一个所含数字不超过10^5的十进制数, 去掉个数最少的数字 (可以为0), 使得新数不含前导0且能被3整除 (可以为0), 求一种方案. 无解输出-1.
比赛时我的做法比Editorial暴力, 但是思路简单一些. 首先一个数能被3整除当且仅当数位和能被3整除. 计算数位和. 特判去掉0个数字的情况. 接下来需要判断能否去掉一些数字, 它们的数位和等于现在的数位和. 去掉模等于0的数是没有意义的, 除非是去掉其他的数导致产生了前导0. 模等于1或2的数, 每种去掉多于2个也是没有意义的. 所以, 枚举一下, 从低位往高位删数字 (尽量避免产生前导0), 再删去高位的0. 最后特判得到0的情况.
通过一点讨论, 可以减小常数. 特判去掉0或1个数字的情况. 如果还没搞定, 一定是只有模3等于1的数, 或者只有模3等于2的数. 而(2+2) mod 3 = 1, (1+1) mod 3 = 2, 所以仍有希望搞定. 可以像上面那样从低位往高位贪心地删数字, 不是很明白Editorial在做什么.
const int L = 1e5;
string s, ans;
bool f[L + 1];
int get(int x, int y)
{
int cnt = 0, first = s.size();
fill_n(f, s.size(), false);
Down (i, s.size()-1, 0) {
if (x && (s[i]-'0')%3 == 1)
--x;
else if (y && (s[i]-'0')%3 == 2)
--y;
else
f[i] = true, ++cnt, first = i;
}
if (x || y) return 0;
while (first < (int)s.size() && s[first] == '0') {
f[first++] = false;
--cnt;
while (first < (int)s.size() && !f[first])
++first;
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin >> s;
int sum = 0;
Rep (i, 0, s.size())
(sum += s[i] - '0') %= 3;
if (sum == 0) {
cout << s << endl;
return 0;
}
For (i, 0, 2) For (j, 0, 2)
if ((i + j*2) % 3 == sum && get(i, j) > (int)ans.size()) {
ans.clear();
Rep (k, 0, s.size())
if (f[k])
ans.push_back(s[k]);
}
if (!ans.size()) {
if (s.find('0') < s.size())
cout << "0" << endl;
else
cout << "-1" << endl;
} else
cout << ans << endl;
return 0;
}D. Paths in a Complete Binary Tree
用中序遍历给n个结点的完全二叉树 (叶子全在同一层的满二叉树) 编号, q个询问, 每次给一个初始位置和一个序列 (Up, Left, or Right), 问结束位置在哪里, 忽略不合法的操作. (1≤n≤10^18, 序列的长度之和不超过10^5)
以前研究过这个问题, 但是不够深入啊. 一种紧凑的线段树存储方法 (后来并没有使用这种方法)
我用栈维护了一下根到当前结点的结点序列和子树大小, 所有选择右子树的结点, 模拟了一发.
Editorial给的方法是bitmask. 观察到实际上有:
inline ll right_child(ll x)
{
return x + (lowbit(x) >> 1);
}
inline ll left_child(ll x)
{
return x - (lowbit(x) >> 1);
}
inline ll parent(ll x)
{
ll t = lowbit(x);
return (x & (t << 1)) ? x - t : x + t;
}我的模拟:
typedef long long ll;
const int D = 70;
ll v[D], sz[D];
int top = 0;
stack<ll> R;
inline void go_up()
{
if (top == 1) return;
--top;
if (R.top() == v[top-1]) R.pop();
}
inline void go_left()
{
if (sz[top-1] == 1) return;
sz[top] = (sz[top-1]-1)/2;
v[top] = R.top() + (sz[top]-1)/2 + 1;
++top;
}
inline void go_right()
{
if (sz[top-1] == 1) return;
R.push(v[top-1]);
sz[top] = (sz[top-1]-1)/2;
v[top] = R.top() + (sz[top]-1)/2 + 1;
++top;
}
int main()
{
ios::sync_with_stdio(false);
ll n, q;
cin >> n >> q;
R.push(0);
while (q--) {
ll u;
string s;
cin >> u >> s;
top = 1;
v[0] = (n+1)/2;
sz[0] = n;
while (v[top-1] != u) {
if (u < v[top-1]) go_left();
else go_right();
}
Rep (i, 0, s.size()) {
switch (s[i]) {
case 'U':
go_up(); break;
case 'L':
go_left(); break;
case 'R':
go_right(); break;
}
}
cout << v[top-1] << endl;
while ((int)R.size() > 1) R.pop();
}
return 0;
}E. Colored Balls
有n种颜色的球, 每种求ai个. 将它们分组, 使得: 所有球属于某个组, 不存在空组, 每组球的颜色相同, 任意两组元素个数之差的绝对值不超过1. 求最少组数. (1≤n≤500, 1≤ai≤10^9)
已知一组的最小规模, 每种颜色的最优分组是确定的. 设某种颜色的球有
枚举
typedef long long ll;
const int N = 500;
const ll inf = 1e9 * 500LL + 1;
int n;
ll a[N];
ll cal(ll x)
{
ll ans = 0;
Rep (i, 0, n) {
ll l = (a[i]+x)/(x+1), r = a[i]/x;
if (l <= r) ans += l;
else return inf;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
ll ans = inf, mn = inf;
cin >> n;
Rep (i, 0, n) {
cin >> a[i];
mn = min(mn, a[i]);
}
for (ll x = 1; x*x <= mn; ++x)
ans = min(ans, cal(x));
for (ll k = 1; k*k <= mn; ++k) {
ll x = mn/k;
ans = min(ans, cal(x));
if (mn % k == 0 && x > 1)
ans = min(ans, cal(x - 1));
}
cout << ans << endl;
return 0;
}