2019 CCPC-Wannafly Winter Camp Day1

https://www.cometoj.com/contest/7/problems

B. 吃豆豆

 

题意：有 $n\cdot m$ 个格子，每个格子在 $T[i] [j]$ 的倍数时会出现一颗糖，下一秒马上消失，若此时wls在这个格子上，就能得到一颗糖。问wls从S到T，至少拿到C颗糖，最少时间。

直接bfs搜，每个点可能呆着不动或者上下左右走，所以五个方向拓展，呆着不动的话直接跳到下一次出现糖的时候。

或者dp也一样。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, C;
int sx, sy, tx, ty;
int d[20][20][2000], vis[20][20][2000];
struct nd
{
	int x, y, k, dis;
	bool operator<(const nd& rhs)const {
		return dis > rhs.dis;
	}
};
int a[20][20];
bool leg(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}
int dx[]{ -1,0,0,1 };
int dy[]{ 0,-1,1,0 };
int bfs() {
	priority_queue<nd> que;
	memset(d, 0x3f, sizeof(d));
	d[sx][sy][0] = 0;
	que.push(nd{ sx,sy,0,0 });
	while (!que.empty()) {
		nd u = que.top(); que.pop();
		if (vis[u.x][u.y][u.k])continue;
		vis[u.x][u.y][u.k] = 1;
		if (u.x == tx && u.y == ty && u.k >= C)return u.dis;
		for (int i = 0; i < 4; i++) {
			int nx = u.x + dx[i], ny = u.y + dy[i];
			if (!leg(nx, ny))continue;
			int nk = u.k + ((u.dis + 1) % a[nx][ny] == 0);
			if (!vis[nx][ny][nk]) {
				d[nx][ny][nk] = u.dis + 1;
				que.push(nd{ nx,ny,nk,d[nx][ny][nk] });
			}
		}
		if (u.k < C)
			if(!vis[u.x][u.y][u.k+1])
				que.push(nd{ u.x,u.y,u.k + 1,u.dis + a[u.x][u.y] - u.dis%a[u.x][u.y] });
	}
	return -1;
}
int main() {
	scanf("%d%d%d", &n, &m, &C);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
	printf("%d", bfs());
	return 0;
}

 

C. 拆拆拆数

 

题意：有两个数A，B，每个数拆成n个数的和，满足 $gcd(a[i],b[i])=1$ 。

一定能拆成两个数。

并且经过不断分类讨论能够发现，一定能拆成一个1到n的数和另一个数的和。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a%b);
}
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		ll a = gcd(x, y);
		if (a == 1) {
			puts("1");
			printf("%lld %lld\n", x, y);
			continue;
		}
		ll b = x / a, c = y / a;
		puts("2");
		ll p;
		if (a & 1) {
			p = (a >> 1);
		}
		else {
			p = (a >> 1);
			if (p & 1)p -= 2;
			else p -= 1;
		}
		printf("%lld %lld\n", p*b, (a - p)*c);
		printf("%lld %lld\n", (a - p)*b, p*c);
	}
	return 0;
}

 

E. 流流流动

 

题意：n个点编号从1到n，奇数点向 $3i+1$ 连无向边，偶数点向 $i/2$ 连无向边，每个点有点权，若两端点都选，则要减去一个值，求最大值。

树形dp

试着画一下就能发现，这是个森林。

$dp[i] [1/0]$ 表示 $i$ 取/不取 时 以 $i$ 为根的子树的最大收益。

转移方程为

$$\begin{cases} dp[u][0]=\sum_v max(dp[v][0],dp[v][1])\\ dp[u][1]=\sum_v max(dp[v][0]+f[u],dp[v][1]+f[u]-d[min(u,v)]) \end{cases}$$

把所有根的 $max(dp[u] [1],dp[u] [0])$ 加起来。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
int n;
int f[maxn], d[maxn];
int dp[110][2], vis[maxn];
vector<int>G[maxn];
void dfs(int u, int fa) {
	vis[u] = 1;
	dp[u][1] = f[u];
	for (int v : G[u]) {
		if (v == fa)continue;
		dfs(v, u);
		dp[u][0] += max(dp[v][0], dp[v][1]);
		dp[u][1] += max(dp[v][0], dp[v][1] - d[min(u, v)]);
	}
}
int ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &f[i]);
	for (int i = 1; i <= n; i++)scanf("%d", &d[i]);
	for (int i = 2; i <= n; i++) {
		if (i & 1) { if (3 * i + 1 <= n)G[i].push_back(3 * i + 1), G[3 * i + 1].push_back(i); }
		else G[i].push_back(i / 2), G[i / 2].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i, 0);
			ans += max(dp[i][0], dp[i][1]);
		}
	}
	cout << ans << endl;
	return 0;
}

 

F. 爬爬爬山

 

题意：有n个点，每个点有高度，从高向低走能加体力，低向高走能减体力，体力必须大于等于0，要降低山高度L米花费 $L\cdot L$，走一段路花费路的长度，求从1到n的最小花费。

能走到的高度范围是固定的，范围外的点通过花费固定值可以降到范围内，算进它的路程花费里，bfs找最短路。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
const ll inf = 1e18;
int n, m;
ll k;
struct E
{
	int v, w;
};
vector<E>G[maxn];
ll h[maxn], cost[maxn];
ll d[maxn];
ll bfs(int s) {
	fill(d + 1, d + n + 1, inf);
	d[s] = 0;
	priority_queue<pii,vector<pii>,greater<pii> >que;
	que.push(pii(0, s));
	while (!que.empty()) {
		int u = que.top().second; ll dis = que.top().first;
		que.pop();
		if (u == n)return dis;
		if (dis > d[u])continue;
		for (E& e: G[u]) {
			int v = e.v;
			ll ndis = d[u] + e.w + cost[v];
			if (ndis < d[v]) {
				d[v] = ndis;
				que.push(pii(d[v], v));
			}
		}
	}
	return -1;
}
int main() {
	scanf("%d%d%lld", &n, &m, &k);
	for (int i = 1; i <= n; i++)scanf("%lld", &h[i]);
	for (int i = 2; i <= n; i++)if (h[i] > h[1] + k) {
		cost[i] = (h[i] - h[1] - k)*(h[i] - h[1] - k);
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(E{ v,w });
		G[v].push_back(E{ u,w });
	}
	printf("%lld\n", bfs(1));
	return 0;
}

 

J. 夺宝奇兵

 

题意：有m个宝物，分别属于某个人，向他买来要花一定钱，wls要成为拥有宝物最多的人，求最小花费。

直接枚举最终wls的宝物数，check之后更新答案。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const ll inf = 1e18;
int n, m;
vector<ll>vc[maxn];
priority_queue<ll, vector<ll>, greater<ll> >Q;
bool check(int mid) {
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += max(0, (int)vc[i].size() - mid + 1);
	return cnt <= mid;
}
ll solve(int k) {
	while (!Q.empty())Q.pop();
	ll res = 0;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (int)vc[i].size(); j++) {
			if (j <= (int)vc[i].size() - k)res += vc[i][j], cnt++;
			else Q.push(vc[i][j]);
		}
	}
	for (; cnt < k; cnt++) {
		res += Q.top();
		Q.pop();
	}
	return res;
}
ll ans = inf;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		ll a;
		int c;
		scanf("%lld%d", &a, &c);
		vc[c].push_back(a);
	}
	for (int i = 1; i <= n; i++)sort(vc[i].begin(), vc[i].end());
	for (int i = 0; i <= m; i++)
		if (check(i))
			ans = min(ans, solve(i));
	printf("%lld\n", ans);
	return 0;
}