2019牛客暑期多校赛（第八场）

G题：https://ac.nowcoder.com/acm/contest/888/G

签到题目。

题意：给一串字符串如果有三个连续相同的字母就消掉，然后右边字符串补齐，求最简的字符串需要操作几次。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dir[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
#define inf 1e18
const int N=1e6+6;
inline int read() {
    char c=getchar(); int x=0, f=1;
    while(c<'0'|c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
ll exgcd(ll a,ll b){
    if(b==0) return a;
    exgcd(b,a%b);
}
ll q_pow(ll a,ll b,ll mod){
    ll anss=1;
    while(b){
        if(b&1) anss=anss*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return anss;
}
ll q_mul(ll a,ll b,ll mod){
    ll anss=0;
    while(b){
        if(b&1) anss=(anss+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return anss;
}
stack<char> ss;
int main(int argc, char * argv[]) 
{
    ios::sync_with_stdio(false);
    string s;
    int ans=0;
    cin>>s;
    ss.push(s[0]),ss.push(s[1]);
    for(int i=2;i<s.size();i++){
        if(!ss.empty()&&s[i]==ss.top()){
            ss.pop();
            if(!ss.empty()&&s[i]==ss.top()){
                ans++;
                ss.pop();
            }
            else{
                ss.push(s[i]);
                ss.push(s[i]);
            }
        }
        else ss.push(s[i]);
    }
    cout<<ans<<endl;
    return 0;
}

 

B题：https://ac.nowcoder.com/acm/contest/888/B

题意：给定一个长度为n的数组，问所有区间中出现数字种类的和是多少。

题解：期望线性

把每种数字对答案的贡献分开计算，枚举每个数字，求原序列有多少个子区间包含至少一个该数字，累加答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dir[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
#define inf 1e18
const int N=1e6+6;
inline int read() {
    char c=getchar(); int x=0, f=1;
    while(c<'0'|c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
ll exgcd(ll a,ll b){
    if(b==0) return a;
    exgcd(b,a%b);
}
ll q_pow(ll a,ll b,ll mod){
    ll anss=1;
    while(b){
        if(b&1) anss=anss*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return anss;
}
ll q_mul(ll a,ll b,ll mod){
    ll anss=0;
    while(b){
        if(b&1) anss=(anss+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return anss;
}
ll a[N],v[N];
int main(int argc, char * argv[]) 
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
    me0(v);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        if(v[a[i]]==0){
            ans=ans+n+(i-1)*(n-i);
        }
        else{
            ans=ans+(i-v[a[i]])*(n-i)+(i-v[a[i]]-1)+1;
        }
        v[a[i]]=i;
    }
    cout<<ans<<endl;
    return 0;
}

 对于核心代码的解释：

c题：https://ac.nowcoder.com/acm/contest/888/C

题意：构造矩阵，可以在上一个矩阵的基础上继续构造，构造出的1，-1矩阵为和为0。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dir[8][2]={{1,0},{0,1},{1,1},{1,-1},{-1,1},{-1,-1},{0,-1},{-1,0}};
#define pi acos(-1)
#define ls rt<<1
#define rs rt<<1|1
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memset(s,1,sizeof(s))
#define mef(s) memset(s,-1,sizeof(s))
#define meinf(s) memset(s,inf,sizeof(s))
#define inf 1e18
const int N=1e6+6;
inline int read() {
    char c=getchar(); int x=0, f=1;
    while(c<'0'|c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
ll exgcd(ll a,ll b){
    if(b==0) return a;
    exgcd(b,a%b);
}
ll q_pow(ll a,ll b){
    ll anss=1;
    while(b){
        if(b&1) anss=anss*a;
        a=a*a;
        b>>=1;
    }
    return anss;
}
ll q_mul(ll a,ll b,ll mod){
    ll anss=0;
    while(b){
        if(b&1) anss=(anss+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return anss;
}
int ans[10000][10000];
int main(int argc, char * argv[]) 
{
    ios::sync_with_stdio(false);
    int k;
    cin>>k;
    int n=1;
    while(n<=k){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==1&&j==1){
                    ans[i][j]=1;
                }
                else if(i>=1&&i<=n/2&&j>n/2&&j<=n){
                    ans[i][j]=ans[i][j%(n/2)==0?n/2:j%(n/2)];
                }
                else if(i>n/2&&j>n/2&&i<=n&&j<=n){
                    ans[i][j]=-ans[i][j%(n/2)==0?n/2:j%(n/2)];
                }
                else if(i>n/2&&i<=n&&j>=1&&j<=n/2){
                    ans[i][j]=ans[i%(n/2)==0?n/2:i%(n/2)][j];
                }
            }
        }
        n*=2;
    }
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            j==1?cout<<ans[i][j]:cout<<' '<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}