常见的解题算法

求矩阵中子矩阵元素和不大于K的个数

前缀和+双指针O(n^3)
思路：

1）枚举子矩阵的 左边界i 和 右边界j，
2）用快指针t枚举子矩阵的下边界，慢指针s维护子矩阵的上边界 (s≤t)
3）如果得到的子矩阵的权值和大于 k，则慢指针s 前进，而子矩阵和必将单调不增，慢指针s 继续前进（如图），直到子矩阵的和不大于k，慢指针没必要前进了，因为该子矩阵的所有宽度为 j - i + 1的子矩阵（总共 t - s + 1种）一定满足要求，更新该情况对答案的贡献 t - s + 1；反之，如果慢指针s越界（s > t），则不操作，直接进入下层循环

#include
using namespace std;typedef long long ll;
const int N = 5e2+3;
int n, m, k;
int a[N][N]`
int main(){ios::sync_with_stdio(false);cin >> n >> m >> k;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin >> a[i][j];a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];}}ll ans = 0;for(int i=1; i<=m; i++){for(int j=i; j<=m; j++){for(int s = 1, t = 1; t <= n; t ++ ){while(s <= t && a[t][j] - a[s - 1][j] - a[t][i - 1] + a[s - 1][i - 1] > k) s ++ ;if(s <= t) ans += t - s + 1;}}}cout << ans << '\n';
}

求字符串中某条件子串的个数

前缀和+哈希

思路：

1.求条件子串的个数，也就是求字符串的前缀和中满足条件子串的个数。 因为任意两个符合条件的·前缀和子串相减就是题目要求的子串。
2. 每种前缀和状态下的个数用哈希来维护，即undered_map
3. 需要构造一些结果，使出现0,1,2三种字符能得到不同但是互补的结果。

#include
using namespace std;
#define INF 0x3f3f3f3f
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define PII pair
#define endl '\n'
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)typedef long long LL;const int maxn=4e5+10;
const int N=1e6+10;
const int mod=1e9+7;void solve(){int n; cin>>n;string s; cin>>s;LL ans=0;mapmp;PII v=make_pair(0,0);mp[v]=1;		//初始化，最开始三个数都为0的前缀和状态有1个 //接下来遍历前缀和的0,1,2个数for(int i=0;iif(s[i]=='0') v.fi++, v.se++;else if(s[i]=='1') v.fi--;else v.se--;ans+=mp[v];mp[v]++;}cout<IOS;int t; cin>>t;while(t--){solve();}return 0;
}