-[x] 2019.02.15 Codeforces Round 532 (Div. 2)
-[ ] 2019.02.17 Codeforces Round 539 (Div. 2)
-[ ] 2019.02.19 Educational Codeforces Round 60 (Div. 2)
-[x] 2019.02.21 Codeforces Round 530 (Div. 2)
-[x] 2019.02.23 Codeforces Round 541 (Div. 2)

[x] CR 532 d2 (6/6) xxxxx?
- [x] D 思维构造
- [x] E 二分+有向图拓扑排序
- [x] F 线性基+预处理（离线或者在线）

F. 线性基

题意

给定$n$个数字（大小为$a_i$），$q$次询问，每次询问区间$[l_i,r_i]$内任选一些数的异或和是多少。

$n,q<=5e5$

$a_i<=1e6$

题解

考虑离线所有询问，记录所有线性基的时间，按照$r_i$排序，每次记录尽可能右的线性基，查询时仅利用不超过$l_i$的即可，具体参照代码。

代码


using namespace std;
#define pb push_back
typedef long long ll;
const int mn = 5e5 + 5;

int n, m;
int a[mn], p[25], pos[25];
void (int i) {
    int id = i, x = a[i];
    for (int j = 21; j >= 0; j--) {
        if (!(x >> j)) continue;  
        if (!p[j]) {
            p[j] = x;
            pos[j] = id;
            break;
        }  //选入线性基中
        if (id > pos[j]) {
            swap(x, p[j]);
            swap(id, pos[j]);
        }
        x ^= p[j];
    }
}

int query(int l) {
    int ans = 0;
    for (int j = 21; j >= 0; j--) {
        if (pos[j] >= l && (ans ^ p[j]) > ans) ans ^= p[j];
    }
    return ans;
}
struct query {
    int l, r, id;
    bool operator<(const query &p) const { return r < p.r; }
} q[mn];
int ans[mn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q + 1, q + m + 1);
    int r = 1;
    for (int i = 1; i <= m; i++) {
        while (r <= q[i].r) ins(r++);
        ans[q[i].id] = query(q[i].l);
    }
    for (int i = 1; i <= m; i++) printf("%dn", ans[i]);
    return 0;
}

2019.02.17 Codeforces Round 539 (Div. 2)

[ ] CR 539 d2 (5/6) xxxx 后两题与d1相同，见下面。
[ ] CR 539 d1 (3/6) xx.o..
- [ ] C 炫酷平衡树
- [x] D 生成树计数
- [ ] E ???
- [ ] F ???

1D. 生成树计数

题意

询问有多少个不同的带权树满足：

有$n$个点，边权范围为$[1,k]$。
其中，$1,n$的简单路径的距离为$k$

$n,kle 1e9$

两棵树不同当且仅当任何一条边的边权不同，结果对$1e9+7$取模。

题解

很容易想到枚举$1,n$之间有几个点。

当内部有$i$个点时，注意到：

外部有$(n-1)-(i+1)$条边，这些边权值任意，所以有$k^{n-i-2}$种方法。
内部有$i+1$条边，由多重集的组合数可知，内部方案有$C_{k-1}^i$种。
所有树的形状可以由cayley定理求出，将$n$个点分成$s$个森林的方案数为$s*n^{n-s-1}$种
上面的形状没有确定点的位置，我们需要从$n-2$个点中选取$i$个，故还要乘上$A_{n-2}^i$

上面的所有式子相乘即为答案。

代码


using namespace std;

#define pb push_back

typedef long long ll;

const int mn = 1e5 + 5;
const int mod = 1e9 + 7;
#define P mod

int n, q;
char s[mn];

int c[150];//计数

ll inv(ll a) {
    if (a == 1) return 1;
    return inv(mod % a) * (mod - mod / a) % mod;
}

int F[mn + 3], Finv[mn + 3];

void init() {//阶乘逆元
    F[0] = 1;
    for (int i = 1; i <= n; i++) F[i] = 1ll * F[i - 1] * i % P;
    Finv[n] = inv(F[n]);
    for (int i = n; i; i--) Finv[i - 1] = 1ll * Finv[i] * i % P;
}

ll d[mn];//背包

inline void (int x) {//加入
    for (int i = n / 2; i >= x; i--) {
        d[i] = (d[i - x] + d[i]);
        if (d[i]>=mod) d[i]-=mod;
    }
}
inline void del(int x) {//删除
    for (int i = x; i <= n / 2; i++) {
        d[i] = (d[i] - d[i - x] + mod);
        if (d[i]>=mod) d[i]-=mod;
    }
}

ll ans[mn];

inline int gethash(int x, int y) {
    return x * 128 + y;
}

ll t;//除了f以外的答案
ll query(int x, int y) {
    x = s[x], y = s[y];
    if (x > y) swap(x, y);
    if (ans[gethash(x, y)] != -1) return ans[gethash(x, y)];
    int need = n / 2 - c[x] - (x == y ? 0 : c[y]);
    if (need < 0) return 0;
    del(c[x]);
    if (x != y) del(c[y]);
    ll a = t * d[need] % mod;
    ins(c[x]);
    if (x != y) ins(c[y]);
    return ans[gethash(x, y)] = a;
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    init();
    t = 1ll * F[n / 2] * F[n / 2] * 2 % mod;
    for (int i = 1; i <= n; i++) {
        c[s[i]]++;
    }
    d[0] = 1;
    memset(ans, -1, sizeof ans);
    for (int i = 1; i <= 128; i++) if (c[i]) ins(c[i]), t = t * Finv[c[i]] % P;
    scanf("%d", &q);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%lldn", query(x, y));
    }

    return 0;
}

2019.02.19 Educational Codeforces Round 60 (Div. 2)

本场待补，看起来ABCD都很没意思，会从E开始。

2019.02.21 Codeforces Round 530 (Div. 2)

[x] CR 530 d2 (6/6) xxxxoo
- [x] E 结论DP/贪心（模拟题）
- [x] F 树状数组二分+树上DP

E. 结论DP+贪心（输出方案、模拟题）

题意

给定一个$n$行$m$列的矩形，矩形每个位置由”ATCG”中的一个组成。现在需要你改变其中的一些位置，要求对于矩形内部任意$2*2$的部分都拥有”ATCG”，问最少改变次数的任意一种改变方案（输出改变后的矩阵）。

$n*mle 300000$

题解

有一个简单的数学结论：如果要形成满足条件的矩形，必须满足二者之一：

每一行仅由两个字母组成，并且交替进行。
每一列仅由两个字母组成，并且交替进行。

结论不再证明，有了这个结论之后，发现题目就转化成了模拟题。

认真实现即可。

时间复杂度不会超过$O(nmk)$，其中$k$在本题中为不大于$24$的常数。

代码


using namespace std;
#define pb push_back
#define sz(x) (int)x.size()

int n, m;

vector<string> s;
string t;

vector<string> ans, temp;
int ansd = 1e9, tempd;

const char dna[] = {"ACGT"};

int judgex(int line, int a, int b) {
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if ((i & 1) == 0 && s[line][i] != dna[a]) ans++;
        if ((i & 1) && s[line][i] != dna[b]) ans++;
    }
    return ans;
}
void drawx(int line, int a, int b) {
    for (int i = 0; i < m; i++) {
        if (i & 1)
            temp[line][i] = dna[b];
        else
            temp[line][i] = dna[a];
    }
}

int judgey(int row, int a, int b) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if ((i & 1) == 0 && s[i][row] != dna[a]) ans++;
        if ((i & 1) && s[i][row] != dna[b]) ans++;
    }
    return ans;
}
void drawy(int row, int a, int b) {
    for (int i = 0; i < n; i++) {
        if (i & 1)
            temp[i][row] = dna[b];
        else
            temp[i][row] = dna[a];
    }
}

void build(int a, int b) {
    int c = -1, d = -1;
    for (int i = 0; i < 4; i++) {
        if (i == a || i == b || i == c) continue;
        if (c == -1)
            c = i;
        else
            d = i;
    }
    tempd = 0;
    for (int i = 0; i < n; i++) {
        if (i & 1) {
            int u = judgex(i, a, b);
            int v = judgex(i, b, a);
            tempd += min(u, v);
            if (min(u, v) == u)
                drawx(i, a, b);
            else
                drawx(i, b, a);
        } else {
            int u = judgex(i, c, d);
            int v = judgex(i, d, c);
            tempd += min(u, v);
            if (min(u, v) == u)
                drawx(i, c, d);
            else
                drawx(i, d, c);
        }
    }
    if (tempd < ansd) swap(ans, temp), swap(ansd, tempd);
    tempd = 0;
    for (int i = 0; i < m; i++) {
        if (i & 1) {
            int u = judgey(i, a, b);
            int v = judgey(i, b, a);
            tempd += min(u, v);
            if (min(u, v) == u)
                drawy(i, a, b);
            else
                drawy(i, b, a);
        } else {
            int u = judgey(i, c, d);
            int v = judgey(i, d, c);
            tempd += min(u, v);
            if (min(u, v) == u)
                drawy(i, c, d);
            else
                drawy(i, d, c);
        }
    }
    if (tempd < ansd) swap(ans, temp), swap(ansd, tempd);
}

void solve() {
    for (int i = 0; i < 4; i++) {
        for (int j = i + 1; j < 4; j++) {
            build(i, j);
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> t, s.pb(t), ans.pb(t), temp.pb(t);
    solve();
    for (auto &i : ans) cout << i << "n";
    return 0;
}

F. 树状数组二分+树上DP

题意

给定$n$个点的一棵带权树，每条边权$l_i$。

每个点上有$x_i$个饼干，吃一个需要耗费时间$t_i$。

根为$1$，一开始大家的位置是$1$，先后手博弈：

先手可以选择一条边并往下走，耗费边权的时间。或者选择结束游戏，回到起点并吃掉路上的一些饼干。但需要保证花费在边权和吃饼干的时间不超过$T$。
后手可以选择切除一条当前点向下的边。

先手的目标是为了让吃到的饼干最多，后手的目标是为了让吃到的饼干数量最少。

$nle 2e5$

题解

考虑$dp[i]$为从$1$走到节点$i$的最大饼干数量。

如果要求$dp[i]$，只需要知道路上最多吃多少饼干即可，这个可以通过重新排序后树状数组上二分求得。

树状数组的位置需要提前排序。

随后做一个简单的树上DP，后手只会切掉子树最大值最大的节点。

代码


using namespace std;
#define pb push_back
#define sz(x) (int)x.size()

typedef long long ll;
typedef pair<int, int> pii;

const int mn = 3e5 + 5;

int n, m;
ll T;

vector<int> g[mn];

ll a[mn], c[mn];
int p[mn];
ll l[mn];
int tid[mn];

ll t[mn];
ll cnt[mn];  // cnt of cookie
void add(ll *t, int i, ll x) {
    while (i <= n) t[i] += x, i += i & -i;
}
ll sum(ll *t, int i) {
    ll s = 0;
    while (i) s += t[i], i -= i & -i;
    return s;
}
// 树状数组二分（返回最后一个可行位置）
int binary_search(ll *t, ll T) {  // return ok position
    int u = 0;
    bool high = 1;
    for (int i = 20; i >= 0; i--) {
        int nxtpos = u ^ (1 << i);
        if (!high || ((1 << i) & n)) {
            if (T < t[nxtpos])
                high = 0;
            else
                T -= t[nxtpos], u ^= (1 << i);
        }
    }
    return u;
}

ll ans;
ll dp[mn];  // 1 -> i , max num of cookies

inline ll getans(ll T) {
    int k = binary_search(t, T);
    T -= sum(t, k);
    ll ans = sum(cnt, k);
    if (k == n) return ans;
    ll more = sum(cnt, k + 1) - ans;
    ll morecost = sum(t, k + 1) - sum(t, k);
    ll cost = morecost / more;
    ans += T / cost;
    return ans;
}

void dfs(int x, ll T) {
    if (T < 0) return;
    add(t, tid[x], a[x] * c[x]);
    add(cnt, tid[x], a[x]);
    dp[x] = getans(T);
    vector<ll> v;
    for (auto &i : g[x]) {
        dfs(i, T - l[i] * 2);
        if (dp[i] > 0) v.pb(dp[i]);
    }
    sort(v.begin(), v.end());
    if (!v.empty() && x != 1) v.pop_back();
    for (auto &i : v) dp[x] = max(i, dp[x]);
    add(t, tid[x], -a[x] * c[x]);
    add(cnt, tid[x], -a[x]);
}

int main() {
    scanf("%d%lld", &n, &T);
    vector<pii> v;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &c[i]);
        v.pb({c[i], i});
    }
    for (int i = 2; i <= n; i++) {
        scanf("%d%lld", &p[i], &l[i]);
        g[p[i]].pb(i);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < sz(v); i++) {
        tid[v[i].second] = i + 1;
    }
    dfs(1, T);
    printf("%lldn", dp[1]);
    return 0;
}

2019.02.23 Codeforces Round 541 (Div. 2)

[x] CR 541 d2 (7/7) xxxxoxo
- [x] E 思维+数学计数（细节）
- [x] G 单调栈优化动态规划

E. 思维+数学计数（细节）

题意

给定$n$个字符串（$S_1,S_2,cdots ,S_n$），总字符串长度不超过k。

一种特别的字符串构造方式是这样的：

$S_1cdot S_2=S_2S_{1,1}S_2S_{1,2}S_2cdots S_{1,|S_1|}S_2$

注意，这种构造方式必须从左到右计算。

问字符串$S_1cdot S_2cdot S_3cdots S_n$中，最长的相同字符字串长度为多少。

数据保证答案不超过$1e9$。

$n,kle 1e5$

题解

让人相当不愉快的题目了。

需要分非常非常多的类讨论。

建议阅读官方题解。

https://codeforces.com/blog/entry/65487

代码


using namespace std;
#define pb push_back
#define sz(x) (int)x.size()

const int mn = 1e5 + 5;

int n;
string s[mn];
char need;
int mini = 1e9;

int find_head(int x) {
    int cnt = 0;
    for (auto &i : s[x]) {
        if (i == need)
            cnt++;
        else
            break;
    }
    return cnt;
}
int find_tail(int x) {
    int cnt = 0;
    for (int i = sz(s[x]) - 1; i >= 0; i--) {
        if (s[x][i] == need)
            cnt++;
        else
            break;
    }
    return cnt;
}
int find_all(int x) {
    int cnt = 0, maxi = 0;
    for (auto &i : s[x]) {
        if (i == need) {
            cnt++;
            if (cnt > maxi) maxi = cnt;
        } else
            cnt = 0;
    }
    return maxi;
}
bool get_others(int x) {
    for (int i = 1; i < x; i++) {
        if (find_all(i)) return 1;
    }
    return 0;
}

int get_head() {
    int ans = 0;
    for (int i = n; i; i--) {
        int u = find_head(i);
        ans = (ans + 1) * u + ans;
        if (u != sz(s[i])) {
            mini = min(i + (u == 0), mini);
            break;
        }
        if (i == 1) mini = 0;
    }
    return ans;
}
int get_tail() {
    int ans = 0;
    for (int i = n; i; i--) {
        int u = find_tail(i);
        ans = (ans + 1) * u + ans;
        if (u != sz(s[i])) {
            mini = min(i + (u == 0), mini);
            break;
        }
        if (i == 1) mini = 0;
    }
    return ans;
}
int maxi = 0;
void get_maxi() {
    for (int i = n; i; i--) {
        int u = find_head(i);
        if (u != sz(s[i])) {
            maxi = i;
            break;
        }
    }
}
int get_max_ans() {
    if (maxi == 0) return 0;
    int ans = 0;
    for (int i = n; i > maxi; i--) {
        int u = find_tail(i);
        ans = (ans + 1) * u + ans;
    }
    return (ans + 1) * find_all(maxi) + ans;
}

int solve(char c) {
    mini = n;
    need = c;
    get_head();
    get_tail();
    get_maxi();
    bool others_has_need = get_others(mini);
    int ans = 0;
    if (others_has_need) {
        ans = get_head() + get_tail() + 1;
    }
    else ans = max({get_head(), get_tail()});
    ans = max({ans, get_max_ans(), find_all(n)});
    return ans;
}

int main() {
    cin.sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    int ans = 0;
    for (int i = 'a'; i <= 'z'; i++) ans = max(ans, solve(i));
    printf("%dn", ans);
    return 0;
}

G. 单调栈优化动态规划

题意

给定$m$个多米诺骨牌，第$i$个多米诺骨牌高度为$h_i$，推倒代价为$c_i$。

相邻的多米诺骨牌距离为$1$，一个多米诺骨牌会被另一个多米诺骨牌推倒当且仅当他们的距离严格小于另一个多米诺骨牌的高度。

多米诺骨牌会产生连锁反应。你需要选择主动推倒代价和尽可能少的多米诺骨牌（向前或者向后），以产生连锁反应。

求让所有多米诺骨牌倒下的最小代价和。

$mle 1e7$

题解

$L[i],R[i]$分别表示主动推倒第$i$个多米诺骨牌（向左或者向右）最远能连锁反应发生到的位置。

这可以简单地使用单调栈维护，时间复杂度$O(m)$

令$dp[i]$表示仅考虑前$i$个多米诺骨牌的最小代价和。

显然有

$dp[i]=min{ displaystylemin_{L[i]-1le kle i}{dp[k]+c[i]}, displaystylemin_{R[k]ge i}{dp[k-1]+c[k]} }$

该式子中，使用单调栈维护右边部分。

以上，总时间复杂度$O(m)$

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<ll, ll> pll;

const int mn = 3e5 + 5;
const int mm = 1e7 + 5;

int n, m;

vector<int> b[mn], c[mn];

int h[mm];
ll a[mm];  // cost of i

int L[mm], R[mm];

void readin() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int u;
        scanf("%d", &u);
        for (int j = 1; j <= u; j++) {
            int v;
            scanf("%d", &v);
            b[i].pb(v);
        }
        for (int j = 1; j <= u; j++) {
            int v;
            scanf("%d", &v);
            c[i].pb(v);
        }
    }
    int q;
    scanf("%d", &q);
    int now = 1;
    for (int i = 1; i <= q; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        for (int k = 0; k < sz(b[u]); k++) {
            h[k + now] = b[u][k];
            a[k + now] = 1ll * c[u][k] * v;
        }
        now += sz(b[u]);
    }
}

pll st[mm];
int cnt;

void getLR() {
    for (int i = 1; i <= m; i++) {
        while (cnt > 0 && st[cnt - 1].first < i) {
            R[st[cnt - 1].second] = i - 1;
            cnt--;
        }
        st[cnt++] = {i + h[i] - 1, i};
    }
    while (cnt > 0) R[st[cnt - 1].second] = m, cnt--;

    for (int i = m; i; i--) {
        while (cnt > 0 && st[cnt - 1].first > i) {
            L[st[cnt - 1].second] = i + 1;
            cnt--;
        }
        st[cnt++] = {i - h[i] + 1, i};
    }
    while (cnt > 0) L[st[cnt - 1].second] = 1, cnt--;
}

ll dp[mm];

void solve() {
    memset(dp, 1, sizeof dp);
    dp[0] = 0;
    // stack: value / maxpos
    for (int i = 1; i <= m; i++) {
        dp[i] = min({dp[L[i] - 1] + a[i]});
        while (cnt > 0 && st[cnt - 1].second < i) cnt--;
        if (cnt > 0) dp[i] = min(dp[i], st[cnt - 1].first);
        if (!cnt || cnt > 0 && R[i] <= st[cnt - 1].second &&
                        st[cnt - 1].first > dp[i - 1] + a[i])
            st[cnt++] = {dp[i - 1] + a[i], R[i]};
    }
    printf("%lldn", dp[m]);
}

int main() {
    readin();
    getLR();
    solve();
    return 0;
}

2019 寒假集训 codeforces 部分 2019.02.17 Codeforces Round 539 (Div. 2) 2019.02.19 Educational Codeforces Round 60 (Div. 2) 2019.02.21 Codeforces Round 530 (Div. 2) 2019.02.23 Codeforces Round 541 (Div. 2)