6

AtCoder Regular Contest 128

 2 years ago
source link: http://www.shuizilong.com/house/archives/atcoder-regular-contest-128/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

arc 好难。。。

讨论一下最后保留哪个，然后就很容易了。

D – Neq Neq

看起来有点像 zuma 那个题。。。不过转移感觉不是很好想。。
首先如果是 x,y,x,y,x … 这样的交错序列，答案就是斐波那契数列，一旦合并之后状态就会被分割。
那么用类似 上次那个题 的方法，可以用相同的相邻元素 x,x 将状态分割成独立的子问题，最后答案用乘法原理乘起来即可。

考虑不存在相邻元素相等的子问题，考察某个区间能否把中间的元素全部合并掉，
判定的条件是，长度 <= 3 或者这个区间有 3 种不同的元素，因为相邻的元素不同，总是可以用第三种元素作为支点反复消，不难用归纳法证明。

设 f[i] 表示以 i 元素结尾的方案数，有了上面的结论，就可以得到转移方程，大概就是斐波那契关系之上再加点东西，
f[i] = f[i-1] + f[i-2] + pre，其中 pre 是所有符合上述判定的前缀和，注意别和长度 <= 3 的算重复了。
用类似 小z的袜子 里的方法维护区间不同元素的数目即可。

实现的时候，可以设置哨兵 f[0] = f[1], f[n+1] = f[n] 以简化代码。

const int N = int(2e5) + 9;
Int f[N]; int a[N], c[N], cn;
int n;
void add(int x) {
x = a[x];
if (!c[x]) ++cn;
c[x] += 1;
}
void dec(int x) {
x = a[x];
c[x] -= 1;
if (!c[x]) --cn;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n); REP_1(i, n) RD(a[i]);
f[0] = 1; f[1] = 1; a[0] = a[1]; a[n+1] = a[n]; ++n;
Int z = 1, pre = 0;
int l = 1; REP_1(i, n) {
if (a[i] == a[i-1]) {
z *= f[i-1]; f[i-1] = 0; f[i] = 1;
while (l < i) dec(l++); add(i); pre = 0;
} else {
add(i); while (cn > 2 && l < i-2) pre += f[l], dec(l++);
f[i] = f[i-1] + f[i-2] + pre;
}
}
cout << z << endl;
}

直接 dfs 显然不行，考虑构造。。。
呃。。。
(1 hour later … )

好吧，我觉得这个题还是挺难的。囧。。完全没看懂 题解。。。
但是 标程 到是挺容易看懂的。。。

我们先考虑 k|n 的情况，那么可以分成 n/k 组，我们尝试贪心构造，每次尽可能放最小的，但是放到后面有可能需要回溯。。。
看来我们需要想一种贪心构造，使得问题的规模不断减小，并且最好不会出现回溯。。

设 n = dk + r，(r > 0)，首先如果存在 Ai > (d+1) 或者有超过 r 组 == (d+1) 那么显然无解，
否则，如果恰好有超过 r 组 == d+1，那么从这 r 组里选最小的，否则选全局最小的，添加到队首，
当然选出的数要保证与上次出现的距离至少为 k，然后递归到 n-1 即可。

上面的过程显然保证字典序最小，我们只要证明这个算法一定能终止，也就是每次都能选出来数即可。
需要尝试反证法。。。

F – Game against Robot

首先考虑静态的问题，然后类似 linearity of expectation，我们设法求出每个 Ai 在结果中出现的次数。
我们只关注排列中每个元素和 Ai 的大小关系，这样只需要考察 01 序列，最后对贡献乘以 i!(n-i)! 即可。

进一步考察静态过程，我们可以计数得到所有大于等于 Ai 的数在答案中的出现次数，类似求 Catalan 数的过程，
最后预处理二项式系数加速即可。

具体看 lyric 的代码。
https://atcoder.jp/contests/arc128/submissions/26604841

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK