2017年多校联训9 部分题解

1002. Ch’s gift

首先考虑序列上的问题。

$a$ 是一个二维数组，如果第 $i$ 位置的值为 $j$，就在 $a_{i,j}$上加上 $j$ 。那么某个询问 $x,y,a,b$ 的答案就是子矩阵的和。如果一开始就把二维前缀和算出来的话就可以回答$O(1)$，答案等于 $(Sum(y,b)-Sum(y,a-1))-(Sum(x,b)-Sum(x,a-1))$ 。

考虑到 $a,b$ 的范围非常大，可以把所有询问离散化。当然就算离散化，预处理二维前缀和还是不行的，我们发现前缀和相当于把 $[a,b]$ 拆成 $[1,b]-[1,a-1]$，联想到扫描线，把 $a,b$ 这一维的每个区间拆成两条线，用扫描线从小到大扫这一维，$x,y$ 这一维直接预处理一下前缀和每次 $O(1)$ 查就行了。

再搬到树上，直接套一个树链剖分就行了，树状数组就能维护。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN=1e5+5;
struct Edge {
    int to,next;
} edge[MAXN*2];
int head[MAXN],tot;
int top[MAXN],fa[MAXN];//父亲节点
int deep[MAXN];//深度
int num[MAXN];//num[v] 表示以v为根的子树的节点数
int p[MAXN];//p[v]表示v对应的位置
int fp[MAXN];//fp和p数组相反
int son[MAXN];//重儿子
int pos;
int v[MAXN*3];

void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
    pos = 1;
    memset(son,sizeof(son));
}

void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u,int pre,int d)
{
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if(v != pre) {
            dfs1(v,u,d+1);
            num[u] += num[v];
            if(son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getpos(int u,int sp)
{
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if(son[u] == -1) return;
    getpos(son[u],sp);
    for(int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if( v != son[u] && v != fa[u])
            getpos(v,v);
    }
}

inline int lowbit(int x)
{
    return x&(-x);
}

ll c[MAXN];
ll sum(int i)
{
    ll s = 0;
    while(i > 0) {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

void add(int i,int val)
{
    while(i <MAXN) {
        c[i] += val;
        i += lowbit(i);
    }
}

ll query(int u,int v)
{
    int f1 = top[u],f2 = top[v];
    ll res=0;
    while(f1 != f2) {
        if(deep[f1] < deep[f2]) {
            swap(f1,f2);
            swap(u,v);
        }
        res+=sum(p[u])-sum(p[f1]-1);
        u = fa[f1];
        f1 = top[u];
    }
    if(deep[u] > deep[v]) swap(u,v);
    res+=sum(p[v])-sum(p[u]-1);
    return res;
}

struct Query {
    int u,v,val,zf,id;
    bool operator <(const Query &R) {
        return val<R.val;
    }
} q[MAXN*2];
int a[MAXN];
struct Node {
    int iv,id;
    bool operator <(const Node &R) {
        return iv<R.iv;
    }
} ia[MAXN];
ll ans[MAXN];

int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        init();
        int vtot=0;
        for (int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            v[++vtot]=a[i];
        }
        for (int i=1;i<n;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        dfs1(1,0,0);
        getpos(1,1);
        for (int i=1;i<=m;i++) {
            int s,t,b;
            scanf("%d%d%d%d",&s,&t,&a,&b);
            q[i+i-1]={s,a-1,i};
            q[i+i]={s,b,1,i};
            v[++vtot]=a-1;
            v[++vtot]=b;
        }
        m<<=1;
        sort(v+1,v+vtot+1);
        vtot=unique(v+1,v+vtot+1)-v-1;
        for (int i=1;i<=m;i++) {
            q[i].val=lower_bound(v+1,v+vtot+1,q[i].val)-v;
        }
        for (int i=1;i<=n;i++) {
            ia[i].iv=lower_bound(v+1,a[i])-v;
            ia[i].id=i;
        }
        sort(q+1,q+1+m);
        sort(ia+1,ia+n+1);
        memset(ans,sizeof(ans));
        int j=1;
        for (int i=1;i<=m;i++) {
            while (j<=n&&ia[j].iv<=q[i].val) {
                add(p[ia[j].id],a[ia[j].id]);
                ++j;
            }
            ans[q[i].id]+=q[i].zf*query(q[i].u,q[i].v);
        }
        m>>=1;
        for (int i=1;i<=m;i++) {
            printf("%lld%c",ans[i]," n"[i==m]);
        }
    }
    return 0;
}

ps: 可持久化线段树可以在线回答，等写出来了更新

1005. FFF at Valentine

强连通缩点加拓扑序判分叉，不多说了。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;//点数
const int MAXM = 50010;//边数
struct Edge {
    int fr,to,next;
} eg[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
int Index,top;
int scc;//强连通分量的个数
bool Instack[MAXN];
int T,n,m;
bool g[MAXN][MAXN];
int in[MAXN];
vector<int> G[MAXN];

void Tarjan(int u)
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = eg[i].next) {
        v = eg[i].to;
        if( !DFN[v] ) {
            Tarjan(v);
            if( Low[u] > Low[v] )Low[u] = Low[v];
        } else if(Instack[v] && Low[u] > DFN[v])
            Low[u] = DFN[v];
    }
    if(Low[u] == DFN[u]) {
        scc++;
        do {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
        } while( v != u);
    }
}

void solve(int N)
{
    memset(DFN,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    Index = scc = top = 0;
    for(int i = 1; i <= N; i++)
        if(!DFN[i])
            Tarjan(i);
}

void init()
{
    tot = 0;
    memset(head,sizeof(head));
}

bool bad()
{
    queue<int> Q;
    for (int i=1;i<=scc;i++) {
        if (!in[i]) {
            Q.push(i);
        }
    }
    while (!Q.empty()) {
        if (Q.size()>1) {
            return true;
        }
        int u=Q.front();
        Q.pop();
        for (int v:G[u]) {
            if (--in[v]==0) {
                Q.push(v);
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&m);
        init();
        for (int i=1;i<=m;i++) {
            int x,y;
            scanf("%d%d",&x,&y);
            eg[tot]={x,head[x]};
            head[x]=tot++;
        }
        solve(n);
        memset(g,sizeof(g));
        memset(in,sizeof(in));
        for (int i=1;i<=scc;i++) {
            G[i].clear();
        }
        for (int i=0;i<m;i++) {
            int x=Belong[eg[i].fr];
            int y=Belong[eg[i].to];
            if (x!=y) {
                if (!g[x][y]) {
                    g[x][y]=1;
                    G[x].push_back(y);
                    in[y]++;
                }
            }
        }
        if (bad()) {
            puts("Light my fire!");
        } else {
            puts("I love you my love and our love save us!");
        }
    }
    return 0;
}

1006. Senior Pan

这题主要是题意有点不清楚。。。大小为 $k$ 的端点集合，题目的意思是起点终点不能是同一个【不过也是有道理的。。。

拆点，加超级源超级汇，再跑一下dij 。这个限制可以每个点维护一下被谁松弛过，比如现在想用 $i$ 松弛 $j'$，如果 $j$ 松弛过 $i'$，直接不让松弛就行了。一个点被松弛的次数小于总点数，复杂度也就是多个 $logn$，具体表现可能比20次dij好一点吧。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int> PLI;
const int N=100010;
struct Edge {
    int go,next;
} eg[N*5];
int last[N<<1],tot;
ll d[N<<1];
int vis[N<<1],st[N];
set<int> re[N<<1];
int T,m,k,cas=0;

namespace fastIO {
    #define BUF_SIZE 100000
    //fread -> read
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1 = buf + BUF_SIZE,*pend = buf + BUF_SIZE;
        if(p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf,BUF_SIZE,stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == 'n' || ch == 'r' || ch == 't';
    }
    inline void read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror)
            return;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
    #undef BUF_SIZE
};

void dij(int S)
{
    priority_queue< PLI,vector<PLI>,greater<PLI> > q;
    memset(d,0x3f,sizeof(d));
    memset(vis,sizeof(vis));
    d[S]=0; q.push(PLI(d[S],S));
    while (!q.empty()){
        PLI tmp=q.top();
        q.pop();
        int u=tmp.second;
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=last[u];i!=-1;i=eg[i].next) {
            int &v=eg[i].go;
// printf("%d %dn",v);
            if (u<=n&&v>n&&st[v-n]) {
                if (re[u+n].find(v-n)!=re[u+n].end()) continue;
            }
            if (d[v]>d[u]+eg[i].val) {
                re[v].insert(u);
                d[v]=d[u]+eg[i].val;
                q.push(PLI(d[v],v));
            }
        }
    }
}

void addedge(int x,int y,int z)
{
    eg[tot]={y,z,last[x]};
    last[x]=tot++;
}

int main()
{
    fastIO::read(T);
    while (T--) {
        fastIO::read(n);
        fastIO::read(m);
        tot=0;
        memset(last,sizeof(last));
        for (int i=1;i<=m;i++) {
            int x,z;
            fastIO::read(x);
            fastIO::read(y);
            fastIO::read(z);
            addedge(x,n+y,z);
        }
        fastIO::read(k);
        memset(st,sizeof(st));
        int S=0,T=n+n+1;
        for (int i=1;i<=k;i++) {
            int x;
            fastIO::read(x);
            st[x]=1;
            addedge(S,x,0);
            addedge(n+x,T,0);
        }
        for (int i=1;i<=n;i++) {
            addedge(n+i,i,0);
        }
        for (int i=0;i<=n+n+1;i++) {
            re[i].clear();
        }
        dij(S);
        printf("Case #%d: %lldn",++cas,d[T]);
    }
    return 0;
}

1008. Numbers

从小到大取，$O(n^2logm)$，$n$ 是 $sqrt{m}$ 级别。

#include <bits/stdc++.h>
using namespace std;

const int M=125260;
int a[M];
multiset<int> ss;

namespace fastIO {
    #define BUF_SIZE 100000
    //fread -> read
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE],stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == 'n' || ch == 'r' || ch == 't';
    }
    inline void read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror)
            return;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
    #undef BUF_SIZE
};

int main()
{
    int m,x;
    while (fastIO::read(m),!fastIO::IOerror) {
        for (int i=1;i<=m;i++) {
            fastIO::read(x);
            ss.insert(x);
        }
        int n=0;
        a[++n]=*ss.begin();
        ss.erase(ss.begin());
        while (!ss.empty()) {
            a[++n]=*ss.begin();
            ss.erase(ss.begin());
            for (int i=1;i<n;i++) {
                ss.erase(ss.find(a[i]+a[n]));
            }
        }
        printf("%dn",n);
        for (int i=1;i<=n;i++) {
            printf("%d%c",a[i]," n"[i==n]);
        }
    }
    return 0;
}

1010. Two strings

主要还是题意比较坑。。。匹配.*是要把.先变成某个字符再处理*。。。

队友(wenwenla)写了一种dp，先预处理pattern，dp[i]保存pattern前i个字符为止可以匹配到text的最左和最右，可以证明这个界里面的每一个都是可取的。

具体实现加一维表示最左最右，然后发现第一维可以去掉。

#include <bits/stdc++.h>
using namespace std;

const int N=2510,INF=1<<30;
char a[N],b[N];
int dp[2];
bool mul[N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%s",a+1);
        scanf("%s",b+1);
        int la=strlen(a+1);
        int lb=strlen(b+1);
        int j=0;
        memset(mul,sizeof(mul));
        for (int i=1;i<=lb;i++) {
            if (b[i]=='*') {
                mul[j]=1;
            } else {
                b[++j]=b[i];
            }
        }
        lb=j;
        int flag=0;
        dp[0]=dp[1]=0;
        for (int i=1;i<=lb;i++) {
            if (mul[i]) {
                int p=dp[1];
                if (p<la&&(b[i]=='.'||b[i]==a[p+1])) {
                    ++p;
                    while (p<la&&a[p+1]==a[p]) p++;
                }
                dp[1]=p;
            } else {
                int ll=INF,rr=-INF;
                for (int j=dp[0]+1;j<=dp[1]+1;j++) {
                    if (j>la) break;
                    if (b[i]=='.'||b[i]==a[j]) {
                        ll=min(ll,j);
                        rr=max(rr,j);
                    }
                }
                if (ll==INF) {
                    flag=1;
                    break;
                }
                dp[0]=ll;dp[1]=rr;
            }
        }
        if (flag||dp[1]!=la) {
            puts("no");
        } else {
            puts("yes");
        }
    }
    return 0;
}

时间0ms，就是容易写错。。。比赛的时候前面WA的都交上去了，最后一次AC的代码却没交上去[cry]。。。而且我们亲眼看到点了submit以后页面跳转了。。。结果连提交记录都没有？？

后来有人说了才发现这样直接正则就能过，这题出得真好？？

#include <bits/stdc++.h>
using namespace std;

const char sp[]="(q*|w*|e*|r*|t*|y*|u*|i*|o*|p*|a*|s*|d*|f*|g*|h*|j*|k*|l*|z*|x*|c*|v*|b*|n*|m*)";

int main() {
    int T;
    scanf("%d",&T);
    scanf("n");
    while(T--) {
        string a,c;
        getline(cin,a);
        getline(cin,b);
        for (int i=0;i<b.length();i++) {
            if (i<b.length()-1&&b[i]=='.'&&b[i+1]=='*') {
                c+=sp;i++;
            } else {
                c+=b[i];
            }
        }
        auto re = regex(c);
        if(regex_match(a,re)) {
            puts("yes");
        } else {
            puts("no");
        }
    }
    return 0;
}