跃迁引擎启动

发表于 分类于 阅读次数：

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$，后一部分也是类似。

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

阅读全文 »

发表于 分类于 阅读次数：

A Eating Soup

B Cat Party

给定序列 $a$，求一个最长前缀，满足删除一个数后，剩下每种数的出现次数相同。

维护每种数的出现次数，每种出现次数的出现次数。

显然，有答案时，出现次数的种类最多为 $2$，分类讨论判断一下即可。

C Power Transmission

给定 $1000$ 个点，两两连着直线，求有多少直线相交，重合的直线只算一次。

只需要将直线去重即可，对于每种斜率，统计即可。

把直线转化为一般方程去重即可。

D Mysterious Code

有一个未知串 $p$，两个模式串 $s$ 和 $t$，要求最大化 $p$ 串中 $s$ 串出现次数减去 $t$ 串出现次数。

对 $s$ 和 $t$ 串建出 $fail$ 指针，记 $dp[t][i][j]$ 表示 $p$ 串前 $t$ 个匹配到两个串 $i$ 和 $j$ 位置时的最大值。对于每个新字符，如果是通配符就跑所有字母的转移，转移就是在两个 $fail$ 指针上找到下一个位置，并更新计数值。

阅读全文 »

发表于 分类于 阅读次数：

模板

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
int main() {
    scanf("%d", &n);
    vector<int> st;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", h + i);
        while (!st.empty() && h[st.back()] > h[i]) {
            r[st.back()] = i - 1;
            st.pop_back();
        }
        st.push_back(i);
    }
    st.clear();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && h[st.back()] > h[i]) {
            l[st.back()] = i + 1; st.pop_back();
        }
        st.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (!r[i]) r[i] = n;
        if (!l[i]) l[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, 1ll * h[i] * (r[i] - l[i] + 1));
    }
    printf("%lld\n", ans);
    return 0;
}