【Problem A】 Square
【题意】
给一个n * n的01矩阵，要求一个最大的全1正方形子矩阵，输出它的面积
N <= 1000
【题解】
朴素的做法是先求二维前缀和，然后暴力找最大的正方形子矩阵，时间复杂度 : O(n^3) 期望得分 ： 80
考虑优化，我们发现如果有边长为n的正方形，就一定有边长为(n - 1)的正方形，因此，可以先二分边长d，然后
判断边长为d的正方形是否存在. 时间复杂度 : O(n^2log(n)) 期望得分 ： 100
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 2050 int i,j,l,r,mid,n,ans; int s[MAXN][MAXN]; char ch; bool check(int d) { int i,j,x,y; for (i = 1; i <= n - d + 1; i++) { for (j = 1; j <= n - d + 1; j++) { x = i + d - 1; y = j + d - 1; if (s[x][y] - s[i-1][y] - s[x][j-1] + s[i-1][j-1] == d * d) return true; } } return false; } int main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); scanf("%d",&n); getchar(); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { ch = getchar(); s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + ch - '0'; } getchar(); } l = 1; r = n; while (l <= r) { mid = (l + r) >> 1; if (check(mid)) { l = mid + 1; ans = mid; } else r = mid - 1; } printf("%d ",ans*ans); return 0; }
【Problem B】 findmax
【题意】
一个包含n个元素的数组，元素的值在1-k之间，存在多少个不同的数组，使得扫描这个数组，最大值更新了p次
【题解】
暴力搜索，期望得分 ： 30
由于T最大10^5,所以，我们不可能每次询问都计算一次答案，因此，我们应该进行一些预处理
考虑动态规划预处理
f[i][j][k]表示选了i个元素，元素的最大值为j，进行了k次更新的合法方案
那么，有f[i][j][k] = f[i-1][j][k] * j + f[i-1][t][k-1] (1 <= t <= j - 1)
这个状态转移方程的意思是 ：
如果选到第i个元素时最大值未发生变化，那么，就相当于前i-1个元素最大值为 j，进行了k次更新，而第i个元素就可 以选1..j中的任何一个数，方案数为f[i-1][j][k] * j
如果选到第i个元素时最大值发生了变化，那么，前i-1个元素，最大值可以是1..j-1中的任何一个数，进行了k-1次更 新， 第i个元素为j，方案数为f[i-1][t][k-1] (1 <= t <= j - 1）
然而，这样算法的时间复杂度是O(nk^2p)，不能通过此题
考虑优化，我们用sum[i][j][k]表示选了i-1个元素，进行j次更新，元素的最大值为1..k的方案数（前缀和），
式子就被简化为了 : f[i][j][k] = f[i-1][j][k] * j + sum[i-1][k-1][j-1]
那么，这样时间复杂度就被优化为了O(nkp)
对于每次询问，答案就是sigma(f[n][i][p])(1 <= i <= k)
总时间复杂度 ： O(nkp + tk) 期望得分 ： 100
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 101 #define MAXK 301 #define MAXP 101 const long long MOD = 1e9 + 7; long long i,j,k,ans,n,p,T; long long f[MAXN+10][MAXK+10][MAXP+10],sum[MAXN+10][MAXP+10][MAXK+10]; int main() { freopen("findmax.in","r",stdin); freopen("findmax.out","w",stdout); cin >> T; for (i = 1; i <= MAXK; i++) { f[1][i][0] = 1; sum[1][0][i] = i; } for (i = 2; i <= MAXN; i++) { for (j = 1; j <= MAXK; j++) { for (k = 0; k <= MAXP; k++) { if (!k) f[i][j][k] = (f[i-1][j][k] * j) % MOD; else f[i][j][k] = ((f[i-1][j][k] * j) % MOD + sum[i-1][k-1][j-1]) % MOD; sum[i][k][j] = (sum[i][k][j] + f[i][j][k]) % MOD; } } for (j = 0; j <= MAXP; j++) { for (k = 1; k <= MAXK; k++) { sum[i][j][k] = (sum[i][j][k] + sum[i][j][k-1]) % MOD; } } } while (T--) { ans = 0; cin>> n >> k >> p; for (i = 1; i <= k; i++) ans = (ans + f[n][i][p]) % MOD; cout<< ans << endl; } return 0; }
【Problem C】bds
【题意】
写出1..n的排列a，每次相邻两个数相加，构成新的序列，再对新序列再次进行这样的操作，知道剩下一个数N
给定N，要求字典序排列最小的a
【题解】
调用algorithm库里的next_permutation函数，判断是否可以得到N 期望得分 ： 20
我们发现，N = C(n,1)a1 + C(n,2)a2 + C(n,3)a3 + C(n,4)a4 + ... + C(n,n)an
因此，可以通过杨辉三角计算C(n,i)，然后深度优先搜索DFS
时间复杂度 O (能过） 期望得分 ： 100
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 25 int i,j,n,sum,l; int c[MAXN][MAXN],visited[MAXN],ans[MAXN]; bool solved = false; inline void dfs(int dep,int s) { int i; if (dep > n) { if (s == sum) solved = true; return; } for (i = 1; i <= n; i++) { if (s + i * c[n][dep] > sum) return; if (!visited[i]) { visited[i] = true; ans[++l] = i; dfs(dep+1,s+i*c[n][dep]); if (solved) return; l--; visited[i] = false; } } } int main(){ freopen("bds.in","r",stdin); freopen("bds.out","w",stdout); scanf("%d%d",&n,&sum); c[0][0] = 1; for (i = 1; i <= n; i++) { for (j = 1; j <= i; j++) { c[i][j] = c[i-1][j] + c[i-1][j-1]; } } dfs(1,0); for (i = 1; i < n; i++) printf("%d ",ans[i]); printf("%d ",ans[n]); return 0; }
【总结】
总分20 + 100 + 100 = 220，第一题失分原因是因为将正方形看成了长方形，这样的错误很不应该，以后
一定要避免！
这次考试，基础算法占了很大比重，虽然最近一直在研究比较复杂的算法，但是，也不能忽视了基础算法的
重要性！