钟柯哲哲的博客
钟柯哲哲8.9总结
钟柯哲哲 LV2 金丹期 LV 6 @ 2024-8-9 20:46:26

Aug.Day05 8.9总结

#A.发射站

本题就是一道无脑的暴力，用双重循环枚举每一个可能的中心点 $(0 \sim 128)$ ，设本次枚举到的点为 $(x, y)$ ，那么就从这个点开始上下左右都枚举 $d$ 个格子，也就是 $(x', y') \ (x' \in [x - d, x + d], y' \in [y - d, y + d])$，不过注意，有可能会导致格子“空置”的情况，所以真正的范围应该是

$$x' \in \big\{\max \{0, x - d\}, \min \{128, x + d\}\big\} \\ y' \in \big\{\max \{0, y - d\}, \min \{128, y + d\}\big\}$$

每次用一个变量 sum 记录和，并用 mxu 记录最大值。可是如何记录最大值的方案数量呢？我想到的方法是用一个 map 桶 sta 统计每种方案的数量，最后输出 sta[mxu] 和 mxu。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 150;
unordered_map <int, int> sta;
int d, n, g[N][N], mxu;

signed main ()
{
	freopen ("fsz.in", "r", stdin);
	freopen ("fsz.out", "w", stdout);
	cin >> d >> n;
	for (int i = 1; i <= n; i ++)
	{
		int x, y, k; cin >> x >> y >> k;
		g[x][y] += k;
	}
	for (int i = 0; i <= 128; i ++)
	{
		for (int j = 0; j <= 128; j ++)
		{
			//pos:i-d,i+d,j-d,j+d
			int sum = 0;
			//公共场所的数量 
			for (int x = max (0ll, i - d); x <= min (128ll, i + d); x ++)
				for (int y = max (0ll, j - d); y <= min (128ll, j + d); y ++)
					sum += g[x][y];
			mxu = max (mxu, sum);
			sta[sum] ++;
			//记录每种方案的数量 
		}
	}
	cout << sta[mxu] << ' ' << mxu;
	return 0;
}

感受与学习：我明白了对于一道十分简单的题，能用暴力就用暴力（前提是不超时），不要浪费时间，留时间给后面难的题。

错误原因：无。

#B.翻译鸡

题目传送门

本题是一道队列模拟题，用一个队列记录每个单词并用一个标记 map 数组标记每种单词的数量（队列的唯一作用是如果它的大小大于等于 $m$ 时要先将标记数组的队头元素的数量减 $1$ ，再弹出元素，最后再推进当前元素）

~~本题以前做过（小W的病毒歼灭战），所以本题是耗时最少的题~~

Code:

#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> tb;
queue <int> wd;
int m, n, cnt;

int main ()
{
	freopen ("fyj.in", "r", stdin);
	freopen ("fyj.out", "w", stdout);
	cin >> m >> n;
	for (int i = 0; i <= 1000; i ++)
		tb[i] = 0;
	for (int i = 1; i <= n; i ++)
	{
		int x; cin >> x;
		if (! tb[x])
		{
			cnt ++;
			tb[x] ++;
			if (wd.size () >= m)
				tb[wd.front ()] --, wd.pop ();
			wd.push (x);
		}
	}
	cout << cnt;
	return 0;
}

感受与学习：无（以前做过，~~且太过简单~~）。

错误原因：无。

#C.字符串

题目传送门

本题稍稍有些复杂，我们用一个字符串 ans 存答案，分几步去思考。

首先，遍历字符串，如果遇到 '-' 则进行处理，否则 ans = ans + s[i] 。
遇到 '-' 的处理方法：先判断减号右边的字符是否严格大于左边的字符，是则进行下一步处理，否则 ans = ans + '-' 并 continue 进入下一次循环。
接下来判断左右两边的字符是否都是数字或小写字母（isdigit 判断数字，islower 判断小写字母），是则执行操作 4，否则又是 ans = ans + '-' 并 continue。
接下来就要对这个减号与两边的字符进行处理了，先用两个变量 f = int (s[i - 1]), t = int (s[i + 1]) 来确定中间字符的遍历，定义一个临时字符串 t 表示从 char (f + 1) 至 char (t - 1) 中间字符组成的字符串，具体如下：
```
int f = int (s[i - 1]), t = int (s[i + 1]);
string t = "";
for (int i = f + 1; i < t; i ++)
    	t += char (i);
```
这样就得到了 t ，接下来要对 t 进行三个参数分别对应的操作，不过这里建议将三个参数的对应操作封装成三个函数以提升代码可读性，这里三个函数的参数只有一个参数 string t 表示要进行操作的字符串。
- 参数 $p_1$ 的操作：首先判断 t[0] 是否为字母，是则判断 $p1$ 是否为 $2$ （因为 $1$ 不用管），如果为 $2$ 则遍历 t ，将 t[i] 变为 t[i] - 'a' + 'A' （对应大写字母，也可使用 toupper 函数），在 t[0] 是否为字母的分支外，再写一个判断判定 $p_1$ 是否为 $3$ ，如果是则全转为 '*' 。
- 参数 $p_2$ 的操作：定义一个临时串 res ，遍历 t ，并在遍历的途中循环从 $1$ 到 $p_2$ ，每次将 res += t[i] ，也就是将每个 t[i] 复制 $p_2$ 份粘贴到 res 里。
- 参数 $p_3$ 的操作：判断 $p_3$ 是否为 $2$ ，是则 reverse (t.begin (), t.end ()) （翻转操作，不会的也可以老老实实打 for 循环），否则不做处理。
处理完后将 ans += t。
最后输出 ans。

Code:

#include <bits/stdc++.h>
using namespace std;
int p1, p2, p3;
string s, ans;

string Solve1 (string t)
{
	if (islower (t[0]))
	{
		if (p1 == 2)
		{
			for (int i = 0; i < t.size (); i ++)
				t[i] = char (t[i] - 'a' + 'A');
		}
	}
	if (p1 == 3)
	{
		for (int i = 0; i < t.size (); i ++)
			t[i] = '*';
	}
	return t;
}

string Solve2 (string t)
{
	string res = "";
	for (int i = 0; i < t.size (); i ++)
		for (int j = 1; j <= p2; j ++)
			res += t[i];
	return res;
}

string Solve3 (string t)
{
	if (p3 == 2) reverse (t.begin (), t.end ());
	return t;
}

int main ()
{
	freopen ("zfc.in", "r", stdin);
	freopen ("zfc.out", "w", stdout);
	cin >> p1 >> p2 >> p3 >> s;
	for (int i = 0; i < s.size (); i ++)
	{
		if (s[i] == '-')
		{
			if (s[i + 1] > s[i - 1])
			{
				if (isdigit (s[i + 1]) && isdigit (s[i - 1]) ||
				islower (s[i + 1]) && islower (s[i - 1])
				)
				{
					string t = "";
					int f = int (s[i - 1]), o = int (s[i + 1]);
					for (int i = f + 1; i < o; i ++)
						t += char (i);
					t = Solve1 (t);
					t = Solve2 (t);
					t = Solve3 (t);
					ans += t;
				}
				else
				{
					ans += '-';
					continue;
				}
			}
			else
			{
				ans += '-';
				continue;
			}
		}
		else ans += s[i];
	}
	cout << ans;
	return 0;
}

感受与学习：本题我知道了在做题时要尽量提高代码的可读性，将一个通用的操作封装成函数或方法，这样在 Debug 时也方便。

错误原因：无。

#D.机器

题目传送门

本题要是完全看懂了题面，你就完成了 $50 \%$ !

~~（以下讲解假设读者已经完全看懂了题面）~~

变量预设：a[i] 表示输入的第二行，也就是安排的顺序。

t[i][j] 表示第 i 台机器的第 j 个时刻有没有被占用。

struct {int tim, id} mt[i][j] 表示第i个工件的第j个工序，tim 为所需时间，id 为需加工机器编号。

stp[i] 表示第 i 个工件进行到了哪个工序，last[i] 表示第 i 种工件上一个加工的工序结束时的时间。

首先，需要明确枚举的顺序，也就是从 a[1] 到 a[n * m] ，每次定义 now = a[i]，取出当前需要加工的工序对应的工件，然后取出当前需加工工序对应的机器和时间，机器为 ncn = mt[now][++ stp[now]].id，时间为 lt = mt[now][stp[now]].tim，再定义一个 tme 表示找的连续的可以放的区间长度。

接下来从本次工件上一个加工工序的结束时间 $+ 1$ （last[now] + 1）开始，一直枚举（中间会有 break 的条件），如果 t[ncn][j] 为 $0$ 说明第 ncn 台机器第 j 个时刻没有被占用，那么 tme ++ ，否则这段区间就装不下了，tme 重置为 $0$ ，如果 tme >= lt 说明这个时间段够，则将从 j - tme + 1 到 j 的位置标记为占用（t 数组），然后更新答案 ans 为 max (ans, j) ，并将当前工件（now）的上一个工序的结束加工时间（last[now]）更新为 j 然后 记得 break !

最后输出 ans 即可。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2;
int m, n, a[N];
bool t[N][7000];
//t[i][j]表示第i台机器第j个时刻有没有被占用 
int stp[N], last[N]; //stp[i]表示第i个工件进行到了哪个工序 
//last[i]表示第i种工件上一个加工的工序结束时的时间 

struct mtsJ
{
	int tim;
	int id;
};
//数组的第1维是指工件号，第2维指工序号
//mt[i][j]表示第i个工件的第j个工序，
//tim为所需时间，id为需加工机器编号
mtsJ mt[N][N];

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 ("jq");
    cin >> m >> n;
	for (int i = 1; i <= n * m; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
		{
			int x; cin >> x;
			//第i次表示输入的第i个工件
			//第j次为输入第i个工件的第j个工序机器编号
			mt[i][j].id = x;
		}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
		{
			int x; cin >> x;
			//x为时间
			mt[i][j].tim = x;
		}
	/*
		思考：接下来干什么？
		由于mt(i, j) --> tim, id求出来了，那么如何循环呢？
		按题目给定工件加工顺序来操作。
		每次看本次需要加工工件工序最优情况下可以安插在哪里
		(要么插在机器的空隙中，要么插在上一道工序后)
	*/
	int ans = 0;
	for (int i = 1; i <= n * m; i ++)
	{
		int now = a[i];
		//now为当前待加工工序所属工件
		int ncn = mt[now][++ stp[now]].id;
		//ncn为当前工序所需机器 
		int lt = mt[now][stp[now]].tim;
		//lt为本次工序需要时间 
		int tme = 0; //tme为连续的可以放的时间区间长度
		//如何检测上一个的工序做完前这个工序不会被做呢？用已知信息。 
		for (int j = last[now] + 1; ; j ++) //j枚举机器能放的时间段 
		{
			if (! t[ncn][j]) tme ++;
			else tme = 0;
			if (tme >= lt) //大于等于lt说明可以记录答案了 
			{
				for (int l = j - tme + 1; l <= j; l ++)
					t[ncn][l] = true;
				ans = max (ans, j);
				last[now] = j;
				break;
			}
		}
	}
	cout << ans;
	return 0;
}

感受与学习：本题我知道了在一道模拟中需要认清楚什么重要的变量需要记录并用对合适的记录方式。

错误原因：没有细看题目 ~~题面都没完全看懂~~ ，去检查之前做的三道题去了qwq。

钟柯哲哲8.9总结

Aug.Day05 8.9总结

#A.发射站

#B.翻译鸡

#C.字符串

#D.机器

状态

开发

支持

关于

钟柯哲哲8.9总结

Aug.Day05 8.9总结

#A.发射站

#B.翻译鸡

#C.字符串

#D.机器

状态

开发

支持

关于

登录