这场比赛很有特点, 前4题想清楚之后都可以用几行搞定 (不过我比较喜欢换行 QAQ)...... 但是D题花了好一段时间......结果就是又掉Rating了 TAT F题很妙, 没想到暴力可AC......但是暂时不会证明时间复杂度. 题解: 5.5/6 # A. Fake NP 把[l,r]中所有整数的大于1的约数写下来, 问哪个出现次数最多. 如果有多个答案, 任意输出一个. (2 ≤ l ≤ r ≤ 10^9, l,r是整数)
诶? 不是模拟......
感觉2应该出现了很多次, 除非l=r且为奇数, 这时候输出l就好啦. 手动验证了一下就提交了......
想出一个证明, 但感觉不是很优雅: x, k是正整数, k>2. ceil(x/k) > floor(x/2) => x < 3 + 4/(k-2). 当k≤6, 暴力验证. 当k>6, 对 x>3 有 ceil(x/k) ≤ floor(x/2), 对x=2,3, 这一不等式显然成立.
int main()
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", l == r ? l : 2);
return 0;
}B. 3-palindrome
用a,b,c构造一个长度为n且不含长度为3的回文子串的字符串, 并要求c出现次数尽可能少. 如有多种答案, 任意输出一个. (1≤n≤2*10^5)
不妨从aa开始往后添加字符. 发现s[i+1]可由s[i-1]确定 - 它们必须且只须不同.
int main()
{
int n;
scanf("%d", &n);
if (n == 1) {
puts("a");
return 0;
}
int x = 0, y = 0;
printf("aa");
rep (i, 2, n) {
int z = x^1;
putchar('a' + z);
x = y;
y = z;
}
puts("");
return 0;
}C. Find Amir
n个点标号1~n, i->j的费用为 (i+j) mod (n+1) 且可以一次付费可正反通行无限次. 求到达所有点的最小费用 (起始点任选). (1 ≤ n ≤ 10^5)
一开始犯了个很逗的错误......以为总费用只需最后取一次模......
这是最小生成树, 来贪心一发.
费用为0的边:
1 n
2 n-1
3 n-2
.
.
.
ceil(n/2)-1 floor(n/2)+2
ceil(n/2) floor(n/2)+1
费用为1的边:
2 n
3 n-1
4 n-2
.
.
.
ceil(n/2) floor(n/2)+2
ceil(n/2)+1 floor(n/2)+1当n为偶数, 需要连 ceil(n/2) 条费用为0的边, ceil(n/2)-1 条费用为1的边.
当n为奇数, 需要连 ceil(n/2)-1 条费用为0的边, ceil(n/2)-1 条费用为1的边.
综上, 输出 ceil(n/2)-1 = floor((n-1)/2) 即可.
D. Minimum number of steps
一个由a,b构成的字符串, 每个操作把ab替换成bba, 不存在子串ab则停止. 问最少多少步后停止, 答案对 10^9 + 7 取模. 字符串长度不超过10^6.
读完题之后没什么头绪......不确定答案是否和操作顺序无关, 于是在考虑怎样避免这个问题 (而不是大胆猜想/仔细分析......).
随着通过的人数越来越多......发现yp同学一小时前就切掉了这题 Orz......也没想到其他思路了, 那么不妨假设对于多个ab, 无论采取怎样的操作顺序, 得到的答案都相同.
目标是把串变成这样: bbb...bbaaa...aa.
从左往右构造. 设前i个已经变成 bbb...bbaaa...aa 的形式: - s[i+1] = 'a', 啥也不用做. - s[i+1] = 'b'. 设前面有x个'a'. 考虑 abbb..bb -> bbbb...bbba, 设这个a跨过y个b, 则变完之后b的数量加倍. 那么, 这种情况下, 将产生(2^x-1)个新的b, 即操作数增加(2^x-1).
想一下假设为什么是正确的. 如果存在一个子串ab, 它就不会消失, 总得替换它. aabb -> abbab, 替换后可能和相邻的字符形成新的ab, 可以通过调整顺序避免吗? 不行.......
咦? 好像一切很显然......
活该掉Rating......
typedef long long ll;
const int MOD = 1e9 + 7, N = 1e6;
char s[N+1];
int main()
{
scanf("%s", s);
ll ans = 0, p2 = 1;
for (int i = 0; s[i]; ++i) {
if (s[i] == 'a')
(p2 *= 2) %= MOD;
else
(ans += p2 - 1 + MOD) %= MOD;
}
cout << ans << endl;
return 0;
}E. Ice cream coloring
一棵n个结点的树T, 每个结点上写着一些数 ([1,m]内的整数), 并且满足所有写了x的结点构成一个连通子图. 构造一张新的无向图G, m个结点, u和v有边当且仅当T存在一个结点同时写着u,v. 求G的最小染色数, 并构造一种方案. (1≤n,m≤3*10^5)
这题倒是会做, 但我没办法用2分钟写出来......而且第二天实践的时候忽略了一个 corner case, 写出来也会 FST......TAT
苟非吾之所有, 虽一毫而莫取......
一般图的最小染色数是NP-Hard问题. 所以, P=NP被证明或推翻之前, 只要是求最小染色数且数据范围较大, 必定是用贪心, DP一类的方法, 或者题目中给的是二分图......
区间图是这样一类图: 可以将顶点对应到数轴上的区间, 使得u,v有边当且仅当u,v对应的区间相交.
求区间图的最小染色数, 将区间按左端点排序, 从左到右, 给顶点赋予不冲突且编号最小的颜色即可.
证明: 首先, 最小染色数 ≥ 最大团. 然后, 显然本算法产生的解合法, 并且最大编号 ≤ 最大团.
推论: 区间图的最小染色数 = 最大团. 这个结论在弦图中也成立, 区间图是一种特殊的弦图.
本题把 "区间" 的概念推广到了树上. 改排序为DFS即可.
注意: 有的数可能没出现在任何结点上.
#define iter iterator
const int N = 3e5, M = 3e5;
int color[M+1];
vector<int> adj[N+1], S[N+1];
void dfs(int u, int p)
{
set<int> U;
U.insert(0);
rep (i, 0, S[u].size()) {
int j = S[u][i];
if (color[j])
U.insert(color[j]);
}
set<int>::iter it = U.begin();
rep (i, 0, S[u].size()) {
int j = S[u][i];
if (!color[j]) {
while (U.find(*it + 1) != U.end())
++it;
U.insert(color[j] = *it + 1);
++it;
}
}
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p)
dfs(v, u);
}
}
int main()
{
int n, m, c = 1;
scanf("%d%d", &n, &m);
rep (i, 1, n+1) {
int s;
scanf("%d", &s);
c = max(c, s);
rep (j, 0, s) {
int x;
scanf("%d", &x);
S[i].push_back(x);
}
}
rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
printf("%d\n", c);
rep (i, 1, m+1)
printf("%d%c", color[i] ? color[i] : 1, " \n"[i == m]);
return 0;
}F. Expected diameter of a tree
n个点m条边的森林, q个询问: 令U,V分别为u,v所在的连通块, 如果U=V, 输出-1; 否则, 等可能地从U,V各任取一个点连起来, 求新连通块的直径的期望. 询问并不真的改变图的结构, 相对误差不超过10^-6即认为正确. (1 ≤ n, m, q ≤ 10^5)
一开始犯了个很逗的错误......忽略了直径不经过新边的情况.
要求 E[max(X+Y, c)]. 最大值的期望......有什么方法吗?
捣鼓了一下式子, 没发现什么好预处理的. 瞥了一下神犇们的代码, 发现大都有一句: if (sz[u] > sz[v]) swap(u, v);. 又瞥了一下 Div.1 里本题的 Tag. Brute Force? Binary Search?
令sz[x] < sz[y]. 把连通块y中所有点的最远距离排序, 则单次暴力时间复杂度可以做到 O(sz[x] lg sz[y]). 如果某个连通块多次作为x, 那么它的大小不会很大. 加个记忆化.
Editorial说这样做的复杂度是O(n^1.5 lg n). 证明待填.
可以从特殊情形理解一下. 假设每个连通块大小相等, 共有k个连通块, 则每个连通块大小n/k. 本质不同的询问数是O(k^2). 如果都问到, 则 k = O(q^0.5). 于是, 总的复杂度为O(q^0.5 n lg n).
typedef pair<int, int> ii;
typedef long long ll;
const int N = 1e5;
vector<int> adj[N+1], d[N+1];
vector<ll> sum[N+1];
int rt[N+1], sz[N+1], dis[N+1];
ii get_farthest(int u, int p)
{
ii ret(0, u);
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p) {
ii t = get_farthest(v, u);
++t.first;
ret = max(ret, t);
}
}
return ret;
}
void cal_dis(int u, int p, int d)
{
dis[u] = max(dis[u], d);
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p) cal_dis(v, u, d+1);
}
}
void dfs(int u, int p, int r)
{
rt[u] = r;
++sz[r];
d[r].push_back(dis[u]);
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p) dfs(v, u, r);
}
}
double query(int x, int y)
{
static map<ii, double> M;
if (sz[x] > sz[y]) swap(x, y);
map<ii, double>::iterator it = M.find(ii(x, y));
if (it != M.end())
return it->second;
ll ans = 0, c = max(d[x].back(), d[y].back()) - 1;
rep (i, 0, d[x].size()) {
ll t = d[x][i];
int j = lower_bound(d[y].begin(), d[y].end(), c-t) - d[y].begin();
// t + d[0..j) < c
ans += c * j + t * (d[y].size() - j) + sum[y][j];
}
return M[ii(x, y)] = 1 + (long double)ans / sz[x] / sz[y];
}
int main()
{
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
rep (i, 0, m) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
rep (i, 1, n+1) if (!rt[i]) {
int x = get_farthest(i, 0).second, y = get_farthest(x, 0).second;
cal_dis(x, 0, 0);
cal_dis(y, 0, 0);
dfs(i, 0, i);
sort(d[i].begin(), d[i].end());
sum[i].resize(d[i].size()+1);
sum[i][d[i].size()] = 0;
per (j, d[i].size()-1, 0)
sum[i][j] = d[i][j] + sum[i][j+1];
}
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
x = rt[x];
y = rt[y];
if (x == y)
puts("-1");
else
printf("%.9f\n", query(x, y));
}
return 0;
}