2022牛客寒假算法基础集训营2_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
目录
A-小沙的炉石
解题思路：数学题，结论题。首先有个非常重要的点是使用攻击牌是一个定值的话，我们的攻击范围是一个区间上的任意的伤害值。设攻击牌使用 a 次，回复牌使用 b 次（其中暗含了一个条件为 ），那么最小伤害是先在使用回复牌的基础上将 a 次攻击牌使用完，最后再将回复牌全部用完，造成的伤害为
；最大伤害是先将 b 次回复牌全部用完，再使用攻击牌，造成的伤害为
。对于使用不同攻击牌数量的不同区间，可以计算一下它们什么条件下能合并，也就是令上个区间的右端点大于等于当前区间的左端点减一，即
，将
代入，可以解出
时，区间可以合并，那么只需要特判
时的情况即可：b = 1时，区间分别为 [1, 2]，[4, 5]；b = 2时，区间分别为 [1, 3]，[4, 7]，[9, 12]，可以发现只有当 b = 1 且 x = 3 时和 b = 2 且 x = 8 时不能合并。其它情况下只要 x 小于等于伤害最大值即可斩杀，否则就不能斩杀。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n, m, k;
cin >> n >> m >> k;
ll a = min(n, m + 1);
ll ans = a * m + a * (a + 1) / 2;
while(k--){
ll x;
cin >> x;
if(m == 1 && x == 3 || m == 2 && x == 8){
cout << "NO" << endl;
continue;
}
if(x <= ans) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}B-小沙的魔法
解题思路：将需要上升较多的城市相关的通道优先加入图中形成极大连通子图（会形成多个极大连通子图），这样每个极大连通子图只需要操作最大上升高度的次数就可以将其中的城市都完成需要上升的高度，由于操作数不够而剩下的城市单独进行操作。具体操作时可以先把每座城市需要上升的高度累加，将有通道的两座城市需要上升的最小高度记录下来并排序。通过并查集的查找和合并来进行操作1，进行合并时将前面累加的数减去两座城市的最小上升高度（因为一个极大连通子图中只需要操作最大上升高度次数）。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 500005, M = 5000005;
int f[M]; // f[i]表示i结点的祖先(f[i] = i表示i为孤立结点)
ll h[N]; // h[i]表示第i座城市需要上升的高度
struct node{
int x, y;
int height;
bool operator < (const node &u) const{
return height > u.height;
}
}e[M];
int find(int x){
if(f[x] != x) f[x] = find(f[x]);
return f[x];
}
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
ll ans = 0;
for(int i = 1; i <= n; i++){
cin >> h[i];
ans += h[i];
f[i] = i;
}
for(int i = 1; i <= m; i++){
cin >> e[i].x >> e[i].y;
e[i].height = min(h[e[i].x], h[e[i].y]);
}
sort(e + 1, e + m + 1);
int x = min(5 * n, m);
for(int i = 1; i <= m; i++){
if(x == 0) break;
int a = find(e[i].x), b = find(e[i].y);
if(a != b){
ans -= e[i].height;
f[a] = b;
x--;
}
}
cout << ans << endl;
return 0;
}C-小沙的杀球
解题思路：签到题，遇到1的时候判断体力是否够杀球，不够就选择不杀，恢复体力；遇到0的时候恢复体力。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll x, a, b;
cin >> x >> a >> b;
string s;
cin >> s;
int len = s.size();
int cnt = 0;
for(int i = 0; i < len; i++){
if(s[i] == '1' && x >= a){
x -= a;
cnt++;
}
else x += b;
}
cout << cnt << endl;
return 0;
}D-小沙的涂色
解题思路：大模拟构造题。根据 n % 3 的值分别为 0，1，2 时进行构造（构造方法很多，下面代码用的其中一种）。注意 n % 3 = 0 时无法满足题意，除此之外还需特判 n == 1 时的情况。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int n, idx;
int a[N][N];
void draw1(int x, int y){ // 1 1
for(int i = x; i <= n; i += 3){ // 1 2
for(int j = y; j <= n; j += 2){ // 2 2
a[i][j] = a[i][j + 1] = a[i + 1][j] = ++idx;
a[i + 1][j + 1] = a[i + 2][j] = a[i + 2][j + 1] = ++idx;
}
}
}
// 1
void draw2(int x){ // 1 1 2
for(int i = x; i <= n; i++){ // 2 2
if(i & 1) a[i - 1][1] = a[i][1] = a[i][2] = ++idx;
else a[i - 1][3] = a[i][2] = a[i][3] = ++idx;
}
}
void draw3(int x, int y){ // 1 1 2
for(int j = y; j <= n; j += 3){ // 1 2 2
a[x][j] = a[x][j + 1] = a[x + 1][j] = ++idx;
a[x][j + 2] = a[x + 1][j + 2] = a[x + 1][j + 1] = ++idx;
}
}
void pf(){
cout << "YES" << endl;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cout << a[i][j] << ' ';
}
cout << endl;
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
if(n % 3 == 0) cout << "NO" << endl;
else if(n == 1) cout << "YES" << endl << 0 << endl;
else if(n % 3 == 1){
idx = 5;
a[1][1] = a[1][2] = a[2][1] = 1;
a[4][3] = a[4][4] = a[3][4] = 2;
a[3][1] = a[3][2] = a[4][2] = 3;
a[2][2] = a[2][3] = a[3][3] = 4;
a[1][3] = a[1][4] = a[2][4] = 5;
draw3(1, 5);
draw3(3, 5);
if(n & 1) draw2(5), draw1(5, 4);
else draw1(5, 1);
pf();
}
else if(n % 3 == 2){
a[1][1] = a[1][2] = a[2][2] = ++idx;
draw3(1, 3);
if(n & 1) draw2(3), draw1(3, 4);
else draw1(3, 1);
pf();
}
return 0;
}E-小沙的长路
解题思路：结论题，最小值是构造尽可能无环的有向图，这样最多经历每个点一次，路径长度为 ；最大值是完全图中删去最短的边数构造欧拉迹（欧拉通路），即只要控制仅有两个结点度数为奇数，其它结点度数为偶数，对于奇数结点的完全图，每条边的度均为偶数，因此最大值即为完全图的边数
；对于偶数结点的完全图，每条边的度数均为奇数，要控制成欧拉迹必须删去
条边，变成欧拉迹后还能多走一步，因此最大值为
。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n;
cin >> n;
cout << n - 1 << ' ';
if(n & 1) cout << n * (n - 1) / 2 << endl;
else cout << n * (n - 1) / 2 - n / 2 + 1 << endl;
return 0;
}F-小沙的算数
解题思路：由于乘号优先级高，可以将每个加号当作分隔符，分隔成若干个区间，每个区间的值单独预处理出来，再在每次询问中对相应区间的值进行修改，并计算出式子结果输出。（由于数值较大需要取模，除法需要变成乘以它的逆元，减法需要加上模数再进行取模）
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f;
const int mod = 1000000007;
const int N = 1000005;
char s[N];
ll a[N], pa[N], b[N];
ll qmi(ll a, ll b){
ll res = 1;
a %= mod;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll inv(ll x){
return qmi(x, mod - 2) % mod;
}
int main(){
int n, q;
cin >> n >> q;
cin >> s + 1;
s[n] = '+';
for(int i = 1; i <= n; i++) cin >> a[i];
ll pos = 0, now = 1;
memset(pa, -1, sizeof pa);
for(int i = 1; i <= n; i++){
now = now * a[i] % mod;
if(s[i] == '+'){
pa[i] = pos;
b[pos++] = now;
now = 1;
}
else pa[i] = pos;
}
ll x, y, ans = 0;
for(int i = 0; i < pos; i++) ans = (ans + b[i]) % mod;
while(q--){
cin >> x >> y;
int pos = pa[x];
ll tmp = b[pos] * y % mod * inv(a[x]) % mod;
if(tmp >= b[pos]) ans = (ans + (tmp - b[pos] + mod) % mod) % mod;
else ans = (ans - (b[pos] - tmp + mod) % mod + mod) % mod;
a[x] = y;
b[pos] = tmp;
cout << ans << endl;
}
return 0;
}G-小沙的身法
解题思路：LCA算法，树上差分思想。将树用邻接表存储（双向），通过dfs将每个结点由上到下的前缀和、由下到上的前缀和都存储起来（设由下到上用存储，由上到下用
存储）。那么总体力消耗为从地面跳到起始点 u 的消耗加上 u 从下到 u 和 v 的最小公共祖先结点的消耗再加上从 u 和 v 的最小公共祖先结点到 v 结点的消耗，即
。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005, M = 2000005;
int a[N], h[N], e[M], ne[M], idx;
int fa[N][20], deep[N]; // fa[i][j]表示i结点的第2^j级祖先
ll sum[N][2]; // sum[i][0]表示i结点向祖先结点跳（由下到上）的前缀和
// sum[i][1]表示i结点的父结点向i结点跳（由上到下）的前缀和
void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int f){
fa[u][0] = f;
deep[u] = deep[f] + 1;
sum[u][0] = sum[f][0] + max(0, a[f] - a[u]);
sum[u][1] = sum[f][1] + max(0, a[u] - a[f]);
for(int i = 1; i < 20; i++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(int i = h[u]; i != -1; i = ne[i]){
int v = e[i];
if(v != f) dfs(v, u);
}
}
int lca(int x, int y){
if(deep[x] < deep[y]) swap(x, y);
for(int i = 19; i >= 0; i--){
if(deep[fa[x][i]] >= deep[y]){
x = fa[x][i];
}
}
if(x == y) return y;
for(int i = 19; i >= 0; i--){
if(fa[x][i] != fa[y][i]){
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(1, 0);
while(m--){
int u, v;
cin >> u >> v;
cout << a[u] + sum[u][0] + sum[v][1] - sum[lca(u, v)][0] - sum[lca(u, v)][1] << endl;
}
return 0;
}H-小沙的数数
解题思路：根据二进制拆分，将 拆分成每一位只有 0 或 1，要想
且
最大，就要保证每个数在同一个二进制位只能有一个 1，即保证
。然后由于每一位都不互相干扰，所以可能产生的情况为
种，设二进制下
有
个 1，则总方案数为
种。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
ll quick_pow(ll a, ll b){
ll res = 1;
a %= mod;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n, m;
cin >> n >> m;
ll cnt = 0;
while(m){
if(m & 1) cnt++;
m >>= 1;
}
cout << quick_pow(n, cnt) << endl;
return 0;
}I-小沙的构造
解题思路：细节较多的模拟题。由于前25个字符是单独对称的，使用两个相同字符时只用了一种，而后10个字符是配套对称的，使用一对字符时用了两种。还需注意 为奇数和偶数时的写法不同，并且注意不成立时的条件特判。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
string s = "\"!'*+-.08:=^_WTYUIOAHXVM|", l = "<\\[{(", r = ">/]})", ans;
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
if(n == m && n == 1) cout << s[24];
for(int i = 0; i < 5; m -= 2, i++){
if(m <= 2 && (n & 1 || m <= 1)) break;
ans = l[i] + ans + r[i];
}
for(int i = 0; i < 24; m--, i++){
if(m <= 1) break;
ans = s[i] + ans + s[i];
}
if(ans.size() >= n || m > 1) cout << -1;
else{
while(ans.size() + 2 <= n)
if(m == 1) ans = s[24] + ans + s[24];
else ans = l[0] + ans + r[0];
if(n & 1){
for(int i = 0; i < n - 1; i++){
if(i == n / 2) cout << s[24];
cout << ans[i];
}
}
else cout << ans;
}
return 0;
}J-小沙的Dota
解题思路：对于不同的技能施放所需要的三颗法球不同，可以列表存储。由于需要进行的两种操作分别为放技能（区间查询）和改手法（定点修改），且数据量不小，可以通过线段树维护DDP来实现。由于施放技能只与法球属性有关，与顺序无关，因此每个技能三颗法球就有最多 6 种排列方式，可以使用 next_permutation() 进行全排列。在操作前预处理好每个技能之间的关系存入（表示第i个技能的第x种排列和第j个技能的第y种排列的关系）中，取值0，1，2，3的含义参考下面代码。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 100005;
int a[N];
int skill[10][3] = { // 1代表火球，2代表雷球，3代表冰球
{1, 1, 1}, {1, 1, 2}, {1, 1, 3},
{3, 3, 3}, {3, 3, 1}, {3, 3, 2},
{2, 2, 2}, {2, 2, 1}, {2, 2, 3}, {1, 2, 3}
};
struct Matrix{ // 矩阵
int c[6][6];
Matrix(){
for(int i = 0; i < 6; i++)
for(int j = 0; j < 6; j++)
c[i][j] = ((i == j) ? 0 : INF);
}
}M[10][10];
Matrix operator * (Matrix A, Matrix B){ // 矩阵乘法重载
Matrix C;
for(int i = 0; i < 6; i++){
for(int j = 0; j < 6; j++){
C.c[i][j] = INF;
for(int k = 0; k < 6; k++){
C.c[i][j] = min(C.c[i][j], A.c[i][k] + B.c[k][j]);
}
}
}
return C;
}
struct sgt_tree{ // 线段树结点
int lchild, rchild;
Matrix v;
}sgt[4 * N];
int root, topt;
void sgt_build(int &now, int l, int r){ // 线段树建立
if(!now) now = ++topt;
if(l == r){
sgt[now].v = M[a[l]][a[l + 1]];
return;
}
int mid = l + r >> 1;
sgt_build(sgt[now].lchild, l, mid);
sgt_build(sgt[now].rchild, mid + 1, r);
sgt[now].v = sgt[sgt[now].lchild].v * sgt[sgt[now].rchild].v;
}
void sgt_modify(int &now, int l, int r, int k){ // 线段树修改
if(!now) now = ++topt;
int mid = l + r >> 1;
if(l == r){
sgt[now].v = M[a[l]][a[l + 1]];
return;
}
if(k <= mid) sgt_modify(sgt[now].lchild, l, mid, k);
else sgt_modify(sgt[now].rchild, mid + 1, r, k);
sgt[now].v = sgt[sgt[now].lchild].v * sgt[sgt[now].rchild].v;
}
Matrix res;
void sgt_query(int &now, int l, int r, int x, int y){ // 线段树查询
if(!now) now = ++topt;
int mid = l + r >> 1;
if(l >= x && r <= y){
res = res * sgt[now].v;
return;
}
if(x <= mid) sgt_query(sgt[now].lchild, l, mid, x, y);
if(y > mid) sgt_query(sgt[now].rchild, mid + 1, r, x, y);
}
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i]--;
}
// 预处理不同技能之间的关系
int s1[3], s2[3];
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
for(int k = 0; k < 3; k++){
s1[k] = skill[i][k];
s2[k] = skill[j][k];
}
for(int x = 0; x < 6; x++){
for(int y = 0; y < 6; y++){
if(s1[0] == s2[0] && s1[1] == s2[1] && s1[2] == s2[2]) M[i][j].c[x][y] = 0;
else if(s1[1] == s2[0] && s1[2] == s2[1]) M[i][j].c[x][y] = 1;
else if(s1[2] == s2[0]) M[i][j].c[x][y] = 2;
else M[i][j].c[x][y] = 3;
next_permutation(s2, s2 + 3);
}
next_permutation(s1, s1 + 3);
}
}
}
sgt_build(root, 1, n - 1);
int op, l, r;
while(m--){
cin >> op >> l >> r;
if(op == 1){
if(l == r){
cout << 3 << endl;
continue;
}
Matrix zero;
res = zero; // 初始化res矩阵
sgt_query(root, 1, n - 1, l, r - 1);
int ans = INF;
for(int i = 0; i < 6; i++){
for(int j = 0; j < 6; j++){
ans = min(ans, res.c[i][j]);
}
}
cout << ans + 3 << endl;
}
if(op == 2){
a[l] = r - 1;
if(l != 1) sgt_modify(root, 1, n - 1, l - 1);
if(l != n) sgt_modify(root, 1, n - 1, l);
}
}
return 0;
}K-小沙的步伐
解题思路：签到题，每走一步都会使那个点和5这个点都经过一次（既要过去又要回来），注意特判当出现的是5时，不需要任何移动。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <climits>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int cnt[10];
int main(){
//freopen("input.txt", "r", stdin);
cin.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
cin >> s;
int n = s.size();
for(int i = 0; i < n; i++){
if(s[i] != '5'){
cnt[s[i] - '0']++;
cnt[5]++;
}
}
for(int i = 1; i < 9; i++)
cout << cnt[i] << ' ';
cout << cnt[9] << endl;
return 0;
}L、M-小沙的remake
解题思路：树状数组维护动态前缀和。先按照气运值排序，然后遍历一遍气运，每次求当前点和当前点前 位的区间和，并将该值加入到当前位下标的树状数组中进行更新。最后对 n 进行查询查询结果即为要求的方案数。
AC代码：
#include<bits/stdc++.h>
namespace GenHelper
{
int z1,z2,z3,z4,z5,u,res;
int get()
{
z5=((z1<<6)^z1)>>13;
z1=((int)(z1&4294967)<<18)^z5;
z5=((z2<<2)^z2)>>27;
z2=((z2&4294968)<<2)^z5;
z5=((z3<<13)^z3)>>21;
z3=((z3&4294967)<<7)^z5;
z5=((z4<<3)^z4)>>12;
z4=((z4&4294967)<<13)^z5;
return (z1^z2^z3^z4);
}
int read(int m) {
u=get();
u>>=1;
if(m==0)res=u;
else res=(u/2345+1000054321)%m;
return res;
}
void srand(int x)
{
z1=x;
z2=(~x)^(0x23333333);
z3=x^(0x12345798);
z4=(~x)+51;
u = 0;
}
}
using namespace GenHelper;
using namespace std;
typedef long long ll;
const int N=2e6+7,mod=1e9+7;
int a[N],b[N];
ll tree[N];
struct node{
int id, x;
bool operator < (const node &u) const{
return x == u.x ? id < u.id : x < u.x;
}
}s[N];
inline int lowbit(int x){
return x & -x;
}
void add(int x, ll c){
while(x < N){
tree[x] = (tree[x] + c) % mod;
x += lowbit(x);
}
}
ll ask(ll x){
ll res = 0;
while(x){
res = (res + tree[x]) % mod;
x -= lowbit(x);
}
return res;
}
int main(){
int n,seed;
scanf("%d %d",&n,&seed);
srand(seed);
for(int i=1;i<=n;i++){
a[i]=read(0),b[i]=read(i);
s[i].id = i, s[i].x = a[i];
}
sort(s + 1, s + n + 1);
for(int i = 1; i <= n; i++){
int id = s[i].id;
ll x = (ask(id - 1) - ask(id - b[id] - 1) + 1 + mod) % mod;
add(id, x);
}
printf("%lld\n", ask(n));
return 0;
}