头像

acwing_zyy

$\color{Red}{AcWing\, University}$




离线:6小时前


最近来访(488)
用户头像
鳕鱼饭
用户头像
一切皆有可能
用户头像
有机物
用户头像
Vertex
用户头像
我是菜狗啊啊啊啊啊
用户头像
牛牛蒟蒻
用户头像
BB_7
用户头像
艾伦_0
用户头像
不高兴的兽奶
用户头像
acwing_xyy
用户头像
种花家的兔兔
用户头像
18985082146
用户头像
瓜瓜
用户头像
仙贝
用户头像
violet_garden
用户头像
dhxdl666
用户头像
DreamFather
用户头像
R虎虎生威R
用户头像
Dragonite
用户头像
五柳先生


acwing_zyy
7小时前

题目链接

3246. 引水入城

MF 城建立在一片高原上。

由于城市唯一的水源是位于河谷地带的湖中,人们在坡地上修筑了一片网格状的抽水水管,以将湖水抽入城市。

如下图所示:

image

这片管网由 $n$ 行 $m$ 列节点(红色,图中 $n = 5$,$m = 6$),横向管道(紫色)和纵向管道(橙色)构成。

行和列分别用 $1$ 到 $n$ 的整数和 $1$ 到 $m$ 的整数表示。

第 $1$ 行的任何一个节点均可以抽取湖水,湖水到达第 $n$ 行的任何一个节点即算作引入了城市。

除第一行和最后一行外,横向相邻或纵向相邻的两个节点之间一定有一段管道,每一段管道都有各自的最大的抽水速率,并需要根据情况选择抽水还是放水。

对于纵向的管道(橙色),允许从上方向下方抽水或从下方向上方放水;如果从图中的上方向下方抽水,那么单位时间内能通过的水量不能超过管道的最大速率;如果从下方向上方放水,因为下方海拔较高,因此可以允许有任意大的水量。

对于横向的管道(紫色),允许从左向右或从右向左抽水,不允许放水,两种情况下单位时间流过的水量都不能超过管道的最大速率。

现在 MF 城市的水务负责人想知道,在已知每个管道单位时间容量的情况下,MF 城每单位时间最多可以引入多少的湖水。

输入格式

由于输入规模较大,我们采用伪随机生成的方式生成数据。

每组数据仅一行包含 $6$ 个非负整数 $n, m, A, B, Q, X_0$。其中,$n$ 和 $m$ 如前文所述,表示管网的大小,保证 $2 ≤ n, m ≤ 5000$;保证 $1 ≤ A, B, Q, X_0 ≤ 10^9$。

$A, B, Q, X_0$ 是数据生成的参数,我们用如下的方式定义一个数列 ${ X_i }$:

$X_{i+1} = ( AX_i + B) \bmod Q, (i ≥ 0)$

我们将数列的第 $1$ 项到第 $(n-1)m$ 项作为纵向管道的单位时间容量,其中 $X_{(s-1)m+t}$ 表示第 $s$ 行第 $t$ 列的节点到第 $s+1$ 行第 $t$ 列管道单位时间的容量;将数列的第 $(n-1)m+1$ 项到第 $(n-1)m+(n-2)(m-1)$ 项(即接下来的 $(n-2)(m-1)$ 项)作为横向管道的单位时间容量,其中 $X_{(n-1)m+(s-2)(m-1)+t}$ 表示第 $s$ 行第 $t$ 列的节点到第 $s$ 行第 $t+1$ 列管道单位时间的容量。

输出格式

输出一行一个整数,表示 MF 城每单位时间可以引入的水量。

注意计算过程中有些参数可能超过 $32$ 位整型表示的最大值,请注意使用 $64$ 位整型存储相应数据。

数据范围

共有 $10$ 组评测数据,每组数据的参数规模如下所示:

image

输入样例1:

3 3 10 3 19 7

输出样例1:

38

样例1解释

使用参数得到数列 ${ X_i }={ 7, 16, 11, 18, 12, 9, 17, 2, 4, … }$,按照输入格式可以得到每个管道的最大抽水量如下图所示:

image

在标准答案中,单位时间可以引水 $38$ 单位。所有纵向管道均向下抽水即可,不需要横向管道抽水,也不需要向上放水。

输入样例2:

2 5 595829232 749238243 603779819 532737791

输出样例2:

1029036148

输入样例3:

5 2 634932890 335818535 550589587 977780683

输出样例3:

192923706

输入样例4:

5 5 695192542 779962396 647834146 157661239

输出样例4:

1449991168

解题思路

分层图,最小割转平面图最短路

显然,如果不考虑数据范围,本题为最大流板题,即建立源点 $s$ 和 汇点 $t$,$s$ 向所有的第一行的点连边,容量足够大,最后一行的点向 $t$ 连边,容量足够大,其余边权在流网络中即为容量,求解 $s$ 到 $t$ 的最大流即为所求,但显然本题数据范围不允许,由最大流最小割定理,$最大流=最小割$,而该图又为一个平面图,可知 $平面图最短路=流网络最小割$,具体见 P4001 [ICPC-Beijing 2006] 狼抓兔子,则现在只用求解最短路即可,但 $O(nlogn)$ 的算法也无法通过本题,考虑性质,由于向上的边的容量足够大,最短路必不会选择该边,即列与列之间的传递是单向的,很容易发现这是一个每一列每一列的分层图,而且在每一层中的某个点,其是一条链,即只能从上或者下转移过来,而列与列之间只有一个方向
另外还需要注意对偶图平面的编号,这里不再赘述

  • 时间复杂度:$O(nm)$

代码

// Problem: 引水入城
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3249/
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5005;
int n,m,A,B,Q,x;
LL f[N][N],w[N][N];
int main()
{
    memset(f,0x3f,sizeof f);
    memset(w,0x3f,sizeof w);
    scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&Q,&x);
    for(int i=1;i<=n;i++)f[i][0]=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=x=((LL)A*x+B)%Q;
    for(int i=1;i<n-1;i++)
        for(int j=1;j<m;j++)
            w[i][j]=x=((LL)A*x+B)%Q;
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<n;i++)    
        {
            f[i][j]+=f[i][j-1];
            f[i][j]=min(f[i][j],f[i-1][j]+w[i-1][j]);
        }
        for(int i=n-2;i;i--)
            f[i][j]=min(f[i][j],f[i+1][j]+w[i][j]);
    }
    LL res=1e18;
    for(int i=1;i<n;i++)res=min(res,f[i][m]);
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 3246. 引水入城

acwing_zyy
7小时前
// Problem: 引水入城
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/3249/
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5005;
int n,m,A,B,Q,x;
LL f[N][N],w[N][N];
int main()
{
    memset(f,0x3f,sizeof f);
    memset(w,0x3f,sizeof w);
    scanf("%d%d%d%d%d%d",&n,&m,&A,&B,&Q,&x);
    for(int i=1;i<=n;i++)f[i][0]=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=x=((LL)A*x+B)%Q;
    for(int i=1;i<n-1;i++)
        for(int j=1;j<m;j++)
            w[i][j]=x=((LL)A*x+B)%Q;
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<n;i++)    
        {
            f[i][j]+=f[i][j-1];
            f[i][j]=min(f[i][j],f[i-1][j]+w[i-1][j]);
        }
        for(int i=n-2;i;i--)
            f[i][j]=min(f[i][j],f[i+1][j]+w[i][j]);
    }
    LL res=1e18;
    for(int i=1;i<n;i++)res=min(res,f[i][m]);
    printf("%lld",res);
    return 0;
}



acwing_zyy
7小时前

题目链接

P4001 [ICPC-Beijing 2006] 狼抓兔子

[ICPC-Beijing 2006] 狼抓兔子

题目描述

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

image

左上角点为 $(1,1)$, 右下角点为 $(N,M)$ (上图中 $N=3$, $M=4$).有以下三种类型的道路:

  1. $(x,y)\rightleftharpoons(x+1,y)$

  2. $(x,y)\rightleftharpoons(x,y+1)$

  3. $(x,y)\rightleftharpoons(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里,现在它们要跑到右下角 $(N,M)$ 的窝中去,狼王开始伏击这些兔子。当然为了保险起见,如果一条道路上最多通过的兔子数为 $K$,狼王需要安排同样数量的 $K$ 只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

输入格式

第一行两个整数 $N,M$,表示网格的大小。

接下来分三部分。

第一部分共 $N$ 行,每行 $M-1$ 个数,表示横向道路的权值。

第二部分共 $N-1$ 行,每行 $M$ 个数,表示纵向道路的权值。

第三部分共 $N-1$ 行,每行 $M-1$ 个数,表示斜向道路的权值。

输出格式

输出一个整数,表示参与伏击的狼的最小数量。

样例 #1

样例输入 #1

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6

样例输出 #1

14

提示

数据规模与约定

对于全部的测试点,保证 $3 \leq N,M \leq 1000$,所有道路的权值均为不超过 $10^6$ 的正整数。

解题思路

最小割

这题不难发现本质上其实就是在找最小割,因为所有的点,都可以分为两个集合 $(1,1)$ 和 $(n,m)$ 属于两个不同的集合,兔子一定要从属于 $s$ 的集合走向属于 $t$ 的集合,即都要通过两个集合中形成的边,即对应流网络中的割边,要求最小值,即对应最小割,本题 dinic 勉强过了

  • 时间复杂度:$O(n^2m)$

最小割平面图转最短路

但还是不够优秀,可以发现这样的图是平面图(即从平面上来看,两条边相交的只能是已经存在的顶点,即一条边跨越另外一条边不行)
有一个重要的结论:$平面图最小割=平面图的对偶图的最短路$

$\color{red}{对偶图是什么?}$
以下是一个平面图转化为对偶图的过程:
image

如果现在要求 $1$ 到 $6$ 的最小割该如何转化为对偶图的最短路问题?建立对偶图后,即以 $1$ 和 $3$ 之间的边为例,这时该边上的面表示的点向该边下的面表示的点连边,边权为 $1$ 到 $3$ 的边权,不难发现:这样的割边可以对应上最短路的某条边,以 $1-3-5-6$ 这部分的边的下面的平面看作起点 $s$,$1-2-4-5$ 这部分的边的上面的平面看作终点 $t$,建立完对偶图后,求从 $s$ 到 $t$ 的最短路即为 $1$ 到 $6$ 的最小割

回到本题
image
同理,要求解 $(1,1)$ 到 $(n,m)$ 的最小割,建立对偶图,左下部分的平面看作起点 $s$,右上部分的平面看作终点 $t$,建立对偶图时,$s$ 要通过左下边界的边和对应的平面连边,$t$ 要通过右上边界的边和对应的平面连边
还有一个常见的难点:$\color{red}{如何建立对偶图?}$
对于一个这样的图,很容易如下编号:
image

即对于一个点 $(i,j)$,其作为小矩形的左上角,通过这个点即可判断区域,即:
image
红色区域表示的点为 $2\times (i-1)\times (m-1)+2\times (j-1)+2$,同理可得到另外一块区域为 $2\times (i-1)\times (m-1)+2\times (j-1)+1$,这样标号即可解决问题,求 $s$ 到 $t$ 的最短路即为答案

  • 时间复杂度:$O(nlogn)$

代码

  • dinic
// Problem: P4001 [ICPC-Beijing 2006] 狼抓兔子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4001
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1000005,M=N*6,inf=1e9;
int n,m,S,T;
int h[N],f[M],e[M],ne[M],idx;
int d[N],q[N],hh,tt,cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
int get(int x,int y)
{
    return x*m+y;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            scanf("%d",&x);
            add(get(i,j),get(i,j+1),x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&x);
            add(get(i,j),get(i+1,j),x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        {
            scanf("%d",&x);
            add(get(i,j),get(i+1,j+1),x);
        }
    S=get(1,1),T=get(n,m);
    printf("%d",dinic());
    return 0;
}
  • 平面图最短路
// Problem: P4001 [ICPC-Beijing 2006] 狼抓兔子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4001
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=2000005,M=N*3;
int n,m;
int h[N],ne[M],e[M],w[M],idx;
int d[N],S,T;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,w[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
void dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[S]=0;
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,S});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int x=t.se,v=t.fi;
        if(x==T)return ;
        if(d[x]==v)
            for(int i=h[x];~i;i=ne[i])
            {
                int y=e[i];
                if(d[y]>d[x]+w[i])
                {
                    d[y]=d[x]+w[i];
                    q.push({d[y],y});
                }   
            }
    }
}
int get(int x,int y,int t)
{
    return 2*(x-1)*(m-1)+2*(y-1)+t;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    T=2*(n-1)*(m-1)+1;
    int x;
    for(int i=1;i<m;i++)
    {
        scanf("%d",&x);
        add(get(1,i,2),T,x);
    }
    for(int i=2;i<n;i++)
        for(int j=1;j<m;j++)
        {
            scanf("%d",&x);
            add(get(i-1,j,1),get(i,j,2),x);
        }
    for(int i=1;i<m;i++)
    {
        scanf("%d",&x);
        add(S,get(n-1,i,1),x);
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d",&x);
        add(S,get(i,1,1),x);
        for(int j=2;j<m;j++)
        {
            scanf("%d",&x);
            add(get(i,j-1,2),get(i,j,1),x);
        }
        scanf("%d",&x);
        add(get(i,m-1,2),T,x);
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        {
            scanf("%d",&x);
            add(get(i,j,1),get(i,j,2),x);
        }
    dijkstra();
    printf("%d",d[T]);
    return 0;
}



acwing_zyy
12小时前

题目链接

2418. 光之大陆

在光之大陆的土地上,各种势力盘根错节。

来自光之峡谷的精灵,来自黑暗森林的亡灵,来自古老东方的人类共同生活在一起。

善于打造装置的矮人,善于发明的侏儒,隐匿于山林的巨人也坚守着属于自己的领土。

这些种族之间关系错综复杂,构成了极其庞大的关系网络。

大魔法师小 $P$ 想要研究其中的种族关系。

两个物种之间可以是盟友,也可以不是盟友,如果 $a_1,a_2..a_n$ 满足 $a_i$ 和 $a_{i+1}$ 是盟友,且 $a_n$ 和 $a_1$ 是盟友,则他们构成了一个联盟。

由于光之大陆正处于微妙的和平之中。所以一个合理的物种关系应满足如下条件:

  1. 对于任意两个物种 $A,B$,都存在一个序列 $A,a_1,a_2..a_n,B$,使得任意相邻两个种族是盟友(注意 $A,B$ 不一定是盟友)。
  2. 对于任意两个联盟 $S_a,S_b$,都不存在一个物种既参加了联盟 $S_a$,又参加了联盟 $S_b$。

小 $P$ 想知道,大陆上的 $N$ 个种族一共有多少种可能的结盟关系,由于结果可能很大,你只需要输出答案 $\bmod M$ 的值。

输入格式

一行,两个正整数 $N,M$。

输出格式

一个整数,表示方案数 $\bmod M$ 的值。

数据范围

$3 \le N \le 200$,
$1 \le M \le 10^6$

输入样例:

4 1000000

输出样例:

31

解题思路

prufer编码

问题即给出一个 $n$ 个点的无向完全图,问有多少个不同的点仙人掌图
将该问题拆解:先求出 $n$ 个点分成 $m$ 个环的方案,然后再将这些环组成生成树的方案数,对于第二步,考虑prufer编码,每个点的父亲节点的范围为 $1\sim n$,且由于是完全图,不难发现,对于任意一个点的父亲节点,对于 $1\sim n$ 的任何一个点作为其父亲节点的概率都是相等的,即prufer编码有 $n^{m-2}$ 种,即将环组成生成树的方案有 $n^{m-2}$ 种,再来考虑第一步,考虑 dp,$f[i][j]$ 表示前 $i$ 个点分成 $j$ 个环的方案数,枚举 $1$ 号所在环的环数,这样的环有 $C_{i-1}^{k-1}$ 种,环也有不同的种类,$k$ 点排列有 $k!$,假定我们每次都是拿环上最上面的那个点连边,则显然有 $k$ 种方案,即对应全排列,可以看成旋转操作形成的环是不同的,但是由于是无向图,对于某条边来说会连两次,则这部分的转移方程:$f[i][j]=\sum_{k=1}^{i-j+1}f[i-k][j-1]\times C_{i-1}^{k-1}\times \frac{k!}{2}$,则答案为 $\sum_{k=1}^{n}f[n][k]\times n^{k-2}$,观察式子,不难发现 $k=1$ 时会出问题,$\color{red}{为什么?}$对于含 $n$ 个点的环,这时显然不用向外连边,即这时的总方案应该为 $\frac{n-1}{2}$

  • 时间复杂度:$O(n^3)$

代码

// Problem: 光之大陆
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/2420/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=205;
int n,m,C[N][N],g[N],f[N][N];
void init()
{
    C[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(!j)C[i][j]=1;
            else
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%m;
        }
    g[1]=1%m,g[3]=3%m;
    for(int i=4;i<=n;i++)g[i]=(LL)g[i-1]*i%m;
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            for(int k=1;k<=i-j+1;k++)
                f[i][j]=(f[i][j]+(LL)f[i-k][j-1]*C[i-1][k-1]*g[k]%m)%m;
    int res=g[n-1],p=1;
    for(int i=2;i<=n;i++)
    {
        res=(res+(LL)f[n][i]*p)%m;
        p=(LL)p*n%m;
    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 2418. 光之大陆

acwing_zyy
12小时前
// Problem: 光之大陆
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/2420/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=205;
int n,m,C[N][N],g[N],f[N][N];
void init()
{
    C[0][0]=1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            if(!j)C[i][j]=1;
            else
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%m;
        }
    g[1]=1%m,g[3]=3%m;
    for(int i=4;i<=n;i++)g[i]=(LL)g[i-1]*i%m;
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            for(int k=1;k<=i-j+1;k++)
                f[i][j]=(f[i][j]+(LL)f[i-k][j-1]*C[i-1][k-1]*g[k]%m)%m;
    int res=g[n-1],p=1;
    for(int i=2;i<=n;i++)
    {
        res=(res+(LL)f[n][i]*p)%m;
        p=(LL)p*n%m;
    }
    printf("%d",res);
    return 0;
}



acwing_zyy
18小时前

题目链接

2419. prufer序列

本题需要你实现prufer序列与无根树之间的相互转化。

假设本题涉及的无根树共有 $n$ 个节点,编号 $1 \sim n$。

为了更加简单明了的描述无根树的结构,我们不妨在输入和输出时将该无根树描述为一个以 $n$ 号节点为根的有根树。

这样就可以设这棵无根树的父亲序列为 $f_1,f_2,…,f_{n-1}$,其中 $f_i$ 表示将该树看作以 $n$ 号节点为根的有根树时,$i$ 号节点的父节点编号。

同时,设这棵无根树的prufer序列为 $p_1,p_2,…,p_{n-2}$。

现在,给定一棵由 $n$ 个节点构成的无根树,以及该无根树的一个序列(父亲序列或prufer序列),请你求出另一个序列。

输入格式

输入共两行。

第一行包含两个整数 $n,m$,表示无根树的节点数以及给定序列类型。

如果 $m = 1$,则第二行包含 $n-1$ 个整数,表示给定序列为父亲序列。

如果 $m = 2$,则第二行包含 $n-2$ 个整数,表示给定序列为prufer序列。

输出格式

共一行,输出另一个序列,整数之间用单个空格隔开。

数据范围

$2 \le n \le 10^5$

输入样例1:

6 1
3 5 4 5 6

输出样例1:

3 5 4 5

输入样例2:

6 2
3 5 4 5

输出样例2:

3 5 4 5 6

解题思路

prufer编码

prufer编码主要作用即将一棵无根树转化为一个序列(即prufer序列),另外prufer序列也可以反过来转化为一棵树,即prufer序列和树之间是一一对应的,常用来解决一些证明问题,如凯莱定理等
证明凯莱定理(一个无向完全图有 $n^{n-2}$ 棵生成树):由于prufer序列和树之间是一一对应的关系,证明有多少棵不同的生成树即证明有多少种prufer序列,显然,prufer序列共有 $n-2$ 项,其范围为 $1\sim n$,故其种类数为 $n^{n-2}$

prufer编码的流程:假定 $n$ 号节点为根,找到除根外度数最小的节点,在删除该节点之前,将其父节点输出,重复该流程,直到最后只剩下两个节点,即prufer序列只有 $n-2$ 个元素,因为prufer序列最多 $n-1$ 个元素,而最后一个元素一定为 $n$,所以这个元素可以省略,输出的元素即为prufer序列
$\color{red}{如何将一棵树线性时间内转化为prufer序列?}$
假定当前出度为 $0$ 且编号最小的节点为 $j$,则输出 $f[j]$,删除 $j$ 之后,出度为 $0$ 的节点至多只会增加一个,即 $f[j]$,判断删除 $j$ 之后 $f[j]$ 的出度是否为 $0$,如果 $f[j]$ 的出度为 $0$ 且 $f[j]<j$ 说明 $f[j]$ 是当前出度为 $0$ 且编号最小的节点,递归输出这样的父节点即可,否则说明这样的 $j$ 只会更大,即 $j$ 只会增加,这样即可线性时间内将一颗树转化为prufer序列

$\color{red}{如何将一个prufer序列转化为一棵树?}$
先将 $n$ 这个节点加入到prufer序列中,不难发现,prufer序列中某个数出现的次数即为该数在树中的儿子节点的数量,从 $1$ 开始找到儿子数量为 $0$ 且编号最小的节点 $j$,其父节点即为当前遍历的prufer序列的元素,将该元素从prufer序列中删去,因为删除该元素后儿子数量为 $0$ 的节点数量至多直接增加一个,如果该元素的儿子数量为 $0$ 且编号小于 $j$,说明当前节点即为儿子数量为 $0$ 且编号最小的节点,递归处理即可,这样的 $j$ 同样也是递增的,故可以在线性时间内将一个prufer序列转化为一棵树

  • 时间复杂度:$O(n)$

代码

// Problem: prufer序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2421/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,m;
int f[N],p[N],d[N];
void tree2prufer()
{
    for(int i=1;i<n;i++)
    {
        scanf("%d",&f[i]);
        d[f[i]]++;
    }
    for(int i=0,j=1;i<n-2;j++)
    {
        while(d[j])j++;
        p[i++]=f[j];
        while(i<n-2&&--d[p[i-1]]==0&&p[i-1]<j)p[i++]=f[p[i-1]];
    }
    for(int i=0;i<n-2;i++)printf("%d ",p[i]);
}
void prufer2tree()
{
    for(int i=1;i<=n-2;i++)
    {
        scanf("%d",&p[i]);
        d[p[i]]++;
    }
    p[n-1]=n;
    for(int i=1,j=1;i<n;i++,j++)
    {
        while(d[j])j++;
        f[j]=p[i];
        while(i<n&&--d[p[i]]==0&&p[i]<j)f[p[i]]=p[i+1],i++;
    }
    for(int i=1;i<n;i++)printf("%d ",f[i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    if(m==1)tree2prufer();
    else
        prufer2tree();
    return 0;
}


活动打卡代码 AcWing 2419. prufer序列

acwing_zyy
19小时前
// Problem: prufer序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2421/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,m;
int f[N],p[N],d[N];
void tree2prufer()
{
    for(int i=1;i<n;i++)
    {
        scanf("%d",&f[i]);
        d[f[i]]++;
    }
    for(int i=0,j=1;i<n-2;j++)
    {
        while(d[j])j++;
        p[i++]=f[j];
        while(i<n-2&&--d[p[i-1]]==0&&p[i-1]<j)p[i++]=f[p[i-1]];
    }
    for(int i=0;i<n-2;i++)printf("%d ",p[i]);
}
void prufer2tree()
{
    for(int i=1;i<=n-2;i++)
    {
        scanf("%d",&p[i]);
        d[p[i]]++;
    }
    p[n-1]=n;
    for(int i=1,j=1;i<n;i++,j++)
    {
        while(d[j])j++;
        f[j]=p[i];
        while(i<n&&--d[p[i]]==0&&p[i]<j)f[p[i]]=p[i+1],i++;
    }
    for(int i=1;i<n;i++)printf("%d ",f[i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    if(m==1)tree2prufer();
    else
        prufer2tree();
    return 0;
}



题目链接

2417. 指挥网络

在漫长的骂战过后,利特肯王国和克努斯海洋王国之间爆发了一场武装战争。

克努斯海洋王国部队的猛烈进攻使得利特肯王国的指挥网络彻底瘫痪

临时指挥网络的建立刻不容缓。

利特肯命令史努比负责该项目。

利特肯王国共有 $N$ 个指挥部,位于平面中的 $N$ 个节点上(编号 $1 \sim N$)。

其中利特肯所在的指挥总部位于节点 $1$。

通过对战时情况的详尽研究,史努比认为,当前最关键的一点在于建立一个单向通信网络,使得利特肯的命令能够成功传达至平面中的每个节点处。

如果希望利特肯的命令能够直接从节点 $A$ 传递到另一个节点 $B$,则必须沿着连接两个节点的直线段构建一条单向传输电线。

因为战争还未停止,所以并不是所有节点对之间都能建立电线。(甚至能够建立从节点 $A$ 传递消息至节点 $B$ 的电线,也不一定能够建立从节点 $B$ 传递消息至节点 $A$ 的电线)

史努比希望这项工程所需耗费的电线长度尽可能短,以便施工可以尽快完成。

输入格式

输入包含若干测试数据。

每组数据第一行包含两个整数 $N,M$,表示节点总数以及可在其间建立电线的节点对数。

接下来 $N$ 行,其中第 $i$ 行包含两个整数 $x_i,y_i$,表示节点 $i$ 的位置坐标为 $(x_i,y_i)$。

接下来 $M$ 行,每行包含两个整数 $a,b$,表示可以建立一条单向电线使得命令可以从节点 $a$ 传递至节点 $b$。

处理至文件末尾。

输出格式

对于每个测试数据,输出结果占一行。

如果临时网络可以成功构建,则输出所需耗费电线的最小可能长度,保留两位小数。

如果不能成功构建,则输出 poor snoopy

数据范围

$1 \le N \le 100$,
$1 \le M \le 10^4$,
$0 \le x_i,y_i \le 10^5$,
$1 \le a,b \le N$,$a \neq b$,
每个输入最多包含 $10$ 组测试。

输入样例:

4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3

输出样例:

31.19
poor snoopy

解题思路

朱刘算法,最小树形图

树形图:对于有向图而言,其无环,且除根外的所有点的入度都为 $1$

朱刘算法主要用来求解有向图的最小树形图,即总权值最小的树形图
算法流程:对于每个点都找一条权值最小的指向该点的边,如果这样的边不能构成一个环的话,则说明找到答案,结束整个算法流程,否则缩点,对于某条指向该缩点的边,其权值需要再减去其指向缩点表示的环的点的前驱边的权值,然后继续找出这样的边,直到没有环出现
证明略

  • 时间复杂度:$O(nm)$

代码

// Problem: 指挥网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2419/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

typedef pair<double,double> PDD;
const int N=105;
const double inf=1e9;
int n,m;
bool g[N][N],st[N];
PDD a[N];
double d[N][N],bd[N][N];
int pre[N];
int dfn[N],low[N],scc_cnt,id[N],timestamp,stk[N],top;
bool in_stk[N];
void dfs(int x)
{
    st[x]=true;
    for(int i=1;i<=n;i++)
        if(g[x][i]&&!st[i])dfs(i);
}
bool check_con()
{
    memset(st,0,sizeof st);
    dfs(1);
    for(int i=1;i<=n;i++)
        if(!st[i])return false;
    return true;
}
double get_dist(int x,int y)
{
    double dx=a[x].fi-a[y].fi;
    double dy=a[x].se-a[y].se;
    return sqrt(dx*dx+dy*dy);
}
void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    stk[++top]=x,in_stk[x]=true;
    int y=pre[x];
    if(!dfn[y])
    {
        tarjan(y);
        low[x]=min(low[x],low[y]);
    }
    else if(in_stk[y])low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        int y;
        scc_cnt++;
        do
        {
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
        }while(y!=x);
    }
}
double work()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j])d[i][j]=get_dist(i,j);
            else
                d[i][j]=inf;
    double res=0;
    while(true)
    {
        for(int i=1;i<=n;i++)
        {
            pre[i]=i;
            for(int j=1;j<=n;j++)
                if(d[pre[i]][i]>d[j][i])
                    pre[i]=j;
        }
        memset(dfn,0,sizeof dfn);
        scc_cnt=timestamp=top=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
        if(scc_cnt==n)
        {
            for(int i=2;i<=n;i++)res+=d[pre[i]][i];
            break;
        }
        for(int i=2;i<=n;i++)
            if(id[i]==id[pre[i]])res+=d[pre[i]][i];
        for(int i=1;i<=scc_cnt;i++)
            for(int j=1;j<=scc_cnt;j++)
                bd[i][j]=inf;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][j]<inf&&id[i]!=id[j])
                {
                    int x=id[i],y=id[j];
                    if(id[pre[j]]==id[j])
                        bd[x][y]=min(bd[x][y],d[i][j]-d[pre[j]][j]);
                    else
                        bd[x][y]=min(bd[x][y],d[i][j]);
                }
        n=scc_cnt;
        memcpy(d,bd,sizeof bd);
    }
    return res;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(g,0,sizeof g);
        for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].fi,&a[i].se);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x!=y&&y!=1)g[x][y]=true;
        }
        if(!check_con())puts("poor snoopy");
        else
            printf("%.2lf\n",work());
    }
    return 0;
}


活动打卡代码 AcWing 2417. 指挥网络

// Problem: 指挥网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2419/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

typedef pair<double,double> PDD;
const int N=105;
const double inf=1e9;
int n,m;
bool g[N][N],st[N];
PDD a[N];
double d[N][N],bd[N][N];
int pre[N];
int dfn[N],low[N],scc_cnt,id[N],timestamp,stk[N],top;
bool in_stk[N];
void dfs(int x)
{
    st[x]=true;
    for(int i=1;i<=n;i++)
        if(g[x][i]&&!st[i])dfs(i);
}
bool check_con()
{
    memset(st,0,sizeof st);
    dfs(1);
    for(int i=1;i<=n;i++)
        if(!st[i])return false;
    return true;
}
double get_dist(int x,int y)
{
    double dx=a[x].fi-a[y].fi;
    double dy=a[x].se-a[y].se;
    return sqrt(dx*dx+dy*dy);
}
void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    stk[++top]=x,in_stk[x]=true;
    int y=pre[x];
    if(!dfn[y])
    {
        tarjan(y);
        low[x]=min(low[x],low[y]);
    }
    else if(in_stk[y])low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        int y;
        scc_cnt++;
        do
        {
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
        }while(y!=x);
    }
}
double work()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j])d[i][j]=get_dist(i,j);
            else
                d[i][j]=inf;
    double res=0;
    while(true)
    {
        for(int i=1;i<=n;i++)
        {
            pre[i]=i;
            for(int j=1;j<=n;j++)
                if(d[pre[i]][i]>d[j][i])
                    pre[i]=j;
        }
        memset(dfn,0,sizeof dfn);
        scc_cnt=timestamp=top=0;
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
        if(scc_cnt==n)
        {
            for(int i=2;i<=n;i++)res+=d[pre[i]][i];
            break;
        }
        for(int i=2;i<=n;i++)
            if(id[i]==id[pre[i]])res+=d[pre[i]][i];
        for(int i=1;i<=scc_cnt;i++)
            for(int j=1;j<=scc_cnt;j++)
                bd[i][j]=inf;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(d[i][j]<inf&&id[i]!=id[j])
                {
                    int x=id[i],y=id[j];
                    if(id[pre[j]]==id[j])
                        bd[x][y]=min(bd[x][y],d[i][j]-d[pre[j]][j]);
                    else
                        bd[x][y]=min(bd[x][y],d[i][j]);
                }
        n=scc_cnt;
        memcpy(d,bd,sizeof bd);
    }
    return res;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(g,0,sizeof g);
        for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].fi,&a[i].se);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x!=y&&y!=1)g[x][y]=true;
        }
        if(!check_con())puts("poor snoopy");
        else
            printf("%.2lf\n",work());
    }
    return 0;
}



题目链接

1032. 游戏

狂野飙车是小 $L$ 最喜欢的游戏。

与其他业余玩家不同的是,小 $L$ 在玩游戏之余,还精于研究游戏的设计,因此他有着与众不同的游戏策略。

小 $L$ 计划进行 $n$ 场游戏,每场游戏使用一张地图,小 $L$ 会选择一辆车在该地图上完成游戏。

小 $L$ 的赛车有三辆,分别用大写字母 $A、B、C$ 表示。

地图一共有四种,分别用小写字母 $x、a、b、c$ 表示。

其中,赛车 $A$ 不适合在地图 $a$ 上使用,赛车 $B$ 不适合在地图 $b$ 上使用,赛车 $C$ 不适合在地图 $c$ 上使用,而地图 $x$ 则适合所有赛车参加。

适合所有赛车参加的地图并不多见,最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。

例如:$S=xaabxcbc$ 表示小 $L$ 计划进行 $8$ 场游戏,其中第 $1$ 场和第 $5$ 场的地图类型是 $x$,适合所有赛车,第 $2$ 场和第 $3$ 场的地图是 $a$,不适合赛车 $A$,第 $4$ 场和第 $7$ 场的地图是 $b$,不适合赛车 $B$, 第 $6$ 场和第 $8$ 场的地图是 $c$,不适合赛车 $C$。

小 $L$ 对游戏有一些特殊的要求,这些要求可以用四元组 ($i,h_i,j,h_j$) 来描述,表示若在第 $i$ 场使用型号为 $h_i$ 的车子,则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 $L$ 选择每场游戏使用的赛车吗?

如果有多种方案,输出任意一种方案。

如果无解,输出 “$-1$”(不含双引号)。

输入格式

输入第一行包含两个非负整数 $n,d$。

输入第二行为一个字符串 $S$ 。

$n,d,S$ 的含义见题目描述,其中 $S$ 包含 $n$ 个字符,且其中恰好 $d$ 个为小写字母 $x$。

输入第三行为一个正整数 $m$ ,表示有 $m$ 条用车规则。

接下来 $m$ 行,每行包含一个四元组 $i,h_i,j,h_j$ ,其中 $i, j$ 为整数,$h_i,h_j$ 为字符 $A 、B$ 或 $C$,含义见题目描述。

输出格式

输出一行。

若无解输出 “$-1$”(不含双引号)。

若有解,则包含一个长度为 $n$ 的仅包含大写字母 $A、B、C$ 的字符串,表示小 $L$ 在这 $n$ 场游戏中如何安排赛车的使用。

如果存在多组解,输出其中任意一组即可。

数据范围

image

输入样例:

3 1
xcc
1
1 A 2 B

输出样例:

ABA

样例解释

小 $L$ 计划进行 $3$ 场游戏,其中第 $1$ 场的地图类型是 $x$,适合所有赛车,第 $2$ 场和第 $3$ 场的地图是 $c$,不适合赛车 $C$。

小 $L$ 希望:若第 $1$ 场游戏使用赛车 $A$,则第 $2$ 场游戏使用赛车 $B$。

那么为这 $3$ 场游戏分别安排赛车 $A、B、A$ 可以满足所有条件。

若依次为 $3$ 场游戏安排赛车为 $BBB$ 或 $BAA$ 时,也可以满足所有条件,也被视为正确答案。

但依次安排赛车为 $AAB$ 或 $ABC$ 时,因为不能满足所有条件,所以不被视为正确答案。

解题思路

2-SAT

对于 $a$,其只能使用 $A$ 或 $B$,对于 $b$,其只能使用 $a$ 或 $c$,对于 $c$,其只能使用 $A$ 或 $B$,对于 $x$,其可以使用 $A$ 或 $B$ 或 $C$,显然这是一个 2-SAT 和 3-SAT 结合的问题,即如果不考虑 $x$ 存在的情况(即只存在 2-SAT 的情况),对于若干个条件,即如果第 $i$ 场使用 $x$,则第 $j$ 场应该使用 $y$,如果第 $i$ 场本身就不能使用 $x$,则显然该条件没用,可以忽略,否则如果第 $j$ 场本身不能使用 $y$,则应该使条件不成立,即第 $i$ 场不应该使用 $x$,否则如果第 $j$ 场能使用 $y$ 的话,则应该使第 $i$ 场使用 $x$ 这个命题表示的节点指向第 $j$ 场使用 $y$ 这个命题表示的节点,同时逆否命题也需要加入边,但是回到问题本身, 3-SAT 是一个 NPC 问题,但是由于 $x$ 的个数不是很多,但如果暴力枚举所有 $x$ 的值的话也不行,但可以将 3-SAT 问题转化为 2-SAT 问题,即对于有 $x$ 的场次来说,其一定是选 $B$ 或 $C$,或者选 $A$ 或 $C$,即其可以等价于两种 2-SAT,共有 $2^d$ 种组合,这样就将问题完全转化为 2-SAT 问题

  • 时间复杂度:$O(2^d\times (n+m)$

代码

// Problem: 游戏
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1034/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=100005,M=2e5+5;
int n,d,m;
char s[N];
int h[N],ne[M],e[M],idx;
int pos[10];
int dfn[N],low[N],timestamp,stk[N],top,scc_cnt,id[N];
bool in_stk[N];
struct Op
{
    int x,y;
    char a,b;
}op[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++timestamp;
    stk[++top]=x,in_stk[x]=true;
    for(int i=h[x];~i;i=ne[i])
    {
        int y=e[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(in_stk[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int y;
        scc_cnt++;
        do
        {
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
        }while(y!=x);
    }
}
int get(int x,char a,int t)
{
    a-='A';
    char b=s[x]-'a';
    if(((b+1)%3==a)^t)return x<<1|1;
    return x<<1;
}
char put(int x,int t)
{
    int y=s[x]-'a';
    return 'A'+(y+t)%3;
}
bool work()
{
    memset(h,-1,sizeof h);
    memset(dfn,0,sizeof dfn);
    idx=timestamp=scc_cnt=0;
    for(int i=0;i<m;i++)
    {
        int x=op[i].x-1,y=op[i].y-1;
        char a=op[i].a,b=op[i].b;
        if(a+32!=s[x])
        {
            if(b+32!=s[y])add(get(x,a,1),get(y,b,1)),add(get(y,b,0),get(x,a,0));
            else
                add(get(x,a,1),get(x,a,0));
        }
    }
    for(int i=0;i<2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=0;i<n;i++)
        if(id[i<<1]==id[i<<1|1])return false;
    for(int i=0;i<n;i++)
        if(id[i<<1]<id[i<<1|1])putchar(put(i,1));
        else
            putchar(put(i,2));
    return true;
}
int main()
{
    scanf("%d%d",&n,&d);
    scanf("%s",s);
    for(int i=0,j=0;s[i];i++)
        if(s[i]=='x')pos[j++]=i;
    scanf("%d",&m);
    for(int i=0;i<m;i++)scanf("%d %c %d %c",&op[i].x,&op[i].a,&op[i].y,&op[i].b);
    for(int i=0;i<1<<d;i++)
    {
        for(int j=0;j<d;j++)
            if(i>>j&1)s[pos[j]]='a';
            else
                s[pos[j]]='b';
        if(work())return 0;
    }
    puts("-1");
    return 0;
}