链接：https://www.nowcoder.com/acm/contest/131/B
来源：牛客网
矩阵 M 包含 R 行 C 列，第 i 行第 j 列的值为 M,。
请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件：
子矩阵的行数不能超过 X 行。
子矩阵的列数不能超过 Y 列。
子矩阵中 0 的个数不能超过 Z 个。
请输出满足以上条件的最大子矩阵和。
请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件：
子矩阵的行数不能超过 X 行。
子矩阵的列数不能超过 Y 列。
子矩阵中 0 的个数不能超过 Z 个。
请输出满足以上条件的最大子矩阵和。
输入描述:
第一行输入五个整数 R，C，X，Y，Z。
接下来 N 行，每行输入 M 个整数，第 i 行第 j 列的整数表示 M,。
1 ≤ R,C ≤ 500.
1 ≤ X ≤ R.
1 ≤ Y ≤ C.
1 ≤ Z ≤ R x C. |Mij|<=1e9
输出描述:
输出满足以上条件的最大子矩阵和。 考虑枚举行数。
枚举行数后枚举从哪行开始。
预处理出来纵向前缀和，然后枚举的时候就把每一个元素转化成柱形图那样的格式，然后求最大值就好了。 求最大值时的思想是枚举最后一个元素，然后看前面的元素，前面元素大于0直接放，小于0的就把队尾取出来，加到这个元素，直到不小于0或者队列为空位置。
以数结尾的最大值是目前队列元素里面的和。 用单调栈也可以做。
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=;
int q[N],p[N],zt[N][N],L[N];
long long mp[N][N],up[N][N],a[N];
int R,C,X,Y,Z;
long long work(){
for(int i=;i<=C;++i) p[i]=i;
int h=,r=;
long long ans=,sum=;
q[]=;
for(int i=;i<=C;++i)
{
while(h<=r&&p[q[h]]<=i-Y) sum-=a[q[h++]];
while(h<=r&&a[i]<) {
sum-=a[q[r]];
a[i]+=a[q[r]];
p[i]=p[q[r--]];
}
if(a[i]>) sum+=a[i],q[++r]=i;
while(h<=r&&(L[i]-L[p[q[h]]]>Z)) sum-=a[q[h++]];
ans=max(ans,sum);
}
return ans;
}
int main(){
long long ans=;
scanf("%d%d%d%d%d",&R,&C,&X,&Y,&Z);
for(int i=;i<=R;++i) for(int j=;j<=C;++j) scanf("%lld",&mp[i][j]);
for(int i=;i<=R;++i) for(int j=;j<=C;++j) up[i][j]=up[i-][j]+mp[i][j],zt[i][j]=zt[i-][j]+(mp[i][j]==);
for(int len=;len<=X;++len){
for(int i=;i<=R-len+;++i){
for(int j=;j<=C;++j) a[j]=up[i+len-][j]-up[i-][j],L[j]=zt[i+len-][j]-zt[i-][j];
for(int j=;j<=C;++j) L[j]+=L[j-];
ans=max(ans,work());
}
}
printf("%lld\n",ans);
}
链接：https://www.nowcoder.com/acm/contest/131/C
来源：牛客网
题目描述
有一棵树包含 N 个节点，节点编号从 1 到 N。节点总共有 K 种颜色，颜色编号从 1 到 K。第 i 个节点的颜色为 A。
F 表示恰好包含 i 种颜色的路径数量。请计算：
![牛客网挑战赛19 B，C，F-LMLPHP]( "牛客网挑战赛19 B，C，F-LMLPHP")
F 表示恰好包含 i 种颜色的路径数量。请计算：
输入描述:
第一行输入两个正整数 N 和 K，N 表示节点个数，K 表示颜色种类数量。
第二行输入 N 个正整数，A
表示第 i 个节点的颜色。
接下来 N - 1 行，第 i 行输入两个正整数 U 和 V，表示节点 U 和节点 V 之间存在一条无向边，数据保证这 N-1 条边连通了 N 个节点。
1 ≤ N ≤ 50000.
1 ≤ K ≤ 10.
1 ≤ A ≤ K.
1 ≤ K ≤ 10.
1 ≤ A ≤ K.
输出描述:
输出一个整数表示答案。
题解：T[i]表示集合意义上小于等于i的路径的总数，状态总数(i的范围)为2^k。
求T[i]只要把i集合中的点拿出来做联通块，每个联通块的价值就是联通块中点的数目+C （点的数目，2）
然后求每个状态的点的数量，只需要让他减去他的所有真子集即可。
然后转态再转为数量就可以了。
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e4+;
const int P=1e9+;
vector<pair<int,int> >G;
int f[N],sz[N],n,k,a[N];
int T[],tran[],F[];
int findx(int x){
return (x==f[x])?x:(f[x]=findx(f[x]));
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;++i) scanf("%d",a+i),--a[i];
for(int i=;i<n;++i) {
int x,y;
scanf("%d%d",&x,&y);
G.push_back(make_pair(x,y));
}
for(int i=;i<;++i) {
int x,y,fx,fy;
for(int j=;j<=n;++j) f[j]=j,sz[j]=;
for(int j=;j<n-;++j) {
x=G[j].first,y=G[j].second;
if(((<<a[x])&i)&&((<<a[y])&i)) {
fx=findx(x),fy=findx(y);
sz[fx]+=sz[fy];
f[fy]=fx;
}
}
for(int j=;j<=n;++j) if(((<<a[j])&i)&&(f[j]==j)){
T[i]=(T[i]+sz[j]+(1LL*sz[j]*(sz[j]-)/)%P)%P;
}
}
for(int i=;i<;++i) for(int j=;j<i;++j)
if(!((i^j)&j))
{
T[i]=(T[i]-T[j]+P)%P;
}
for(int i=;i<;++i) for(int j=;j<;++j)
if(i&(<<j)) ++tran[i];
for(int i=;i<;++i) F[tran[i]]=(F[tran[i]]+T[i])%P;
int x=,ans=;
for(int i=;i<=k;++i){
ans=(ans+1LL*F[i]*x%P)%P;
x=131LL*x%P;
}
printf("%d\n",ans);
}
链接：https://www.nowcoder.com/acm/contest/131/F
来源：牛客网
ZZT 得到了一个字符串 S 以及一个整数 K。
WZH 在 1995 年提出了“优雅 K 串”的定义：这个字符串每一种字符的个数都是 K 的倍数。
现在 ZZT 想要对字符串进行 Q 次询问，第 i 次询问给出一个区间 [L, R]，他想计算 [L, R] 中有多少个子串是“优雅 K 串”。
由于 ZZT 忙于工作，所以他把这个问题交给了你，请你帮忙解决。
WZH 在 1995 年提出了“优雅 K 串”的定义：这个字符串每一种字符的个数都是 K 的倍数。
现在 ZZT 想要对字符串进行 Q 次询问，第 i 次询问给出一个区间 [L, R]，他想计算 [L, R] 中有多少个子串是“优雅 K 串”。
由于 ZZT 忙于工作，所以他把这个问题交给了你，请你帮忙解决。
输入描述:
第一行输入一个正整数 K。
第二行输入一个字符串 S。
第三行输入一个正整数 Q，表示有 Q 次询问。
接下来 Q 行，每行输入两个正整数 L 和 R，表示第 i 次询问。
1 ≤ K ≤ 50.
1≤ | S | ≤ 3 x 10 且 S 仅包含小写英文字母.
1≤ Q ≤ 3 x 10.
1 ≤ X ≤ Y ≤ N.
1≤ | S | ≤ 3 x 10 且 S 仅包含小写英文字母.
1≤ Q ≤ 3 x 10.
1 ≤ X ≤ Y ≤ N.
输出描述:
每次询问，输出一个正整数，表示满足条件的“优雅 K 串”的数量。
输入
1
abc
3
1 3
1 2
2 3
输出
6
3
3 题解：先求前缀和，然后可知前缀和相同的左开右闭区间就是所求区间（在模k意义下），所以每个询问的l要先减掉1。
然后前缀和转哈希，对每一个点赋予哈希后的权值。
然后就莫队就好了。
也可以用字典树写。
#include<map>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e4+;
int now,Be[N],ans[N];
int pp[N][];
unsigned long long a[N]; struct Query{
int l,r,id;
bool operator < (const Query &A)const{
return Be[l]==Be[A.l]?r<A.r:l<A.l;
}
}q[N];
char s[N];
int k,l,r;
map<unsigned long long,int> M;
void work(int x,int y){
if(y==) now+=M[a[x]]++;
else now-=--M[a[x]];
}
int main(){
int m,len,unit;
now=;
scanf("%d %s",&k,s+);
len=strlen(s+);
//M[0]=1;
for(int i=;s[i];++i) {
for(int j=;j<;++j) pp[i][j]=pp[i-][j];
pp[i][s[i]-'a']=(pp[i][s[i]-'a']+)%k;
}
for(int i=;s[i];++i) {
unsigned long long pt=;
for(int j=;j<;++j) pt=pt*+pp[i][j];
a[i]=pt;
}
unit=sqrt(len);
for(int i=;i<=len;++i) Be[i]=i/unit+;
scanf("%d",&m);
for(int i=;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i,--q[i].l;
sort(q+,q+m+);
l=q[].l,r=q[].l-;
for(int i=;i<=m;++i) {
while(l<q[i].l) work(l++,-);
while(l>q[i].l) work(--l,);
while(r<q[i].r) work(++r,);
while(r>q[i].r) work(r--,-);
ans[q[i].id]=now;
}
for(int i=;i<=m;++i) {
printf("%d\n",ans[i]);
}
}