华为8.19笔试2，3部分AC，烦请大佬指点
1. 100%，模拟遍历
#include<iostream>
#include<vector>
using namespace std;
int flag = 1;
bool inner(int k)
{
int a, b;
a = k % 10;
k /= 10;
b = k % 10;
if (b % 2 == 1 && a == 7)
return 1;
return 0;
}
void print(int k, int i, int j)
{
if (inner(k))
{
if (flag == 1)
{
cout << "[[" << i << "," << j << "]" ;
flag = 0;
}
else
{
cout << ",[" << i << "," << j << "]" ;
}
}
return;
}
void fac(int m, int n)
{
vector<int> res;
int hig = m, wid = n;
int size = hig * wid;
int i = 0, j = 0, lowh = 0, loww = 0, k = 1;
while (size > 0 && lowh <= hig && loww <= wid)
{
while (i == lowh && j < wid)
{
print(k++, i, j);
size--;
++j;
}
--j;
++i;
while (j == wid - 1 && i < hig)
{
print(k++, i, j);
size--;
++i;
}
--i;
--j;
while (i == hig - 1 && j >= loww && lowh != hig - 1)
{
print(k++, i, j);
size--;
--j;
}
++j;
--i;
while (j == loww && i > lowh && loww != wid - 1)
{
print(k++, i, j);
size--;
--i;
}
lowh++;
loww++;
wid--;
hig--;
i = lowh;
j = loww;
}
cout << "]" << endl;
return ;
}
int main()
{
int m, n;
cin >> m >> n;
fac(m, n);
return 0;
} 2. 计算组合数，手动打表dp，大小自己调整。未考虑当前层数的节点数大于最多可以存放节点的数量，应该返回0。
#include <iostream>
#include <vector>
using namespace std;
vector<long long> nums, dp;
long long mod = 1e9 + 7;
long long rut(long long n, long long m)
{
int ret = 1;
ret = dp[m] / dp[m - n] / dp[n];//计算组合数
return ret;
}
long long inner(vector<int>& vec, long long& ret, int pos, int tem)//递归计算，pos当前层数，tem是当前层数最多的存放节点位置
{
if (vec[pos] == 0)
{
return 1;
}
return (rut(vec[pos], tem) * inner(vec, ret, pos + 1, vec[pos] * 2)) % mod;
}
void fac(int n)
{
vector<int> vec(n, 0);
for (auto i : nums)
{
vec[i]++;
}
dp.resize(1000000);
dp[0] = 1;
for (int i = 1; i < 1000000; ++i)//手动计算阶乘表dp，方面快速计算组合
{
dp[i] = dp[i - 1] * i;
}
long long ret = 0;
ret = inner(vec, ret, 0, 1);
cout << ret << endl;
}
int main()
{
int n, i;
cin >> n;
nums.resize(n);
for (i = 0; i < n; ++i)
{
cin >> nums[i];
}
fac(n);
return 0;
} 3. 暴力模拟， 70%。未考虑原先字符串存在可以消掉的情况；未考虑方块可以掉落的情况；
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> vs; //存储整个方块矩阵
string s, str;
int ret = 19, mm;
bool fatiction(string& s)//判断一行是否全是方块，全是直接消掉，
{
for (auto i : s)
{
if (i == '0')
return 0;
}
return 1;
}
void inner(int pos, int maxhigh, vector<string> vs)
{
int size = str.size();
for (int i = pos; i < (pos + size); ++i)//上面的俄罗斯方块落下来，调整vs矩阵
{
int j = i - pos;
for (int k = maxhigh - 1, t = str[j] - '0' - 1; t >= 0; t--,k--)
{
vs[k][i] = '1';
}
}
int x = max(mm, maxhigh);
for (int i = maxhigh - 1; i >= 0; i--)//遍历每一行，若可以消掉某一行，存活行数减一
{
if (fatiction(vs[i]))
{
x--;
}
}
if (ret > x)
{
ret = x;
}
return;
}
void fac()
{
int size = s.size(), strSize = str.size();
vs = vector<string>(18, string(size, '0'));
for (int i = 0; i < size; ++i)//将字符串s填充到方块矩阵vs中
{
int hig = s[i] - '0';
if (mm < hig)
mm = hig;
for (int j = 0; j < hig; ++j)
{
vs[j][i] = '1';
}
}
for (int i = 0; i < (size - strSize); ++i)//从左到右遍历字符串str可以落下来的地方，然后调用inner计算
{
int maxhig = 0;
for (int j = 0; j < strSize; ++j)
{
int cur = s[i + j] - '0' + str[j] - '0';
if (maxhig < cur)
{
maxhig = cur;
}
}
inner(i, maxhig, vs);
}
cout << ret << endl;
}
int main()
{
cin >> s;
cin >> str;
fac();
} 