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

传送门

B.Beauty Values （dp）

•题意

给你一个序列 a，求序列 a 的任意一个区间 [l,r] 中，元素不同的个数的加和；

•思路

定义 dp[ i ] 表示以 i 为结尾的所有区间所包含的元素不同的数的个数；

　　即 $dp[i]=sum_{j=1}^{j <= i}f{j,i}$，$f{j,i}$指的是[ j , i ]区间不同数的个数；

　　那么，对于 i 位置的数 a_i：

　　①i 位置为 a_i 首次出现的位置：

　　　　$dp[i]=dp[i-1]+i$;

　　为什么是+i?

　　因为在 [1,i] 比 [1,i-1] 多了个不同的数

　　同理 [2,i]，[3,i]....[i,i]一共多了i个

　　②[1,i-1] 中 a_i 出现的最晚的位置为 j：

　　　　$dp[i]=dp[i-1]+i-j$;

　　为什么-j?

　　比如x在 2,10，... j位置出现过

　　那既然j位置出现过也就是在 [j,i-1] 区间出现过，

　　必然在[j-1,i-1]，[j-2,i-1] ...   [1,i-1]位置出现过

也就是多算了j次，要 -j

•代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
int pos[maxn];
int a[maxn];
ll dp[maxn];
int main()
{
    int n;
    cin>>n;
    dp[1]=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>1)
            dp[i]=dp[i-1]+i-pos[a[i]];
        pos[a[i]]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=dp[i];
    cout<<ans<<endl;
}

C.CDMA（构造）

•题意

　　假设序列 s,t 都只含有 n 个元素；

　　定义 $scdot t=sum_{i=1}^{i<=n}s_icdot t_i$ ;

　　构造一个 m×m 的矩阵 a，其中 m = 2^k , 1 ≤k ≤ 10，使其满足：

　　①矩阵中只包含 -1,1；

　　②任意不同的两行 a[ i ],a[ j ]， a[ i ]·a[ j ] = 0；

•题解

　　根据 m = 2 , m = 4 的满足条件的矩阵找规律；

　　m = 2:

　　$left( egin{array}{cc} 1 & 1 \ 1 & -1 end{array} ight)$

　　m = 4:

　　$left( egin{array}{cccc} 1 & 1 & 1 & 1 \ 1 & -1 & 1 & -1 \ 1 & 1 & -1 & -1 \ 1 & -1 & -1 & 1 \ end{array} ight)$

　　m = 4 时，从行，列的中间分开，分成成 4 个 2×2 的子矩阵，你会发现，前三个子矩阵 = (m=2时的矩阵)；

　　最后一个子矩阵 = (m=2时的矩阵取反);

　　根据上述规律，可以求出 m = 8,16,....,1024 时的满足条件的矩阵；

•代码

#include<bits/stdc++.h>
using namespace std;
string base[2000];
int m;
void Slove()
{
    for(int k=2;k<=10;k++)
    {
        m=1<<k;
        for(int i=0;i<m/2;i++)
            base[i]+=base[i]; ///double
        for(int i=m/2;i<m;i++)
        {
            base[i]=base[i%(m/2)];

            for(int j=m/2;j<m;j++)
                 base[i][j]=(base[i][j]=='0'?'1':'0');
        }
    }
}
int main()
{
    int m;
    cin>>m;
    base[0]="11";
    base[1]="10";
    //0代表-1 便于用字符表示

    Slove();
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            printf("%d%c",base[i][j]=='0'?-1:1,j==m-1?'
':' ');
}

G.Gemstones（模拟）

•题意

　　给你一个只包含大写字母的串 s；

　　如果相邻的三个字符为相同的字母，那么，便可将这三个相同的字母消去；

　　求最多可以消去多少次；

•思路

用栈模拟

当栈中大于两个时，往里加入时判断是否构成相同三字符，

若能构成则消去，不能构成则继续加入

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
stack<char> sta;
char s[maxn];
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    bool flag;
    int ans=0;

    for(int i=1;i<=len;i++)
    {
        flag=true;
        while(flag)
        {
            flag=false;
            if(sta.size()>=2)
            {
                char a=sta.top();
                sta.pop();
                char b=sta.top();
                sta.pop();
                if(s[i]==a&&a==b)
                {
                    flag=true;
                    i++;
                    ans++;
                }
                else
                {
                    sta.push(b);
                    sta.push(a);

                }
            }
        }
        sta.push(s[i]);
    }

    printf("%d
",ans);
}