2018 Nowcoder Multi-University Training Contest 2

目录

• Contest Info
• Solutions
  • H. travel
  • I. car

Contest Info

---

[Practice Link](https://ac.nowcoder.com/acm/contest/140#question)

Solved	A	B	C	D	E	F	G	H	I	J	K
6/10	Ø	.	.	Ø	.	.	Ø	Ø	Ø	Ø	.

• O 在比赛中通过
• Ø 赛后通过
• ! 尝试了但是失败了
• . 没有尝试

Solutions

---

### A. run

题意：
白云每次可以移动(1)米或者(k)米，询问移动的米数在([L, R])范围内的方案数有多少。

思路：
(dp[i][0/1])表示到第(i)米，是通过(1)米的方式过来的还是(k)米的方式过来的，递推即可。

代码：

#include <bits/stdc++.h>
using namespace std;

#define N 100010
const int p = 1e9 + 7;
int f[N][2], g[N];
int q, k, l, r;
void add(int &x, int y) {
	x += y;
	if (x >= p) {
		x -= p;  
	}
}

int main() {
	scanf("%d%d", &q, &k);
	memset(f, 0, sizeof f);
	f[0][0] = 1;
	for (int i = 0; i <= 100000; ++i) {
		add(f[i + 1][0], (f[i][0] + f[i][1]) % p);
		if (i + k <= 100000) {
			add(f[i + k][1], f[i][0]);
		}
	} 
	memset(g, 0, sizeof g);
	for (int i = 1; i <= 100000; ++i) {
		g[i] = g[i - 1];
		add(g[i], f[i][0]);
		add(g[i], f[i][1]);
	}
	while (q--) {
		scanf("%d%d", &l, &r);
		printf("%d
", (g[r] - g[l - 1] + p) % p);	
	}
	return 0;
}

---

### D. monrey

题意：
有(n)个物品，从(1)到(n)的顺序去访问，身上最多只能携带一个物品，每次可以买进或者卖出物品，身上有无限的钱，问最后获得的利润最多是多少。

思路：
考虑将买入和卖出合并成一种操作，买入就是减去收益，卖出是增加收益，维护两个堆，遍历(i)个物品。

• 如果当次是买入，那么去找之前收益最高的一个卖出操作，或者直接买入。
• 如果当次是卖出，那么取找之前收益最高的一个买入操作。

代码:

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 100010
int n, a[N]; 
struct node {
	ll tot; int cnt;
	node() {}
	node (ll tot, int cnt) : tot(tot), cnt(cnt) {} 
	bool operator < (const node &other) const {
		if (tot == other.tot) {
			return cnt > other.cnt;
		}
		return tot < other.tot;
	}
};

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
		}
		//0表示上一次操作是买入
		//1表示上一次操作是卖出 
		priority_queue <node> pq[2];
		node res = node(0, 0);
		pq[0].push(node(-a[1], 1));
		node t1, t2;
		for (int i = 2; i <= n; ++i) {
			pq[0].push(node(-a[i], 1));
			if (!pq[0].empty()) {
				t1 = pq[0].top();
				pq[1].push(node(t1.tot + a[i], t1.cnt + 1));
			}
			if (!pq[1].empty()) {
				t2 = pq[1].top();
				pq[0].push(node(t2.tot - a[i], t2.cnt + 1));
			}
			if (!pq[1].empty()) {
				res = max(res, pq[1].top());
			}
		}
		printf("%lld %d
", res.tot, res.cnt);
	}
	return 0;
}

---

### G. transform

题意：
一维坐标系上，在(x_i)有(a_i)个物品，每次移动一个物品的代价为(2 cdot abs(x_u - x_v))，现在有(T)元钱，问在不超过(T)的代价下，移动物品使得
在同一个位置上的物品最多。

思路：
显然可以二分物品数量，check的时候枚举左端点，双指针维护右端点，多余的部分从右端回退。
再枚举右端点，反着搞一遍。

代码：

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 500010
int n, x[N], a[N];
ll sum[N], cost[N];
ll T, L, R, need;
int u;
 
ll cost_l(int i) {
    //将L+1~i的物品移动到i的费用
    ll a = (sum[i] - sum[L]) * x[i] - (cost[i] - cost[L]);
    //将i+1~R的物品移动到i的费用
    ll b = (cost[R] - cost[i]) - x[i] * (sum[R] - sum[i]);
    //将多余的物品从R移动到i的费用
    ll c = (sum[R] - sum[L] - need) * (x[R] - x[i]);
    return a + b - c;
}
 
ll cost_r(int i) {
    //将L+1~i的物品移动到i的费用
    ll a = (sum[i] - sum[L]) * x[i] - (cost[i] - cost[L]);  
    //将i+1~R的物品移动到i的费用
    ll b = (cost[R] - cost[i]) - x[i] * (sum[R] - sum[i]);
    //将多余的物品从L移动到i的费用
    ll c = (sum[R] - sum[L] - need) * (x[i] - x[L + 1]);
    return a + b - c;
}
 
bool check(ll x) {
    need = x;
    L = 0, R = 1, u = 0;
    while (1) {
        while (R < n && sum[R] - sum[L] < x) ++R;
        if (sum[R] - sum[L] < x) break;
        while (u < L) ++u;
        while (u < R && cost_l(u) > cost_l(u + 1)) ++u;
        if (cost_l(u) <= T) return 1;
        ++L;
    }
    L = n - 1, R = n, u = n;
    while (1) {
        while (L > 0 && sum[R] - sum[L] < x) --L;
        if (sum[R] - sum[L] < x) break;
        while (u > R) --u;
        while (u > L && cost_r(u) > cost_r(u - 1)) --u;
        if (cost_r(u) <= T) return 1;
        --R;
    }
    return 0;
}
 
int main() {
    while (scanf("%d%lld", &n, &T) != EOF) {
        T /= 2;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", x + i);
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            sum[i] = sum[i - 1] + a[i];
            cost[i] = cost[i - 1] + 1ll * a[i] * x[i];
        }
        ll l = 0, r = sum[n], res = -1;
        while (r - l >= 0) {
            ll mid = (l + r) >> 1;
            if (check(mid)) {
                l = mid + 1;
                res = mid;
            } else {
                r = mid - 1;
            }
        }
        printf("%lld
", res);
    }
    return 0;
}

H. travel

题意：
询问一棵树上三条不相交路径的最大点权和。

思路：
(f[u][x][y])表示以(u)为根的子树中，(u)的状态为(x)，已经选了(y)条树链的最大点权和是多少。
三种状态：

• 当前点不选
• 当前点是链的一端
• 当前点是链的拐点，即两条链的交界处

考虑转移：

• 对于(y)的转移可以枚举(y)和(i)，可以推出(j)
• 注意(y)和(i)的枚举要降序枚举。
• 对于当前点是拐点，转移过来的可以是链+链，也可以是拐点+不选
• 对于当前点是链，可以是当前点是空，转移过来是链，也可以是当前点是链，转移过来的是空
• 对于当前点不选，那么可以是任何状态转移过来，但是当前点不要选。
• 最后答案是(f[1][0][3])

代码：

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 400010
int n, a[N];
vector <vector<int>> G;
// 0 表示当前点不选
// 1 表示当前点链的一端
// 2 表示当前点是拐点
// 第三维表示已经选了0, 1, 2, 3条链
ll f[N][3][4];
 
void Max(ll &x, ll y) {
    if (x < y) x = y;
}
void DFS(int u, int fa) {
    f[u][1][0] = a[u];
    for (auto v : G[u]) if (v != fa) {
        DFS(v, u);
        //转移2状态
        for (int k = 2; ~k; --k) {
            for (int i = k, j; ~i; --i) {
                j = k - i; 
                //链+链
                Max(f[u][2][k], f[u][1][i] + f[v][1][j]);
                //拐点+空
                Max(f[u][2][k], f[u][2][i] + f[v][0][j]);
            }
        }
 
        //转移1状态
        for (int k = 2; ~k; --k) {
            for (int i = k, j; ~i; --i) {
                j = k - i;
                Max(f[u][1][k], f[u][0][i] + a[u] + f[v][1][j]);
                Max(f[u][1][k], f[u][1][i] + f[v][0][j]);
            }
        }
         
        //转移0状态
        for (int k = 3; ~k; --k) {
            for (int i = k, j; ~i; --i) {
                j = k - i;
                f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][0][j]);
                if (j) {
                    f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][1][j - 1]);
                    f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][2][j - 1]);
                }
            }
        }
 
    }
    for (int k = 3; k; --k) {
        Max(f[u][0][k], f[u][1][k - 1]);
        Max(f[u][0][k], f[u][2][k - 1]);
    }
}
 
 
 
int main() {
    while (scanf("%d", &n) != EOF) {
        memset(f, 0, sizeof f);
        G.clear(); G.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        for (int i = 1, u, v; i < n; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        DFS(1, 0);
        printf("%lld
", f[1][0][3]);
    }
    return 0;
}

I. car

题意：
在一个(n cdot n)的二维平面上，要放置尽量多的小车，使得每一俩小车都要直行到它的对面边界，其中有一些障碍物，小车行驶的时候不能相撞，也不能碰到障碍物，
问最多放多少辆小车。

思路：

• 显然每一行每一列最多放一辆小车。
• 假设(a[x][y])有障碍物，那么第(x)行第(y)列都不能有小车。
• 如果(n)是奇数，那么第(frac{n + 1}{2})行，第(frac{n + 1}{2})只能放一辆小车。

代码：

#include <bits/stdc++.h>
using namespace std;
 
#define N 100010
int n, m;
int vis[N][2];
 
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(vis, 0, sizeof vis);
        for (int i = 1, x, y; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            vis[x][0] = 1;
            vis[y][1] = 1;
        }
        int ans = 0;
        if (n & 1) {
            if (vis[n / 2 + 1][0] == 0 && vis[n / 2 + 1][1] == 0) {
                ++ans;
                vis[n / 2 + 1][0] = 1;
                vis[n / 2 + 1][1] = 1;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 2; ++j) {
                ans += (vis[i][j] == 0);
            }
        }
        printf("%d
", ans);   
    }
    return 0;
}

---

### J. farm

题意：
在(n cdot m)的农田上，有(n cdot m)棵植物，每棵植物只能施放第(a[i][j])种肥料，有(T)次操作，每次操作时将(x_1, y_1, x_2, y_2)矩形内的作物都施上第(k_i)种肥料，
一旦作物被施上不是第(a[i][j])种肥料，它就会立刻死亡。
问最后死亡的作物数目.

思路一：
考虑：
作物的施肥次数 = 第(a[i][j])种肥料的施肥次数+其他种类肥料的施肥次数。
我们先二维差分求出所有作物的总的施肥次数。
然后将操作按(k_i)分类，用二维BIT维护二维前缀和，表示(k_i)操作下作物的施肥次数。
然后再枚举初始值为(k_i)的所有作物，判断它总的施肥次数以及第(k_i)种肥料的施肥次数是否相等，不相等就挂了。
时间复杂度：(mathcal{O}(nm + T cdot log(n) cdot log(m)))

代码一：

#include <bits/stdc++.h>
using namespace std;

#define N 1000010
#define pii pair <int, int>
#define fi first
#define se second
int n, m, q;
struct node {
	int x[2], y[2];
	node() {}
	node(int x1, int y1, int x2, int y2) {
		x[0] = x1; x[1] = x2;
		y[0] = y1; y[1] = y2;  
	}
};
vector < vector <pii> > a;
vector < vector <node> > b;

struct BIT {
	vector < vector <int> > a;
	void init() {
		a.clear();
		a.resize(n + 1);
		for (int i = 0; i < n + 1; ++i) {
			a[i].resize(m + 1);
		}
	}
	void update(int x, int y, int v) {
		for (int i = x; i <= n; i += i & -i) {
			for (int j = y; j <= m; j += j & -j) {
				a[i][j] += v;
			}
		}
	}
	void update(int x1, int y1, int x2, int y2, int v) {
		update(x1, y1, v);
		update(x2 + 1, y2 + 1, v); 
		update(x1, y2 + 1, -v);
		update(x2 + 1, y1, -v);
	}
	int query(int x, int y) {
		int res = 0;
		for (int i = x; i > 0; i -= i & -i) {
			for (int j = y; j > 0; j -= j & -j) {
				res += a[i][j]; 
			}
		}
		return res;
	}
}bit;

void read(int &x) {
	x = 0; char ch;
	while (!isdigit(ch = getchar()));
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
}

int main() {
	while (scanf("%d%d%d", &n, &m, &q) != EOF) {
		a.clear(); 
		a.resize(n * m + 1);
		b.clear();
		b.resize(n * m + 1);
		bit.init();
		for (int i = 1; i <= n; ++i) {
			for (int j = 1, x; j <= m; ++j) {
				read(x);
				a[x].emplace_back(i, j);
			}
		}
		for (int i = 1, k, x1, y1, x2, y2; i <= q; ++i) {
			read(x1); read(y1); read(x2); read(y2); read(k);
			b[k].push_back(node(x1, y1, x2, y2));
			bit.update(x1, y1, x2, y2, 1);
		}
		int res = 0;
		for (int i = 1; i <= n * m; ++i) {
			for (auto it : b[i]) {
				bit.update(it.x[0], it.y[0], it.x[1], it.y[1], -1);
			}
			for (auto it : a[i]) {
				if (bit.query(it.fi, it.se) != 0) {
					++res;
				}
			}
			for (auto it : b[i]) {
				bit.update(it.x[0], it.y[0], it.x[1], it.y[1], 1);
			}
		}
		printf("%d
", res);
	}
	return 0;
}

思路二：
考虑每次施肥的时候加上的是(k_i)而不是1，那么最终如果作物没有死，那么它的值应该是(a[i][j] cdot 施肥次数)。
但是这样容易被卡，将权值映射成素数即可。
时间复杂度：(mathcal{O}(n + m + 10^7))

代码二：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 15500010
int prime[1000010], tot;
bool check[N];
void init() {
	tot = 0;
	memset(check, 0, sizeof check);
	for (int i = 2; i < N; ++i) {
		if (!check[i]) {
			prime[++tot] = i;
			if (tot >= 1000000) break;
		}
		for (int j = 1; j <= tot; ++j) {
			if (1ll * i * prime[j] >= N) break;
			check[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}
int n, m, q;
vector <vector<int>> a, c;
vector <vector<ll>> b;
template <class T>
void up(vector <vector<T>> &vec, int x1, int y1, int x2, int y2, int v) {
	vec[x1][y1] += v;
	vec[x2 + 1][y2 + 1] += v;
	vec[x1][y2 + 1] -= v;
	vec[x2 + 1][y1] -= v;
}
template <class T>
void work(vector <vector<T>> &vec) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			vec[i][j] += vec[i - 1][j] + vec[i][j - 1] - vec[i - 1][j - 1];
		}
	}
}

int main() {
	init();
	random_shuffle(prime + 1, prime + 1 + tot);
	while (scanf("%d%d%d", &n, &m, &q) != EOF) {
		a.clear(); a.resize(n + 2, vector <int> (m + 2, 0));
		b.clear(); b.resize(n + 2, vector <ll> (m + 2, 0));
		c.clear(); c.resize(n + 2, vector <int> (m + 2, 0));
		for (int i = 1; i <= n; ++i) {  
			for (int j = 1; j <= m; ++j) {
				scanf("%d", &a[i][j]); 
			}
		}		
		int x[2], y[2], k;
		while (q--) {
			scanf("%d%d%d%d%d", x, y, x + 1, y + 1, &k);
			up(b, x[0], y[0], x[1], y[1], prime[k]);
			up(c, x[0], y[0], x[1], y[1], 1);
		}
		work(b); work(c); 
		int res = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (b[i][j] != c[i][j] * prime[a[i][j]]) {
					++res;
				}
			}
		}
		printf("%d
", res);
	}
	return 0;
}

思路三：
依据：

[egin{eqnarray*} 2c &=& a + b\ 2c^2 &=& a^2 + b^2 \ end{eqnarray*} ]

当且仅当(a = b = c)时成立。
增加一个平方验证。

代码三：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int n, m, q;
vector <vector<int>> a, c;
vector <vector<ll>> b;
template <class T>
void up(vector <vector<T>> &vec, int x1, int y1, int x2, int y2, int v) {
	vec[x1][y1] += v;
	vec[x2 + 1][y2 + 1] += v;
	vec[x1][y2 + 1] -= v;
	vec[x2 + 1][y1] -= v;
}
template <class T>
void work(vector <vector<T>> &vec) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			vec[i][j] += vec[i - 1][j] + vec[i][j - 1] - vec[i - 1][j - 1];
		}
	}
}
void read(int &x) {
	x = 0; char ch;
	while (!isdigit(ch = getchar()));
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
}

int main() {
	while (scanf("%d%d%d", &n, &m, &q) != EOF) {
		a.clear(); a.resize(n + 2, v    ector <int> (m + 2, 0));
		b.clear(); b.resize(n + 2, vector <ll> (m + 2, 0));
		c.clear(); c.resize(n + 2, vector <int> (m + 2, 0));
		for (int i = 1; i <= n; ++i) {  
			for (int j = 1; j <= m; ++j) {
				read(a[i][j]);
			}
		}		
		int x[2], y[2], k;
		while (q--) {
			read(x[0]); read(y[0]); read(x[1]); read(y[1]); read(k);
			up(b, x[0], y[0], x[1], y[1], 1ll * k); 
			up(c, x[0], y[0], x[1], y[1], 1);
		}
		work(b); work(c); 
		int res = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) { 
				if (b[i][j] != c[i][j] * a[i][j]) {
					++res;
				}
			}
		}
		printf("%d
", res);
	}
	return 0;
}

思路四：
考虑两个数不同，那么它们的二进制位至少有一位是不同的。
那么考虑枚举二进制位，当每次操作的(k_i)的当前二进制上为一时那么施肥。
然后枚举每个作物：

• 如果当前作物的(a[i][j])的二进制位上为(1)，如果施肥总次数与当次总次数不同，那么它挂了
• 如果当前作物的(a[i][j])的二进制位上为(0)，如果存在施肥次数，那么它挂了

实现的时候开一维数组然后映射二维坐标就过了，开二维vector就T了。。

代码四：

#include <bits/stdc++.h>
using namespace std;
 
#define N 4000010
#define y1 y_1
int x1[N], y1[N], x2[N], y2[N], k[N];
int n, m, q;
int a[N], b[N], c[N];
bool die[N];
int id(int x, int y) {
    return (x - 1) * (m + 2) + y;
}
void up(int *f, int x1, int y1, int x2, int y2, int v) {
    f[id(x1, y1)] += v;
    f[id(x2 + 1, y2 + 1)] += v;
    f[id(x1, y2 + 1)] -= v;
    f[id(x2 + 1, y1)] -= v;
}
void work(int *f) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            f[id(i, j)] += f[id(i - 1, j)] + f[id(i, j - 1)] - f[id(i - 1, j - 1)];
        }
    }
}
 
int main() {
    while (scanf("%d%d%d", &n, &m, &q) != EOF) {
        memset(b, 0, sizeof b);
        for (int i = 1; i <= n; ++i) { 
            for (int j = 1; j <= m; ++j) {
                scanf("%d", &a[id(i, j)]);
            }
        }      
        for (int i = 1; i <= q; ++i) {
            scanf("%d%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i, k + i);
            up(b, x1[i], y1[i], x2[i], y2[i], 1);
        }
        work(b); 
        for (int i = 15; i >= 0; --i) {
            for (int _i = 1; _i <= n; ++_i) {
                for (int _j = 1; _j <= m; ++_j) {
                    c[id(_i, _j)] = 0;
                }
            }
            for (int j = 1; j <= q; ++j) {
                if (k[j] >> i & 1) {
                    up(c, x1[j], y1[j], x2[j], y2[j], 1);
                }
            }
            work(c);
            for (int _i = 1; _i <= n; ++_i) {
                for (int _j = 1; _j <= m; ++_j) {
                    if (a[id(_i, _j)] >> i & 1) {
                        if (b[id(_i, _j)] != c[id(_i, _j)]) {
                            die[id(_i, _j)] = 1;
                        }               
                    } else if (c[id(_i, _j)]) {
                        die[id(_i, _j)] = 1;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                res += die[id(i, j)];
            }
        }
        printf("%d
", res);
    }
    return 0;
}