| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 7/10 | Ø | O | O | Ø | Ø | . | O | . | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2019牛客暑期多校训练营第八场
A
题目描述
问一个$01$矩阵中有多少个极大全$1$子矩形。
解题思路
扫描先处理一遍，枚举每一行作为底边，对这条底边上任意一个点$i$，只要$[l_i,r_i]$不是被包含在$[l_{i+1},r_{i+1}]$里，就能构成一个极大的矩形。每行记录一下是否计算过左右端分别为$[l,r]$的矩形防止多次计算即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
typedef long long ll;
using namespace std;
char a[N];
int l[N][N],r[N][N],u[N][N],mt[N][N];
int vis[N][N];
int main(){
int i,j,n,m,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%s",a);
for(j=1;j<=m;j++)mt[i][j]=a[j-1]-'0';
}
memset(r,0x3f,sizeof(r));
for(i=1;i<=n;i++){
int lm=0,rm=m+1;
for(j=1;j<=m;j++){
if(mt[i][j]){
if(i==1)l[i][j]=lm+1;
else l[i][j]=max(l[i-1][j],lm+1);
u[i][j]=u[i-1][j]+1;
}else lm=j;
}
for(j--;j;j--){
if(mt[i][j]){
if(i==1)r[i][j]=rm-1;
else r[i][j]=min(r[i-1][j],rm-1);
}else rm=j;
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(!mt[i][j])continue;
int L=l[i][j],R=r[i][j];
if(vis[L][R]==i)continue;
vis[L][R]=i;
if(i==n||!mt[i+1][j]||l[i+1][j]>L||r[i+1][j]<R)ans++;
}
}
printf("%d",ans);
return 0;
}
B
题目描述
给一个数列，求所有连续非零子序列的美丽值，其中一个序列的美丽值定义为其中不同元素的个数。
解题思路
枚举每一位结尾的贡献，记录一下每个数最后出现的位置即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long ll;
using namespace std;
int n,a,last[100010];
ll s,f[100010];
int main(){
int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a);
f[i]=f[i-1]+(i-last[a]);
last[a]=i;
s+=f[i];
}
printf("%d",s);
return 0;
}
C
题目描述
求一个$m=2^k$维的、只由$1,-1$构成的$m$个互相垂直的向量。
解题思路
$m=2$时，向量组可以写为$A_2=\left(\begin{aligned}1\space {1}\\ -1\space{1}\end{aligned}\right) $
$m=2^k$时，向量组可以写为$A_k=\left(\begin{aligned}A_{k-1}\space {A_{k-1}}\\ -A_{k-1}\space{A_{k-1}}\end{aligned}\right) $
可行性显然。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;
using namespace std;
int n;
int mt[2000][2000];
int main(){
int i,j,k;
mt[0][0]=mt[0][1]=mt[1][1]=1;mt[1][0]=-1;
for(i=1;i<10;i++){
for(j=0;j<(1<<i);j++){
for(k=0;k<(1<<i);k++){
mt[(1<<i)+j][k]=mt[j][k];
mt[(1<<i)+j][(1<<i)+k]=mt[j][k];
mt[j][(1<<i)+k]=-mt[j][k];
}
}
}
scanf("%d",&n);
for(i=0;i<n;i++){
for(j=0;j<n;j++)printf("%d ",mt[i][j]);
puts("");
}
return 0;
}
D
题目描述
$q$次操作，每次可能在$(x,y,z)$点插入一个标签，也可能问离$(x,y,z)$曼哈顿距离最近的标签离它有多远。
解题思路
维护八个三维树状数组，表示坐标原点分别在限制范围长方体的八个顶点上的时候，对应的有标签的$x+y+z$的最大值，每次按照坐标原点对应移动暴力询问即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef long long ll;
using namespace std;
int n,m,h,q;
int bit[10][500110];
int id(int i,int j,int k){return i*m*h+j*h+k;}
int lb(int x){return x&(-x);}
void upd(int px,int py,int pz,int ind,int x){
int i,j,k;
for(i=px;i<=n;i+=lb(i))for(j=py;j<=m;j+=lb(j))for(k=pz;k<=h;k+=lb(k))
bit[ind][id(i,j,k)]=max(x,bit[ind][id(i,j,k)]);
}
int que(int px,int py,int pz,int ind){
int i,j,k,ans=-1e8;
for(i=px;i;i-=lb(i))for(j=py;j;j-=lb(j))for(k=pz;k;k-=lb(k))
ans=max(ans,bit[ind][id(i,j,k)]);
return ans;
}
int main(){
int i,j;
scanf("%d%d%d%d",&n,&m,&h,&q);
n++,m++,h++;
for(i=0;i<10;i++)for(j=0;j<500110;j++)bit[i][j]=-1e8;
while(q--){
int opt,x,y,z,ans=1e8;
scanf("%d%d%d%d",&opt,&x,&y,&z);
if(opt==1){
upd( x, y, z,1,x+y+z);
upd(n-x, y, z,2,n-x+y+z);
upd( x,m-y, z,3,x+m-y+z);
upd(n-x,m-y, z,4,n-x+m-y+z);
upd( x, y,h-z,5,x+y+h-z);
upd(n-x, y,h-z,6,n-x+y+h-z);
upd( x,m-y,h-z,7,x+m-y+h-z);
upd(n-x,m-y,h-z,8,n-x+m-y+h-z);
}else{
ans=min(ans,-que( x, y, z,1)+x+y+z);
ans=min(ans,-que(n-x, y, z,2)+(n-x)+y+z);
ans=min(ans,-que( x,m-y, z,3)+x+(m-y)+z);
ans=min(ans,-que(n-x,m-y, z,4)+(n-x)+(m-y)+z);
ans=min(ans,-que( x, y,h-z,5)+x+y+(h-z));
ans=min(ans,-que(n-x, y,h-z,6)+(n-x)+y+(h-z));
ans=min(ans,-que( x,m-y,h-z,7)+x+(m-y)+(h-z));
ans=min(ans,-que(n-x,m-y,h-z,8)+(n-x)+(m-y)+(h-z));
printf("%d\n",ans);
}
}
return 0;
}
E
题目描述
有一些边，每个边限制人的高度范围，问从$1$走到$n$，有多少种身高能够走过去。
解题思路
线段树分治，把大小离散化后的区间当做“时间”，写一个可撤销并查集就可以了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
typedef long long ll;
using namespace std;
int n,u[N],v[N],lo[N],ro[N],b[N<<1];
int l[N],r[N];
int L[N<<2],R[N<<2];
vector<pii>P[N<<2];
int f[N];
void build(int p,int l,int r){
L[p]=l;R[p]=r;
if(l==r)return;
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
}
void modify(int p,int l,int r,pii pr){
if(L[p]>r||R[p]<l)return;
if(l<=L[p]&&R[p]<=r){
P[p].pb(pr);
return;
}
modify(p<<1,l,r,pr);
modify(p<<1|1,l,r,pr);
}
pii sta[N];
int top,rnk[N],drnk[N];
int find(int x){
return x==f[x]?f[x]:find(f[x]);
}
void unite(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy){
sta[top++]=mp(0,0);
return;
}
if(rnk[fx]<rnk[fy])f[fx]=fy,sta[top++]=mp(fx,fy);
else{
f[fy]=fx;
if(rnk[fy]==rnk[fx]){
rnk[fx]++;
drnk[top]=1;
}
sta[top++]=mp(fy,fx);
}
}
void deunite(){
int son=sta[top-1].fi,fa=sta[top-1].se;
if(drnk[top-1])rnk[fa]--;
f[son]=son;
top--;
}
int ans;
void dfs(int p){
for(auto pr:P[p])unite(pr.first,pr.second);
if(L[p]==R[p]){
if(find(1)==find(n))ans+=b[L[p]+1]-b[L[p]];
}else dfs(p<<1),dfs(p<<1|1);
for(auto pr:P[p])deunite();
}
int main(){
int i,m,tot=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)f[i]=i,rnk[i]=0;
for(i=0;i<m;i++){
scanf("%d%d%d%d",&u[i],&v[i],&lo[i],&ro[i]);
ro[i]++;//[l,r)
b[tot++]=lo[i];
b[tot++]=ro[i];
}
sort(b+1,b+tot);
tot=unique(b+1,b+tot)-b-1;
build(1,1,tot);
for(i=0;i<m;i++){//b[l[i]]=lo[i]
l[i]=lower_bound(b+1,b+tot,lo[i])-b;
r[i]=lower_bound(b+1,b+tot,ro[i])-b;
modify(1,l[i],r[i]-1,mp(u[i],v[i]));
}
dfs(1);
printf("%d",ans);
return 0;
}
F
题目描述
解题思路
AC代码
2
G
题目描述
给一个串，每次可以去掉三个相同的相邻字母，问最多能去多少次。
解题思路
签到。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
using namespace std;
char a[100010];
int p[100010];
int main(){
int i,now=0,ans=0;
scanf("%s",a);
for(i=0;a[i];i++){
p[now]=a[i];
if(now>=2&&p[now]==p[now-1]&&p[now-1]==p[now-2]){
ans++;
now-=3;
}
now++;
}
printf("%d",ans);
return 0;
}
H
题目描述
解题思路
AC代码
2
I
题目描述
解题思路
AC代码
2
J
题目描述
有一条长度为$l$的道路，从$0$走到$l-1$，每次走的步长为$\geq d$的任意正整数，有$m$次袭击，每次袭击有一个位置和时间，表示第$t_i$步不能到$p_i$这个位置，求从$0$ 走到$l-1$的总方案数。
解题思路
首先可以很容易递推求出，从$x$到$x+i$不考虑袭击有多少种走法。我们假设这个走法为$f_i$。
考虑容斥。总方案数为$f_l$，减去至少走到某一次袭击的方案数之和，加上两次的，减去三次……
把所有的袭击按时间或者坐标排一下序，显然可以得出，后面的袭击进行之后，前面的袭击不可能再遇到。有了这个性质就可以递推求解，设$g[i][0]$表示受到第$i$次袭击、总受袭击次数为偶数的方案数，$g[i][1]$表示总受袭击次数为奇数的方案数。递推即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef long long ll;
using namespace std;
const ll mod=998244353;
ll f[N],g[N][2],inv[N],fac[N],l,d,m,ans,s;
ll c(ll n,ll m){
if(n<m||m<0)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
struct Event{
int t,p;
bool operator<(const Event&q)const{return t<q.t;}
}e[M];
ll F(ll p,ll t){return c(p-t*d+t-1,t-1);}
int main(){
int i,j;
fac[0]=fac[1]=inv[0]=inv[1]=f[0]=1;
for(i=2;i<N;i++)fac[i]=fac[i-1]*i%mod,inv[i]=inv[mod%i]*(mod-mod/i)%mod;
for(i=2;i<N;i++)inv[i]=inv[i]*inv[i-1]%mod;
scanf("%lld%lld%lld",&l,&d,&m);
for(i=1;i<=l;i++){
if(i>=d)(s+=f[i-d])%=mod;
f[i]=s;
}
for(i=1;i<=m;i++)scanf("%d%d",&e[i].t,&e[i].p);
sort(e+1,e+m+1);
for(i=1;i<=m;i++){
if(l<e[i].p)continue;
g[i][1]=F(e[i].p,e[i].t);
for(j=1;j<i;j++){
if(e[j].p>=e[i].p)continue;
(g[i][0]+=g[j][1]*F(e[i].p-e[j].p,e[i].t-e[j].t))%=mod;
(g[i][1]+=g[j][0]*F(e[i].p-e[j].p,e[i].t-e[j].t))%=mod;
}
(ans+=mod-g[i][1]*f[l-e[i].p]%mod+g[i][0]*f[l-e[i].p]%mod)%=mod;
}
printf("%lld",(ans+f[l])%mod);
return 0;
}