本场总结：
A.单调栈
B.区间贡献
C.构造
D.三维树状数组----维护曼哈顿距离
E.线段树区间维护dfs并查集撤销
G.签到
I.树上差分和树状数组区间差分
J.组合数学和dp
小结：
---矩阵中子矩阵问题 单调栈继续练
---构造先蒙
---学习三维树状数组如何维护，后缀最小值转前缀最大值
---学习线段树维护区间交，dfs并查集撤销
---树上dfs序差分和区间交贡献差分
---组合数学复习经典不定方程解个数C(n+m-1,n-1) 和容斥运用
A.All-one Matrices
大致题意：n×m的01矩阵中求极大全1子矩阵的个数.极大全1子矩阵的定义:不被其他全1矩阵所包含.
分析：
- 首先我们可以定义一个a的二维数组代表向上的最长连续1的个数。
- 再定义一个L数组表示当前枚举a[i][j]时第i+1行的第j位向前的最长连续1的个数。
- 那么当枚举到a[i][j]若其前一项 ( 单调队列里的队尾，我们定义为a[i][j-1],因为先出队的队尾就是a[i][j-1] ) a[i][j-1]的向上最长连续a[i][j-1]大于当前这一项 , 并且第i+1行的第j-1位的向前最长连续1的个数少于a[i][j-1]在第i行的向前最长连续1的个数时( 代表以a[i][j-1]为右下角的矩阵无法在向下向右扩充大小了 ) 就存在一个符合上述情况的矩阵ans++即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3005;
struct node{
int h,l,r;
}q[maxn];
int a[maxn][maxn];
int L[maxn];
char mp[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for( int i=1;i<=n;i++ )
{
scanf("%s",mp+1);
for( int j=1;j<=m;j++ )
{
a[i][j]= mp[j]=='1';
a[i][j]+=a[i-1][j]*a[i][j];
}
}
int ans=0;
for( int i=1;i<=n;i++ )
{
int l=1,r=0;
for( int j=1;j<=m+1;j++ )
{
if( a[i+1][j] ) L[j]=L[j-1]+1;
else L[j]=0;
node tmp={ a[i][j],j,j };
while( l<=r && tmp.h<=q[r].h )
{
if( tmp.h<q[r].h && L[j-1]<j-q[r].l ) ans++;
tmp.l=q[r].l;
r--;
}
q[++r]=tmp;
}
}
printf("%d\n",ans);
return 0;
}B. Beauty Values
大致题意：给一个序列,求该序列的值.一个序列的值定义为：所有子区间值的和。(区间值：区间内不同元素个数 ).
分析: 我们枚举每一个位置数字的贡献就可，对与当前位置的数字的贡献区间数( 区间出现第一次的数算作贡献 )，左区间的范围就是 当前位置 减去 max(前一次该数字出现的位置,0) ，右区间就是 n+1 减去 当前位置,左区间方案乘以右区间方案 得出贡献.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int a[maxn];
int n;
vector<int> g[maxn];
int main()
{
int n;
ll ans=0;
cin>>n;
for( int i=1;i<=n;i++ ) g[i].push_back(0);
for( int i=1;i<=n;i++ ) cin>>a[i],g[a[i]].push_back(i);
for( int i=1;i<=n;i++ )
{
if( g[i].size()<2 ) continue;
for( int j=0;j<g[i].size()-1;j++ )
{
ans+=1ll*(g[i][j+1]-g[i][j])*(n-g[i][j+1]+1);
}
}
cout<<ans<<endl;
} C. CDMA
大致题意:求构造一个2^n阶01矩阵 使得内积为0------构造2^n个2^n维正交向量.
**分析：著名问题----阿达马矩阵的西尔维斯特构造法。就是如同给的样例，矩阵分成四个区域。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mp[12][2105][2105];
int main()
{
mp[0][0][0]=1;mp[0][0][1]=1;
mp[0][1][0]=1;mp[0][1][1]=-1;
int cnt=2;
for( int i=1;i<=10;i++ )
{
for( int j=0;j<cnt;j++ )
{
for( int k=0;k<cnt*2;k++ )
{
mp[i][j][k]=mp[i-1][j][k%cnt];
}
}
for( int j=cnt;j<cnt*2;j++ )
{
for( int k=0;k<cnt*2;k++ )
{
if( k>=cnt ) mp[i][j][k]=-mp[i-1][j%cnt][k%cnt];
else mp[i][j][k]=mp[i-1][j%cnt][k%cnt];
}
}
cnt*=2;
}
int n;
cin>>n;
cnt=log2(n);
for( int i=0;i<n;i++ )
{
for( int j=0;j<n;j++ ) printf("%d ",mp[cnt][i][j]);puts("");
}
return 0;
} D. Distance
大致题意：三维空间，两种操作。( 1≤n×m×h,q≤1e5,1≤x≤n,1≤y≤m,1≤z≤h )
- (1,x,y,z) 添加(x,y,z) 点。
- (2,x,y,z) 确定到给定位置(x,y,z)的最小曼哈顿距离.曼哈顿距离定义为 |x1-x2|+|y1-y2|+|z1-z2| .
分析:令 f=|x2-x1|+|y2-y1|+|z2-z1|,那么可以讨论去绝对值后f的八种情况
由于 x2+y2+z2 的值是固定的，只需要求出最大的符合条件的 x1+y1+z1即可，发现 x1<=x2 && y1<=y2 && z1<=z2这个条件刚好可以用三维树状数组来维护(求前缀最大值，单点更新)
当x1>x2时,我们本应该求后缀最小值,需要将 x1>x2 转换成 n-x1+1<=n-x2+1,就转变为前缀最大值了, 然后更新的是x1+y1-z1，查询的结果是最大的 x1+y1-z1(其他情况类似)
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int n,m,h,T;
struct BIT{
int d[maxn];
void init()
{
memset(d,128,sizeof(d));
}
int f( int i,int j,int k )
{
return (i-1)*m*h+(j-1)*h+k;
}
void update( int x,int y,int z,int w )
{
for( int i=x;i<=n;i+=lowbit(i) )
{
for( int j=y;j<=m;j+=lowbit(j) )
{
for( int k=z;k<=h;k+=lowbit(k) ) d[f(i,j,k)]=max( d[f(i,j,k)],w );
}
}
}
int sum( int x,int y,int z )
{
int res=-inf;
for( int i=x;i;i-=lowbit(i) )
{
for( int j=y;j;j-=lowbit(j) )
{
for( int k=z;k;k-=lowbit(k) ) res=max( d[f(i,j,k)],res );
}
}
return res;
}
}t[8];
int main()
{
for( int i=0;i<8;i++ ) t[i].init();
scanf("%d%d%d",&n,&m,&h);
scanf("%d",&T);
while( T-- )
{
int opt,x,y,z;
scanf("%d%d%d%d",&opt,&x,&y,&z);
if( opt==1 )
{
t[0].update(x,y,z,x+y+z);
t[1].update(x,y,h-z+1,x+y-z);
t[2].update(x,m-y+1,z,x-y+z);
t[3].update(x,m-y+1,h-z+1,x-y-z);
t[4].update(n-x+1,y,z,-x+y+z);
t[5].update(n-x+1,y,h-z+1,-x+y-z);
t[6].update(n-x+1,m-y+1,z,-x-y+z);
t[7].update(n-x+1,m-y+1,h-z+1,-x-y-z);
}
else
{
int ans=inf;
ans=min( ans,x+y+z-t[0].sum(x,y,z) );
ans=min( ans,x+y-z-t[1].sum(x,y,h-z+1) );
ans=min( ans,x-y+z-t[2].sum(x,m-y+1,z) );
ans=min( ans,x-y-z-t[3].sum(x,m-y+1,h-z+1) );
ans=min( ans,-x+y+z-t[4].sum(n-x+1,y,z) );
ans=min( ans,-x+y-z-t[5].sum(n-x+1,y,h-z+1) );
ans=min( ans,-x-y+z-t[6].sum(n-x+1,m-y+1,z) );
ans=min( ans,-x-y-z-t[7].sum(n-x+1,m-y+1,h-z+1) );
printf("%d\n",ans);
}
}
return 0;
}
E. Explorer
大致题意:n个点,m条边的无向图,每条边有属性区间[li,ri],主角要从1走到n，主角可以刚开始时设定一个大小值size,主角可以通过一条边i当且仅当 li<=size<=ri,问主角到达 n 点的方案数.(n,m<=1e5, li,ri<=1e9 )
**分析：
- 首先将区间进行离散化 就有2e5个点,我们可以枚举size进行check判断是否能到达。
- 那么区间如何维护呢,我们可以用一个线段树key为size,每个节点一个vector维护满足size的边信息。
- 然后dfs边搜边用并查集缩边,dfs到叶节点进行判断当前size是否符合(必须到叶节点才能去算贡献，不然无法从离散点中找到当前贡献答案 )。这里要注意dfs回溯时 并查集撤销操作。**
#include<bits/stdc++.h>
#define ls cur<<1
#define rs cur<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,m;
struct node{
int u,v,le,re;
}e[maxn];
vector<int> p;
int ans;
vector< pair<int*,int> > sav[20];
int fa[maxn<<1],siz[maxn<<1],np;
vector<int> uns[maxn<<3];
int get_id( int x ) { return lower_bound( p.begin(),p.end(),x )-p.begin(); }
int get_fa( int x ) { return fa[x]==x ? x : get_fa(fa[x]) ; };
void update( int cur,int l,int r,int L,int R,int idx )
{
if( L<=l && r<=R )
{
uns[cur].push_back(idx);
return;
}
int mid=(l+r)>>1;
if( L<=mid ) update(ls,l,mid,L,R,idx);
if( R>mid ) update(rs,mid+1,r,L,R,idx);
}
void unit( int x,int y,int dep )
{
int fx=get_fa(x), fy=get_fa(y);
if( fx==fy ) return;
if( siz[fx]<siz[fy] ) swap(fx,fy);
sav[dep].push_back( { &fa[fy],fy } );
sav[dep].push_back( { &siz[fx],siz[fx] } );
fa[fy]=fx;
siz[fx]+=siz[fy];
return;
}
void dfs( int cur,int l,int r,int dep )
{
for( auto &id:uns[cur] )
{
unit( e[id].u,e[id].v,dep );
}
if( l==r )
{
int f1=get_fa(1),fn=get_fa(n);
if( f1==fn ) ans+= p[l]-p[l-1];
}
else
{
int mid=(l+r)>>1;
dfs(ls,l,mid,dep+1);
dfs(rs,mid+1,r,dep+1);
}
for( auto it:sav[dep] ) *it.first=it.second;
sav[dep].clear();
return;
}
int main()
{
scanf("%d%d",&n,&m);
for( int i=1;i<=m;i++ )
{
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].le,&e[i].re);
p.push_back( e[i].le-1 );
p.push_back( e[i].re );
}
p.push_back( *min_element(p.begin(), p.end())-1 );
sort( p.begin(),p.end() );
p.erase( unique(p.begin(),p.end()),p.end() );
int num=p.size()-1;
for( int i=1;i<=m;i++ )
{
update( 1,1,num,get_id(e[i].le),get_id(e[i].re),i );
}
for( int i=1;i<=n;i++ ) fa[i]=i,siz[i]=1;
dfs(1,1,num,1);
printf("%d\n",ans);
return 0;
}G. Gemstones
大致题意：给一个字符串，连续三个相同字符就可删除(每删除一次都可以再判断),计算删除次数.
分析：栈,签到.
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn],top,ans;
int main()
{
string s;
cin>>s;
for( int i=0;i<s.size();i++ )
{
if( top<2 ) a[top++]=s[i];
else
{
if( a[top-1]==s[i] && a[top-2]==s[i] ) top-=2,ans++;
else a[top++]=s[i];
}
}
cout<<ans<<endl;
}I. Inner World
大致题意：一开始n棵树，每棵树只有一个根节点，标号为1。多次操作，每次在区间[l,r]的树中的结点 u 下增加一个结点 v ,多次询问，问区间 [l,r] 的树的结点 u 的子树的大小求和.
分析：
- 题意表明增加的结点 v 是互不相同的，所以可以建成一棵树，在结点加一个区间，表示在 [l,r] 中才存在这一个结点.
- 询问操作.等价于问 结点 u 的子树中，所有结点表示的区间与 [l,r] 求交集之后的区间大小，再求和.
- 因为是一颗树,我们可以将点按照dfs序排序变成区间,每个节点与[l,r]的交集.
- 首先按照dfs序进行询问贡献 差分,询问贡献差分有个小技巧,对于标记 当前节点dfs序编号的前一个位置,清除 当前询问不符合的多余贡献,然后标记以 当前点为根的子树的最后dfs序编号,从而求得答案.
- 对于求区间交贡献部分,显然用两个树状数组就可求得.(类似 第七场 E题 )
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
int l[maxn],r[maxn];
int in[maxn],out[maxn];
int id[maxn],cnt;
ll ans[maxn];
vector<int> a[maxn];
struct EX_BIT{
struct BIT{
ll c[maxn];
void add( int x,ll k ) { while( x<maxn ) c[x]+=k,x+=lowbit(x); }
ll sum( int x ) { ll ans=0; while( x ) ans+=c[x],x-=lowbit(x); return ans; }
} BIT1,BIT2;
ll sum( ll x ) //算 区间交贡献
{
return (x+1)*BIT1.sum(x)-BIT2.sum(x);
}
void add( int x,ll k )
{
BIT1.add(x,k); BIT2.add(x,x*k);
}
ll getsum( int l,int r )
{
return sum(r)-sum(l-1);
}
void update( int l,int r,ll x )
{
add(l,x); add(r+1,-x); //区间差分
}
}BIT;
struct node{
int l,r,sign,id;
};
vector<node> g[maxn];
void dfs( int x )
{
in[x]=++cnt;id[ in[x] ]=x; // dfs 序编号 in[点编号] || id[ dfs序 ] = 对应点编号
for( auto v:a[x] ) dfs(v);
out[x]=cnt; // 当前节点最后的 dfs序编号
}
int main()
{
int n,m;
scanf("%d%d",&n,&m); // n棵树 m个添点操作
l[1]=1;r[1]=n;
for( int i=1;i<=m;i++ )
{
int x,y;
scanf("%d%d",&x,&y); // x->y [Ly,Ry]
a[x].push_back(y);
scanf("%d%d",&l[y],&r[y]);
}
dfs(1);
int q;
scanf("%d",&q);
for( int i=1;i<=q;i++ )
{
int x,L,R;
scanf("%d%d%d",&x,&L,&R);
g[ in[x]-1 ].push_back( node{L,R,-1,i} ); // dfs序 的区间贡献 差分
g[ out[x] ].push_back( node{L,R,1,i} );
}
for( int i=1;i<=cnt;i++ )
{
int x=id[i];
BIT.update( l[x],r[x],1 );
for( auto v:g[i] )
{
ans[ v.id ]+=1ll*v.sign*BIT.getsum( v.l,v.r );
}
}
for( int i=1;i<=q;i++ ) printf("%lld\n",ans[i]);
}J. Just Jump
大致题意：有一只青蛙在0位置处，他想跳到L位置处，但是路上会受到一些攻击，这只青蛙在出发前就知道自己在跳第几次的时间时哪一个位置会受到攻击，并且青蛙每次跳的距离要大于等于d，问青蛙安全（不受一次攻击）跳到L处的方案数.
( 1≤d≤L≤1e7, 1≤t,p<L, 1≤m≤3000, mod=998244353 )
**分析:
首先不考虑受攻击的情况，那么可以用一个dp和 前缀和优化 算出所有情况dp[i]=sum[i-d],sum[i]=sum[i-1]+dp[i].
考虑减去被攻击的方案数( 受到一次攻击的情况 ) 就是对于每个受攻击的位置，正好第ti步跳到那里受到攻击那么情况数
,那么可以暴力容斥,减去一次受到攻击的次数，加上两次受到攻击的次数，减去三次受到攻击的次数...根据位置索引进行排序.
容斥原理:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int mod=998244353;
int n,m,t;
int dp[maxn],sum[maxn],b[maxn];
int fac[maxn],inv[maxn];
int L,d;
pair<int,int> a[3005];
int qpow( ll a, ll b )
{
ll ans=1;a%=mod;
while( b )
{
if( b&1 ) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
void init()
{
fac[0]=inv[0]=1;
for( int i=1;i<maxn;i++ ) fac[i]=1ll*fac[i-1]*i%mod;
inv[maxn-1]=qpow(fac[maxn-1],mod-2);
for( int i=maxn-1;i>0;i-- ) inv[i-1]=1ll*inv[i]*i%mod;
}
int C( int x,int y )
{
if( x<y )return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int solve( int l,int r )
{
if( a[l].second>=a[r].second || a[l].first==a[r].first ) return 0;
int len=a[r].first-a[l].first,tmp=a[r].second-a[l].second;
if( 1ll*tmp*d-len>0 ) return 0;
return C( len-tmp*d+tmp-1,tmp-1 );
}
int main()
{
init();
scanf("%d%d%d",&L,&d,&m);
for( int i=1;i<=m;i++ ) scanf("%d%d",&a[i].second,&a[i].first);
sort(a+1,a+1+m);
sum[0]=b[0]=1;
for( int i=1;i<d;i++ ) sum[i]=sum[i-1];
for( int i=d;i<=L;i++ )
{
dp[i]=sum[i-d];
sum[i]=( sum[i-1]+dp[i] )%mod;
}
for( int i=1;i<=m;i++ )
{
for( int j=0;j<i;j++ ) b[i]=( b[i]+1ll*b[j]*solve(j,i)%mod )%mod;
b[i]=(-b[i]+mod)%mod;
}
for( int i=1;i<=m;i++ ) dp[L]=( dp[L]+1ll*b[i]*dp[L-a[i].first]%mod )%mod;
printf("%d\n",dp[L]);
return 0;
}
京公网安备 11010502036488号