跃迁引擎启动

发表于 更新于 分类于 ， 阅读次数：

A From Hero to Zero

B Catch Overflow!

C Electrification

给定 $x$ 正半轴的 $n$ 个点，求一个点 $x$ 到所有点距离的第 $k+1$ 大的最小值。

二分答案，当前值为 $m$，考虑线段 $[a_i-m,a_i+m]$，就是判是否有一个点被覆盖了 $k+1$ 次。

判断过程可以双指针扫一下，具体参考代码。

D Array Splitting

给定一个序列 $a$，将一个区间分成 $k$ 个连续段，记 $f(i)$ 表示 $i$ 属于第几个段，最大化 $\sum_{i=1}^n a_if(i)$。

考虑贡献，首先每个位置都加了一次，某些后缀多加一些次。

其实就是对所有后缀排序，取前 $k$ 大，注意整体是必选的即可。

E Minimal Segment Cover

给定 $n$ 条线段，询问 $q$ 次一个线段内所有点是否被覆盖，包含非整数点。

因为要包含整数之间的部分，因此考虑一个贪心的跳转的过程，每个点跳一次到最右端点，然后从这个位置继续往后跳。

这个跳转过程可以用倍增进行加速，预处理每个位置被一条线段覆盖到的最右端点，倍增一下。

F The Number of Subpermutations

给定序列 $a_1, a_2, \dots, a_n$，求有多少个子区间是对应长度的排列。

观察一下，要么 $1$ 很少，要么重复的数字很多。枚举包含 $1$ 的子区间，向右跑到出现相同数字停止，判断这个点为右端点的子区间是否是一个排列，即判断两个集合是否相同。随机一个权值异或判断即可。

阅读全文 »

发表于 更新于 分类于 阅读次数：

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 1 << 18;

int n, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], f[maxn];

void fwtOR(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                if (op == 1)
                    a[i + j + d] = (a[i + j + d] + a[i + j]) % mod;
                else
                    a[i + j + d] = (a[i + j + d] + mod - a[i + j]) % mod;
            }
}
void fwtAND(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                if (op == 1)
                    a[i + j] = (a[i + j] + a[i + j + d]) % mod;
                else
                    a[i + j] = (a[i + j] + mod - a[i + j + d]) % mod;
            }
}
void fwtXOR(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                int x = a[i + j], y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x + mod - y) % mod;
                if (op != 1) {
                    // inv2 = 499122177
                    a[i + j] = 1ll * a[i + j] * 499122177 % mod;
                    a[i + j + d] = 1ll * a[i + j + d] * 499122177 % mod;
                }
            }
}

int main() {
    scanf("%d", &n);
    int m = 1 << n;
    for (int i = 0; i < m; i++) scanf("%d", a + i), c[i] = a[i], e[i] = a[i];
    for (int i = 0; i < m; i++) scanf("%d", b + i), d[i] = b[i], f[i] = b[i];
    fwtOR(a, 1 << n); fwtOR(b, 1 << n);
    for (int i = 0; i < m; i++) a[i] = 1ll * a[i] * b[i] % mod;
    fwtOR(a, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", a[i], " \n"[i == m - 1]);
    fwtAND(c, 1 << n); fwtAND(d, 1 << n);
    for (int i = 0; i < m; i++) c[i] = 1ll * c[i] * d[i] % mod;
    fwtAND(c, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", c[i], " \n"[i == m - 1]);
    fwtXOR(e, 1 << n); fwtXOR(f, 1 << n);
    for (int i = 0; i < m; i++) e[i] = 1ll * e[i] * f[i] % mod;
    fwtXOR(e, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", e[i], " \n"[i == m - 1]);
    return 0;
}
阅读全文 »

发表于 更新于 分类于 阅读次数：

F 的做法实在是太优美了www。

A Ehab Fails to Be Thanos

B Ehab Is an Odd Person

给定一个序列，你仅可以交换奇偶不同的两个位置，求字典序最小的序列。

若所有数奇偶性相同，显然无法操作。否则，可以两两任意操作，排序即可。

C Ehab and a Special Coloring Problem

给 $2$ 到 $n$ 所有数字染色，要求满足互质的两个数颜色不同。

考虑类似于调和级数那样子染色即可。

D Ehab and the Expected XOR Problem

在 $1$ 到 $2^n$ 内选一些数字，满足任意子串异或和不为 $0$ 或 $x$，求长度最长的序列。

转化为构造前缀和，显然前缀和两两不同且没有两个异或起来为 $x$，显然选了一个就不能选另外一个异或起来为 $x$，容易构造。

F Ehab and the Big Finale

给定一棵树，猜一个隐藏的点 $x$。

有 $36$ 次询问，询问一个点到 $x$ 的距离，询问 $x$ 的一个祖先到 $x$ 的路径上下一个点。

最开始时，询问到根的距离，这样就有很多备选解，考虑将这个解空间缩小。

再考虑给定的询问方式，我们于是需要加速一个点往下跳转的过程，并且保证正确性，而不是一步一步走。

考虑轻重链剖分，当前考虑的根为 $u$，重链的底端为 $v$，考虑 $v$ 和 $x$ 的最近公共祖先，联想树上差分距离这个过程的逆，可以得到这个 LCA。

如果 LCA 不是答案，那么将 LCA 往下移一步递归地解决即可。

显然，轻链的个数是 $O(\log n)$ 的，每次最多只能询问两次。

注意：有一个询问可以在缩小问题规模时维护出来，无需单独询问。

类似于轻重链剖分的做法，也可以用重心分解来加速跳转。

讨论一下 $x$ 是不是在当前的重心内，在重心内就往下走一步，否则取当前的子问题为重心的父亲，并标记删除。

阅读全文 »

发表于 更新于 分类于 阅读次数：

最大团

编号从 $0$ 开始。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct Max_Clique {
    static const int N = 100;
    vector<int> sol;
    int el[N][N / 30 + 1], s[N][N / 30 + 1];
    int n, ans, dp[N];
    void init(int _n) {
        n = _n;
        for(int i = 0; i <= n; i++) {
            dp[i] = 0;
            ms(el[i], 0);
        }
    }
    /* Zero Base */
    void add_edge(int a,int b) {
        if(a > b) swap(a, b);
        if(a == b) return;
        el[a][b / 32] |= (1 << (b % 32));
    }
    bool dfs(int x,int k) {
        int c = 0, d = 0;
        for(int i = 0; i < (n + 31) / 32; i++) {
            s[k][i] = el[x][i];
            if (k != 1) s[k][i] &= s[k - 1][i];
            c += __builtin_popcount(s[k][i]);
        }
        if (c == 0) {
            if(k > ans) {
                ans = k;
                sol.clear();
                sol.push_back(x);
                return 1;
            }
            return 0;
        }
        for (int i = 0; i < (n + 31) / 32; i++) {
            for (int a = s[k][i]; a; d++) {
                if (k + (c - d) <= ans) return 0;
                int lb = a & (-a), lg = 0;
                a ^= lb;
                while (lb!=1) {
                    lb = (unsigned int)(lb) >> 1;
                    lg++;
                }
                int u = i * 32 + lg;
                if (k + dp[u] <= ans) return 0;
                if (dfs(u, k + 1)) {
                    sol.push_back(x);
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve() {
        ans = 0;
        for(int i = n - 1; i >= 0; i--) {
            dfs(i,1);
            dp[i] = ans;
        }
        return ans;
    }
} mcp;
阅读全文 »

发表于 更新于 分类于 阅读次数：

A Circle Metro

B Pairs

C Increasing by Modulo

给定一个序列，每次选择一些位置模 $m$ 加一，求最小操作次数使得序列不减。

显然有一个 $\mathcal{O}(nm)$ 的 dp。

考虑二分答案，贪心构造使得每个位置尽量小。

D Good Triple

给定一个 $01$ 串，求有多少子串存在 $3$ 个不同位置间隔相同且字符相同。

注意到串长大于 $10$ 时已经不可能不满足条件，暴力筛掉错误情况即可。

E And Reachability

给定一个序列，询问 $q$ 次，两个位置 $l$ 和 $r$，存在一条路径 $a_l,a_{i_0}, a_{i_1}, \dots , a_r$，满足相邻两个至少二进制表示下有一个共同位置是 $1$。

预处理每个位置到下一个第 $i$ 位为 $1$ 的第一个位置。倒序维护一下全局的每一个二进制位的最后出现位置，对于每个数的每个 $1$ 的二进制位，从全局的后一个转移过来。询问的时候，枚举 $r$ 的二进制即可。

时间复杂度 $\mathcal{O}(n \log^2 n + q \log n)$。

阅读全文 »

发表于 更新于 分类于 阅读次数：

王室联邦分块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, b;
vector<int> edge[maxn];

int stk[maxn], tot, bel[maxn], bcnt, key[maxn];
void dfs(int u, int f) {
    int bot = tot;
    for (int& v: edge[u]) {
        if (v == f) continue;
        dfs(v, u);
        if (tot - bot >= b) {
            bcnt++; key[bcnt] = u;
            while (tot != bot) {
                bel[stk[tot--]] = bcnt;
            }
        }
    }
    stk[++tot] = u;
} 

int main() {
    scanf("%d%d", &n, &b);
    for (int i = 2, u, v; i <= n; i++) {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 0);
    while (tot) bel[stk[tot--]] = bcnt;
    printf("%d\n", bcnt);
    for (int i = 1; i <= n; i++) printf("%d%c", bel[i], " \n"[i == n]);
    for (int i = 1; i <= bcnt; i++) printf("%d%c", key[i], " \n"[i == bcnt]);
    return 0;
}
阅读全文 »

发表于 更新于 分类于 阅读次数：

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int sz = 700;
const int maxn = 100000 + 5;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
PII get(ll a, ll b) {
    if (a == 0) return { 0, 1 };
    ll g = gcd(a, b);
    return { a / g, b / g };
}

struct Que {
    int l, r, id;
    bool operator<(const Que& b) const {
        if (l / sz == b.l / sz) {
            if ((l / sz) % 2) return r > b.r;
            else return r < b.r;
        }
        return l < b.l;
    }
} q[maxn];

int n, m, a[maxn];
PII ans[maxn];

ll fz, bag[maxn];
ll cal(ll x) {
    return x * (x - 1) / 2;
}
void update(int x, int t) {
    fz -= cal(bag[x]);
    bag[x] += t;
    fz += cal(bag[x]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q + 1, q + 1 + m);
    int l = 1, r = 0; // important
    for (int i = 1; i <= m; i++) {
        while (r < q[i].r) update(a[++r], 1);
        while (l > q[i].l) update(a[--l], 1);
        while (l < q[i].l) update(a[l++], -1);
        while (r > q[i].r) update(a[r--], -1);
        dbg(q[i].l, q[i].r, l, r);
        ans[q[i].id] = get(fz, cal(r - l + 1));
    }
    for (int i = 1; i <= m; i++) {
        printf("%lld/%lld\n", ans[i].first, ans[i].second);
    }
    return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 阅读次数：

A Telephone Number

B Lost Numbers

C News Distribution

D Bicolored RBS

给你一个括号匹配好的括号序列，现在你要将其分成两个，使得长度最大的那个最小。

想都没想直接写了二分，然后就过了。

实际上，直接构造奇偶就行了。

E Range Deleting

（惨遭带走

给定一个序列 $a$，每个数字范围在 $1$ 到 $x$ 之间，定义 $f(l,r)$ 表示把数值大小在 $[l,r]$ 到内的全部剔除，检查剩余数字是否单调不减，对 $f$ 求和。

显然被剔除之后剩下一个前缀和后缀，对每一个前缀找到一个最长的后缀使得能拼成满足要求的序列。

因此，只需要预处理每一个前缀是否满足条件即可，记录一下每种数字的第一个和最后一个出现位置。

F Scalar Queries

给定一个序列 $a$，定义 $f(l,r)$ 表示把 $a[l\dots r]$ 抠出来排序，生成 $b$ 序列，$f(l,r)=\sum_{i=1}^{r-l+1} i \cdot b_i$，对 $f(l,r)$ 求和。

考虑每个位置对答案的总贡献，也就是对应位置的权值乘上系数。我们首先注意到，一个点系数之和前后有多少数字比它小有关，因此考虑从小到大枚举。

记当前枚举的位置为 $pos$，记 $g(l,r)$ 表示 $[l,r]$ 内有多少数字小于等于 $a_{pos}$。

因此，贡献就等于 $\sum_{i=1}^{pos} \sum_{j=pos}^{n} g(i, pos) + g(pos, j) - 1$，其中 $pos$ 被算了两次。

发现这两个维度独立，上式也就是 $\sum_{i=1}^{pos} g(i,pos) \times \sum_{j=pos}^n g(pos,j) - pos \cdot (n-pos+1)$。

最后，先考虑前一部分，发现如果之前已经算过了 $i,i < pos $，他对答案的贡献也就是 $i$，后一部分也是类似。

单点修改查询前缀和，树状数组维护即可。

阅读全文 »