当前位置：网站首页>8/7 牛客6+div2D+倍增lca

8/7 牛客6+div2D+倍增lca

2022-08-08 11:06:00 【钟钟终】

J Number Game

此题分析的差不多了，但是思路想到扩欧那里去了，越想越着急，便做不出了
思路：a的值不会改变，b的值会出现b和a-b两种
c 的值： 初始 c
第一轮： b-c 和 a-b-c
第二轮: a-2b+c 和 -a+2b+c
第三轮： -a+3b-c 和 2a-3b-c
第四轮: 2a-4b+c 和 -2a+4b+c
根据b和c的正负号可进行归类，奇数轮为一组，偶数轮为一组，得出四个公式：

  1. b-c+k(2b-a)
  2. a-b-c+k(a-2b)
  3. a-2b+c+k(a-2b)
  4. -a+2b+c+k(2b-a)
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int a,b,c,x;

signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>a>>b>>c>>x;
        int x1=b-c,x2=a-b-c,x3=a-2*b+c,x4=-a+2*b+c;
        if(b==a-b)
        {
    
            if(c==x||b-c==x)    cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else if((x-x1)%(2*b-a)==0||(x-x2)%(a-2*b)==0||(x-x3)%(a-2*b)==0||(x-x4)%(2*b-a)==0)
        {
    
            cout<<"Yes"<<endl;
        }
        else
            cout<<"No"<<endl;
    }
    return 0;
}

M. Z-Game on grid

题意很清楚，不过我还是没想到可以用dp去做，思路：
1.三种状态，f[i][j][0]表示从i行j列出发可否到达A ；f[i][j][1]表示从i行j列出发可否到达B ；f[i][j][2]表示从i行j列出发可否平局；
2.预处理:若该格子为A，则f[i][j][0]=1；若该格子为B，则f[i][j][1]=1；若n行m列没有其他字母，则f[i][j][2]=1（这个题目没说清楚）。
3.为保证无后效性，逆推状态。对于A来说，右边和下边若一旦出现了1，就肯定向A的方向走，则该格子必定为1；对于B来说，右边和下边若一旦出现了1，就肯定向不是A的方向走，只有当该格子右边和下变都为B时，该格子才为1

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m;
char mp[505][505];
bool f[505][505][3];
signed main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        cin>>n>>m;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
            f[i][j][0]=f[i][j][1]=f[i][j][2]=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
        {
    
            cin>>mp[i][j];
            if(mp[i][j]=='A') f[i][j][0]=1;
            else if(mp[i][j]=='B')
                f[i][j][1]=1;
        }
        if(mp[n][m]=='.')f[n][m][2]=1;
        for(int i=n;i>=1;i--)
        {
    
            for(int j=m;j>=1;j--)
            {
    
                if(i==n&&j==m) continue;
                if(i==n)
                {
    
                    f[i+1][j][0]=f[i][j+1][0];
                    f[i+1][j][1]=f[i][j+1][1];
                    f[i+1][j][2]=f[i][j+1][2];
                }
                if(j==m)
                {
    
                    f[i][j+1][0]=f[i+1][j][0];
                    f[i][j+1][1]=f[i+1][j][1];
                    f[i][j+1][2]=f[i+1][j][2];
                }
                if((i+j)&1) //Bob走
                {
    
                    if(mp[i][j]=='.'){
    
                    f[i][j][0]=max(f[i][j][0],f[i][j+1][0]&&f[i+1][j][0]);  //Bob能否走到A
                    f[i][j][1]=max(f[i][j][1],f[i][j+1][1]&&f[i+1][j][1]);  //Bob能否走到B
                    f[i][j][2]=max(f[i][j][2],f[i][j+1][2]&&f[i+1][j][2]);
                    }
                }
                else
                {
    
                    if(mp[i][j]=='.'){
    
                    f[i][j][0]=max(f[i][j][0],f[i][j+1][0]||f[i+1][j][0]);
                    f[i][j][1]=max(f[i][j][1],f[i][j+1][1]||f[i+1][j][1]);
                    f[i][j][2]=max(f[i][j][2],f[i][j+1][2]||f[i+1][j][2]);
                    }
                }
            }
        }
        if(f[1][1][0])  cout<<"yes ";
        else    cout<<"no ";
        if(f[1][1][2])  cout<<"yes ";
        else    cout<<"no ";
        if(f[1][1][1])  cout<<"yes"<<endl;
        else    cout<<"no"<<endl;
    }
    return 0;
}

倍增lca

模板：

int dep[N];     //存u点的深度
int fa[N][20];  //存从u点向上跳2^i层的祖先节点
vector<int>e[N];
void dfs(int u,int pare)
{
    
    dep[u]=de[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;
    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];
}

Eezie and Pie

倍增lca+树上差分

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N =2e6+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,d[N],num[N],ans[N];
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);
}
void dfs2(int u,int pare)
{
    
    for(int i=0;i<e[u].size();i++)
    {
    
        int v=e[u][i];
        if(v!=pare)
        {
    
            dfs2(v,u);
            num[u]+=num[v];
            ans[u]+=ans[v];
        }
    }
    ans[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];
}
signed main()
{
    
    cin>>n;
    for(int i=1;i<n;i++)
    {
    
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
    
        cin>>d[i];
        num[i]=ans[i]=0;
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
    
        int g=min(d[i],dep[i]-1); //可经过的路径长度
        g=dep[i]-g;    //向上最大可跳到到的层数
        int u=i;
        for(int j=19;j>=0;j--) //跳到第g层
            if(dep[fa[u][j]]>=g)
                u=fa[u][j];
        num[fa[u][0]]--;  //标记该子树中不能到达的节点数
    }
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]+num[i]<<" ";
    cout<<endl;
    return 0;
}

P3128 [USACO15DEC]Max Flow P

不明白这模板哪错了，看了2个消失了，快烦死了 哭……
啊啊，我真的蠢，卧槽，我没有调用深搜函数。。。。
思路：就是将每次询问u，v的路径上经过的点+1，通过倍增实现。
方式：++cnt[u],++cnt[v],--cnt[g],--cnt[fa[g][0]];

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int N =2e6+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,cnt[N],ans;
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 dfs2(int u,int pare)
{
    
    for(int i=0;i<e[u].size();i++)
    {
    
        int v=e[u][i];
        if(v!=pare)
        {
    
            dfs2(v,u);
            cnt[u]+=cnt[v];
        }
    }
    ans=max(ans,cnt[u]);
}
signed main()
{
    
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
    
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cout<<lca(2,3)<<endl;
    dfs(1,0)
    for(int i=1;i<=m;i++)
    {
    
        int u,v;cin>>u>>v;
        int g=lca(u,v);
        //cout<<lca<<endl;
        ++cnt[u],++cnt[v],--cnt[g],--cnt[fa[g][0]];
    }
    dfs2(1,0);
    cout<<ans<<endl;
    return 0;
}
原网站

版权声明
本文为[钟钟终]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51934288/article/details/126215138

边栏推荐

猜你喜欢

随机推荐