本场总结:
题目类型:
A.概率问题
D.bfs第K小团
E.线性dp，线段树维护矩阵加速
F.dfs剪搜
H.单调栈维护第二大子矩阵
J.区间合并问题其他题目暂时鸽了
小结:
--概率问题脑子不够用
--k小团问题bit<int.> & 极好用
--线段树还能维护矩阵加速 震惊
--单调栈找第二大子矩阵小细节--注意
--区间合并问题一直是zero 下次还是不会
A. Eddy Walker
大致题意：一个由0--n-1组成的环，你的起点为0,你在环上行走,你会独立地随机选择前进或后退。现给你T个场景，场景先后关联产生。场景给定n,m，n表示行走的是0--n-1的环,m表示你从起点0开始行走,环上每个点都走了一次，最后落脚点为m.
分析：
- 我们先考虑一个场景,起点为0，终点不定，其实走的顺序组合就是(n-1)个点的排列---(n-1)!.那么场景要求终点是m,那么组合就是(n-2)个点的排列---(n-2)!.那么该场景发生的概率就是 (n-2)! / (n-1)! = 1/(n-1). ( n>1 , m!=0 )
- 那么如果n>1,m=0时，显然该场景的发生概率为0,因为起始点为0.
- n=1,m=0时,因为环只有一个点，那么该场景发生概率为1.
最后有个坑点，就是前后场景关联，发生第n个场景的概率要乘以前缀场景发生概率乘积即为答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,m,t;
ll poww( ll a,ll b )
{
ll ans=1;
while( b )
{
if( b&1 ) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int main()
{
ll ans=1;
scanf("%d",&t);
while( t-- )
{
scanf("%d%d",&n,&m);
if( n==1 && m==0 ) ans=ans*1;
else if( m==0 ) ans=0;
else ans=ans*poww(n-1,mod-2)%mod;
printf("%lld\n",ans);
}
}D. Kth Minimum Clique
大致题意：给定n个点和每个点的点权，再给定各点的边关系.求一个第k小加权团.
加权团定义:一个点集合的点权总和,集合中各点满足任意两点在图中可达. 注:空集是最小的加权团
分析:显然用优先队列bfs直接找就行，对于当前点集合，一个新的点要加入进去必须满足到集合各点都是可达的，那么我们可以用bitset来维护更新集合，具体实现看代码.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
bitset<105> bit1[105];
int n,k;
ll w[105];
struct node{
ll sum;
bitset<105> bit;
int idx;
bool operator < ( node t ) const{
return sum>t.sum;
}
};
priority_queue<node> que;
int main()
{
scanf("%d%d",&n,&k);k--;
for( int i=1;i<=n;i++ ) scanf("%d",&w[i]);
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=n;j++ )
{
int x;scanf("%1d",&x);
bit1[i][j]=x;
}
}
if( !k )
{
puts("0");
return 0;
}
for( int i=1;i<=n;i++ ) que.push( {w[i],bit1[i],i} );
while( !que.empty() )
{
node p=que.top();que.pop();
if( k==1 )
{
printf("%lld\n",p.sum);
return 0;
}
k--;
for( int i=p.idx+1;i<=n;i++ )
{
if( p.bit[i] )
{
que.push( {p.sum+w[i],p.bit&bit1[i],i} );
}
}
}
puts("-1");
return 0;
} E. MAZE
题目大意:走迷宫，n*m大小的01迷宫,1的位置有一堵墙不可访问，每次可以向左或者向右或者向上走，到达位置标记必须为0，并且不可以走回头路。q个询问，问到第n层某个位置有多少种走法。( n<=5e4 , m<=10 )
分析：
https://blog.csdn.net/weixin_43702895/article/details/99197116
#include<bits/stdc++.h>
#define ls ( cur<<1 )
#define rs ( cur<<1|1 )
#define ms(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
const int maxn=5e4+10;
const int maxm=12;
const int mod=1e9+7;
int n,M,q;
int mp[maxn][maxm];
struct matrix{
ll m[maxm][maxm];
matrix operator * ( matrix &a ) // 乘法重载
{
matrix x;
ms(x.m);
for( int i=1;i<=M;i++ )
{
for( int j=1;j<=M;j++ )
{
for( int k=1;k<=M;k++ )
x.m[i][j]=(x.m[i][j]+this->m[i][k]*a.m[k][j])%mod;
}
}
return x;
}
};
struct node{
int l,r;
matrix mat;
}t[maxn<<2];
void pushup( int cur )
{
t[cur].mat=t[ls].mat*t[rs].mat;
}
void build( int cur,int l,int r )
{
t[cur].l=l;
t[cur].r=r;
if( l==r )
{
for( int i=1;i<=M;i++ )
{
if( mp[l][i]==1 ) continue;
else t[cur].mat.m[i][i]=1;
for( int j=i+1;j<=M;j++ )
{
if( mp[l][j]==0 ) t[cur].mat.m[j][i]=1;
else break;
}
for( int j=i-1;j>=1;j-- )
{
if( mp[l][j]==0 ) t[cur].mat.m[j][i]=1;
else break;
}
}
return;
}
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(cur);
}
void update( int cur,int x )
{
int l=t[cur].l,r=t[cur].r;
if( l==r )
{
ms(t[cur].mat.m);
for( int i=1;i<=M;i++ )
{
if( mp[x][i]==1 ) continue;
else t[cur].mat.m[i][i]=1;
for( int j=i+1;j<=M;j++ )
{
if( mp[l][j]==0 ) t[cur].mat.m[j][i]=1;
else break;
}
for( int j=i-1;j>=1;j-- )
{
if( mp[l][j]==0 ) t[cur].mat.m[j][i]=1;
else break;
}
}
return;
}
int mid=(l+r)/2;
if( x<=mid ) update(ls,x);
else update(rs,x);
pushup(cur);
}
int main()
{
scanf("%d%d%d",&n,&M,&q);
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=M;j++ ) scanf("%1d",&mp[i][j]);
}
build(1,1,n);
while( q-- )
{
int opt,a,b;
scanf("%d%d%d",&opt,&a,&b);
if( opt==1 )
{
mp[a][b]^=1;
update(1,a);
}
else
{
printf("%lld\n",t[1].mat.m[a][b]);
}
}
return 0;
}
F. Partition problem
大致题意:2*n个人有不同的竞争关系权值(两个人所属不同队伍就会产生对应的竞争关系权值)，请给他们分成两支队伍，使得竞争值最大。
分析:dfs边搜 边更新答案，当前队伍用一个vector来存,一个新人加入队伍更新贡献.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int v[30][30];
ll sum[30];
int n;
ll ans=0;
vector<int> q;
void dfs( int x,ll p )
{
if( x>2*n ) return;
if( q.size()==n )
{
ans=max(ans,p);
return;
}
dfs(x+1,p);
q.push_back(x);
p+=sum[x];
for( int i=0;i<q.size();i++ ) p-=2*v[x][q[i]];
dfs(x+1,p);
q.pop_back();
}
int main()
{
scanf("%d",&n);
for( int i=1;i<=2*n;i++ )
{
sum[i]=0;
for( int j=1;j<=2*n;j++ )
{
scanf("%d",&v[i][j]);
sum[i]+=v[i][j];
}
}
dfs(1,0ll);
printf("%lld\n",ans);
}H. Second Large Rectangle
大致题意：给定n*m的01矩阵，找第二大的全1子矩阵.
分析:枚举下边界，单调队列处理出 以a(ij)为高的左右边界,然后更新答案即可.判段重复矩阵那就用个set维护一下.
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int a[maxn][maxn];
int L[maxn],R[maxn];
int s[maxn];
set< pair<pair<int,int>,int> > p;
priority_queue<int, vector<int>, greater<int> > q;
void add(int x)
{
q.push(x);
while (q.size() > 2) q.pop();
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=m;j++ )
{
scanf("%1d",&a[i][j]);
a[i][j]+=a[i-1][j]*a[i][j];
}
}
int ans1=0,ans2=0;
q.push(0);q.push(0);
for( int i=1;i<=n;i++ )
{
int top=0;
p.clear();
for( int j=1;j<=m;j++ ) // find l
{
while( top && a[i][s[top]]>=a[i][j] ) --top;
L[j]=( top==0 ? 1 : s[top]+1 );
s[++top]=j;
R[j]=j;
}
top=0;
for( int j=m;j>=1;j-- ) // find r
{
while( top && a[i][s[top]]>=a[i][j] ) --top;
R[j]=( top==0 ? m : s[top]-1 );
s[++top]=j;
}
for( int j=1;j<=m;j++ )
{
p.insert( make_pair( make_pair(L[j],R[j]),a[i][j] ) );
}
for( auto v:p )
{
int l1=v.first.first,r1=v.first.second,tmp=v.second;
int tmp1=(r1-l1+1)*tmp;
int tmp2=(r1-l1+1)*(tmp-1);
int tmp3=(r1-l1)*tmp;
add(tmp1);add(tmp2);add(tmp3);
}
}
printf("%d\n",q.top());
}J.Subarray
题目大意：一个长度为1e9的序列,给定n组全为1的区间，求有多少区间对(l,r)满足区间和大于0. 序列中1的个数不超过1e7( n<1e6 )
分析:
- 首先我们讨论如果序列长度很短的话如何求解.显然我们会用前缀和。对于一个区间对，我们固定右边界r,要找有效的左边界，我们只需要的前缀中小于sum[r]的个数即可.
- 那么回到这道题.虽然序列的长度是1e9,但是1的个数不超过1e7.那么我们考虑一段区间(3,5)全为1,与其关联的产生贡献区间只有(1,2) 和 (6,7).那么对于整个1e9序列，我们只用考虑区间长度最多其实就是1e7的量级.
- 对于刚才的举例如何求得(1,2) 和(6,7)呢.我们可以用两个数组来维护back[]和front[],back 表示一个区间 以 第 i 段的左边界为左边界 向右延长的最大区间和,front 表示一个区间 以 第 i段的右边界为右边界 向左延长的最大区间和.这样就可以求得关联区间了.
- 并且为了优化计算，我们还可以合并有效区间，对于两个区间交，并为一个区间计算。这样就处理出所有区间，那么我们按照前缀和的方法计算即可.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int maxm=1e6+10;
int n;
int l[maxm],r[maxm]; // l[i],r[i]表示第i段全1区间的左右边界
int back[maxm],front[maxm]; // back 表示一个区间 以 第 i段的左边界为左边界 的最大区间和
// front 表示一个区间 以 第 i段的右边界为右边界 的最大区间和
int cnt[maxn<<2]; // 计数相同前缀和个数
int num2;
int sum[maxn<<2]; // 维护有效合并区间前缀和
ll ans=0;
int main()
{
scanf("%d",&n);
r[n+1]=l[n+1]=1e9+10;
for( int i=1;i<=n;i++ )
{
int a,b;scanf("%d%d",&a,&b);
l[i]=a+1;r[i]=b+1;
}
// 更新 back front
for( int i=1;i<=n;i++ ) front[i]=r[i]-l[i]+1+max( front[i-1]-(l[i]-r[i-1]-1),0 );
for( int i=n;i>=1;i-- ) back[i]=r[i]-l[i]+1+max( back[i+1]-(l[i+1]-r[i]-1),0 );
int i=1;
int base=1e7+10;
while( i<=n )
{
int pos=i,t=i;
while( pos<=n && front[pos]+back[pos+1]>=l[pos+1]-r[pos]-1 ) pos++; // 合并区间
int first=max(l[i]-back[i],1),last=min((int)1e9,r[pos]+front[pos]); // 确定合并区间的有效边界
int len=last-first+1; // 合并区间de长度
for( int k=first;k<=last;k++ )
{
int id=k-first+1;
if( k>=l[t] && k<=r[t] ) sum[id]=sum[id-1]+1; // 当前位置是 1
else sum[id]=sum[id-1]-1; // 当前位置是 -1
if( k==r[t] ) t++; // t就是 区间迭代序号
cnt[sum[id]+base]=0; // 初始化
}
cnt[base+0]=1;
for( int k=1;k<=len;k++ )
{
if( sum[k]>sum[k-1] ) num2=num2+cnt[sum[k-1]+base]; // num2表示在sum[i]前面比sum[i]小的数的个数
else num2=num2-cnt[sum[k]+base];
cnt[sum[k]+base]++;
ans+=num2; //区间对 右边界为 last+k-1 的贡献
}
num2=0;
i=pos+1;
}
printf("%lld\n",ans);
return 0;
}
京公网安备 11010502036488号