2020牛客寒假算法基础集训营3

• 若执行某项操作后应立即跳出，那么后续任何操作都不应该对它再有影响。
• 除法分母不能取模

https://ac.nowcoder.com/acm/contest/3004

题解 https://ac.nowcoder.com/discuss/365306?type=101&order=0&pos=1&page=2

B. 牛牛的DRB迷宫II

 

题意：一个nm迷宫，每格为’R’,‘D’,‘B’，分别表示向右走，向下走，向右/向下走。从 $(1,1)$ 出发，已知到 $(n,m)$ 共有 $k$ 种路径，要求构造出一个迷宫。

神奇的构造题

先构造出一个主对角线上都是’B’，主对角线上一个对角线都是’D’，主对角线下一个对角线都是’R’，主对角线以下没填的都放’D’，以上没填的都放’R’.

$$BDRRR\\ RBDRR\\ DRBDR\\ DDRBD\\ DDDRB\\$$

这样主对角线上的路径数分别是 1,2,4,8,16，都是2的幂次，而二的幂次可以构造出任意数，所以要考虑把这些数加起来。

考虑再加一行，并在最后一行都放’R’，就可以把最后一行的所有数都加起来。

$$BDRRR\\ RBDRR\\ DRBDR\\ DDRBD\\ DDDRB\\ RRRRR\\$$

但是仅仅这样的话，本身最后一行没有值，加起来也没用，所以要考虑把上面有值的数都加到最后行，上面之所以没有值，就是因为只有主对角线和下面一条对角线有值，但由于下一条对角线都是’R’，就没法传下来，所以如果需要这个二的幂次，就把它的主对角线上的位置的下一位的’R’改成’D’，让它能传递下来。

而由于 $k$ 可能为 0，但 $(n,m)$ 上方的那个’B’必定会传下来，但我们不需要它，所以再最后一行上方再加一行，都放’D’，保证传递性，而在’B’下方放’R’，让不需要的位传走。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n = 32, m = 30, k;
char mp[55][55];
int main() {
	scanf("%d", &k);
	printf("%d %d\n", n, m);
	mp[n][m] = 'B';
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 1; j <= m; j++) {
			if (j < i - 1 || j == i + 1)mp[i][j] = 'D';
			else if (j > i + 1 || j == i - 1)mp[i][j] = 'R';
			else mp[i][j] = 'B';
		}
	}
	for (int i = 1; i <= m; i++) {
		if (k&(1 << (i - 1)))mp[i + 1][i] = 'B';
		mp[n][i] = 'R';
	}
	for (int i = 1; i <= n; i++)printf("%s\n", mp[i] + 1);
	return 0;
}

 

E. 牛牛的随机数

 

题意：给定两个区间，问随机从每个区间里各取一个数，异或之后的期望。

显然是按每一位加权，则要考虑每一位出现一的概率，可以预处理出来，再前缀和相减得到区间的概率，再取两个区间分别为0，1的概率乘积相加。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1000000007;
int T;
ll cal0(ll x, ll i) {
    ll ans = (((x + 1) >> (i + 1) << i) % mod + min((x + 1) % (1ll << (i + 1)), (1ll << i))) % mod;
    return ans % mod;
}
inline ll ksm(ll a, ll b) {
    ll ret = 1;
    a %= mod;
    while (b)
    {
        if (b & 1)ret = (ret*a) % mod;
        a = (a*a) % mod;
        b >>= 1;
    }
    return ret % mod;
}
ll inv(ll x) {
    return ksm(x, mod - 2) % mod;
}
ll Sub(ll x, ll y) {
    ll ans = x - y;
    while (ans < 0)ans += mod;
    return ans % mod;
}
int main() {
    cin >> T;
    while (T--) {
        ll l1, l2, r1, r2;
        scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
        ll ans = 0;
        ll len1 = (r1 - l1 + 1) % mod, len2 = (r2 - l2 + 1) % mod;
        for (ll i = 0; i <= 62; i++) {
            ll cnt10 = Sub(cal0(r1, i), cal0(l1 - 1, i));
            ll cnt20 = Sub(cal0(r2, i), cal0(l2 - 1, i));
            ll p10 = cnt10 % mod; ll p11 = Sub(len1, p10);
            ll p20 = cnt20 % mod; ll p21 = Sub(len2, p20);
            ll tmp = (p10 * p21%mod + p11 * p20%mod) % mod;
            ans = (ans + (tmp * ((1ll << i) % mod) % mod)) % mod;
        }
        ans = ans * inv(len1) % mod*inv(len2) % mod;
        printf("%lld\n", ans);
    }
    return 0;
};

 

G. 牛牛的Link Power II

 

题意：从1到n共n个数，每个数有0或1标记，两个都为1的点的贡献为两者的差的绝对值，问所有点对的贡献值和。有多次操作，把0变1或把1变0，问每次操作后的总贡献值。

新插入一个点i，产生的贡献为它后面所有为1的数的和-后面为1的数个数* i+前面为1的数的个数* i-前面为1的数的和。由于保证了插入前该点一定为0，所以前后为1的点就是全局的为1点.

删除时也是类似。

所以可以分两个线段树维护点数和数的和，每次操作动态更新。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1000000007;
int n, m;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll t1[maxn << 2], t2[maxn << 2];
void update1(int l, int r, int rt, int q, ll x) {
    if (l == r) {
        t1[rt] = x;
        return;
    }
    if (q <= mid)update1(lson, q, x);
    else update1(rson, q, x);
    t1[rt] = t1[rt << 1] + t1[rt << 1 | 1];
}
void update2(int l, int r, int rt, int q, int x) {
    if (l == r) {
        t2[rt] = x;
        return;
    }
    if (q <= mid)update2(lson, q, x);
    else update2(rson, q, x);
    t2[rt] = t2[rt << 1] + t2[rt << 1 | 1];
}
ll query1(int l, int r, int rt, int ql, int qr) {
    if (ql > qr)return 0;
    if (ql <= l && qr >= r)return t1[rt];
    ll res = 0;
    if (ql <= mid)res = (res + query1(lson, ql, qr)) % mod;
    if (qr > mid)res = (res + query1(rson, ql, qr)) % mod;
    return res;
}
ll query2(int l, int r, int rt, int ql, int qr) {
    if (ql > qr)return 0;
    if (ql <= l && qr >= r)return t2[rt];
    ll res = 0;
    if (ql <= mid)res = (res + query2(lson, ql, qr)) % mod;
    if (qr > mid)res = (res + query2(rson, ql, qr)) % mod;
    return res;
}
ll ans;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        scanf(" %c", &c);
        if(c=='1'){
            update1(1, n, 1, i, 1);
            update2(1, n, 1, i, i);
            ll tmp = query2(1, n, 1, i + 1, n) - 1ll * i*query1(1, n, 1, i + 1, n);
            while (tmp < 0)tmp += mod;
            tmp %= mod;
            ll tmp2 = 1ll * i*query1(1, n, 1, 1, i - 1) - query2(1, n, 1, 1, i - 1);
            while (tmp2 < 0)tmp2 += mod;
            tmp2 %= mod;
            ans = (ans + tmp + tmp2) % mod;
        }
    }
    cout << ans << endl;
    cin >> m;
    while (m--) {
        int op, b;
        scanf("%d%d", &op, &b);
        if (op == 1) {
            update1(1, n, 1, b, 1);
            update2(1, n, 1, b, b);
            ll tmp = query2(1, n, 1, b + 1, n) - 1ll * b*query1(1, n, 1, b + 1, n);
            while (tmp < 0)tmp += mod;
            tmp %= mod;
            ll tmp2 = 1ll * b*query1(1, n, 1, 1, b - 1) - query2(1, n, 1, 1, b - 1);
            while (tmp2 < 0)tmp2 += mod;
            tmp2 %= mod;
            ans = (ans + tmp + tmp2) % mod;
        }
        else {
            update1(1, n, 1, b, 0);
            update2(1, n, 1, b, 0);
            ll tmp = query2(1, n, 1, b + 1, n) - 1ll * b*query1(1, n, 1, b + 1, n);
            while (tmp < 0)tmp += mod;
            tmp %= mod;
            ll tmp2 = 1ll * b*query1(1, n, 1, 1, b - 1) - query2(1, n, 1, 1, b - 1);
            while (tmp2 < 0)tmp2 += mod;
            tmp2 %= mod;
            ans = (ans - tmp - tmp2 + 2 * mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

J. 牛牛的宝可梦Go

 

题意：给定一个图，在某些时间会出现宝可梦，每只都有战斗力，出现后仅当人恰好在该点时才会抓到，否则立刻消失。初始在点1，移动花1，问最多有多少战斗力。

最短路+dp优化

把宝可梦按时间排序，设 $dp[i]$ 为到第 $i$ 只宝可梦的最大战斗力。

$dp[i]=max(dp[j]_{dis[i][j]\leq t[i]-t[j]})$

由于最长距离不会超过200，所以和 $i$ 差距超过两百的一定可以及时到达，所以可以混在一起，就从 $O(k^2)$ 优化到 $O(200k)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const ll mod = 1000000007;
int n, m, k;
ll d[300][300]; ll dp[maxn], ans;
void floyd() {
    for (int i = 1; i <= n; i++)d[i][i] = 0;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}
struct X
{
    int p;
    ll t, v;
    bool operator<(const X& rhs)const {
        return t < rhs.t;
    }
}a[maxn];
int main() {
    memset(d, 0x3f, sizeof(d));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        d[u][v] = d[v][u] = 1;
    }
    floyd();
    scanf("%d", &k);
    for (int i = 1; i <= k; i++)scanf("%lld%d%lld", &a[i].t, &a[i].p, &a[i].v);
    a[0].p = 1, a[0].t = a[0].v = 0;
    ll premax = 0;
    fill(dp + 1, dp + k + 1, -inf);
    sort(a + 1, a + k + 1);
    for (int i = 1; i <= k; i++) {
        if (i <= 200) {
            for (int j = 0; j < i; j++)
                if (d[a[i].p][a[j].p] <= a[i].t - a[j].t) {
                    dp[i] = max(dp[i], dp[j] + a[i].v);
                }
        }
        else {
            dp[i] = premax + a[i].v;
            for (int j = i - 1; i - j <= 200; j--) {
                if (d[a[i].p][a[j].p] <= a[i].t - a[j].t)
                    dp[i] = max(dp[i], dp[j] + a[i].v);
            }
            premax = max(premax, dp[i - 200]);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
};