西山居3.22游戏开发程序题
第一题：dfs只有54%，出来后听说是折半特地去学习了一下
思路写了篇题解发在csdn
代码
#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] << " ";
}
} 
