2022牛客寒假算法基础集训营2

A小沙的炉石

题意：

给定$n$张法术攻击牌（造成一点基础攻击）和$m$张法术回复牌（回复一点法力）。有一个随从，每使用一张法术牌就会增加法术攻击力1点。每次使用攻击牌造成的攻击是基础攻击加法术攻击，初始有一点法力，法术攻击力为0点。给定$k$个询问，是否可以恰好杀死血量为$x$的怪物。

分析：

首先可以最多攻击的次数cnt = min(m + 1, n),我们考虑最小的攻击伤害$mn$和最大的攻击伤害$mx$。那么我们很容易贪心算出每使用一张攻击牌再使用一张回复牌是最优的，$mn=cn{t}^2$，先把所有回复牌用完再使用攻击牌所造成 的伤害是最大的，$mx=cnt\ast (cnt+2m+1)/2$。那么我们对一些相邻的牌交换顺序后可以发现，该区间内的所有伤害都可以取到，那么我们二分判断即可。

code:

void solve() {
    int n, m;
    in(n), in(m);
    int cnt = min(m + 1, n);
    LL mx = 1LL * cnt * (cnt + 2 * m + 1) / 2;
    int k; in(k);
    while(k--) {
        LL x;
        in(x);
        if(x > mx) {
            puts("NO");
        } else {
            LL l = 1, r = cnt;
            while(l < r) {
                LL mid = l + r >> 1;
                LL now = mid * 1LL * (mid + 2 * m + 1) / 2;
                if(now >= x) r = mid;
                else l = mid + 1;
            }
            if(l * l <= x) puts("YES");
            else puts("NO");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

C小沙的杀球

题意：

给定一串01序列，0代表是小球，1代表高远球，只有高远球可选择进行杀球操作。初始体力x，每次杀球消耗a点，不杀球回复b点，问最多能杀多少个。

code：

模拟即可。

int main() {
	ll x, a, b;
	cin >> x >> a >> b;
	string s; cin >> s;
	ll res = 0;
	for (char c : s) {
		if (c == '0' || x < a)x += b;
		else {
			res++;
			x -= a;
		}
	}
	cout << res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

E小沙的长路

题意：

给定一个n个点的完全图，可以给每条边选择方向且每条边最多走一次，求最长路的最大值和最小值。

思路：

对于最小值：首先如果图中有一个环，那么我们肯定走环，这样会更长，所以我们要少构造有环的边，没有环的话，每个点只能走一次，即$min=n-1$。
对于最大值：那么我们肯定想每一条边都走一遍，就是构造一个欧拉通路：度数为奇数的点只能有0个或2个。那么我们就要尽可能少的删去一些边。如果n是奇数，那么我们每个点的度数都是偶数，一条边都不用删即可；否则，我们要删去$(n-2)/2$条边，使得$n-2$个点的度数变为偶数。

code:

void solve() {
    int n;
    in(n);
    cout << n - 1 << ' ';
    if(n & 1) cout << 1LL * n * (n - 1) / 2 << '\n';
    else {
        cout << 1LL * n * (n - 1) / 2 - (n - 2) / 2 << '\n';
    }
}
1
2
3
4
5
6
7
8
9

F小沙的算数

题意：

给定一个算术式，只包含$\ast 和+$运算符，$q$次询问，每次询问会修改某个数字的值，并输出修改后式子的答案。（修改是永久性修改）

思路：

首先乘法肯定是优先计算的，那么就启发我们先把乘法运算的数合并起来，看作一个连通块，之后每次修改的时候修改一下连通块的值然后更改答案即可。

code:

typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
template <typename T> void inline pr(T x) {
    if (x < 0) { putchar('-'); pr(-x); return ; }
    if (x >= 10) pr(x / 10);
    putchar((x % 10) + '0');
}

const int N = 1e6 + 10, M = N * 2, mod = 1e9 + 7;
inline LL ksm(LL a, LL b){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
//----------------------------------------------------------------------------------------//
#define int LL
int n, q, p[N];
int a[N], b[N];

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if(a != b) p[pa] = pb;
}
void solve() {
    in(n), in(q);
    string s; cin >> s;
    for(int i = 1; i <= n; i++) p[i] = i;
    for(int i = 1; i <= n; i++) in(a[i]), b[i] = a[i];
    for(int i = 2; i <= n; i++) {
        if(s[i - 2] == '*') merge(i - 1, i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(find(i) != i) {
            int pa = find(i);
            a[pa] = a[pa] * 1LL * a[i] % mod;
        } else ans = (ans + a[i]) % mod;
    }
    // D(ans);
    while(q--) {
        int x, y;
        in(x), in(y);
        int fx = find(x);
        ans = (ans - a[fx] + mod) % mod;
        a[fx] = a[fx] * ksm(b[x], mod - 2) % mod * y % mod;
        ans = (ans + a[fx]) % mod;
        b[x] = y;
        cout << ans << '\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
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

G小沙的身法

题意：

给定$n$个木桩，每个木桩离地的高度为$a[i]$，$n$个木桩构成一棵树，边代表着可以从木桩$u$跳到木桩$v$，如果$a[u]>a[v]$,则不消耗体力，否则消耗$a[u]-a[v]$点体力。$m$个询问，每次询问从木桩$x$跳到$y$的最小体力。

思路：

既然是树上的问题且是无根树，那么我们首先能想到的是先任选一个根节点去操作，操作什么呢？根据题目的要求，我们可以先求出根节点跳到每一个节点的最小体力：g[i] = g[fa] + max(0, a[i] - a[fa])。但是这样是不够的，我们思考：我们是需要$x$节点先往上跳，跳到根节点，再从根节点往下跳跳到$y$节点。所以我们还需要求出每一个点向上跳到根节点的最小体力值f[i] = f[fa] + max(0, a[fa] - a[i])，那么对于重复部分，减去它们的$LCA$即可。即ans = f[u] - f[lca(x,y)] + g[y] - g[lca(x,y)] + a[x].

code:

typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline in(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
template <typename T> void inline pr(T x) {
    if (x < 0) { putchar('-'); pr(-x); return ; }
    if (x >= 10) pr(x / 10);
    putchar((x % 10) + '0');
}

const int N = 1e6 + 10, M = N * 2, mod = 1e9 + 7;
inline LL ksm(LL a, LL b){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
//----------------------------------------------------------------------------------------//

int n, m;
int h[N], e[M], ne[M], idx;
LL a[N];
int depth[N], fa[N][25];
LL f[N], g[N]; //f[x]向上跳，g[x]向下跳
inline void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void dfs(int u, int FA = 0) {
    depth[u] = depth[FA] + 1;
    fa[u][0] = FA;
    for(int k = 1; k < 20; k++) fa[u][k] = fa[fa[u][k - 1]][k - 1];

    f[u] = f[FA] + max(0LL, a[FA] - a[u]);
    g[u] = g[FA] + max(0LL, a[u] - a[FA]);

    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == FA) continue;
        dfs(j, u);
    }
}
inline int LCA(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    for(int k = 20; k >= 0; k--) {
        if(depth[fa[a][k]] >= depth[b]) 
            a = fa[a][k];
    }
    if(a == b) return a;
    for(int k = 20; k >= 0; k--) {
        if(fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
void solve() {
    in(n), in(m);
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++) in(a[i]);
    for(int i = 1; i < n; i++) {
        int x, y; in(x), in(y);
        add(x, y); add(y, x);
    }
    dfs(1); 
    while(m--) {
        int x, y;
        in(x), in(y);
        int L = LCA(x, y);
        LL ans = f[x] - f[L] + g[y] - g[L] + a[x];
        cout << ans << '\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
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76

H小沙的数数

题意：

给定$n,m(n,m<10^{18})$，构造一个长度为$n$数列满足的数组的和等于$m$的情况下$sum=a[1]\oplus a[2]\oplus ...\oplus a[n]$的值尽可能的大。求有多少种方案。

分析：

对于异或运算，相当于无进位加法。更严谨的说：$a+b=(a\&b)\ast 2+a\oplus b$， 要使$a\oplus b$最大，即让$a\&b=0$。
那么我们想让异或和$sum$尽可能的大，就是让$sum=m$，同时所有数的二进制下的每一位最多只有一个1，且该位是由$m$决定的。同时该位的1可以放在任意一个数的相应位上。

code：

void solve() {
    LL n, m;
    in(n), in(m);
    n %= mod;
    LL res = 1;
    for(; m; m -= lowbit(m)) res = res * n % mod;
    cout << res << '\n';

}
1
2
3
4
5
6
7
8
9

L/M小沙的remake

题意：

有$n$个物品，每个物品价值为$a[i]$,我们可以选择这个物品，也可以不，如果选择它的话，保证在它前面的区间$[i-b[i],i)$内所有选择过的物品的价值都小于它。问有多少种选择方案。

思路：

既然要保证按价值大小进行选择，那么我们就先按照价值对其进行排序。然后用树状数组优化转移即可。

code：

int a[N], b[N];
pii p[N];
LL tr[N];
int n,seed;

inline void add(int x, LL v) {
    while(x <= n) {
        tr[x] = (tr[x] + v) % mod;
        x += lowbit(x);
    }
}
inline LL get(int x) {
    LL sum = 0;
    while(x) {
        sum = (sum + tr[x]) % mod;
        x -= lowbit(x);
    }
    return sum;
}
void solve() {
    scanf("%d %d",&n,&seed);
	srand(seed);
	for(int i = 1; i <= n; i++) {
		a[i]=read(0),b[i]=read(i);
        p[i].fi = a[i];
        p[i].se = i;
	}
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; i++) {
        LL now = (get(p[i].se) - get(p[i].se - b[p[i].se] - 1) + 1 + mod) % mod;
        add(p[i].se, now);
    }
    cout << get(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
34