G. SlavicG‘s Favorite Problem(DFS序) 2022绵阳H(思维构造),M(并查集)

最近组队vp大概都在稳铜位置，水平和预选赛排在300-400的队伍相当，加油，到最后了。
G. SlavicG’s Favorite Problem
作为div4的最后一题虽然没有算法难度但是把思维拉满了。

题意：给定一棵树，每个边都边权，现在给定源点a和终点b，请问你能否找到一种方案使得在从a走到b只是用一次传送的前提下使得走过的路径上所有的边权异或和为0。能输出YES，反之输出NO

传送：从一个点到任意一个不是b的点上的。

思路：首先考虑到从a点直接深搜，如果能够到b的时候权值为0自然是yes。

那么如果不能呢？我想大概是需要传送操作来结合两段路径才行，也就是说，选择两段路径，一段起点是a，一段终点是b，这两段路径的权值异或和为0即可。

那么维护这样的权值异或和显然做两次DFS深搜即可，一次a为根，一次b为根。但是要怎么确保这两段是合法的呢，或者说什么情况下是不合法的呢。

既然b是题目意义上的终点，显然是不可以重复走过b的。考虑把b为根的所有路径的异或和存储，然后在a为根的情况下，找到所有不包含b的路径，只要能在这两种意义下找到两条异或和一样的路径即可。

那么不包含b的路径怎么找呢，这里用dfs序，如果a为根时，b子树内的节点dfs序必定比b大，而要论子树内部dfs序的最大值，b是要大于其内部所有节点的。这样就可以轻松判断了。

#include
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=1e5+100;
struct node
{
    int nex,to,w;
}edge[N<<1];
int head[N],tot;
int n,a,b;
int dfn[N][2],mdfn[N][2];
int val[N][2],cnt;
void add(int from,int to,int w)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
    edge[tot].w=w;
}
void DFS(int now,int fa,int falg)
{
    dfn[now][falg]=++cnt;
    for(int i=head[now];i;i=edge[i].nex)
    {
        int to=edge[i].to;
        if(to==fa)
            continue;
        val[to][falg]=(val[now][falg]^edge[i].w);
        DFS(to,now,falg);
    }
    mdfn[now][falg]=cnt;
}
void init()
{
    for(int i=0;i<=n;i++)
       head[i]=dfn[i][1]=dfn[i][0]=mdfn[i][0]=mdfn[i][1]=0;
    for(int i=0;i<=tot;i++)
        edge[i].nex=edge[i].to=edge[i].w=0;
    tot=0;cnt=0;
}
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        cin>>n>>a>>b;
        for(int i=1,u,v,w;i<=n-1;i++)
        {
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        cnt=val[a][0]=0;
        DFS(a,0,0);
        cnt=val[b][1]=0;
        DFS(b,0,1);
        if(!val[b][0])
            cout<<"Yes"<<endl;
        else
        {
            map<int,int>mp;
            for(int i=1;i<=n;i++)
            {
                if(i==b)
                continue;
                mp[val[i][1]]=1;
            }
            bool falg=false;
            for(int i=1;i<=n;i++)
            {
                if(dfn[i][0]>=dfn[b][0]&&mdfn[i][0]<=mdfn[b][0])
                    continue;
                if(mp.find(val[i][0])!=mp.end())
                {
                    falg=true;
                    break;
                }
            }
            if(falg)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        init();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

M. Rock-Paper-Scissors Pyramid(并查集，思维)

题意：给定s代表剪刀，p代表布，r代表石头，给定一个只含有psr的串，相邻的两个字母根据剪刀石头布的规则来产生胜者，不断决胜可以将整个game产生的出手过程视为金字塔。

问，金字塔顶端谁赢。

思路：我们发现每次被吞并的都是相对位置在左侧的字母所以并查集吞就可以了。至于可以吞掉的字母就是这个字母能赢得和等于这个字母的。

#include 
using namespace std;
#define endl '\n'
const int N = 1e6+100;
int dsu[N];
char s[N];
int tfind(int x)
{
    if(x==dsu[x])
        return x;
    return dsu[x]=tfind(dsu[x]);
}
void tmerge(int x,int y)
{
    x=tfind(x);
    y=tfind(y);
    if(x==y)
        return ;
    dsu[y]=x;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    map<char,char>mp;
    mp['S']='P';mp['P']='R';mp['R']='S';
    for(cin>>t;t;t--)
    {
        cin>>(s+1);
        int n=strlen(s+1);
        for(int i=1;i<=n;i++)
            dsu[i]=i;
        for(int i=2;i<=n;i++)
        {
            if(mp[s[i]]==s[i-1]||s[i]==s[i-1])
            {
                int j=i-1;
                while(j>0&&(mp[s[i]]==s[j]||s[i]==s[j]))
                {
                    tmerge(j-1,j);
                    j=tfind(j);
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(dsu[i]==i)
            {
                cout<<s[i]<<endl;
                break;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

Life is Hard and Undecidable, but

题意：在二维的图上，如果一个空位置周围有且仅有三个点则空位置会出生一个点，如果一个点周围不是2或者3个且仅2或者3个点则这个点会在下次回合消失，否则其将继续存活。

现在想要再n论后平面上无点存在，那么应该构造一个什么样的图，请你输出。
思路：这个题如果想到正确思路则是一个div2的A级别，但是想不到就完犊子了
直接构造n*2长度的斜线即可。

#include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e6+100;
char ch[N];
int s[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n;
    cin>>n;
    int x1=1,y1=1;
    cout<<n*2<<endl;
    for(int i=1;i<=n*2;i++)
    {
        cout<<x1<<" "<<y1<<endl;
        x1++;
        y1++;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23