Day08 7.16总结

第一类：暴力(T1, T2)

---

T1.小田的同余

题目传送门

题目大意就是给定一个正奇数 $m$ 要找出一个小于 $m$ 的整数 $x$ 使得 $2x \ \% \ m = 1$ ，并且 $3 \le m \le 10^{12}$ ，所以第一个可以想到的是 要开 long long ，另外可以思考为什么 $m$ 一定是奇数，因为 $2x$ 一定是个偶数，而偶数对偶数取模是不可能得到 $1$ 的，所以 $m$ 一定是奇数，并且由于一个大于 $1$ 的数加上 $1$ 对自己取模余数一定为 $1$ ，所以 $2x$ 应该等于 $m + 1$ 。

那么， $m$ 为奇数的话如何让 $2x$ 比 $m$ 多 $1$ 呢？可以列出一个方程：

$$2x + 1 ≡ 0 \ (mod \ m)\\ (2x + 1) \% m = 0\\ 2x\ \% \ (m + 1) = 0\\ 为了使 \ x \ 最小，所以\\ 2x \ \div \ (m + 1) = 1\\ 2x = m + 1\\ x = (m + 1) \div 2$$

所以直接输出 $(m + 1) \div 2$ 即可。

$Code:$

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

int main ()
{
	freopen ("mod.in", "r", stdin);
	freopen ("mod.out", "w", stdout);
	cin >> m;
	cout << (m + 1) / 2;
	return 0;
}

感受与学习：无(太简单了)

错误原因：无

---

T2.小田的奶牛要饿坏啦！！

题目传送门

本题就是一道纯模拟，一开始暴力可以想到的是从第一天开始枚举天数 day ，一直到第 $t$ 天，由于 $d_i$ 是按升序排列的，所以可以用一个变量 idx 表示 $d$ 的下标，如果 day == d[idx] ，说明这一天送了草，让 idx ++ ，并且将草数变量 $wht$ 加上 $b_{idx}$ 。其余天数如果 $wht > 0$ 则 cnt ++ 并让 wht -- ，否则直接 continue ，但是定睛一看！—— $t \le 10^{14}$ ，开 long long 都来不及，更别说枚举了，铁超时，考虑优化。

可以发现，中间这段 每天加时间并减去干草的操作 是多余的，并且由于 $d_i$ 是升序排列，所以可以从 $1$ 到 $n$ 按顺序枚举 $d_1$ 至 $d_n$ 。下一步，我们会发现，统计哪些天能吃草太过于麻烦，所以我们可以统计 吃不到草的天数 ct ，最后的答案就是 t - ct 。不过如何更新 ct 的值呢？可以想到，每次小田来送完草后，牛能吃的草又多了，又有了 $b_i$ 堆草，那么接下来有 $b_i$ 天不会挨饿。那么我们用一个变量 sti 表示小田送来的草能够吃到第几天，那么在小田送来草时判断一下以前的草够不够吃到现在(if (sti >= d[i]))，够则直接让 sti += b[i] ，说明又能多吃 b[i] 天。如果不够，则用能吃的天数 sti 去更新 ct ，从送草的这一天 d 到之前能吃的天数 sti 共有 d[i] - sti - 1 天 (因为在送草的那一天也能吃到，也就是两边的边界都能吃到) ，更新完 ct 后，就要改变 sti ，这时之前的由于更新了 ct ，可以看成是之前的能够吃 d[i] 天，那么从 d[i] 天又能够多吃 b[i] 天，而由于送来的那天( d[i] 天) 已经算过了，所以 sti 被更新为 d[i] + b[i] - 1 。

最后问的是在前 $t$ 天中能吃多少草，直接输出 t - ct 即可。

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, t;
int sti, ct;

signed main ()
{
	freopen ("cow.in", "r", stdin);
	freopen ("cow.out", "w", stdout);
	cin >> n >> t;
	for (int i = 1; i <= n; i ++)
	{
		int d, b; cin >> d >> b;
		if (sti >= d) sti += b;
		else ct += d - sti - 1, sti = d + b - 1;
	}
	cout << t - ct;
	return 0;
}

感受与学习：本题的思考量应该是前四题中最多的，因为正向思维不好思考，很麻烦，有很多变量需要处理，所以需要逆向的思考，统计不能吃的天数，最后的答案就是总天数 $-$ 不能吃的天数。

错误原因：思维紊乱，模拟一头雾水，不知道草量够怎么写，不够又怎么写，用的是正向思维，云里雾里， 头晕目眩 ，连逆向的的思维都没有考虑，认为比正向还麻烦，所以做题时在时间允许的情况下应该将所有可能的做法都做一遍，尝试一遍。

---

第二类：简单算法(T3, 前缀和, T4, 模拟, T5, 二分 + 前缀和, T6, 模拟 + 双指针)

---

T3.小田喂猫

题目传送门

本题首先可以想到的暴力解法是先对猫粮的数量进行排序(因为营养没关系，每天都可以得到固定的)。每次得到一个 $k$ 后，循环遍历所有猫粮，如果当前猫粮数小于等于 $k$ ，说明可以全部吃完，所以直接把 ans 加上 当前猫粮的数量 * 当前猫粮的营养值 。否则则只能吃 $k$ 份，加上 当前猫粮的数量 * k ，最终加上 min (数量, k) * 营养值 。

这种做法的时间复杂度为 $O(kn)$ ，最坏复杂度为

$$O (kn) : \\ 1 \le k \le 10^9, \max (k) = 10^9\\ 1 \le n \le 10^5, \max (n) = 10^5\\ \max (kn) = \max (k) \times \max (n)\\ = 10^9 \times 10^5\\ = 10^{9 + 5}\\ = 10^{14}\\ 10^{14} > 10^8$$

当然，铁超时，考虑优化。

可以想到，每次从 $1$ 枚举到 $n$ 的过程是不必要的，因为我们只要将猫粮排序后找到第一个大于数量 $k$ 的位置，或最后一个小于等于 $k$ 的位置，我们设这个数据为 $x$ 。这样 $x$ 左边的值的数量就都是小于等于 $k$ 的(包括它自己)，右边都是大于 $k$ 的。这样就可以用 前 + 后缀和 来计算，前缀和数组 frt[i] 表示从 $1$ 到 $i$ (左边)可以全部吃完的话，全部加上 当前猫粮的数量 * 当前猫粮的营养值 的。而后缀和数组 bak[i] 表示从 $i$ 到 $n$ 右边只吃一份的营养值，最后将 bak[i] * k 即可得到右边吃 $k$ 份的值。

相信当你看到"第一个大于""最后一个小于等于"这些词，一定能马上想到—— 二分 ！是的，套一个二分模版上去就可以了，这里推荐使用第二个模板，也就是最后一个小于等于 $k$ 的位置(好用一些，且好处理边界) 。这里有一个细节是边界的问题，通常要是想搜这种位置( $1$ 至 $n$ ) ，一般是 l = 1, r = n 去搜，如果使用第二套模版的话，那么最终的答案就是 frt[l] + bak[l + 1] * k ，可是如果没有最后一个小于等于 $k$ 的位置呢 (也就是全部大于 $k$ 的元素) ？这样的话， $l$ 就会被卡在 $1$ 的位置，输出 frt[1] + bak[2] * k ，可是我们本来是想输出全部元素取 $k$ 个的，也就是 bak[1] * k ，这里却多了一个边界。如何解决呢？很简单，把 l 的初始值设为 $0$ 即可，这样当 l 被压住时输出的就是 bak[0 + 1] * k = bak[1] * k 了，其余情况也不会影响。

$Code:$

#include <bits/stdc++.h>
#define int long long
#define a first
#define b second
using namespace std;
const int N = 1e5 + 10;
int n, q;
int frt[N], bak[N];
pair <int, int> cat[N];
//为方便，这里用pair存，并将first和second重定义了

signed main ()
{
	freopen ("cat.in", "r", stdin);
	freopen ("cat.out", "w", stdout);
	ios :: sync_with_stdio (0);
	cin.tie (0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> cat[i].b;
	for (int i = 1; i <= n; i ++) cin >> cat[i].a;
	sort (cat + 1, cat + n + 1);
    //用pair就不用写cmp了
	for (int i = 1; i <= n; i ++) frt[i] = frt[i - 1] + cat[i].a * cat[i].b;
	for (int i = n; i >= 1; i --) bak[i] = bak[i + 1] + cat[i].b;
	cin >> q;
	while (q --)
	{
		int k; cin >> k;
		int l = 0, r = n; //边界细节
		while (l < r)
		{
			int mid = l + r + 1 >> 1;
			if (cat[mid].a <= k) l = mid;
			else r = mid - 1;
		}
		cout << frt[l] + bak[l + 1] * k << '\n';
	}
	return 0;
}

感受与学习：本题的细节在于对二分边界问题的处理，由于二分查找的过程中是一定不会超出 l 和 r 的范围的，所以对于这种可能有超出边界范围的答案情况，应该仔细思考到底是什么地方会超出，比如对于这里的第二套模板就有可能是 $0$ ，而使用第一套模板则有可能没有第一个大于 $k$ 的情况，所以 r 要设为 n + 1 。

错误原因：大部分思路都想到了，可是关于二分查找下标的却没有想到，而是拿一个标记数组来标记每种猫粮可能的数量的最后一个位置来达到二分的效果，当时也想到了 $a[i] \le 10^9$ 的限制 (会爆空间) ，但是愣是没有想到用二分来找下标，以后应该灵活变通，了解各种算法、数据结构的用途并在合适的时候将所有可能用到的算法都用一遍。

---

T4.小田的打字练习

题目传送门

本题应该是本次考试中最纯正 (无脑) 的模拟，先定义两个字符串数组 eg 和 key 表示范文和小田打入的字，然后要对这两个数组进行输入并同时处理，下面以范文 eg 数组为例说明。

• 首先，用 while (getline (cin, ts)) 来每次读取一个临时字符串 ts ，并用一个变量 idx 记录现在在字符串数组的第几项，同时由于遇到 EOF 结束，所以 while 条件中应该还加上 ts != "EOF" 。
• 然后，就要对 ts 进行处理了。首先将初始值为 $0$ 的 idx 变量 ++ 以移动到下一行，并且这里由于有退格键的存在，所以我们从 $0$ 到 ts.size () - 1 进行遍历，遍历输入字符串中的每一个字符，如果当前遍历到的字符不是退格键，那么将 eg[idx] push_back 进来一个 ts[i] (string 是可以 push_back 和 pop_back 的) 。如果是退格键，则将 eg[idx] pop_back 掉，也就是删掉上一个字符。不过注意，如果当前字符位于行首，也就是 eg[idx].size () == 0 ，那么是不能 pop 的。
• 处理完 eg 后，就要用同样的方法处理 key (记得将 idx 重置为 $0$ ) ，不过不同的一点是在每次处理完当前行的字符时要再遍历当前字符串并判断这个字符串与范文对应字符串的正确性，如果遍历到的两边的字符相等，则 cnt ++ 。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4;
string ts, eg[N], key[N];
int t, idx, cnt;

int main ()
{
    freopen ("key.in", "r", stdin);
    freopen ("key.out", "w", stdout);
	while (getline (cin, ts) && ts != "EOF")
	{
		idx ++;
		for (int i = 0; i < ts.size (); i ++)
		{
			char tc = ts[i];
			if (tc == '<') {if (eg[idx].size ()) eg[idx].pop_back ();}
            //这两个条件要分开判断，不能直接&&，这是为了以后else做准备
			else eg[idx].push_back (tc);
		}
	}
	idx = 0;
	while (getline (cin, ts) && ts != "EOF")
	{
		idx ++;
		for (int i = 0; i < ts.size (); i ++)
		{
			char tc = ts[i];
			if (tc == '<') {if (key[idx].size ()) key[idx].pop_back ();}
			else key[idx].push_back (tc);
		}
		for (int i = 0; i < eg[idx].size (); i ++)
			if (eg[idx][i] == key[idx][i]) cnt ++;
	}
	cin >> t;
	cout << int ((cnt * 1.0) / (t * 1.0 / 60) + 0.5);
    return 0;
}

感受与学习：本题就是一道纯模拟，只有 退格键 需要想一下，下次应该思考如何达到题目的要求并用好且合适的方法实现 (如在线处理，使用正确的数据结构，利用 题目的隐藏性质 等) 。

错误原因：没有想到退格键的正确处理法，想的是利用 substr 函数在判断到 < 键时将 eg[i] 变为 eg[i].substr (0, j/*j是当前枚举eg[i]每一个字符的下标*/) + eg[i].substr (j + 1) ，也就是将退格键与前一个字符一并删除，使用的是离线处理，而正确做法是按每一个字符枚举。

---

T5.小田切蛋糕

题目传送门

本题