「2019计蒜之道」初赛第二场题解 2019-05-27

A. 百度AI小课堂-矩阵问题

\((i,j)\)这个位置的值为\(i+j-2\),把求矩阵转化一下改成求四个从(1,1)开始的矩阵。设当前矩阵的右下角为\((x,y)\)

对于第一行的和乘二是\((1+y)\times y\),第二行是\((3+y)\times y\)......。把y提出来就是\(y\times (\frac{(y+1+y+2x-1)x}{2})\)

发现又做复杂了。std做法比较妙。

把选中矩阵旋转180度和原来的加起来发现每个位置都等于\((a+b+c+d-2)\),乘上矩阵元素个数\((b-a+1)\times (c-d+1)\)就做完了。

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
int main(){
    ll a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    swap(c,b);int t=pls(c%mod,d%mod);t=pls(t,a%mod);t=pls(t,b%mod);t=dec(t,2);
    printf("%d\n",mul((d-b+1)%mod,(c-a+1)%mod,t));
    return 0;
}

B. 百度AI小课堂-上升子序列(简单)

由于方案是固定的。模拟就好了。

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=1e5+10;
int n;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("/home/noilinux/Desktop/input.txt","r",stdin);
#endif
    int T=gi();
    while(T--){
        n=gi();rep(i,1,n)a[i]=gi();
        static int s1[maxn],s2[maxn],top1,top2;
        bool GG=0;top1=top2=0;
        rep(j,1,n){
            if(!top1||a[j]>s1[top1])s1[++top1]=a[j];
            else if(!top2||a[j]>s2[top2])s2[++top2]=a[j];
            else { puts("-1");GG=1;break; }
        }
        if(GG)continue;
        else printf("%d\n",abs(top1-top2));     
    }
    return 0;
}

C. 百度AI小课堂-上升子序列(中等)

不妨设\(f[i][j]\)表示ai所在的那个序列长度为\(j\),另一个序列的最后一个元素的最小值。对于固定长度,一个串长度为\(j\),那么另一个串长度为\(i-j\),如果最后一个元素越小,显然是对后面的元素不劣的。

这个DP比较有意思。

转移: \[ \begin{aligned} \text{if a[i+1]>a[i]: }f_{i,j} &\to f_{i+1,j+1}\\ \text{if a[i+1]>f[i][j]: }f_{i,j} &\to f_{i+1,i-j+1} \end{aligned} \]

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=(1<<30)+1;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=1005;
int f[maxn][maxn],a[maxn];
int main(){
    #ifdef LOCAL
        freopen("/home/noilinux/Desktop/input.txt","r",stdin);
    #endif
    int T=gi();
    while(T--){
        int n=gi();rep(i,1,n)a[i]=gi();
        rep(i,1,n)rep(j,1,n)f[i][j]=INF;
        f[1][1]=-1;
        rep(i,1,n-1)rep(j,1,i)if(f[i][j]!=INF){
            if(a[i+1]>a[i])chkmin(f[i+1][j+1],f[i][j]);
            if(a[i+1]>f[i][j])chkmin(f[i+1][i-j+1],a[i]);
        }
        int ans=INF;
        rep(i,1,n)if(f[n][i]!=INF){
            ans=min(ans,abs(n-i-i));
        }
        cout<<(ans==INF?-1:ans)<<endl;
    }
    return 0;
}

D. 百度AI小课堂-上升子序列(困难)

比赛的时候完全不知道方案数和这个题有什么关系,就连算方案数都不会。后来发现真的很妙。

考虑一个暴力的思路。如果存在两个元素\(i,j\)满足\(i<j,a[i]\geq a[j]\),(我们称这样的对为逆序对),那么\((i,j\))显然不能放在同一个数组里,不满足则可以。我们把不满足条件的点对连边,形成若干个图。如果图不能二分图染色就说明答案是-1,否则对于这个联通图来说方案唯一。对于一个染色后的联通图,要么把一个颜色的放入a数组,要么放入b数组。而联通图和联通图之间是没有影响关系的,所以方案数是\(2^{\text{联通图个数}}\),由于方案数数小于\(1e18\),那么联通块最多有60个。

对于这60个联通图,可以跑一个背包。\(f[i][j]\)表示前i个联通图,是否能构成长度差为j的两个数组。复杂度\(O(\log 1e18 * n)\)

现在复杂度的瓶颈在于建图。

  • 性质:联通块对应的一定是数组上连续的一段

    证明:考虑反证。如果数轴上有三个位置\(i,j,k\),满足\(i,j,k,a[i]\geq a[k]\),如果满足\(a[j]\)不和\(i,k\)联通就说明结论不对。

    • \(a[j]\geq a[i]\),因为\(a[i]\geq a[k]\),所以\(a[j]\geq a[k]\),j和\(i,k\)联通。
    • \(a[j]\le a[i]\),那么\(i>j\)\(a[i]\geq a[j]\)\(j\)\(i,k\)联通。

那么说明联通块一定是连续的一段,现在考虑怎么划分。

  • 方法一:求出每个点\(i\)最远的逆序对\(\text{far[i]}\),如果能组成一段\([L,R]\)说明\(\max_{i=L}^{R}far[i]=R\)

  • 方法二:记录一个后缀\(\min\),对于一段\([L,R]\),如果\((\min_{i=R+1}^n a[i])>(\max_{i=L}^Ra[i])\),就说明\([L,R]\)不存在\([R+1,n]\)的逆序对,\([L,R]\)就是一个段。

至此问题解决,复杂度\(O(n\log K)\)\(K\)为划分方案数。

#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define repd(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
#define db double
#define mp make_pair
#define mp3(a,b,c) mp(mp(a,b),c)
#define pii pair<int,int>
#define piii pair<pii,int>
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pbc(x) __builtin_popcount(x)
#define clr(x) memset(x,0,sizeof x)
#define SIZE(x) (int)(x.size())
const int mod=1e9+7;
IL int pls(int x,int y){x+=y;return x>=mod?x-mod:x;}
IL int dec(int x,int y){x-=y;return x<0?x+mod:x;}
IL int mul(int x,int y){return 1ll*x*y%mod;}
IL int mul(int x,int y,int z){return mul(mul(x,y),z);}
IL int mul(int x,int y,int z,int p){return mul(mul(x,y),mul(z,p));}
IL void add(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
IL int fpw(int x,int y,int r=1){for(;y;y>>=1,x=mul(x,x))if(y&1)r=mul(r,x);return r;}
IL int inv(int x){return fpw(x,mod-2);}
IL int gi(){int x;int _w=scanf("%d",&x);return x;}
IL void gi(int &x){int _w=scanf("%d",&x);}
IL void write(int x){printf("%d\n",x);}
void chkmax(int &x,int y){x=(x>y)?x:y;}
void chkmin(int &x,int y){x=(x<y)?x:y;}
const int INF=0x3f3f3f3f;
template<typename T>IL void debug(T x){cerr<<x;return;}
/* --------------------------------------------------------------------------------------------------------- */
const int maxn=1e5+10;
int n;
int a[maxn],bel[maxn],Len[maxn],B[maxn];
int f[61][maxn];
int main(){
#ifdef LOCAL
    freopen("/home/noilinux/Desktop/input.txt","r",stdin);
#endif
    int T=gi();
    while(T--){
        n=gi();rep(i,1,n)a[i]=gi();
        int cnt=1;
        bel[1]=1;
        int mx=a[1];
        //define Mx Min
        static int Mx[maxn];
        rep(i,1,n)Mx[i]=a[i];
        repd(i,n-1,1)chkmin(Mx[i],Mx[i+1]);
        rep(i,2,n){
            if(Mx[i]>mx){mx=a[i];cnt++;}
            bel[i]=cnt;mx=max(mx,a[i]);
        }
        static int s1[maxn],s2[maxn],top1,top2;
        bool GG=0;
        int last=1;
        rep(tag,1,cnt){
            int num=0;
            top1=0,top2=0;
            int j;
            for(j=last;j<=n+1;++j){
                if(j==n+1||bel[j]!=tag)break;
                num++;
                if(!top1||a[j]>s1[top1])s1[++top1]=a[j];
                else if(!top2||a[j]>s2[top2])s2[++top2]=a[j];
                else { puts("-1");GG=1;break; }
            }last=j;
            if(GG)break;
            Len[tag]=num;
            B[tag]=top1;
        }
        if(GG){continue;}
        memset(f,0,sizeof f);
        f[0][0]=1;
        rep(i,1,cnt){
            int aa=B[i],bb=Len[i]-B[i];
            int dec=abs(aa-bb);
            rep(j,0,n)if(f[i-1][j]){
                f[i][j+dec]=1;
                f[i][abs(j-dec)]=1;
            }
        }
        rep(i,0,n)if(f[cnt][i]){
            printf("%d\n",i);
            break;
        }
        rep(i,1,cnt)B[i]=Len[i]=0;
        memset(bel,0,sizeof bel);
    }
    return 0;
}