2019牛客暑期多校训练营（第二场）题解

题目博主还没补完陆续更新中。

先是参考的大佬的题解：https://www.cnblogs.com/Dup4/p/11220210.html

D Kth Minimum Clique

题意：给出一个至多100个点的无向图，每个点有权值，问这幅图第k小的团的权值大小。

解法：考虑按权值暴力从小到大生成团，我们用优先队列生成，优先队列里用val记录团的大小用bitset像状压一样记录团的点集，然后优先队列把val小的出队，以出队的这个团拓展新的团。这里我们要考虑一个问题，因为如果不加限制，同一个团可能会被多个团拓展而来从而造成重复，所以我们要想办法避免重复，这里采用的办法是：只考虑加入比当前团所有点编号都要大的点，这样就能避免重复生成了。

#include<bits/stdc++.h>
using namespace std;
const int N=100+10;
typedef bitset<N> B;
typedef long long LL;
int n,k,v[N];
B G[N];
struct dat{
    LL val;
    B now;  //Bitset相当于状压记录当前团 
    bool operator < (const dat &rhs) const {
        return val>rhs.val;
    }
};
priority_queue<dat> q;

int main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) {
        int x; scanf("%1d",&x);
        G[i][j]=x;
    }
    
    q.push((dat){0,0});
    for (int i=1;i<k;i++) {
        if (q.empty()) return puts("-1"),0;
        dat x=q.top(); q.pop();
        int p=0;  //当前最右位置 
        for (int j=1;j<=n;j++) if (x.now[j]) p=j;
        for (int j=p+1;j<=n;j++) {  //下一个可能加入的数 
            if ((G[j]&x.now)!=x.now) continue;
            x.val+=v[j]; x.now[j]=1;
            q.push(x);
            x.val-=v[j]; x.now[j]=0;
        }    
    }
    cout<<q.top().val<<endl;
    return 0;
}

View Code

E MAZE

题意：

解法: 线段树维护矩阵乘法。相邻两行之间建一个矩阵mat[x][y]表示mp[i-1][x]是否能到达mp[i][y]，然后用线段树维护。修改操作就是单点修改，查询操作就是线段树第一个点的值。

一开始超时，去掉long long之后才能AC。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10;
const int P=1e9+7;
int n,m,q; char mp[N][12];

int mul(int t1,int t2) {
    LL ret=(LL)t1*t2; 
    return ret<P ? ret : ret%P;
}
int add(int t1,int t2) {
    int ret=t1+t2;
    return ret<P ? ret : ret-P;
}
struct matrix{
    int m[12][12];
    matrix() { memset(m,0,sizeof(m)); }
    friend matrix operator*(matrix a,matrix b) {
        matrix res;
        for (int i=1;i<=10;i++) for (int j=1;j<=10;j++) for (int k=1;k<=10;k++)
            res.m[i][j]=add(res.m[i][j],mul(a.m[i][k],b.m[k][j]));
        return res;    
    }
};
matrix tree[N<<2];

void upd(int rt,int l) {
    memset(tree[rt].m,0,sizeof(tree[rt].m));
    for (int i=1;i<=m;i++)
        if (mp[l][i]=='0') {
            for (int j=i;j;j--)
                if (mp[l-1][j]=='0') tree[rt].m[j][i]=1;
                else break;
            for (int j=i;j<=m;j++)
                if (mp[l-1][j]=='0') tree[rt].m[j][i]=1;
                else break;    
        }
}

void pushup(int rt) { tree[rt]=tree[rt<<1]*tree[rt<<1|1]; }

void build(int rt,int l,int r) {
    if (l==r) {
        upd(rt,l);
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

void update(int rt,int l,int r,int x) {
    if (l==r) {
        upd(rt,l);
        return;
    }
    int mid=l+r>>1;
    if (x<=mid) update(rt<<1,l,mid,x);
    if (x>mid) update(rt<<1|1,mid+1,r,x);
    pushup(rt);
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n;i++) scanf("%s",mp[i]+1);
    
    build(1,1,n+1);
    while (q--) {
        int opt,x,y; scanf("%d%d%d",&opt,&x,&y);
        if (opt==1) {
            if (mp[x][y]=='0') mp[x][y]=1;
            else mp[x][y]='0';
            update(1,1,n+1,x);
            update(1,1,n+1,x+1);
        } else {
            for (int i=1;i<=m;i++) mp[0][i]='1',mp[n+1][i]='1';
            mp[0][x]=mp[n+1][y]='0';
            update(1,1,n+1,1);
            update(1,1,n+1,n+1);
            int ans=0;
            for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) ans=(ans+tree[1].m[i][j])%P;
            printf("%d
",ans);
        }
    }
    return 0;
}

View Code

J Subarray

题意：

解法：