比赛地址

2019牛客暑期多校训练营（第八场）

[A]All-one Matrices

题意

给出一个01矩形，求其中全为1的矩形的数量，且该种矩形不能被更大的全1矩形包含。

题解

首先维护一个up[i][j]，记录每一个位置向上能延伸的1的数量。然后逐行枚举，再枚举每一列。维护一个关于up[i][j]的单调递增栈，对于每个高度，记录下向左可以延伸的最大距离pos。每当有元素出栈时，便检查一下(i-up+1,pos)-(i,j-1)是否符合题意。不难证明，这个全1矩形只有可能向下延伸。所以提前处理好每一行的前缀和判断一下就好了。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 3005
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,tot,Ans,pos;
char c[N];
int a[N][N],s[N][N],up[N][N],l[N][N];

struct Data{
    int x,l;
}z[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Ready(){
    int i=0,j=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            s[i][j]=s[i][j-1]+a[i][j];
    for (i=1;i<=n;i++)  
        for (j=1;j<=m;j++)
            if (a[i][j]){
                up[i][j]=up[i-1][j]+1;
                l[i][j]=l[i][j-1]+1;
            }
}

inline void Check(int x,int y,int p){
//  cout<<x<<" "<<y<<" "<<p<<endl;
    if (s[p][y]-s[p][x-1]!=(y-x+1)) Ans++;
}

inline void Work(){
    int i=0,j=0;
    for (i=1;i<=n;i++){
        memset(z,0,sizeof(z));  tot=0;      
        for (j=1;j<=m+1;j++){
            pos=j;
            if (up[i][j]==z[tot].l) continue;
            if (up[i][j]>z[tot].l)  z[++tot]=(Data){pos,up[i][j]};
            else {
                while (z[tot].l>up[i][j]&&tot){
                    Check(z[tot].x,j-1,i+1);
                    pos=z[tot].x;   tot--;
                }
                if (up[i][j]>z[tot].l)  z[++tot]=(Data){pos,up[i][j]};
            }
        }
    }
    printf("%d\n",Ans);
}

int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%s",&c);
        for (j=0;j<m;j++)   a[i][j+1]=c[j]-48;
    }
    Ready();    Work();
    return 0;
}

[B]Beauty Values

题意

给定一个数字序列，对于每一个子序列，定义其价值为其中含有的数字种类数。求该序列的所有子序列的价值总和。

题解

直接暴力计算每个数字的贡献即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int last[100005];
long long int tim = 0;

int main() {
    long long int n, ans = 0;
    cin >> n;
    long long int all = n*(n+1)/2;
    for (int i = 1; i <= n; i++) {
        int a; scanf("%d", &a);
        if (last[a] == 0) tim++;
        long long int k = i-last[a]-1;
        last[a] = i;
        ans -= k*(k+1)/2;
    }
    for (int i = 1; i <= n; i++) if (last[i]) {
        long long int k = n-last[i];
        ans -= k*(k+1)/2;
    }
    ans += tim * all;
    cout << ans << endl;
    return 0;
}

[C]CDMA

题意

给定一个2的次幂n，求n维空间中的一组正交基。要求每个向量只能含有0和1。

题解

若得到了n维空间的一组正交基A，则2n空间的正交基为

(^A_A,^A_{-A})

证明过程显然。

代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int map[1050][1050];

int main() {
    int now = 2;
    map[1][1] = 1;
    map[1][2] = 1;
    map[2][1] = 1;
    map[2][2] = -1;
    for (; now < 1024; now*=2) {
        for (int i = now+1; i <= now*2; i++)
            for (int j = 1; j <= now; j++) map[i][j] = map[i-now][j];
        for (int i = now+1; i <= now*2; i++)
            for (int j = 1; j <= now; j++) map[j][i] = map[j][i-now];
        for (int i = now+1; i <= now*2; i++)
            for (int j = now+1; j <= now*2; j++) map[i][j] = -1 * map[i-now][j-now];
    }
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) printf("%d ", map[i][j]);
        cout << endl;
    }
    return 0;
}

[G]Gemstones

题意

给定一个由小写字母组成的序列，每次可以消去相邻的三个相同的字母。求最多能消多少次。

题解

维护一个栈，每次检查栈首的三个元素能不能消去即可。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,len,i,Ans,cnt,top;
char c[N],z[N];

inline int Max(int a,int b){return (a>b)?a:b;}

inline bool Check(){
    int i=0;
    if (top<3)  return 0;
    if (z[top]==z[top-1]&&z[top]==z[top-2]){
        top-=3; Ans++;
        return 1;
    }
    return 0;
}

int main(){
    scanf("%s",&c);
    len=strlen(c);
    for (i=0;i<len;i++){
        z[++top]=c[i];
        while (Check());
    }
    cout<<Ans<<endl;
    return 0;
}

总结&吐槽

整场比赛发挥很不好，排名爆炸。主要原因是我在做G题的时候把数组第零位用来计数了，但是忘了数组是字符类型的。。。导致疯狂WA。总共做出来了三题，最后在A题上卡了很久。看出来思维能力还需要训练一下。比赛过程中的E题和I题我都口胡出了正确的做法，但是都因为在一个关键步骤卡住导致放弃。看来需要补一些知识点了。

这场比赛没有抱枕，还好，下一场牛客比赛争取吧。

话说目前为止每场比赛必有线段树，而且必做不出来QAQ