首页 > 其他分享 >TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) A~G 题解

TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) A~G 题解

时间：2024-09-08 23:25:57浏览次数：16  
标签：AtCoder le 10 int 题解 Contest ans include mathrm

好久没写题解了，这就来水一篇。

A - Job Interview

题目大意

给定一个长为 \(N\) 的字符串 \(S\)，由 o、-、x 组成。

判断 \(S\) 是否符合下列条件：

  • \(S\) 中至少有一个 o。
  • \(S\) 中没有 x。

\(1\le N\le 100\)

分析

签到题。直接按题意模拟即可。

代码

#include <cstdio>
using namespace std;

int main()
{
	while(getchar() != '\n');
	char c;
	bool ok = false;
	while((c = getchar()) != '\n')
	{
		if(c == 'x')
		{
			puts("No");
			return 0;
		}
		if(c == 'o')
			ok = true;
	}
	puts(ok? "Yes": "No");
	return 0;
}

Python 水题大法 速通大法

input()
s = input()
print('Yes' if 'o' in s and 'x' not in s else 'No')

成功省掉\(208\)个字符（逃

B - Coloring Matrix

题目大意

给定两个 \(N\times N\) 的矩阵 \(A\) 和 \(B\)，都由 \(0\) 和 \(1\) 组成。

你可以将 \(A\) 顺时针旋转 \(0\degree,90\degree,180\degree\) 或 \(270\degree\)（任选其一）。

判断旋转后的 \(A\) 能否满足：

  • 对于每个 \(A_{i,j}=1\) 的 \((i,j)\)，\(B_{i,j}=1\)。

\(1\le N\le 100\)

分析

原题中还贴心的给出了如何将一个矩阵旋转\(90\degree\)，照题意模拟，旋转\(4\)次并逐个判断即可。

代码

#include <cstdio>
#define maxn 105
using namespace std;

int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", a[i] + j);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", b[i] + j);
	for(int x=0; x<4; x++)
	{
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				c[i][j] = a[i][j];
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				a[i][j] = c[n - 1 - j][i];
		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
				if(a[i][j] && !b[i][j])
					goto bad; // goto 不是好习惯（改不掉了），千万不要学
		puts("Yes");
		return 0;
		bad:;
	}
	puts("No");
	return 0;
}

C - Cards Query Problem

题目大意

有 \(N\) 个盒子，编号 \(1\sim N\)，初始均为空。依次处理 \(Q\) 次询问：

  • 1 i j：将数字 \(i\) 写在一张空卡牌上，放入盒子 \(j\)。
  • 2 i：按升序输出盒子 \(i\) 中的所有卡牌（允许重复）。
  • 3 i：按升序输出包含卡牌 \(i\) 的所有盒子的编号。若一个盒子里有多张卡牌 \(i\)，则这个盒子的编号仅输出一次。

\(1\le N,Q\le 2\times 10^5\)

对于查询中所有卡牌上的数字 \(x\)，均有 \(1\le x\le 2\times 10^5\)。
对于查询中所有的盒子编号 \(y\)，均有 \(1\le y\le N\)。

题目保证输出不超过 \(2\times 10^5\) 个整数。

分析

我们分别考虑两种输出操作的做法。

  • 2 i：很容易想到，既然要按升序输出，并且允许重复，我们可以使用 \(N\) 个 multiset 来依次存储每个盒子中的卡牌，处理操作 \(1\) 时更新。
  • 3 i：首先不能从 \(N\) 个盒子中依次查找，这样明显会 TLE。正确的做法是，使用 \(2\times 10^5\) 个 set（注意不能重复，所以不用 multiset）分别存储每张卡牌所在的箱子编号，处理操作 \(1\) 时更新。

此外，本题也可以使用 priority_queue、map，甚至直接输出时排序并去重，不过使用 set 的方式是最简单、代码量最少的。几种方法的总时间复杂度都是 \(\mathcal O(Q\log N)\)。

代码

#include <cstdio>
#include <set>
#define maxn 200005
using namespace std;

multiset<int> box[maxn];
set<int> has[maxn];

int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	while(q--)
	{
		int op, i;
		scanf("%d%d", &op, &i);
		if(op == 1)
		{
			int j;
			scanf("%d", &j);
			box[j].insert(i);
			has[i].insert(j);
		}
		else if(op == 2)
		{
			for(int x: box[i])
				printf("%d ", x);
			putchar('\n');
		}
		else if(op == 3)
		{
			for(int x: has[i])
				printf("%d ", x);
			putchar('\n');
		}
	}
	return 0;
}

D - Writing a Numeral

题目大意

我们有一个字符串 \(S\)。初始时，\(S=\) 1。

处理如下 \(Q\) 次询问：

  • 1 x：将数字 \(x\) 追加至 \(S\) 的最后面。保证 \(x \in \{1,2,3,4,5,6,7,8,9\}\)。
  • 2：删除 \(S\) 的第一个字符。保证此时 \(|S|>1\)。
  • 3：输出 \(S\) 在十进制中对应的数字，对 \(998244353\) 取模。

\(1\le Q\le 6\times 10^5\)

分析

首先，我们必须使用一个 queue 或 deque 来存储字符串 \(S\)。然后，为了在 \(\mathcal O(1)\) 的时间内处理第三种操作，我们必须维护 \(S \bmod (P=998244353)\) 的值，记为 \(A\)。下面考虑前两种操作对 \(A\) 的影响：

  • 1 x：只需在十进制中腾出一位 \(0\) 再加上 \(x\) 即可，可表示为 \(A \leftarrow (10A+x)\bmod P\)。
  • 2：先从队列中取出 \(S\) 的第一位，记为 \(x\)。我们需要从 \(A\) 中减掉最高位乘上其在十进制中的权值，即 \(A \leftarrow (A-10^{|S|}x)\bmod P\)（此时 \(|S|\) 表示队列取出前一位后的长度，等同于取出前的 \(|S|-1\)）

对于 \(10^n\) 的计算，我们可以用一个变量实时维护 \(10^{|S|}\bmod P\) 的值，也可以预处理出所有 \(10^n \bmod P\)，或者直接使用快速幂。

总时间复杂度为 \(\mathcal O(Q\log Q)\)（快速幂）或 \(\mathcal O(Q)\)（预处理）。

代码

实现 \(1\)：使用 AtCoder Library + 快速幂，队列使用 deque

#include <cstdio>
#include <deque>
#include <atcoder/modint>
using namespace std;

using modint = atcoder::modint998244353;

int main()
{
	deque<int> s;
	s.push_back(1);
	int q;
	scanf("%d", &q);
	modint ans = 1;
	while(q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int x;
			scanf("%d", &x);
			s.push_back(x);
			ans = ans * 10 + x;
		}
		else if(op == 2)
		{
			int x = s.front(); s.pop_front();
			ans -= x * modint(10).pow((int)s.size());
		}
		else printf("%d\n", ans.val());
	}
	return 0;
}

实现 \(2\)：用变量维护 \(10^{|S|} \bmod P\) 的值，队列使用 queue

#include <cstdio>
#include <queue>
#define MOD 998244353
using namespace std;

int main()
{
	int Q;
	scanf("%d", &Q);
	queue<int> q;
	q.push(1);
	int ans = 1, p = 1;
	while(Q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int x;
			scanf("%d", &x);
			q.push(x);
			ans = (ans * 10LL + x) % MOD;
			p = p * 10LL % MOD;
		}
		else if(op == 2)
		{
			ans -= (long long) q.front() * p % MOD; q.pop();
			p = p * 299473306LL % MOD; // 299473306 是 10 对于 MOD 的逆元，这句话相当于把 p 除以 10 
			if(ans < 0) ans += MOD;
		}
		else printf("%d\n", ans);
	}
	return 0;
}

E - Unfair Sugoroku

题目大意

Takahashi 和 Aoki 将玩一个游戏。游戏规则如下：

  • 游戏棋盘有 \(N\) 个点（编号 \(1\sim N\)），两玩家轮流投骰子并前进。
  • Takahashi 初始在点 \(A\)，Aoki 初始在点 \(B\)。
  • Takahashi 的骰子等概率出现 \(1,2,\dots,P\)，Aoki 的骰子等概率出现 \(1,2,\dots,Q\)。
  • 当一个玩家当前在点 \(x\) 且骰子出现 \(i\) 时，他移动到点 \(\min(x+i,N)\)。
  • 先到达点 \(N\) 的玩家胜利。

假定 Takahashi 先行，求他赢的概率，对 \(998244353\) 取模。

\(2\le N\le 100\)
\(1\le A,B\le N\)
\(1\le P,Q\le 10\)

分析

自己的赛时解法太复杂了，这里介绍官方题解的做法。

考虑概率 DP（下面用 Ta 表示 Takahashi，Ao 表示 Aoki）：

  • 令 \(f_{i,j}\) 表示 Ta 在点 \(i\)，Ao 在点 \(j\)，下一轮 Ta 移动时 Ta 获胜的概率。
  • 令 \(g_{i,j}\) 表示 Ta 在点 \(i\)，Ao 在点 \(j\)，下一轮 Ao 移动时 Ta 获胜的概率。

首先考虑初始状态。根据游戏规则，对于任意 \(1\le i<n\)，\(f_{n,i}=g_{n,i}=1,f_{i,n}=g_{i,n}=0\)。

转移也很显然：

  • 对于 Ta 当前走的每种可能的步数 \(k=1,2,\dots,P\)，有 \(f_{i,j}:=f_{i,j}+\frac1Pg_{\min(i+k,N),j}\)。
  • 对于 Ao 当前走的每种可能的步数 \(k=1,2,\dots,Q\)，有 \(g_{i,j}:=g_{i,j}+\frac1Qf_{i,\min(j+k,N)}\)。

整理上面的式子，得到：

\[f_{i,j}=\begin{cases} 0 & (j=N)\\ 1 & (i=N)\\ \frac1P\sum\limits_{k=1}^Pg_{\min(i+k,N),j} & (i,j\ne N) \end{cases}\\ ~\\ g_{i,j}=\begin{cases} 0 & (j=N)\\ 1 & (i=N)\\ \frac1Q\sum\limits_{k=1}^Qf_{i,\min(j+k,N)} & (i,j\ne N) \end{cases}\\ \]

这里注意，由于 \(i=j=N\) 的情况无意义（不可能达到），所以无需特殊考虑。

最终输出结果即为 \(f_{p,q}\)。总时间复杂度为 \(\mathcal O(N^2(P+Q))\)。使用前缀和可以优化到 \(\mathcal O(N^2)\)，有兴趣的可以自己尝试，这里不详细解释了。

代码

#include <cstdio>
#include <algorithm>
#define MOD 998244353
#define maxn 105
using namespace std;

using LL = long long;
inline LL inv(LL x) // x ^ (MOD - 2) % MOD
{
	int y = MOD - 2;
	LL res = 1LL;
	while(y)
	{
		if(y & 1) (res *= x) %= MOD;
		(x *= x) %= MOD, y >>= 1;
	}
	return res;
}

inline void add(int& x, int y)
{
	if((x += y) >= MOD)
		x -= MOD;
}

int f[maxn][maxn], g[maxn][maxn];

int main()
{
	int n, a, b, p, q;
	scanf("%d%d%d%d%d", &n, &a, &b, &p, &q);
	for(int i=0; i<n; i++)
		f[n][i] = g[n][i] = 1, f[i][n] = g[i][n] = 0;
	LL prob_p = inv(p), prob_q = inv(q);
	for(int i=n-1; i>=a; i--)
		for(int j=n-1; j>=b; j--)
		{
			for(int k=1; k<=p; k++)
				add(f[i][j], g[min(i + k, n)][j]);
			f[i][j] = f[i][j] * prob_p % MOD;
			for(int k=1; k<=q; k++)
				add(g[i][j], f[i][min(j + k, n)]);
			g[i][j] = g[i][j] * prob_q % MOD;
		}
	printf("%d\n", f[a][b]);
	return 0;
}

F - Rook Score

题目大意

有一个 \(10^9\times 10^9\) 的网格。令 \((i,j)\) 表示第 \(i\) 行 \(j\) 列的格子（\(1\le i,j\le 10^9\)）。

对于 \(i=1,2,\dots,N\)，整数 \(x_i\) 被写在 \((r_i,c_i)\) 上。在剩余的 \(10^{18}-N\) 个格子里只有数字 \(0\)。

你可以选择一个格子 \((R,C)\) 并计算与其同行或同列的 \(2\times 10^9-1\) 个整数之和 \(S\)。

求最大可能的 \(S\)。

\(1\le N\le 2\times 10^5\)
\(1\le r_i,c_i,x_i\le 10^9\)
\((r_i,c_i)\ne (r_j,c_j)~~~~~~(i\ne j)\)

分析

我们令 \(f(R,C)\) 表示对于 \((R,C)\) 的 \(S\)，令 \(\mathrm{rs}_R\) 表示第 \(R\) 行的整数之和，\(\mathrm{cs}_C\)表示第 \(C\) 列的整数之和，\(A_{R,C}\) 表示 \((R,C)\) 上的整数。

容易发现，\(f(R,C)=\mathrm{rs}_R+\mathrm{cs}_C-A_{R,C}\)。

然后证明当 \(f(R,C)\) 最大时，\(\mathrm{rs}_R,\mathrm{cs}_C\ne0\)：

  • 若 \(\mathrm{rs}_R=\mathrm{cs}_C=0\)，则 \(f(r_0,c_0)=x_0>0=f(R,C)\)，所以 \((R,C)\) 不是最优解；
  • 若 \(\mathrm{rs}_R\ne0,\mathrm{cs}_C=0\)，则 \(f(R,c_0)=\mathrm{rs}_R+\mathrm{cs}_{c_0}-A_{R,c_0}\ge f(R,C)=\mathrm{rs}_R\)，所以 \((R,C)\) 不是最优解（或有多个最优解，但其中至少有一个解 \((x,y)\) 使得 \(\mathrm{rs}_x,\mathrm{cs}_y\ne0\)）
  • \(\mathrm{rs}_R=0,\mathrm{cs}_C\ne0\) 同理。

所以，我们可以依次考虑每一行 \(R\)（\(\mathrm{rs}_R\ne 0\)），相当于固定了 \(\mathrm{rs}_R\)。这时，我们只需找到一列 \(C\)（\(\mathrm{cs}_C\ne 0\)），使得 \(\mathrm{cs}_C-A_{R,C}\) 最大，就可以解决此问题。

但如果依次考虑所有包含点的列，则最坏情况下时间复杂度为 \(\mathcal O(N^2)\)，无法通过此题。这时，我们可以使用一个 multiset 或 map 来维护当前每列对答案的贡献（\(\mathrm{cs}_C-A_{R,C}\)）。对于每一行 \(R\)，仅需更新这一行上有非 \(0\) 数字的点 \((R,C)\) 的贡献（减去 \(A_{R,C}\)）即可。

这样，由于每个点会被更新正好一次，所以总时间复杂度为 \(\mathcal O(N\log N)\)。

代码

注意更新完成，求得当前答案后需要复原 map 或 multiset。

#include <cstdio>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

using LL = long long;
using pii = pair<int, int>;

unordered_map<int, vector<pii>> rows;
unordered_map<int, LL> col_sum;

template <typename T>
class MaxSet {
private:
	multiset<T> s;
public:
	inline void insert(const T& x) { s.insert(x); }
	inline void update(const T& old, const T& New) {
		s.erase(s.find(old));
		s.insert(New);
	}
	inline T max() { return *s.rbegin(); }
};

int main()
{
	int n;
	scanf("%d", &n);
	while(n--)
	{
		int x, y, v;
		scanf("%d%d%d", &x, &y, &v);
		rows[x].emplace_back(y, v);
		col_sum[y] += v;
	}
	MaxSet<LL> s;
	for(auto [_, sum]: col_sum)
		s.insert(sum);
	LL ans = 0LL;
	for(auto& [x, v]: rows)
	{
		for(auto [y, val]: v)
			s.update(col_sum[y], col_sum[y] - val);
		LL cur = s.max();
		for(auto [y, val]: v)
			s.update(col_sum[y] - val, col_sum[y]), cur += val;
		if(cur > ans) ans = cur;
	}
	printf("%lld\n", ans);
	return 0;
}

G - Strawberry War

题目大意

注意本题时间限制为 \(6\mathrm s\)。

我们有一块长方形的蛋糕。它可被看作一个 \(H\times W\) 的网格，第 \(i\) 行 \(j\) 列上有 \(s_{i,j}\) 个草莓。

我们对蛋糕进行 \(T\) 次切分，切成 \(T+1\) 块。每次切蛋糕可以选择当前的一块，并将其从中间横切或竖切成两块：
切分方式

你想把蛋糕切的尽可能均匀。意思是，令 \(M\) 表示切分完成后每一块上的草莓数量的最大值，\(m\) 表示最小值，求出 \(M-m\) 的最小值。

\(1\le H,W\le 6\)
\(1\le T\le HW-1\)
\(0\le s_{i,j}\le 10^{16}\)

分析

本题解参考官方题解。

操作完成后得到的蛋糕一定是蛋糕的子矩形，所以最多只有 \(\binom {H+1}2\times\binom {W+1}2=\frac{H(H+1)W(W+1)}4\le 441\) 种数字在剩下的块中。令这些可能的数分别为 \(a_1,a_2,\dots,a_X\)。可知 \(X\le \frac{H(H+1)W(W+1)}4\le 441\)。

根据上面的 \(a\)，我们只需先确定 \(m\in \{a_1,a_2,\dots,a_X\}\)，再找到与其对应的最小 \(M\)，算出 \(M-m\) 的最小值即可。

定义 \(f_{i,j,k,l,m}\) 表示将 \(x\in[i,j),y\in[k,l)\) 的子矩形切成 \(m\) 片时最小可能的每片上草莓数的最大值。

详见代码。

代码

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
int main(){
  int H, W, T;
  cin >> H >> W >> T;
  vector<vector<long long>> s(H, vector<long long>(W));
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> s[i][j];
    }
  }
  vector<vector<vector<vector<long long>>>> sum(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, 0))));
  vector<long long> x;
  for (int i = 0; i < H; i++){
    for (int j = i + 1; j <= H; j++){
      for (int k = 0; k < W; k++){
        for (int l = k + 1; l <= W; l++){
          for (int m = i; m < j; m++){
            for (int n = k; n < l; n++){
              sum[i][j][k][l] += s[m][n];
            }
          }
          x.push_back(sum[i][j][k][l]);
        }
      }
    }
  }
  int cnt = x.size();
  long long ans = INF;
  for (int i = 0; i < cnt; i++){
    vector<vector<vector<vector<vector<long long>>>>> dp(T + 1, vector<vector<vector<vector<long long>>>>(H, vector<vector<vector<long long>>>(H + 1, vector<vector<long long>>(W, vector<long long>(W + 1, INF)))));
    for (int j = H - 1; j >= 0; j--){
      for (int k = j + 1; k <= H; k++){
        for (int l = W - 1; l >= 0; l--){
          for (int m = l + 1; m <= W; m++){
            if (sum[j][k][l][m] >= x[i]){
              dp[0][j][k][l][m] = sum[j][k][l][m];
            }
            for (int n = j + 1; n < k; n++){
              for (int o = 0; o < (n - j) * (m - l); o++){
                for (int p = 0; p < (k - n) * (m - l) && o + p < T; p++){
                  dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][n][l][m], dp[p][n][k][l][m]));
                }
              }
            }
            for (int n = l + 1; n < m; n++){
              for (int o = 0; o < (k - j) * (n - l); o++){
                for (int p = 0; p < (k - j) * (m - n) && o + p < T; p++){
                  dp[o + p + 1][j][k][l][m] = min(dp[o + p + 1][j][k][l][m], max(dp[o][j][k][l][n], dp[p][j][k][n][m]));
                }
              }
            }
          }
        }
      }
    }
    ans = min(ans, dp[T][0][H][0][W] - x[i]);
  }
  cout << ans << endl;
}

标签：AtCoder,le,10,int,题解,Contest,ans,include,mathrm
From： https://www.cnblogs.com/stanleys/p/18403710/abc298

相关文章

  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\)，且经过\(B\)的简单路径？数据范围：\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)（\(1\leB,G\le1000\)且\(B\neG\)），判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力，所以直接给出基本思路：由于可以递归式的创建元素，最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制，元素的数量也能达到\(10^{18}\)。显然，依次构造每个元素，在空......
  • AT_agc027_f [AGC027F] Grafting 题解
    笑点解析：NOIP模拟赛把这题放在T3。因为每一个点只能动一次，答案一定\(\len\)，所以我们分两种情况讨论：当答案小于\(n\)答案如果小于\(n\)，那么一定有一个点是一直没有被动过的。我们枚举这个点，将无根树转化为两棵以这个点为根的有根树。我们将第一棵树和第二棵树同构的部分......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\)，求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位，注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数，因此无需使用整数输入，直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏，由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡，你必须先花\(A_i\)的时间看一次介绍。然后，用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡，则第一次需要看介绍，后面无需再看（即如果想打通第\(i\)关\(N\)次，则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母（任意，如abc中，三个字母都可为答案）。如果没有，输出-1。数据保证\(S\)的长为\(3\)，且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......
  • LINE Verda Programming Contest (AtCoder Beginner Contest 263) A~E 题解
    A-FullHouse题目大意来自一个掼蛋爱好者的翻译qwq给定一副扑克牌中五张牌的编号\(A,B,C,D,E\)，判断这五张是否为一组“三带二”。（不懂的自行百度数据范围：\(1\leA,B,C,D,E\le13\)，且\(A,B,C,D,E\)不会全部相同。输入格式\(A~B~C~D~E\)输出格式如果是“三带二”，输出Yes；否......
  • 动态规划01背包的一个例题——洛谷P2871 题解
    题面有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。样例数据输入46142631227输出23分析（如果亲爱的读者对动态规划略有了解的话应该能看出来这是个01背包的板子......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99