F-选座椅_牛客小白月赛61 (nowcoder.com) 双指针，差分，2021济南ICPC- K Search For Mafuyu (pintia.cn) dfs

98 阅读 0 评论 65 点赞

我是靠谱客的博主酷酷鸡，这篇文章主要介绍F-选座椅_牛客小白月赛61 (nowcoder.com) 双指针，差分，2021济南ICPC- K Search For Mafuyu (pintia.cn) dfs，现在分享给大家，希望可以做个参考。

F-选座椅_牛客小白月赛61 (nowcoder.com) 双指针，差分

如果区间[l,r]满足所有条件，那么包含[l,r]的区间也一定是满足条件的，那就考虑双指针遍历每一个区间，如果当前区间满足条件，那么当前的长度，以及大于他的长度就都是符合条件的，价值就加一，即[r-l+1,n-l+1]都要加上1的方案数，最后每个长度的方案数乘以阶乘累加起来就是答案，因为人是不同的所以要乘以一个全排列

【比赛题目讲解】牛客小白月赛61_哔哩哔哩_bilibili

复制代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
int n,m,a[N],b[N],c[N],cnt[N],sum,fac[N],ans[N];
vector<int>v[N];
void add(int p)
{
    for(auto x:v[p])
    {
        cnt[x]++;
        if(cnt[x]==1) sum++;
    }
}
void del(int p)
{
    for(auto x:v[p])
    {
        cnt[x]--;
        if(cnt[x]<=0) sum--;
    }
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;sum=0;fac[0]=1;
    for(int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=m;i++) cin>>c[i];
    for(int i=1;i<=m;i++)
    {
        set<int>s;
        s.insert(a[i]);s.insert(b[i]);s.insert(c[i]);
        for(auto x:s)
        {
            v[x].push_back(i);
        }
    }
    for(int i=1,j=0;i<=n;i++)
    {
        while(j+1<=n&&sum<m) j++,add(j);
        if(sum==m)
        {
            ans[j-i+1]++;
            ans[n-i+2]--;
        }
        del(i);
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]+=ans[i-1];
        int res=ans[i]*fac[i]%mod;
        cout<<res;
        if(i!=n) cout<<" ";
    }
    pause;
    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
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
int n,m,a[N],b[N],c[N],cnt[N],sum,fac[N],ans[N];
vector<int>v[N];
void add(int p)
{
    for(auto x:v[p])
    {
        cnt[x]++;
        if(cnt[x]==1) sum++;
    }
}
void del(int p)
{
    for(auto x:v[p])
    {
        cnt[x]--;
        if(cnt[x]<=0) sum--;
    }
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;sum=0;fac[0]=1;
    for(int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=m;i++) cin>>c[i];
    for(int i=1;i<=m;i++)
    {
        set<int>s;
        s.insert(a[i]);s.insert(b[i]);s.insert(c[i]);
        for(auto x:s)
        {
            v[x].push_back(i);
        }
    }
    for(int i=1,j=0;i<=n;i++)
    {
        while(j+1<=n&&sum<m) j++,add(j);
        if(sum==m)
        {
            ans[j-i+1]++;
            ans[n-i+2]--;
        }
        del(i);
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]+=ans[i-1];
        int res=ans[i]*fac[i]%mod;
        cout<<res;
        if(i!=n) cout<<" ";
    }
    pause;
    return 0;
}

2021济南ICPC- K Search For Mafuyu (pintia.cn) dfs

因为概率是一样的所以算出所有情况的步数然后再乘以概率就是期望了，最佳策略就是已经走过的点不会无缘无故的再去走了，正是因为这一点所以概率dp是不适用的，因为已经走过的点一定是不满足条件的点了；

手玩一下样例就可以知道怎么走了，然后再用代码实现掉就可以

复制代码

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
int t,n,head[N],siz[N],f[N],cnt,ans;
struct Edge
{
    int nxt,to;
}e[N];
void addedge(int from,int to)
{
    e[++cnt].nxt=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
void dfs1(int u,int fa)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int j=e[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
    }
}
void dfs(int u,int fa)
{
    f[u]=f[fa]+1;
    ans+=f[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int j=e[i].to;
        if(j==fa) continue;
        dfs(j,u);
        f[u]+=siz[j]*2;
    }
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            addedge(u,v);
            addedge(v,u);
        }
        dfs1(1,0);
        f[0]=-1;ans=0;
        dfs(1,0);
        double res=ans*1.0/(n-1.0);
        cout<<fixed<<setprecision(10)<<res<<endl;
        for(int i=1;i<=cnt;i++) e[i].nxt=e[i].to=0;
        for(int i=1;i<=n;i++) head[i]=0;cnt=0;
    }
    pause;
    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
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl 'n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e18;
int t,n,head[N],siz[N],f[N],cnt,ans;
struct Edge
{
    int nxt,to;
}e[N];
void addedge(int from,int to)
{
    e[++cnt].nxt=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
void dfs1(int u,int fa)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int j=e[i].to;
        if(j==fa) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
    }
}
void dfs(int u,int fa)
{
    f[u]=f[fa]+1;
    ans+=f[u];
    for(int i=head[u];i;i=e[i].nxt)
    {
        int j=e[i].to;
        if(j==fa) continue;
        dfs(j,u);
        f[u]+=siz[j]*2;
    }
}
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            addedge(u,v);
            addedge(v,u);
        }
        dfs1(1,0);
        f[0]=-1;ans=0;
        dfs(1,0);
        double res=ans*1.0/(n-1.0);
        cout<<fixed<<setprecision(10)<<res<<endl;
        for(int i=1;i<=cnt;i++) e[i].nxt=e[i].to=0;
        for(int i=1;i<=n;i++) head[i]=0;cnt=0;
    }
    pause;
    return 0;
}