/ ALGORITHM

四川省第七届大学生程序设计竞赛

Contest Information

source: It’s from the Vjudge

Problem C

给出一个禁止串和一个原串,要求从原串中不断删除禁止串,然后输出删除后的新串。

数据范围:$ length ≤ 5\times 10^{6}$

Solution

先求出禁止串的 $next$ 数组,然后在 $KMP$ 的匹配过程中,同时开一个答案串同步存储,开一个数组保存答案串和禁止串的匹配情况,并且维护它俩的长度。如果某次匹配到了禁止串末尾,那么回退禁止串长度,同时更新当前匹配位置。

AC code

char no[MaxN];
char str[MaxN];
int Next[MaxN];
void makeNext(const char *P,int *next)
{
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}
int match[MaxN],top;
char ans[MaxN];
void kmp(const char *T,const char *P,int *next)
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    top = 0;
    for (i = 0,q = 0; i < n; ++i)
    {
        ans[top] = T[i];
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;  
        }
        match[++top] = q;
        if (q == m)
        {
            top -= m;
            if(top==0) q = 0;
            else q = match[top];
        }
    }
    ans[top] = '\0';
}

void solve()
{
    kmp(str,no,Next);
    printf("%s\n", ans);
}

int main()
{
    while(~scanf("%s%s", no, str))
    {
        solve();
    }
}

Problem D

给出一个 $n$ 个点,$m$ 条边的无向图,求最小点覆盖

数据范围:$ 1 ≤ n ≤ 500, 1 ≤ m ≤ \frac{n(n-1)}{2}, min(u,v) ≤ 30 $

Solution

无向图的最小点覆盖本是NPC问题,但是本题中因为 $min(u,v) ≤ 30 $ ,所以图中的每条边都和 $30$ 以内的点相连,那么我们只需要枚举这些点的染色状态就能求出覆盖所有边的最小点集了。

从第一个点开始 $DFS$ :如果当前点被染色过,那么和它相连的边必然被覆盖,走下一个点;如果未被染色,我们枚举将它染色和不将它染色(需要将和它相邻的点都染色以确保覆盖掉它的边)两种情况,再走下一个点。每次回溯时记得恢复现场,使用最优化剪枝可以快速求解。

AC code

int N, M;
struct Edge
{
    int u,v,next;
}edge[MaxM];
int cont;
int head[MaxN];
void add(int u, int v)
{
    edge[cont].u = u;
    edge[cont].v = v;
    edge[cont].next = head[u];
    head[u] = cont++;
}
int vis[MaxN];
int ans,tot;
void DFS(int u, int sum)
{
    if(sum>ans) return;
    if(u>tot)
    {
        ans = sum;
        return;
    }
    if(vis[u]) DFS(u+1, sum);
    else
    {
        vis[u]++;
        DFS(u+1,sum+1);
        vis[u]--;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            if(!vis[v]) sum++;
            vis[v]++;
        }
        DFS(u+1,sum);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {           
            int v = edge[i].v;
            vis[v]--;
            if(vis[v]==0) sum--;
        }
    }
}
int solve()
{
    ans = INF;
    tot = min(N,30);
    CLR(vis);
    DFS(1,0);
    printf("%d\n", ans);
}
void init()
{
    cont = 0;
    MST(head,-1);
}
int main()
{
    while(~scanf("%d%d", &N, &M))
    {
        init();
        for(int i=0;i<M;i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a,b);add(b,a);
        }
        solve();
    }
}

Problem F

给出一串项链,上面有 $n$ 个珠子,每个珠子有其价值 $a_{1…n}$,要求删除一些珠子使得其满足:

  1. 整串项链只有一个价值为 $10000$ 的珠子,称为完美珠子。

  2. 完美珠子的后面开始是一串价值组成不上升序列的珠子

  3. 完美珠子的前面开始是一串价值组成不下降序列的珠子

要求求出满足要求的项链的最大价值和

数据范围:$ 1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^4, 1 ≤ num_{10000} ≤ 10$

Solution

首先枚举完美珠子的位置,那么问题就转化为在这个位置后求一个不上升子序列与一个不下降子序列使得它们的和最大。

我们可以先分别求出在完美珠子之后每一个位置的和最大的非降子序列和非升子序列,然后枚举连接点就可以求出答案。 而求一个和最大的非升(降)子序列,我们可以类比 $LDS$ 的做法:它是对于每一个位置找到在它之前第一个大于它的位置以保证长度最大。 那么求和最大的非升子序列,我们就可以对于每一个位置找到在它之前的大于等于它的和最大的位置。

那么问题又转换为:怎么快速 $(O(logn))$ 找到在某一个位置之前的大于等于它的和最大的位置?

我们可以使用树状数组来维护:

  • 树状数组的下标 $1…i$ 对应原序列中的值域 $[0, max(a_{1..n})]$。不过是最大值 $max(a_{1..n})$ 对应前面的下标,最小值 $min(a_{1..n})$ 对应后面的下标:因为树状数组是后面的节点保存前面的节点的信息,而我们每次需要查询值大于等于当前 $a_i$ 的最大价值和的节点,所以需要将小的值的信息保存在后面节点, 大的值的信息保存在前面节点

  • 查询:因为最大值为 $10000$,所以对于每次查询的 $a_i$,我们转换为下标 $10000-a_i+1$,然后查询 $[0,10000-a_i+1]$ 内的最大价值和,即查询了所有大于 $a_i$ 的节点的信息。

  • 更新:每次更新到当前位置 $i$ 的最大价值和,即需要更新所有小于 $a_i$ 的节点的最大价值和,对应更新树状数组中 $[10000-a_i+1, 10000]$ ,即当前值对应节点后面的所有节点:因为当前值的节点信息的更改只会影响到比它小的值的节点的信息,而树状数组前面节点信息的更改也只会影响到后面节点的信息。

AC code

int n,a[MaxN],c[MaxN*2];
int mid[12],num;
struct BIT{
	int n;
	int tree[MaxN];
	void init( int n ){
		this->n = n ;
		CLR(tree);
	}
	
	int lowbit( int x ){
		return x & ( -x );
	}
	
	int getmax( int n ){
		int ans = 0;
		for( int i = n; i ; i -= lowbit(i) ){
			ans = max( ans , tree[i] );
		}
		return ans;
	}
	
	void update( int x, int val ){
		for( int i = x; i <= n; i += lowbit( i ) ){
			tree[i] = max( tree[i] , val )  ;
		}
	}
}bit;
int Down[MaxN],Up[MaxN];
int solve(int loc)
{
    bit.init(10000);
    Down[0] = 0;
    for(int i=loc+1;i<loc+n;i++)
    {
        if(c[i]==10000)
        {
            Down[i-loc] = Down[i-loc-1];
            continue;
        }
        int tmp = bit.getmax(10000-c[i]+1) + c[i];
        Down[i-loc] = max(Down[i-loc-1],tmp);
        bit.update(10000-c[i]+1, tmp);
    }
    bit.init(10000);
    Up[n] = 0;
    for(int i=loc+n-1;i>loc;i--)
    {
        if(c[i]==10000)
        {
            Up[i-loc] = Up[i-loc+1];
            continue;
        }
        int tmp = bit.getmax(10000-c[i]+1) + c[i];
        Up[i-loc] = max(Up[i-loc+1],tmp);
        bit.update(10000-c[i]+1, tmp);
    }
    int ans = 0;
    for(int i=0;i<=n-1;i++)
    {
        ans = max(Down[i]+Up[i+1], ans);
    }
    return ans;
}
int main()
{
    while(~scanf("%d", &n))
    {
        num = 0;
        for(int i=1;i<=n;i++) 
        {
            scanf("%d", a+i);
            c[i] = a[i];
            c[n+i] = a[i];
            if(a[i]==10000) mid[num++] = i;
        }
        int ans = 0;
        for(int i=0;i<num;i++)
        {
            ans = max(ans, solve(mid[i]));
        }
        printf("%d\n", ans+10000);
    }
}

Problem G

Party 上有 $n$ 只青蛙,每只青蛙都有自己喜欢喝的茶:$1$ 表示喜欢喝红茶,$2$ 喜欢喝绿茶,$3$ 表示都喜欢。

但同时有 $m$ 对青蛙之间有矛盾:不能给它们喝同样的茶,否则会打起来。同时,青蛙都喜欢宝石,如果给第 $i$ 只青蛙 $W_i$ 个宝石,它就不在乎矛盾了

问最少需要花费多少宝石才能使得这些青蛙之间不会产生矛盾?

数据范围:$ 1 ≤ n ≤ 10^3, 0 ≤ m ≤ 10^4, 1 ≤ W_i ≤ 10^6$ , 并且有矛盾的青蛙刚好可以被分成两个集合,集合中的青蛙互相间没有矛盾。

Solution

由于矛盾建图刚好是一个二分图,所以我们可以先将青蛙染色,分成两个内部无矛盾的集合 $A,B$,然后使用网络流来求解该题:

首先我们将每只青蛙拆分成两个点,并且建边$i \rightarrow i’, W_i$。

对于 $A$ 集合中的青蛙 $a_i$,如果它不喜欢红茶,我们建边 $S \rightarrow a_i, INF$;如果它不喜欢绿茶,我们建边 $a_i’ \rightarrow T, INF$。

对于 $B$ 集合中的青蛙 $b_i$,如果它不喜欢红茶,我们建边 $b_i’ \rightarrow T, INF$;如果它不喜欢绿茶,我们建边 $S \rightarrow b_i, INF$。

此时,整个图并不联通,如果集合 $A,B$ 之间无矛盾的话,那么我们就不用消除矛盾,原图的最小割也为0,答案也就是0。

但是,如果二分图中存在一条边 $a_i,b_i$,假如他们都不喜欢红茶,说明这两只不喜欢喝红茶的青蛙之间有矛盾,那么我们需要将它添加到网络流建图中,即建立 $a_i’ \rightarrow b_i, INF$,表示需要花费流量来消除这对矛盾

这时,整个图就存在一条从 $S$ 到 $T$ 的边:$S \rightarrow a_i \rightarrow a_i’ \rightarrow b_i \rightarrow b_i’ \rightarrow T $,它的满流即 $a$ 和 $b$ 需要宝石的最小值,即对应消除矛盾的最小花费。

所以,若对每一对矛盾在网络流中建图,最后的满流即最小割就对应消除这些矛盾的最小花费。

AC code

int n,m,cost[MaxN], like[MaxN];
struct EDGE{int u,v,w,next;}edge[MaxM];
int cont,head[MaxN];
void inline Add(int u, int v) 
{edge[cont].u = u, edge[cont].v = v, edge[cont].next = head[u], head[u] = cont++; }
void inline ADD(int u, int v) { Add(u,v), Add(v,u);}
int col[MaxN];
void BFS(int u)
{
    queue< int > Q;
    Q.push(u);
    col[u] = 2;
    while(!Q.empty())
    {
        //debug(u)
        u = Q.front();
        Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            if(col[v]==-1)
            {
                col[v] = col[u]^1;
                Q.push(v);
            }
        }
    }
}
void color()
{
    cont=0,MST(head,-1);
    int a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d", &a,&b);
        ADD(a,b);
    }
    MST(col,-1);
    for(int i=1;i<=n;i++)
    {
        if(col[i]==-1) BFS(i);
    }
}
void cal()
{
    G.init(2*n+2);
    int S = 0,T=2*n+1;
    for(int i=1;i<=n;i++)
    {
        if(col[i]&1)
        {
            if(!(like[i]&1)) G.insert(S,i,INF);
            if(!(like[i]&2)) G.insert(i+n,T,INF);
        }
        else
        {
            if(!(like[i]&2)) G.insert(S,i,INF);
            if(!(like[i]&1)) G.insert(i+n,T,INF);
        }
    }
    for(int u=1;u<=n;u++)
    {
        G.insert(u,u+n,cost[u]);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            G.insert(u+n,v,INF);
            //cout << u << v << endl;
        }
    }
    LL ans = G.MaxFlow(S,T);
    printf("%d\n", ans);
}
void solve()
{
    color();
    cal();
}
int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        for(int i=1;i<=n;i++) scanf("%d", &cost[i]);
        for(int i=1;i<=n;i++) scanf("%d", &like[i]);
        solve();
    }
}

Problem H

给出一个长度为 $n$ 的排列 $P_{1…n}$,其中有 $m_1+m_2$ 条记录:$(a_i, b_i, c_i)$

  • 前 $m_1$ 条表示 $[a_i, b_i]$ 的最小值为 $c_i$。

  • 前 $m_2$ 条表示 $[a_i, b_i]$ 的最大值为 $c_i$。

输出满足条件的最小字典序的排列。

数据范围:$ 1 ≤ n ≤ 50, 0 ≤ m_1+m_2 ≤ 50$

Solution

如果不管最小字典序,那么这个题就是一个二分图匹配,求出一个 $1-n$ 到 $1-n$ 的满足条件的完备匹配即可。 对于最小字典序,由于 $n$ 的范围很小,所以我们可以枚举 $1-n$ 的每个位置看能否用一个更小的数来匹配。

AC code

int n,m1,m2;
int Min[55],Max[55],L[55],R[55];
int G[55][55],matching[55];
bool check[55];
int ans[55];
bool DFS(int u)
{
    for(int v=1;v<=n;v++)
    {
        if(G[u][v] && !check[v])
        {  
            check[v] = true;
            if(matching[v] == -1 || DFS(matching[v])) 
            {
                matching[v] = u;
                ans[u] = v;
                return true;
            }
        }
    }
    return false; 
}
int pipi;
void Hungarian()
{
    pipi = 0;       
    MST(matching, -1);
    for(int u=1;u<=n;u++)  
    {
        CLR(check);
        if(DFS(u))
            pipi++;       
    }
}
void init()
{
    CLR(G);
    for(int i=1;i<=n;i++)
    {
        L[i]=Min[i]=1;
        R[i]=Max[i]=n;
    }
}
int main()
{
    while(~scanf("%d%d%d", &n, &m1, &m2))
    {
        init();
        int a,b,c;
        while(m1--)
        {
            scanf("%d%d%d", &a, &b, &c);
            for(int i=a;i<=b;i++) Min[i] = max(Min[i], c);
            L[c] = max(L[c], a); R[c] = min(R[c], b);
        }
        while(m2--)
        {
            scanf("%d%d%d", &a, &b, &c);
            for(int i=a;i<=b;i++) Max[i] = min(Max[i], c);
            L[c] = max(L[c], a); R[c] = min(R[c], b);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=Min[i];j<=Max[i];j++)
            {
                if(L[j]<=i && i<=R[j])
                {
                    G[i][j] = 1;
                }
            }
        }
        Hungarian();
        int cnt = 0;    
        if(pipi!=n) puts("-1");
        else
        {            
            for(int i=1;i<=n;i++)
            {
                int x = ans[i];
                G[i][x] = 0;
                matching[x] = -1;
                bool flag = true;   
                CLR(check);
                for(int v=1;v<x;v++)
                {
                    if(G[i][v] && !check[v])
                    {  
                        check[v] = true; 
                        if(matching[v] == -1 || DFS(matching[v]))
                        {
                            matching[v] = i;
                            ans[i] = v;
                            flag = false;
                            break;
                        }
                    }
                }
                if(flag) 
                {
                    G[i][x] = 1;
                    matching[x] = i;
                }
                x = ans[i];
                for(int j=1;j<=n;j++) G[j][x] = 0;
            }
            for(int i=1;i<=n;i++) printf("%d%c", ans[i], i==n?'\n':' ');
        }
    }
}

Problem I

给出一个 $N$ 个点的完全图,其中有 $m$ 条边的边权为 $a$,其他的边边权为 $b$。求 $1$ 到 $n$ 的最短路。

数据范围:$ 2 ≤ n ≤ 10^5, 0 ≤ m ≤ 5\times 10^5, 1 \leq a, b \leq 10^9$

Solution

分两种情况:

  • $ (1,n)$ 边权为 $b$,那么如果 $b \leq a$,最短路就是 $b$;否则我们需要判断是否存在一条从 $1$ 到 $n$ 的全由 $a$ 构成的路径使得最短路小于 $b$,因为 $a$ 边不多,所以这一步最短路算法或 $BFS$ 即可解决;

  • $ (1,n)$ 边权为 $a$,那么如果 $a \leq b$,最短路就是 $a$;否则我们需要判断是否存在一条从 $1$ 到 $n$ 的全由 $b$ 构成的路径使得最短路小于 $a$,虽然图是完全图,但是每个点都只会被用来松弛一次,所以我们可以用 $set$ 来维护一个下次可能用来松弛的点集,走一遍 $BFS$ 即可。

AC code

int n,m;
LL a, b;
struct Edge
{
    int u,v,next;
    LL w;
}edge[MaxM];
int cont, head[MaxN];
void add(int u, int v)
{
    edge[cont].u = u, edge[cont].v = v, edge[cont].w = 1, edge[cont].next = head[u], head[u] = cont++;
}
typedef pair<LL,int> pii; 
struct cmp
{                       
    bool operator()(pii a,pii b)
    {
        return a.first>b.first;
    }
};
bool vis[MaxN];
LL dis[MaxN];  
void Dijkstra(int s, int t)
{
    CLR(vis);
    for(int i=1;i<=n;i++) dis[i] = INF;
    dis[s] = 0;
    priority_queue<pii,vector<pii>,cmp> q;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        pii u = q.top();
        q.pop();
        if(vis[u.second]) continue;
        vis[u.second] = 1;
        for(int i=head[u.second];i!=-1;i=edge[i].next)
        {
            int to = edge[i].v;
            //debug((u.first + edge[i].w))
            if(dis[to] > u.first + edge[i].w)
            {
                dis[to] = u.first + edge[i].w;
                q.push(make_pair(dis[to], to));
            }
        }
    }
    printf("%lld\n",min(dis[n]*a,b));
}
set<int> sa, sb;
set<int>::iterator it;
void BFS()
{
    sa.clear(),sb.clear();
    queue<int> Q;
    for(int i=2;i<=n;i++) dis[i] = INF,sb.insert(i);
    dis[1] = 0;
    Q.push(1);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            if(sb.count(v)==0) continue;
            sb.erase(v);
            sa.insert(v);
        }
        for( auto v : sb)
        {
            dis[v] = dis[u]+1;
            Q.push(v);
        }
        sb.swap(sa);
        sa.clear();
    }
    printf("%lld\n",min(dis[n]*b,a));
}
void init()
{
    cont = 0, MST(head, -1);
}
int main()
{
    while(~scanf("%d%d%lld%lld", &n, &m, &a, &b))
    {
        init();
        int u,v;
        bool flag = true;
        while(m--)    
        {
            scanf("%d%d", &u, &v);
            if(u==1 && v==n || u==n && v==1  ) flag = false;
            add(u,v),add(v,u);
        }
        if(flag) 
        {
            if(b<=a) printf("%lld\n", b);
            else Dijkstra(1,n);
        }
        else 
        {
            if(a<=b) printf("%lld\n", a);
            else BFS();
        }
    }
}

Contest Summary

  • 记一次血崩的组队赛,三路开题,三路卡题

  • 需要加强组队配合,任务分配,并且规划一下训练内容了