20180213小测

20180213小测

上了几天课后，我么迎来了秦神的考试……

上次秦神出题T1T3集体爆零的心里阴影还没有褪去QAQ……

T1:

说白了就是让你在原串中选出一些子串使之价值和最大，已经被删去的子串使得区间两端合并。

首先注意这题是子串而不是子序列。考试的时候我当子序列做了半天，什么贪心、DP、网络流全都试了一遍，发现根本不可做，连爆搜都不会写……

然而看到这题这样就肯定是区间DP了，因为我们选择的是一个子串，所以对于一个我们要选出的串，他要么在原串中连续出现，要么在原串中分开出现且间隔部分可以全部被选出。

所以我们令f[i][j][p][k]表示原串区间[i,j]，匹配目标串p，第i位匹配第1位，第j维匹配第k位，dp[i][j]表示原串[i,j]能否被完全选出(先别管我为什么这么定义，一会看转移就明白了QAQ)。

我们考虑串p的位置k-1匹配的位置。我们在区间[I,j)枚举l，表示第k-1位匹配的位置。

若l==k-1，则中间没有间隔串，f[i][j][p][k]从f[i][l][p][k-1]转移。

若l!=k-1，说明中间间隔了一些部分且他们必须完全消去，所以我们让f[i][j][p][k]从f[i][l][p][k-1]&&dp[l+1][j]转移。

对于dp数组，一个能完全选出的区间要么由两边两个能完全选出的区间组成，要么恰好完美匹配某个目标串，我们枚举一下分割位置或者匹配的目标串即可。

复杂度？f的转移把[p][k]摊还下来是O(n^4)的，且为区间DP，有一个最大1/8的常数。dp的转移只用枚举中间位置或匹配串，复杂度O(n^3)。实测跑得飞快。

然而这题限制64mb内存，你直接开会MLE。用vector进行动态resize依旧会MLE(亲测还会TLE)。你需要开出f[i][j][p]的指针，最后一维k用C++的new分配内存就好了。

关于答案统计，我们可以看做在区间内选择几条有权值且不相同的线段覆盖，做线段覆盖就好了。

代码:

#include<cstdio>
#include<cstring>
#include<vector>
#define bool unsigned char
const int maxn=1e2+1e1,maxl=1.5e2+1e1;

char in[maxl],tar[maxn][maxl];
int val[maxn],sum[maxl],lt[maxn],g[maxl]; 
bool* f[maxl][maxl][maxn];
bool dp[maxl][maxl];
int n,li;

inline void getans() {
    for(int len=1;len<=li;len++)
        for(int st=1;st+len-1<=li;st++) {
            const int ed = st + len - 1;
            for(int p=1;p<=n;p++) { // p is the pairing string .
                for(int k=1;k<=lt[p]&&k<=len;k++) {
                    if( in[ed] != tar[p][k] ) continue;
                    if( k == 1 ) {
                        if( st == ed ) f[st][ed][p][k] = 1;
                        else f[st][ed][p][k] = dp[st][ed-1];
                        continue;
                    }
                    for(int l=st;l<ed;l++) {
                        if( l == ed - 1 ) f[st][ed][p][k] |= f[st][l][p][k-1];
                        else f[st][ed][p][k] |= f[st][l][p][k-1] && dp[l+1][ed-1];
                    }
                }
            }
            for(int mid=st;mid<ed;mid++)
                dp[st][ed] |= ( dp[st][mid] && dp[mid+1][ed] );
            for(int p=1;p<=n;p++)
                dp[st][ed] |= f[st][ed][p][lt[p]];
        }
    for(int i=0;i<=li;i++) { // g[i] is proccessed
        if( i ) g[i] = std::max( g[i] , g[i-1] );
        for(int ed=i+1;ed<=li;ed++)
            if( dp[i+1][ed] ) g[ed] = std::max( g[ed] , g[i] + sum[ed] - sum[i] );
    }
}
inline void readin() {
    static int k,p;
    static char s[maxl];
    scanf("%d",&k);
    while( k-- ) {
        scanf("%s%d",s,&p);
        val[(int)*s-'a'] = p;
    }
    scanf("%s",in+1) , li = strlen(in+1);
    for(int i=1;i<=li;i++) sum[i] = sum[i-1] + val[(int)in[i]-'a'];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%s",tar[i]+1);
        lt[i] = strlen(tar[i]+1);
        for(int j=1;j<=li;j++)
            for(int k=1;k<=li;k++) {
                f[j][k][i] = new bool [lt[i]+1];
                for(int p=0;p<=lt[i];p++)
                    f[j][k][i][p] = 0;
            }
    }
}

int main() {
    readin();
    getans();
    printf("%d
",g[li]);
    return 0;
}

T2:

关于题意:如果若干个点全都距离很近能相互到达，使得能到达每家店的数量大于等于k，则全部关门。

我们把距离转成切比雪夫距离，那么一家店能到达的店在一个矩形内。我们只用统计出一家店能被多少家到达，就可以知道他是否需要关门。

二维数据结构随便做啊，然而64mb内存卡树套树，懒得调扫描线或分治。考虑n只有10w，分块的数据范围，所以好写好调的kdtree随便过啊。

我们对于每个节点记录这个节点被完整覆盖了多少遍，最后再把树dfs一遍好了。统计答案的时候别忘了减去自身对自身的贡献。

码了十几分钟考场一发AC，话说这题为什么就我一个拿分的？别人都写跪了？

代码:

#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lli long long int
#define debug cout
using namespace std;
const int maxn=1e5+1e2;

int cmp;
struct Point {
    int d[2],id; // 0 means x , 1 means y .
    friend bool operator < (const Point &a,const Point &b) {
        return a.d[cmp] < b.d[cmp];
    }
}ps[maxn],nv[maxn];
int lson[maxn],rson[maxn],mx[maxn][2],mi[maxn][2],lazy[maxn],cnt;
int inx[maxn],iny[maxn],ind[maxn],ans[maxn];

inline void fill(int pos,const Point &p) {
    nv[pos] = p;
    for(int i=0;i<2;i++)
        mx[pos][i] = mi[pos][i] = p.d[i];
}
inline void update(int fa,int son) {
    if( !son ) return;
    for(int i=0;i<2;i++)
        mx[fa][i] = max( mx[fa][i] , mx[son][i] ) ,
        mi[fa][i] = min( mi[fa][i] , mi[son][i] );
}
inline void build(int pos,int dir,int l,int r) {
    const int mid = ( l + r ) >> 1;
    cmp = dir;
    nth_element(ps+l,ps+mid,ps+r+1);
    fill(pos,ps[mid]);
    if( l < mid ) build(lson[pos]=++cnt,dir^1,l,mid-1);
    if( mid < r ) build(rson[pos]=++cnt,dir^1,mid+1,r);
    update(pos,lson[pos]) , update(pos,rson[pos]);
}
inline bool insqr(int p,int sx,int tx,int sy,int ty) {
    return sx <= mi[p][0] && mx[p][0] <= tx
        && sy <= mi[p][1] && mx[p][1] <= ty;
}
inline bool insqr(const Point &p,int sx,int tx,int sy,int ty) {
    return sx <= p.d[0] && p.d[0] <= tx
        && sy <= p.d[1] && p.d[1] <= ty;
}
inline bool outsqr(int p,int sx,int tx,int sy,int ty) {
    return mx[p][0] < sx || tx < mi[p][0]
        || mx[p][1] < sy || ty < mi[p][1];
}
inline void update(int pos,int sx,int tx,int sy,int ty) {
    if( !pos || outsqr(pos,sx,tx,sy,ty) ) return;
    if( insqr(pos,sx,tx,sy,ty) ) {
        ++lazy[pos];
        return;
    }
    if( insqr(nv[pos],sx,tx,sy,ty) ) ans[nv[pos].id]++;
    update(lson[pos],sx,tx,sy,ty) , update(rson[pos],sx,tx,sy,ty);
}
inline void dfs(int pos) {
    ans[nv[pos].id] += lazy[pos];
    if( lson[pos] ) lazy[lson[pos]] += lazy[pos] , dfs(lson[pos]);
    if( rson[pos] ) lazy[rson[pos]] += lazy[pos] , dfs(rson[pos]);
}

int main() {
    static int n,k,cn;
    scanf("%d%d",&n,&k);
    for(int i=1,x,y;i<=n;i++) {
        scanf("%d%d%d",&x,&y,ind+i);
        inx[i] = x + y , iny[i] = x - y;
        ps[i] = (Point){ { inx[i] , iny[i] } , i };
    }
    build(cnt=1,0,1,n);
    for(int i=1;i<=n;i++) {
        update(1,
        max((lli)inx[i]-ind[i],-2147483648ll),
        min((lli)inx[i]+ind[i],2147483647ll),
        max((lli)iny[i]-ind[i],-2147483648ll),
        min((lli)iny[i]+ind[i],2147483647ll));
    }
    dfs(1);
    for(int i=1;i<=n;i++) cn += ( ans[i] > k );
    printf("%d
",cn);
    for(int i=1;i<=n;i++) if( ans[i] > k ) printf("%d ",i);
    puts("");
    return 0;
}

T3:

不能相互到达？不就是最大独立集？点数减最大匹配就好了。

等等，一般图最大匹配？这不是经典的NP问题吗？这题能做？

发现按照行列分组后这是一个二分图，然后就拿到了48分……

这个思路为什么有问题呢？因为一旦n为奇数的话，这图存在奇环，就不是二分图了……

根据鸽笼原理，一定有一行点数<=10，我们暴力枚举这一行状态，剩下的就是二分图了。

说着简单写着难系列。

考场48分代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define debug cout
using namespace std;
const int maxn=2e2+1e1,maxm=maxn*maxn,maxe=55;
const int inf=0x3f3f3f3f;

int k[maxe],sum[maxn],n,full;
int st,ed;

struct Elevator {
    int h,x,y;
    friend bool operator < (const Elevator &a,const Elevator &b) {
        if( a.h != b.h ) return a.h < b.h;
        if( a.x != b.x ) return a.x < b.x;
        return a.y < b.y;
    }
    friend bool operator == (const Elevator &a,const Elevator &b) {
        return a.h == b.h && a.x == b.x && a.y == b.y;
    }
};
vector<Elevator> v;

namespace Flow {
    int s[maxn],t[maxm<<1],nxt[maxm<<1],f[maxm<<1],dep[maxn];
    
    inline void coredge(int from,int to,int flow) {
        static int cnt = 1;
        t[++cnt] = to , f[cnt] = flow ,
        nxt[cnt] = s[from] , s[from] = cnt;
    }
    inline void singledge(int from,int to,int flow) {
        coredge(from,to,flow) , coredge(to,from,0);
    }
    inline bool bfs() {
        memset(dep,-1,sizeof(dep)) , dep[st] = 0;
        queue<int> q; q.push(st);
        while( q.size() ) {
            const int pos = q.front(); q.pop();
            for(int at=s[pos];at;at=nxt[at]) {
                if( f[at] && !~dep[t[at]] ) dep[t[at]] = dep[pos] + 1 , q.push(t[at]);
            }
        }
        return ~dep[ed];
    }
    inline int dfs(int pos,int flow) {
        if( pos == ed ) return flow;
        int ret = 0 , now = 0;
        for(int at=s[pos];at;at=nxt[at])
            if( f[at] && dep[t[at]] > dep[pos] ) {
                now = dfs(t[at],min(flow,f[at]));
                ret += now , flow -= now ,
                f[at] -= now , f[at^1] += now;
                if( !flow ) return ret;
            }
        if( !ret ) dep[pos] = -1;
        return ret;
    }
    inline int dinic() {
        int ret = 0 , now = 0;
        while( bfs() ) {
            while( ( now = dfs(st,inf) ) ) ret += now;
        }
        return ret;
    }
}

inline int covdep(int dep,int pos) {
    return sum[dep-1] + pos;
}
inline int cov(int id,int tpe) { // tpe == 0 means out point , 1 means in point
    return id * 2 + tpe - 1;
}

inline void pre() {
    sort(v.begin(),v.end());
    unsigned len = unique(v.begin(),v.end()) - v.begin();
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + k[i];
    full = sum[n] , st = full * 2 + 1 , ed = full * 2 + 2;
    for(unsigned i=0;i<len;i++) {
        const int x = covdep(v[i].h,v[i].x);
        const int y = covdep(v[i].h!=n?v[i].h+1:1,v[i].y);
        if( v[i].h & 1 ) {
            Flow::singledge(cov(x,1),cov(y,0),1);
        } else {
            Flow::singledge(cov(y,1),cov(x,0),1);
        }
    }
    for(int i=1;i<=full;i++)
        Flow::singledge(cov(i,0),cov(i,1),1);
    for(int i=1;i<=n;i++)
        if( i & 1 ) {
            for(int j=1;j<=k[i];j++)
                Flow::singledge( st , cov(sum[i-1]+j,0) , 1 );
        } else {
            for(int j=1;j<=k[i];j++)
                Flow::singledge( cov(sum[i-1]+j,1) , ed , 1 );
        }
}

int main() {
    static int h,x,y,ans;
    scanf("%d",&n);
    int t = 0;
    while( scanf("%d%d%d",&x,&y,&h) == 3 ) {
        v.push_back((Elevator){h,x,y});
        k[h] = max( k[h] , x ) , k[h!=n?h+1:1] = max( k[h!=n?h+1:1] , y );
        ++t;
    }
    pre();
    ans = full - Flow::dinic();
    printf("%d
",ans);
    return 0;
}

考后AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define debug cout
using namespace std;
const int maxn=2e2+1e1,maxm=4e4+1e2,maxe=55;
const int inf=0x3f3f3f3f;

int k[maxe],sum[maxn],n,full,mip,ans;
int st,ed,len;
bool vis[maxn];

struct Elevator {
    int h,x,y;
    friend bool operator < (const Elevator &a,const Elevator &b) {
        if( a.h != b.h ) return a.h < b.h;
        if( a.x != b.x ) return a.x < b.x;
        return a.y < b.y;
    }
    friend bool operator == (const Elevator &a,const Elevator &b) {
        return a.h == b.h && a.x == b.x && a.y == b.y;
    }
};
vector<Elevator> v;

namespace Flow {
    int s[maxn],t[maxm<<1],nxt[maxm<<1],f[maxm<<1],dep[maxn],cnt=1;
    
    inline void coredge(int from,int to,int flow) {
        t[++cnt] = to , f[cnt] = flow ,
        nxt[cnt] = s[from] , s[from] = cnt;
    }
    inline void singledge(int from,int to,int flow) {
        coredge(from,to,flow) , coredge(to,from,0);
    }
    inline bool bfs() {
        memset(dep,-1,sizeof(dep)) , dep[st] = 0;
        queue<int> q; q.push(st);
        while( q.size() ) {
            const int pos = q.front(); q.pop();
            for(int at=s[pos];at;at=nxt[at]) {
                if( f[at] && !~dep[t[at]] ) dep[t[at]] = dep[pos] + 1 , q.push(t[at]);
            }
        }
        return ~dep[ed];
    }
    inline int dfs(int pos,int flow) {
        if( pos == ed ) return flow;
        int ret = 0 , now = 0;
        for(int at=s[pos];at;at=nxt[at])
            if( f[at] && dep[t[at]] > dep[pos] ) {
                now = dfs(t[at],min(flow,f[at]));
                ret += now , flow -= now ,
                f[at] -= now , f[at^1] += now;
                if( !flow ) return ret;
            }
        if( !ret ) dep[pos] = -1;
        return ret;
    }
    inline int dinic() {
        int ret = 0 , now = 0;
        while( bfs() )
            while( ( now = dfs(st,inf) ) ) ret += now;
        return ret;
    }
    inline void reset() {
        memset(s,0,sizeof(s)) , cnt = 1;
    }
}

inline int countbit(int x) {
    #define lowbit(x) (x&-x)
    int ret = 0;
    while( x ) ++ret , x -= lowbit(x);
    return ret;
}
inline int covdep(int dep,int pos) {
    return sum[dep-1] + pos;
}

inline int rebuild(int sta) {
    Flow::reset() , memset(vis,0,sizeof(vis));
    int ret = 0;
    for(int i=0;i<k[mip];i++) if( ! ( sta & ( 1 << i ) ) ) vis[covdep(mip,i+1)] = 1;
    for(int i=0;i<len;i++) {
        const int h = v[i].h , th = h != n ? h + 1 : 1;
        if( h == mip) {
            if( ( 1 << ( v[i].x - 1 ) ) & sta ) vis[covdep(th,v[i].y)] = 1;
        }
        else if( th == mip ) {
            if( ( 1 << ( v[i].y - 1 ) ) & sta ) vis[covdep(h,v[i].x)] = 1;
        }else {
            if( ( h > mip && ( ( h - mip ) & 1 ) ) || ( h < mip && ! ( ( mip - h ) & 1 ) ) )
                Flow::singledge(covdep(h,v[i].x),covdep(th,v[i].y),1);
            else Flow::singledge(covdep(th,v[i].y),covdep(h,v[i].x),1);
        }
    }
    for(int i=1;i<=n;i++) {
        if( ( i > mip && ( ( i - mip ) & 1 ) ) || ( i < mip && !( ( mip - i ) & 1 ) ) ) {
            for(int j=1;j<=k[i];j++)
                if( !vis[covdep(i,j)] ) Flow::singledge(st,covdep(i,j),1);
        } else if( i != mip ) {
            for(int j=1;j<=k[i];j++)
                if( !vis[covdep(i,j)] ) Flow::singledge(covdep(i,j),ed,1);
        }
    }
    for(int i=1;i<=full;i++) ret += !vis[i];
    ret -= Flow::dinic();
    return ret;
}
inline void getansodd() {
    int fs = ( 1 << k[mip] );
    for(int i=0;i<fs;i++) ans = max( ans , rebuild(i) );
}
inline void getanseven() {
    for(int i=0;i<len;i++) {
        const int x = covdep(v[i].h,v[i].x);
        const int y = covdep(v[i].h!=n?v[i].h+1:1,v[i].y);
        if( v[i].h & 1 ) Flow::singledge(x,y,1);
        else Flow::singledge(y,x,1);
    }
    for(int i=1;i<=n;i++) {
        if( i & 1 ) {
            for(int j=1;j<=k[i];j++)
                Flow::singledge( st , covdep(i,j) , 1 );
        } else {
            for(int j=1;j<=k[i];j++)
                Flow::singledge( covdep(i,j) , ed , 1 );
        }
    }
    ans = full - Flow::dinic();
}

inline void pre() {
    sort(v.begin(),v.end());
    len = unique(v.begin(),v.end()) - v.begin();
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + k[i];
    full = sum[n] , st = full + 1 , ed = full + 2;
    *k = inf;
    for(int i=1;i<=n;i++) if( k[i] < k[mip] ) mip = i;
}

int main() {
    static int h,x,y;
    scanf("%d",&n);
    int t = 0;
    while( scanf("%d%d%d",&x,&y,&h) == 3 ) {
        v.push_back((Elevator){h,x,y});
        k[h] = max( k[h] , x ) , k[h!=n?h+1:1] = max( k[h!=n?h+1:1] , y );
        ++t;
    }
    pre();
    if( n & 1 ) getansodd();
    else getanseven();
    printf("%d
",ans);
    return 0;
}

话说在从老家回来汽车上写这东西真是晃死我了……