G-Day02 10.3 总结

#A.神秘金币

题目传送门

这题乍一眼看上去像是01背包，但是注意题目中一个重要的条件（好像也不重要）：

$1 \le t_i \le n$ 且所有 $t_i$ 不重复。

那么我们可以贪心，先按价值 $v_i$ 排序，接下来我们就要思考一个重要的问题：这题可不可以有后效性，这决定了我们使用贪心还是DP。

思考：如果有一枚金币价值不那么高，但是是前 $k$ 大的金币之一，并且存在时间很短，而其他价值更高的金币的存在时间更长的话，我们可不可以先拿这枚金币呢?

答案是可以的。

所以我们在常理上要对前 $k$ 个金币再进行一次时间排序（按 $t_i$ 排序，因为题目保证 $t_i$ 互不相同）。而正因为 $t_i$ 互不相同，所以拿完前面一个金币一定有时间拿后面一个（后面的 $t_i$ 一定比前面大）；又因为题目只要求看总价值，所以也不用再对时间排序了，直接整个按 $v_i$ 排序再选前 $k$ 大的求和就行。

所以其实 $t_i$ 一点用没有

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long sum;
int n, k;

struct coinS { int t, v; }; coinS a[N];

bool cmp_val (coinS a, coinS b)
{ return a.v > b.v; }

void Fio (string iofile)
{
	string ifl = iofile + ".in", ofl = iofile + ".out";
	freopen (ifl.c_str (), "r", stdin);
	freopen (ofl.c_str (), "w", stdout);
}

int main ()
{
	Fio ("coin");
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i].t;
	for (int i = 1; i <= n; i ++) cin >> a[i].v;
	sort (a + 1, a + 1 + n, cmp_val);
	for (int i = 1; i <= k; i ++) sum += a[i].v;
	cout << sum;
	return 0;
}

感受与学习：在遇到看上去十分复杂或困难的题时，应该仔细思考其本质，不要被吓到。

错误原因：无。

---

#B.学习乘法

题目传送门

这一题又是一道很像数学题的题，但是仔细一看数据范围：$a,b \le 999999$，也就是说 $a,b$ 不超过六位数，那么可以直接使用字符串处理+爆搜，枚举每一位是交换还是不换，到头了则更新答案。

爆搜时间复杂度 $\Theta (2^{|\max\{a,b\}|})$，其中 $|a|$ 表示 $a$ 的位数，那么最高时间复杂度为 $\Theta (2^6=64)$，绝对不会超时。

Code:

/*
思路：
	每一位都可以选择换或者不换
	a,b 最多只有 6 位，可以 2^6 = 64 暴力枚举
	DFS !
*/

#include <bits/stdc++.h>
using namespace std;
long long ans;
string a, b;

long long mul_str (string a, string b)
{ return ((long long)stoi (a) * (long long)stoi (b)); }

void Fio (string iofile)
{
	string ifl = iofile + ".in", ofl = iofile + ".out";
	freopen (ifl.c_str (), "r", stdin);
	freopen (ofl.c_str (), "w", stdout);
}

void DFS_str (string a, string b, int flo)
{
	if (flo == a.size ())
	{
		ans = max (ans, mul_str (a, b));
		return;
	}
	DFS_str (a, b, flo + 1);
	swap (a[flo], b[flo]);
	DFS_str (a, b, flo + 1);
}

int main ()
{
	Fio ("mul");
	cin >> a >> b;
	DFS_str (a, b, 0);
	cout << ans;
	return 0;
}

感受与学习：仔细看数据范围，说不定有惊吓喜。

错误原因：无。

---

#C.饮料难题

题目传送门

刚看完题目就知道这题就是妥妥数学题了，那就还是打表找规律，最终发现规律：答案就是 $\lfloor \dfrac{n}{k-1} \rfloor$，那不就直接 $\Theta (1)$ 输出就行了嘛……呃？。

果然，出题人肯定不会这么良心的，发现 $n$ 的最大值为 $10^{100000}$，而 $k$ 的范围最大为 $10^9$，那这就是一个高精除低精模板题了，直接套模板即可。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
string n;
int k;

void Fio (string iofile)
{
	string ifl = iofile + ".in", ofl = iofile + ".out";
	freopen (ifl.c_str (), "r", stdin);
	freopen (ofl.c_str (), "w", stdout);
}

vector <int> divH (vector <int> ah, int bh)
{
	vector <int> res; int r = 0;
	for (int i = ah.size () - 1; i >= 0; i --)
	{
		r = r * 10 + ah[i];
		res.push_back (r / bh);
		r %= bh;
	}
	reverse (res.begin (), res.end ());
	while (res.back () == 0 && res.size () > 1) res.pop_back ();
	return res;
}

signed main ()
{
	Fio ("drink");
	cin >> n >> k;
	vector <int> nh, ans;
	for (int i = n.size () - 1; i >= 0; i --) nh.push_back (n[i] - '0');
	ans = divH (nh, k - 1);
	for (int i = ans.size () - 1; i >= 0; i --) cout << ans[i];
	return 0;
}

感受与学习：数学题打表找规律！！！

错误原因：无。

最后一题真的实在肝不出来了qwq