https://www.cometoj.com/contest/7/problems
B. 吃豆豆
题意:有 n ⋅ m n\cdot m n ⋅ m 个格子,每个格子在 T [ i ] [ j ] T[i] [j] T [ i ] [ j ] 的倍数时会出现一颗糖,下一秒马上消失,若此时wls在这个格子上,就能得到一颗糖。问wls从S到T,至少拿到C颗糖,最少时间。
直接bfs搜,每个点可能呆着不动或者上下左右走,所以五个方向拓展,呆着不动的话直接跳到下一次出现糖的时候。
或者dp也一样。
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 #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个数的和,满足 g c d ( a [ i ] , b [ i ] ) = 1 gcd(a[i],b[i])=1 g c d ( a [ i ] , b [ i ]) = 1 。
一定能拆成两个数。
并且经过不断分类讨论能够发现,一定能拆成一个1到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 #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,奇数点向 3 i + 1 3i+1 3 i + 1 连无向边,偶数点向 i / 2 i/2 i /2 连无向边,每个点有点权,若两端点都选,则要减去一个值,求最大值。
树形dp
试着画一下就能发现,这是个森林。
d p [ i ] [ 1 / 0 ] dp[i] [1/0] d p [ i ] [ 1/0 ] 表示 i i i 取/不取 时 以 i i i 为根的子树的最大收益。
转移方程为
{ d p [ u ] [ 0 ] = ∑ v m a x ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ] ) d p [ u ] [ 1 ] = ∑ v m a x ( d p [ v ] [ 0 ] + f [ u ] , d p [ v ] [ 1 ] + f [ u ] − d [ m i n ( u , v ) ] ) \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}
{ d p [ u ] [ 0 ] = ∑ v ma x ( d p [ v ] [ 0 ] , d p [ v ] [ 1 ]) d p [ u ] [ 1 ] = ∑ v ma x ( d p [ v ] [ 0 ] + f [ u ] , d p [ v ] [ 1 ] + f [ u ] − d [ min ( u , v )])
把所有根的 m a x ( d p [ u ] [ 1 ] , d p [ u ] [ 0 ] ) max(dp[u] [1],dp[u] [0]) ma x ( d p [ u ] [ 1 ] , d p [ u ] [ 0 ]) 加起来。
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 #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 ⋅ L L\cdot L L ⋅ L ,走一段路花费路的长度,求从1到n的最小花费。
能走到的高度范围是固定的,范围外的点通过花费固定值可以降到范围内,算进它的路程花费里,bfs找最短路。
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 #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之后更新答案。
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 #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 ; }