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(); }
全部评论
(0) 回帖