这题应该做法有很多吧，我提供一种奇怪的做法
将每一行连续的1提出来，形成一个个区间\(l,r\)
实际是求对于每一\(1\leq l \leq r \leq m\)，能覆盖它的\(l,r\)有多少个
怎么求呢?
首先我们将这些区间存储在每个左端点上
循环枚举左端点，每次将右端点的sum++，维护一个后缀即可,累加得到每个右端点的答案
直接这样做，复杂度应该是\(n \cdot m+m \cdot m\)
那对于\(m\)较大\(n\)较小的情况，如何优化为\(n*m\)呢？
其实是非常简单的，记录右端点出现的最远位置\(maxr\)，每次从\(maxr\)循环到i即可
这样的话，其实每一次是循环一个连续区间的块长，总共块长应该是\(n*m\)
const int N=5010; bool be; int n,m; int a[N][N]; struct Edge{ int to,nxt; }e[N*N/2]; int head[N],ecnt; void AddEdge(int u,int v){ e[++ecnt]=(Edge){v,head[u]}; head[u]=ecnt; } int sum[N],k[N]; bool ed; int main(){ n=rd(),m=rd(); rep(i,1,n) { int c=0,l=1; rep(j,1,m) { char ch; do ch=getchar(); while(ch!='1'&&ch!='0'); a[i][j]=ch^'0'; } rep(j,1,m) { if(a[i][j]) { if(!c) l=j; c++; if(!a[i][j+1]) { AddEdge(l,j); c=0; } } } } int ans=0; rep(i,1,m) { int ma=0; for(int j=head[i];j;j=e[j].nxt) { ma=max(ma,e[j].to); k[e[j].to]++; } int d=0; drep(j,ma,i) { d+=k[j],k[j]=0; sum[j]+=d; ans=max(ans,(j-i+1)*sum[j]); } } printf("%d\n",ans); }\[ \ \]
\[ \ \]
\[ \ \]
dp裸题吧
\[dp[i][j]\]前j个数，分成\(i\)段的最大收益
首先我们考虑\(n^3\)转移
for(int k=1;k<j;++k) dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[k][j])原理简单，拿到部分分
如何优化呢？
考虑\(dp[i-1][k]\)的单调非递减性
我们倒着思考这个循环，\(dp[i-1][k]\)递减，而\(sum[k][j]\)单调非递增
当\(sum[k][j]=sum[k+1][j]\)时，这次的转移一定没有\(dp[i-1][k]+sum[k+1][j]\)优
故只考虑\(sum[k][j]>sum[k+1][j]\)的情况
而什么时候存在这种情况呢？当且仅当\(a[k]\)中存在\(a[k+1..j]\)的二进制位中不拥有的1时递增
所以存下每一位的一上一次出现的位置，一共有\(log_2(10^7)\)的转移方案
总复杂度\(n\cdot k \cdot log_2(10^7)\)，略大于一个亿的样子，但实际上这题时限2s，不是特别卡常吧
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i) char IO; int rd(){ int s=0,f=0; while(!isdigit(IO=getchar())) if(IO=='-') f=1; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; } const int N=5100; int n,k; int a[N],sum[N][N]; ll dp[N/5][N]; int pre[26]; inline int max(int a,int b){ return a>b?a:b; } int main(){ n=rd(),k=rd(); rep(i,1,n) a[i]=rd(); rep(i,1,n) rep(j,i,n) sum[i][j]=sum[i][j-1]|a[j]; ll ans=0; rep(i,1,n) dp[1][i]=sum[1][i]; rep(i,2,k) { memset(pre,-1,sizeof pre); rep(j,1,n) { rep(o,0,23) { if(a[j]&(1<<o)) pre[o]=j; if(~pre[o]) { dp[i][j]=max(dp[i][j],dp[i-1][pre[o]-1]+sum[pre[o]][j]); } } ans=max(ans,dp[i][j]); } } printf("%lld\n",ans); }\[ \ \]
\[ \ \]
\[ \ \]
这不是线性基裸题吗。。
我就不提供代码了
我大概有三种办法写这题
1.DSU+线性基
2.线性基合并，收集子树信息
3.转化为序列问题，维护最优性线性基，保证线性基里的数出现的位置最靠近右端点即可
但是复杂度均为\(log^2n\),并不是特别优秀
比赛时敲的DSU，感觉没什么细节
const int N=1e5+10; bool be; int n; struct Edge{ int to,nxt; }e[N<<1]; int head[N],ecnt; void AddEdge(int u,int v){ e[++ecnt]=(Edge){v,head[u]}; head[u]=ecnt; } #define erep(u,i) for(int i=head[u];i;i=e[i].nxt) int a[N]; int sz[N],son[N],L[N],R[N],dfn,id[N]; void pre_dfs(int u,int f){ id[L[u]=++dfn]=u; sz[u]=1; erep(u,i) { int v=e[i].to; if(v==f) continue; pre_dfs(v,u); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } R[u]=dfn; } struct Linear_Basis{ int d[20]; int Add(int x){ drep(i,17,0) if(x&(1<<i)) { if(d[i]) x^=d[i]; else { d[i]=x; return 1; } } return 0; } int Quemax() { int ans=0; drep(i,17,0) if((ans^d[i])>ans) ans^=d[i]; return ans; } void init(){ memset(d,0,sizeof d); } } B; int ans[N]; void Dsu(int u,int f){ erep(u,i) { int v=e[i].to; if(v==f||v==son[u]) continue; Dsu(v,u); B.init(); } if(son[u]) Dsu(son[u],u); B.Add(a[u]); erep(u,i) { int v=e[i].to; if(v==f||v==son[u]) continue; rep(j,L[v],R[v]) B.Add(a[id[j]]); } ans[u]=B.Quemax(); } bool ed; int main(){ //printf("%lf\n",(&ed-&be)/1024.0/1024.0); rep(i,2,n=rd()) { int u=rd(),v=rd(); AddEdge(u,v); AddEdge(v,u); } rep(i,1,n) a[i]=rd(); pre_dfs(1,0); Dsu(1,0); rep(i,1,rd()) printf("%d\n",ans[rd()]); }转载于:https://www.cnblogs.com/chasedeath/p/11393835.html
