上个星期五晚上打的, 现在来补一下题解. 这是一场毫无悬念的比赛. 眼睁睁地看着C题的通过人数破千, 我却不会做......D一时也没有好的想法. 没有仔细看E题. 所以只完成了A,B. 遇到这种情况我也不知道咋办啊...... 题解: 5/5 # A. Mike and palindrome 字符集为全体小写英文字母. 给一个长度不超过15的字符串. 问是否能恰好改动1个字符, 使其成为回文串.
题面中说恰好. 如果该字符串已经是回文串了呢?
当长度为偶数, YES当且仅当对折后只有1个字符不同. 当长度为奇数, YES当且仅当对折后有0或1个字符不同.
char s[20];
int main()
{
scanf("%s", s);
int n = strlen(s), cnt = 0;
rep (i, 0, n/2)
cnt += s[i] != s[n-1-i];
puts(cnt == 1 || ((n & 1) && !cnt) ? "YES" : "NO");
return 0;
}B. Mike and strings
n个长度不超过50的字符串, 每次操作选择一个串循环左移一位. 问最少多少次操作后, 这些字符串变得相等, 或报告无解. (1≤n≤50)
暴力一番. 枚举第一个串循环左移的次数, 看后面的串最少多少次才能变得和它相等. 有解当且仅当所有串循环同构.
Editorial给了一个DP, 时间复杂度与暴力是相同的.
char s[50][101];
bool cmp(char s[], char t[], int n)
{
rep (i, 0, n)
if (s[i] != t[i])
return false;
return true;
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 0, n)
scanf("%s", s[i]);
int m = strlen(s[0]);
rep (i, 0, n)
copy(s[i], s[i]+m, s[i]+m);
int ans = 1<<30;
rep (i, 0, m) {
int x = i;
rep (j, 1, n) {
bool ok = false;
rep (k, 0, m) {
if (cmp(s[0]+i, s[j]+k, m)) {
ok = true;
x += k;
break;
}
}
if (!ok) {
puts("-1");
return 0;
}
}
ans = min(ans, x);
}
printf("%d\n", ans);
return 0;
}C. Mike and gcd problem
一个长度为n的序列a, 每次操作可以选择两个相邻的数a[i], a[i+1], 用a[i]-a[i+1], a[i]+a[i+1]来替换它们. 问最少多少次操作可以使gcd(a[1],a[2],...,a[n])>1, 或报告无解. (2≤n≤10^5, 1≤a[i]≤10^9)
(a,b) -> (a-b,a+b) -> (-2b,2a)
所以总是有解.
但是, 怎样最小化操作次数呢?
想用DP, 但是得枚举最终的gcd, 而且可能有后效性.
最后几分钟, 猜测了一个解法:
先特判0次操作的情况. 不妨假设现在要把gcd搞成2. 所有数对2取模, 变成0-1序列. 有4种操作: 0 0 -> 0 0 0 1 -> 1 1 1 0 -> 1 1 1 1 -> 0 0
目标是变成全0序列且操作数最少. 不妨从左到右做一个DP, 即便东搞一下西搞一下也是合法的.
正解几乎就是这样. 为什么是2呢? 给一个证明.
设d=gcd(a[1],a[2],...,a[i]-a[i+1],a[i]+a[i+1],...,a[n]), gcd(a[1],a[2],...,a[n])=1.
d|a[i]-a[i+1], d|a[i]+a[i+1] => d|2a[i], d|2a[i+1]. 又 d|a[j] (j!=i, j!=i+1), 所以
d|gcd(a[1],a[2],...,2a[i],2a[i+1],...,a[n])|2gcd(a[1],a[2],...,a[n])=2.
也就是说, 如果先前gcd=1, 经过一次变换, 数列的gcd要么保持为1, 要么变成2. 所以只用考虑怎样快速变到2 (否则, 考虑操作前的gcd, 它已经大于1, 所以本次操作可以省略).
解决这个转化后的问题可以采用贪心的策略. 每一段连续的1可以分开考虑. 设这一段有s个1, 最少操作(floor(s/2) + 2[s mod 2 = 1])次 (先从左到右操作相邻的两个1, 如果s为奇数, 将最后一个单独的1和左/右一起操作两次). 累加即可.
如果这个贪心是正确的, DP可以得出相同的答案, 因为都是从左到右操作.
It can be proved...
How?
没有做出来, 一个原因是, 总是在局部观察, 而没有考虑总体gcd的变化.
const int N = 1e5;
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
int a[N+1];
int main()
{
puts("YES");
int n, d = 0;
scanf("%d", &n);
rep (i, 0, n) {
scanf("%d", a+i);
d = gcd(d, a[i]);
a[i] &= 1;
}
if (d > 1) {
puts("0");
return 0;
}
int ans = 0;
for (int i = 0, j; i < n; i = j+1) {
j = i;
while (a[j]) ++j;
ans += (j-i+1)/2 + ((j-i) & 1);
}
printf("%d\n", ans);
return 0;
}D. Mike and distribution
两个长度为n的序列A,B, 选出[1,n]上k个不同的整数p, 使得2(a[p[1]]+...+a[p[k]])>a[1]+...+a[n], 2(b[p[1]]+...+b[p[k]])>b[1]+...+b[n], 要求k≤floor(n/2)+1. 构造一组解. (1≤n≤10^5, 1≤ai,bi≤10^9, 保证有解)
首先, 条件等价于选中的数之和大于未选的数之和.
如果只有一个序列, 直接取前(n/2+1)大. 现在有两个序列, 我在考虑是否先取一个序列的前(n/2+1)大, 然后调整一番.
不太行得通......
Editorial:
如果只有一个序列, 考虑另一种取法: 从大到小排序, 最大者必选; 接下来, 每相邻两个分一组, 每组任取一个即可; 如果序列的长度为偶数, 选上最后一个.
为什么是正确的呢? 考虑最差情况, 即每组选较小的那个. 对于奇数的情形, 我们选了a[c[1]]+a[c[3]]+...+a[c[n]]>a[c[1]]+a[c[3]]+...+a[c[n-2]]≥a[c[2]]+a[c[4]]+...+a[c[n-1]]; 对于偶数情形, 删掉最后一个数就来到奇数情形.
这种取法相对于粗暴地取前(n/2+1)大更具可扩展性. 现在把B考虑进来, 每组取b较大的那个, 于是b也满足了限制.
题面中保证有解. 上面的算法只要a,b均为正就可以工作.
看到(n/2+1)得产生点联想. 除以2 - 每两个分一组. 加1 - 取最大肯定不亏. 这样的问题中, 常数可能起到关键作用.
const int N = 1e5;
int a[N], b[N], c[N];
bool cmp(int i, int j)
{
return a[i] > a[j];
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 0, n) {
scanf("%d", a+i);
c[i] = i;
}
rep (i, 0, n)
scanf("%d", b+i);
sort(c, c+n, cmp);
printf("%d\n%d ", n/2+1, c[0] + 1);
for (int i = 1; i < n; i += 2)
printf("%d ", (i+1 == n || b[c[i]] > b[c[i+1]] ? c[i] : c[i+1]) + 1);
puts("");
return 0;
}E. Mike and code of a permutation
一个1~n的排列P. 对i=1,...,n, 寻找最小的未标记的j, 使得p[j]>p[i], 令a[i]=j, 标记j; 如果不存在这样的j, 则令a[i]=-1. 现给出序列a, 求构造一个排列P. (1≤n≤5*10^5, 保证有解)
对i拓扑排序可以解决问题, 现在考虑怎样简化构图. 注意到i只向一个挖掉一些点的区间以及单点连边. 联想到之前一道在线段树上建图跑最短路的题. 先倒过来, 变挖点为加点 (其实不变也可以), 然后在可持久化线段树上跑拓扑排序.
实现的时候, 注意我们最终需要的是1~n的编号.
这样可以AC, 但是空间复杂度为O(nlg n), 得开一个1kw+的数组. Editorial给了一个空间复杂度O(n)的算法.
首先, 把a[i]=-1替换为a[i]=n+1以简化讨论. 令b[i]=j当且仅当a[j]=i (可能不存在), 则b[i]之后i被标记.
i向b[i] (如果存在) 和 [1,a[i]) 中满足b[j]≤i的j连边. 不再用邻接表储存. 后者在线段树中查询[1,a[i])中b[j]的最大值及其对应的j. 访问过点v后, 将b[v]置为0.
有些图论算法的时间复杂度为O(|V|+|E|). 通常我们认为这已经很优了, 然而有时|E|会成为瓶颈, 这就需要一些能快速寻找相邻且未访问过的点的方法. 想起Claris的省选十连测, 有一道题用bitset去优化求解强连通分量的Kosaraju算法. 之所以不选择Tarjan, 是因为在Tarjan算法中, 所有边, 无论另一端点是否访问过, 都对low值的计算有贡献.
const int N = 5e5, M = 1e7 + 500;
int ptr = 1, lc[M], rc[M];
vector<int> adj[M];
void insert(int x, int& o, int p, int l, int r)
{
o = ptr++;
if (l == r) return;
int m = (l+r)/2;
if (x <= m) rc[o] = rc[p], insert(x, lc[o], lc[p], l, m);
else lc[o] = lc[p], insert(x, rc[o], rc[p], m+1, r);
}
inline void add(int x, int y)
{
adj[x].push_back(y);
}
void link(int L, int R, int x, int o, int l, int r)
{
if (!o) return;
if (L <= l && r <= R) {
add(x, o);
return;
}
int m = (l+r)/2;
if (L <= m)
link(L, R, x, lc[o], l, m);
if (R > m)
link(L, R, x, rc[o], m+1, r);
}
bool mark[N+1], vis[M];
int num, a[N+1], b[N+1], c[M], root[N+2], ord[N+1];
void topsort(int u)
{
if (vis[u]) return;
vis[u] = true;
rep (i, 0, adj[u].size()) topsort(adj[u][i]);
if (c[u])
ord[c[u]] = ++num;
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 1, n+1) {
scanf("%d", a+i);
if (a[i] > 0)
mark[a[i]] = true;
}
// root[i] - before marking the ith number
rep (i, 1, n+1)
if (!mark[i]) {
insert(i, root[n+1], root[n+1], 1, n);
b[i] = ptr-1;
c[ptr-1] = i;
}
per (i, n, 1) {
if (a[i] == -1)
root[i] = root[i+1];
else {
insert(a[i], root[i], root[i+1], 1, n);
b[a[i]] = ptr-1;
c[ptr-1] = a[i];
}
}
rep (i, 1, ptr) {
if (lc[i]) add(i, lc[i]);
if (rc[i]) add(i, rc[i]);
}
rep (i, 1, n+1) {
if (a[i] == -1) {
if (i > 1) link(1, i-1, b[i], root[i], 1, n);
if (i+1 <= n) link(i+1, n, b[i], root[i], 1, n);
} else {
if (a[i] < i) {
if (a[i] > 1) link(1, a[i]-1, b[i], root[i], 1, n);
} else {
if (i > 1) link(1, i-1, b[i], root[i], 1, n);
if (a[i]-1 >= i+1) link(i+1, a[i]-1, b[i], root[i], 1, n);
}
add(b[a[i]], b[i]);
}
}
rep (i, 1, ptr)
topsort(i);
rep (i, 1, n+1)
printf("%d%c", ord[i], " \n"[i == n]);
return 0;
}