CF Round 542 Div1.

B. Wrong Answer

构造一个长度为 2000 的数组，满足最大“子段和 $\times$ 子段长度”比最大子段和刚好大 k

sol：

一个比较好的构造方法：

令数组总和为 $S$，然后构造 $a_1,a_2,...,a_{1998}=0,a_{1999}=-d,a_{2000}=S+d$

这样正确答案是 $2000 \times S$，最大子段和是 $S+d$

发现 $S = \frac{k+d}{1999}$

于是令 $d=1999-(k \space mod \space 1999)$ 即可

#include<bits/stdc++.h>

#define LL long long

#define rep(i,s,t) for(register int i = (s),i##end = (t); i <= i##end; ++i)

#define dwn(i,s,t) for(register int i = (s),i##end = (t); i >= i##end; --i)

using namespace std;

inline int read()

{

    int x=,f=;char ch;

    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

    for(;isdigit(ch);ch=getchar())x=*x+ch-'';

    return x*f;

}

int main()

{

    int k = read();

    int d =  - k % ;

    int S = (k + d) / ;

    cout <<  << endl;

    rep(i, , ) cout <<  << " ";

    cout << -d << " ";

    cout << S + d << endl;

}

D. isolation

给一个数组 a，把数组分成若干不相交的子段，使得每段“只出现一次的数”不超过 k 个

求有多少种分法，膜 998244353

$n \leq 10^5$

sol：

考虑 dp，令 $f(l,r)=[l,r]中只出现一次的数的数量$，假设可以很快的算出 $f(l,r)$ ，令 $dp(i)=前i个的分法$ ，则 $dp(0)=1,dp(n) = \sum\limits_{i=0}^{n} dp(i) \times [f(i+1,n) \leq k]$

现在只要快速算出 $f(l,r)$ 并想办法加速转移即可

然后是一系列神仙操作：

首先，枚举 $r$，尝试构造一个数组 $b[l,r]$ 使得对于枚举的 $r$，$f(l,r) = \sum\limits_{i=l}^r b[i]$，

因为我们要枚举 $r$ ，所以只需考虑如何快速使 $b_x[]$ 变成 $b_{x+1}[]$ 即可（$b_x$ 表示当 $r=x$ 时的 $b[]$）

一开始，$b_0[0]=0$，为方便描述，记 $pre(x)$ 为数字 $x$ 上一次在 $a$ 数组中出现的位置，保证存在

对于给定的 $a_{x+1}$

如果 $a_{x+1}$ 在之前至少出现过 $2$ 次，把 $b[pre(pre(x+1))]$ 设为 $0$

如果 $a_{x+1}$ 在之前出现过 $1$ 次，把 $b[pre(x+1)]$ 设为 $-1$

最后不管如何，把 $b[x+1]$ 设为 $1$

这样就能保证：出现两次或以上的数对 sumb 的贡献为 0，出现一次的数对 sumb 的贡献为 1

b 数组可以 $O(n)$ 递推出来，考虑怎么优化转移

考虑分块（这就是我的知识盲区了）

每块 [l,r] 维护：

1. $f(l,r)$ （也就是 sumb）

2. 对于每一个 $i \in [-\sqrt{n},\sqrt{n}]$，维护对于每个 $f(x,r) \leq i$ 的 $x$ ，维护 $dp(x-1)$ 的和

对于 2. ，因为 $i$ 是递增的，我们可以对 $i$ 维护一个前缀和

转移的时候在本块以及前面的块里查，本块查的是 $[0,k]$ ，往前查就把右端点每次减这一块的 sumb 就可以了

这样递推到每一个 $r$ 的时候，单块修改 $O(\sqrt{n})$ ，状态转移最多涉及到 $O(\sqrt{n})$ 个块

一路递推到 $n$ 就可以了

#include<bits/stdc++.h>

#define LL long long

#define rep(i, s, t) for(register int i = s, i##end = t; i <= i##end; ++i)

#define dwn(i, s, t) for(register int i = s, i##end = t; i >= i##end; --i)

using namespace std;

inline int read()

{

    int x = , f = ; char ch = getchar();

    for(;!isdigit(ch);ch=getchar())if(ch == '-')f = -f;

    for(;isdigit(ch);ch=getchar())x =  * x + ch - '';

    return x * f;

}

const int mod = ,maxn = 1e5 + ;

int n,k;

int a[maxn], b[maxn], nx[maxn], cur[maxn], f[maxn], bl[maxn];

inline void inc(int &x, int y) {x += y; if(x >= mod) x -= mod;}

struct block

{

    int l, r, sum, sumf[], sz;

    void calsum()

    {

        memset(sumf, , sizeof(sumf));

        int cur = ;

        dwn(i, r, l)

        {

            cur += b[i];

            inc(sumf[sz + cur], f[i - ]);

        }

        rep(i, , sz + sz) inc(sumf[i], sumf[i - ]);

    }

    int query(int pos)

    {

        if(pos + sz < )return ;

        return sumf[min(pos + sz, sz + sz)];

    }

}bs[];

inline void update(int pos, int val)

{

    f[pos] = val;

    bs[bl[pos + ]].calsum();

}

int query(int x)

{

    int ans = bs[bl[x]].query(k), cursum = bs[bl[x]].sum;

    dwn(i, bl[x]-, )

    {

        inc(ans, bs[i].query(k - cursum));

        cursum += bs[i].sum;

    }

    return ans;

}

int main()

{

    n = read(), k = read();

    rep(i, , n) a[i] = read();

    rep(i, , n) nx[i] = cur[a[i]], cur[a[i]] = i;

    f[] = ; int kk = sqrt(n);

    rep(i, , n) bl[i] = (i - ) / kk + ;

    rep(i, , bl[n])

    {

        bs[i].r = min(i * kk, n);

        bs[i].l = bs[i-].r + ;

        bs[i].sz = bs[i].r - bs[i].l + ;

    }bs[].calsum();

    rep(i, , n)

    {

        if(nx[nx[i]])

        {

            int pos = nx[nx[i]]; b[pos]++;

            bs[bl[pos]].sum++; bs[bl[pos]].calsum();

        }

        if(nx[i])

        {

            int pos = nx[i]; b[pos] -= ;

            bs[bl[pos]].sum -= ; bs[bl[pos]].calsum();

        }

        b[i]++; bs[bl[i]].sum++; bs[bl[i]].calsum();

        update(i, (f[i] = query(i)));

    }

    cout << f[n] << endl;

}

E.Legendary Tree

交互题，有一棵不知道形态的树

每次可以给定两个不相交点集 $A,B$ 和一个点 $v$ ，系统会回答你满足 $v$ 在 $s->t$ 简单路径上，$s\in A,t\in B$，这样的点对 $(s,t)$ 数量

求树形态

$n \leq 500,交互次数 \leq 11111$

sol：

一道我不是很喜欢的构造题

因为构造出来基本上只有题解的一种

那我就发题解吧

首先，令 $1$ 为根，对每个 $i$ ，询问 $({1},{2,3,...,n},i)$，这样可以问出来每个点的子树大小，这样是 $(n-1)$ 次（$1$ 号点的子树大小显然是 $n$）

之后把点按子树大小从小到大排序，按字数大小递增顺序枚举每个点，设 $v_i$ 为子树第 $i$ 大的点，

设已知点（下面已经知道，上面还不知道）的集合为 $X$，一开始，$X$ 中只有 $v_1$，因为显然 $v_1$ 是一个叶子

每次我们按如下步骤：

1.询问 $({1},{X},v_i)$，得到 $v_i$ 的直接儿子数量，记为 $k$

2.把 $X$ 中元素按任意顺序排成一列 $X_1,X_2,...,X_{|X|}$

3.重复 $k$ 次，每次二分找一个最小的 $m$，满足：询问 $({1},{X_1,X_2,...,X_m},v_i)$ 的结果大于 $0$，这个等价于 $X_m$ 和 $v_i$ 有一条边相连，每次找到这个 $m$ 就把 $X_m$ 删了（因为不满足 $X$ 的定义）

4.把 $v_i$ 加入 $X$

总询问次数 $(n-1) + (n-1) + (n-1) log_2n$

会感觉“好强啊但给我自己做我永远都做不出来”

可能这就是菜吧 quq

#include<bits/stdc++.h>

#define LL long long

#define rep(i,s,t) for(register int i = (s),i##end = (t); i <= i##end; ++i)

#define dwn(i,s,t) for(register int i = (s),i##end = (t); i >= i##end; --i)

using namespace std;

inline int read() {

    int x=,f=;char ch;

    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

    for(;isdigit(ch);ch=getchar())x=*x+ch-'';

    return x*f;

}

int query(vector<int> s, vector<int> t, int node) {

    cout << s.size() << endl;

    for(int i = ; i < (int)s.size(); ++i) {

        if(i != )putchar(' ');

        cout << s[i] + ;

    }

    cout << endl;

    cout << t.size() << endl;

    for(int i = ; i < (int)t.size(); ++i) {

        if(i != )putchar(' ');

        cout << t[i] + ;

    }

    cout << endl;

    cout << node +  << endl;

    return read();

}

vector<int> nd, size, p;

vector<pair<int, int>> ans;

set<int> X;

int main() {

    int n;

    cin >> n;

    for (int i = ; i < n; ++i) nd.push_back(i);

    p.resize(n);

    for (int i = ; i < n; ++i) p[i] = i;

    size.resize(n);

    size[] = n;

    for (int i = ; i < n; ++i) size[i] = query({  }, nd, i);

    sort(p.begin(), p.end(), [](int x, int y) { return size[x] < size[y]; });

    for (auto node : p) {

        if (size[node] != ) {

            while (!X.empty()) {

                vector<int> cur(X.begin(), X.end());

                if (!query({  }, cur, node)) break;

                int l = , r = (int)cur.size();

                while (l +  < r) {

                    int mid = l + r >> ;

                    if (query({  }, vector<int>(cur.begin() + l, cur.begin() + mid), node)) r = mid;

                    else l = mid;

                }

                ans.emplace_back(node, cur[l]);

                X.erase(cur[l]);

            }

        }

        X.insert(node);

    }

    cout << "ANSWER" << endl;

    for (auto p : ans) cout << p.first +  << " " << p.second +  << endl;

    return ;

}

巴特西

CF Round 542 Div1.

最新文章

热门文章