西山居3.22游戏开发程序题

第一题：dfs只有54%，出来后听说是折半特地去学习了一下

思路写了篇题解发在csdn

https://blog.csdn.net/qq_41820091/article/details/123733954?spm=1001.2014.3001.5502

代码

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

int a[100][100] = { 0 }, n, m, k, ans = 0, cnt1 = 0, cnt2 = 0;

typedef struct States
{
	int val = 0, t = 0, l = 0;
};

States s1[200005] = { 0 }, s2[200005] = { 0 };

void dfs1(int x, int y, int temp)
{
	if ((x - 1) + (y - 1) == (m + n - 2) / 2) {
		s1[cnt1].t = x - 1;
		s1[cnt1].l = y - 1;
		s1[cnt1++].val = temp;
		return;
	}
	else {
		if (x < m) dfs1(x + 1, y, temp ^ a[x + 1][y]);
		if (y < n) dfs1(x, y + 1, temp ^ a[x][y + 1]);
		return;
	}
}

void dfs2(int x, int y, int temp)
{
	if ((m - x) + (n - y) == (m + n - 2) - (m + n - 2) / 2) {
		s2[cnt2].t = m - x;
		s2[cnt2].l = n - y;
		s2[cnt2++].val = temp ^ a[x][y];
		return;
	}
	else {
		if (x > 1) dfs2(x - 1, y, temp ^ a[x - 1][y]);
		if (y > 1) dfs2(x, y - 1, temp ^ a[x][y - 1]);
		return;
	}
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++) cin >> a[i][j];
	dfs1(1, 1, a[1][1]);
	dfs2(m, n, a[m][n]);

	for (int i = 0; i < cnt1; i++)
		for (int j = 0; j < cnt2; j++)
			if (((s1[i].val ^ s2[j].val) == k) && (s1[i].t + s2[j].t == m - 1) && (s1[i].l + s2[j].l == n - 1)) ans++;
	cout << ans;
}

第二题：模拟，主要难点是心理承受能力，以及禁止用本地IDE无法调试，我承受能力差就没写。

代码

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

int main()
{
	int n, m, x, y, ans = 1, a[100][100] = {0};
	cin >> n >> m;
	int floor = { 0 }, count = { 0 }, move[100005] = { 0 };
	for (int i = 0; i < m; i++) {
		cin >> floor >> count;
		move[floor] += count;
	}
	int b = 4 * n - 4;
	for (int i = 1; i <= n / 2 + n % 2; i++) {
		x = i; y = i;
		move[i] %= b;
		if (b != 8) b -= 8;
		else b -= 7;
		while (move[i]) {
			move[i]--;
			if ((x == i) && (y < n - i + 1)) {
				y++;
				continue;
			}
			if ((y == n - i + 1) && (x < n - i + 1)) {
				x++;
				continue;
			}
			if ((x == n - i + 1) && (y > i)) {
				y--;
				continue;
			}
			if ((y == i) && (x > i)) {
				x--;
				continue;
			}
		}
		while (a[x][y] == 0) {
			a[x][y] = ans;
			//cout << x << " " << y << "\n";
			ans++;
			if ((x == i) && (y < n - i + 1)) {
				y++;
				continue;
			}
			if ((y == n - i + 1) && (x < n - i + 1)) {
				x++;
				continue;
			}
			if ((x == n - i + 1) && (y > i)) {
				y--;
				continue;
			}
			if ((y == i) && (x > i)) {
				x--;
				continue;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

第三题：数据范围很明显要用O(n)才能ac,因此我去想了O(n)的写法，可惜不知道为什么没AC还只过了15%..复盘的时候发现b[i]=0的特判好像写错地方了

核心思路是将所有的b[i]加起来求和，并且求出第i天买的花会在哪天凋零，在那一天减去b[i]就可以了(余数就开个数组另算)

代码

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

int n, a[100005] = { 0 }, b[100005] = { 0 }, c[100005] = { 0 }, d[100005] = { 0 }, sumb = 0;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		sumb += b[i] - c[i];
		if (b[i] != 0) {
			c[i + a[i] / b[i]] += b[i];			//第i天买的花在i + a[i] / b[i]天就无法提供完整的b[i]芳香值了，用c数组存下准备到时候减掉
			d[i + a[i] / b[i]] += a[i] % b[i];	     //第i天买的花在i + a[i] / b[i]天剩下的芳香值
		}
		cout << sumb + d[i] << " ";
	}
}

#西山居笔试##笔经##西山居游戏#