8/21 牛客补题+cf思维+tarjan

P3398 仓鼠找 sugar

题意：在一棵树上，给定四个点，在a和b的最短路径中能否在c和d的最短路径中相遇。
思路：可看出题目给了伪标签，不是tarjan的题。一道倍增lca的题。
1.若要满足相遇，则需要a和b的lca在c和d的最短路径上；或者c和d的lca在a和b的最短路径上。
2.在树中，判断一个点是否在一条路径上，可采用距离公式：dep[x]+dep[y]-2*dep[lca(x,y)]
3.满足条件为：DIS(c,x)+DIS(d,x)==DIS(c,d)，x为a和b的lca。
代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,q;
int dep[N];     //存u点的深度
int fa[N][20];  //存从u点向上跳2^i层的祖先节点
vector<int>e[N];
void dfs(int u,int pare)
{
    dep[u]=dep[pare]+1;
    fa[u][0]=pare;
    for(int i=1;i<=19;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:e[u])
        if(v!=pare) dfs(v,u);
}

//利用st表求lca
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--)
        //先跳到同一层
        if(dep[fa[u][i]]>=dep[v])
            u=fa[u][i];
    if(u==v)    return v;
    //跳到lca的下一层
    for(int i=19;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
        u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

int DIS(int x,int y)
{
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
bool check(int a,int b,int c,int d)
{
    int x=lca(a,b);
    if(DIS(c,x)+DIS(d,x)==DIS(c,d))
        return 1;
    return 0;
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    while(q--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(check(a,b,c,d)||check(c,d,a,b))
            cout<<"Y"<<endl;
        else
            cout<<"N"<<endl;
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    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

P2746 [USACO5.3]校园网Network of Schools

题意：为了使所有学校都用上软件，需要给几个学校发送软件；若是给任意一个学校发送了软件，就会分发搭配各个学校，则最少需要添加几条通信线路
思路：和之前做过的一道题类似。
1.先将各个强连通分量中的点看作一个点，进行tarjan的缩点操作。
2.根据原图建立缩点后的拓补图。
3.对于问题二，是将该拓扑图变成一个环，最少需要添加多少条边，取入读为0和出度为0中的较大值。
代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
vector<int>e[N],ne[N];
int dfn[N],low[N],tot;
int stk[N],instk[N],top;
int scc[N],siz[N],cnt;
int n,m,a[N],din[N],dout[N];
void tarjan(int x)
{
    //盖戳、入栈
    dfn[x]=low[x]=++tot;
    stk[++top]=x,instk[x]=1;
    for(int y:e[x])
    {
        if(!dfn[y])
        {
            tarjan(y);
            //回x时及时更新low
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) //若x已访问且在栈中
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]) //若x时SCC的根
    {
        int y;++cnt;
        do{
            y=stk[top--];instk[y]=0; //出栈
            scc[y]=cnt; //SCC编号
            ++siz[cnt];
        }while(y!=x);
    }
}

void solve()
{
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        while(cin>>x&&x)
            e[i].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
    {
        for(int j:e[i])
            if(scc[i]!=scc[j])
                din[scc[j]]++,dout[scc[i]]++;
    }
    int ans1=0,ans2=0;
    for(int i=1;i<=cnt;i++)
    {
        if(!din[i]) ans1++;
        if(!dout[i]) ans2++;
    }
    cout<<ans1<<endl;
    if(cnt==1)
        cout<<0<<endl;
    else
        cout<<max(ans1,ans2)<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    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

C. 3SUM Closure

题意：给定一个数组中，是否存在任意三个数相加都为数组中元素，数据范围是2e5。
思维：
1.首先暴力肯定被排除。此外可看出若出现三个以上正数或者负数，则一定会出现三个数相加结果
2.此外若出现元素0，出现两个在意义上即可以代表所有的0.
3.因此可筛选元素进行暴力。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,a[N];
vector<int>v1,v2,v3;
void solve()
{
    v1.clear();v2.clear();v3.clear();
    cin>>n;
    int a1=0,a2=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>0) a1++,v1.push_back(a[i]);
        if(a[i]<0) a2++,v2.push_back(a[i]);
        if(a[i]==0&&v3.size()<2) v3.push_back(a[i]);
    }
    if(a1>2||a2>2)
    {
        cout<<"NO"<<endl;return;
    }
    for(int i:v1) v3.push_back(i);
    for(int i:v2) v3.push_back(i);
    int g=v3.size();
    for(int i=0;i<g;i++)
    {
        for(int j=i+1;j<g;j++)
        {
            for(int k=j+1;k<g;k++)
            {
                int flag=0;
                for(int c=0;c<g;c++)
                    if(v3[i]+v3[j]+v3[k]==v3[c])
                        flag=1;
                if(!flag)
                {
                    cout<<"NO"<<endl;return;
                }
            }
        }
    }
    cout<<"YES"<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    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

C. Monoblock

题意：数值相同的块可合并，将任意段区间的块数累加，输出结果。每次可修改一个位置的值。
思路：算最近做的最难的一道思维题了。
1.数字的值仅和相邻位置的值有关，因此每次修改都要考虑相邻的值即可。
2.若a[x]==y，则直接输出答案；若不相等，需要和相邻两个元素值进行讨论。
3.对于两边的值的比较，在于影响到的区间数目。具体见代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,m,a[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[0]=a[n+1]=-1;
    int suf=1,ans=1,ls=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]!=a[i-1]) suf+=i,ans+=suf;
        else suf++,ans+=suf;
    }
    while(m--)
    {
        int x,y;cin>>x>>y;
        if(a[x]==y)
        {
            cout<<ans<<endl;continue;
        }
        if(y==a[x-1]&&a[x]!=a[x-1]) ans-=(n-x+1)*(x-1);
        if(y!=a[x-1]&&a[x]==a[x-1]) ans+=(n-x+1)*(x-1);
        if(y==a[x+1]&&a[x]!=a[x+1]) ans-=(n-x)*x;
        if(y!=a[x+1]&&a[x]==a[x+1]) ans+=(n-x)*x;
        cout<<ans<<endl;
        a[x]=y;
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    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

F-Shannon Switching Game?

思路：
1.两人一人删除路径，一人移动完路径后转移标记，并删除路径，即每次转移至少需要两条边转移到其他点上。
2.若从s走到t，需要判断经过改变的路径是否能走到t；不妨逆向考虑，从t走到s，通过广搜若能走到s，则赢得游戏

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e2;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,m,s,t,a[N][N],p[N];
vector<int>e[N],num[N];
bool vis[N];
queue<int>q;
void solve()
{
    cin>>n>>m>>s>>t;
    for(int i=0;i<=n;i++)
    {
        e[i].clear();
        num[i].clear();
        vis[i]=p[i]=0;
        for(int j=0;j<=n;j++)
            a[i][j]=0;
    }
    while(!q.empty())
        q.pop();
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        a[u][v]++;a[v][u]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        if(a[i][j])
        {
            e[i].push_back(j);
            num[i].push_back(a[i][j]);
        }
    }
    vis[t]=1;
    q.push(t);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=0;i<e[x].size();i++)
        {
            int y=e[x][i];
            p[y]+=num[x][i];
            if(p[y]>=2&&!vis[y])
                vis[y]=1,q.push(y);
        }
    }
    if(vis[s])
        cout<<"Join Player"<<endl;
    else
        cout<<"Cut Player"<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    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