题目链接
2019牛客暑期多校训练营(第八场)
A
题目描述
给出一个大小为N*M的01矩阵，求出包含多少个由1组成的矩形，矩形唯一：即一个矩形不能被另一个矩形包含。
思路
用单调栈处理，栈中储存两个值，一个为该点能够向上延申的最大长度，一个是能够延申到最左边的位置。
向上延申的最大长度很明显能够使用前缀和来解决。
细节处理：
处理好前缀和后，从左上角遍历到右下角，当前位置能够向上延申的最大长度大于当前栈顶元素的最大长度时，就可以进栈。
然后，当栈顶元素能够向上延申的最大长度大于当前位置能够向上延申的最大长度时，这时候判断栈顶元素向左延申的位置是否小于等于下一行中右边0的位置
也就是防止出现
111
111
而计算了两行为两个矩阵的情况。
代码实现
1
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
| #include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
stack<pii>S;
char s[3005][3005];
int pre[3005][3005];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
pre[i][j]=s[i][j]=='1'?pre[i-1][j]+1:0;
int ans = 0;
for(int i=1;i<=n;i++)
{ int tmp = -1;
while(!S.empty())S.pop();
for(int j=1;j<=m+1;j++)
{
int pos = j;
while(!S.empty()&&S.top().first>pre[i][j])
{
if(S.top().second<=tmp)ans++;
pos = S.top().second;
S.pop();
}
if(!pre[i+1][j])tmp = j;
if(pre[i][j]&&(S.empty()||S.top().first<pre[i][j]))S.push({pre[i][j],pos});
}
}
return 0*printf("%d",ans);
}
|
C
题目描述
给出数字n，构造一个2^n*2^n的矩阵，使得每行相乘相加=0.
思路
容易求出2*2的矩阵A，接下来构造如下矩阵即可
代码实现
1
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
| #include<bits/stdc++.h>
using namespace std;
int a[1050][1050];
int main()
{
int n;
scanf("%d",&n);
a[1][1]=1;
a[1][2]=1;
a[2][1]=1;
a[2][2]=-1;
int now = 2;
while(now<n){
for(int i=1;i<=now;i++)
{
for(int j=1;j<=now;j++)
{
a[i][j+now]=a[i][j];
a[i+now][j]=a[i][j];
a[i+now][j+now]=-a[i][j];
}
}
now*=2;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j!=n)
{
printf("%d ",a[i][j]);
}
else printf("%d\n",a[i][j]);
}
}
return 0;
}
|
B
题目描述
定义一个序列美丽值为这个序列不同数字的个数。
给出一个长度为n的序列，求出这个序列所有连续子序列的美丽值的和。
思路
每个位置的贡献等于当前数与上一次这个数出现位置的差乘以后面的长度。
枚举位置然后计算答案就好了
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
long long ans;
int a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{ int x;
scanf("%d",&x);
ans+=1ll*(i-a[x])*(n-i+1);
a[x]=i;
}
printf("%lld\n",ans);
}
|
G
题目描述
类似于祖玛的游戏，给出一个序列，每三个相同的就消除，答案为消除的次数
思路
用栈来模拟一下就可以过了
代码实现
1
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
| #include<bits/stdc++.h>
using namespace std;
char st[100010];
string s;
int cnt[100010];
int main()
{
cin>>s;
int top = 0;
int temp = 0;
int ans = 0;
for(int i=0;i<s.size();i++)
{
if (st[top] == s[i])
{
cnt[top]++;
if (cnt[top] == 3)
{
temp++;
top--;
}
}
else
{
st[++top] = s[i];
cnt[top] = 1;
}
}
cout<<temp<<endl;
}
|