2022天梯赛

拓扑排序 dfs序 记忆化搜索 剪枝
算法
发布日期:   2022-04-27
更新日期:   2022-04-27
文章字数:   3k
阅读时长:   15 分
阅读次数:  

2022天梯赛

L1

L1的题目冲的非常快，就败在了L2-1的模拟题，主要是种种原因后面心态炸了

L1-7

赛场上我用容斥写的
但是听说下面这种解法更简便

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int visn[100010],vism[100010];
#define int long long
int n,m,k,op,x;
signed main(){
    cin>>n>>m>>k;
    while(k--){
        cin>>op>>x;
        if(op==0)
            if(!visn[x])n--,visn[x]=1;
        if(op==1)
            if(!vism[x])m--,vism[x]=1;
    }
    cout<<n*m;
}

L1-8

对权值进行维护就好了

L2-1

天梯赛就三个小时占了我
这个一个半小时的题目，我觉得写不出来一是基础不扎实，二就是当时心态炸了，后面根本没心思调

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
queue<int>q;
stack<int>stk;
int n,m,k;
vector<vector<int>>ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q.push(x);
    }
    vector<int>t;
    int cnt=1;
    while(q.size()||stk.size()){
//         cout<<"cnt="<<cnt<<endl;
        //if(++cnt>20)break;
        if(stk.empty()&&q.size()){
            int x=q.front();
            //cout<<"x="<<x<<endl;
            if(t.size()==0)t.push_back(x),q.pop();
            else if(x<=t.back())t.push_back(x),q.pop();
            else stk.push(x),q.pop();
            if(t.size()==k)ans.push_back(t),t.clear();
        }
        else{
            //如果栈符合要求就塞进去
            int x;
            x=stk.top();
            //cout<<"x="<<x<<endl;
            if(t.size()==0)t.push_back(x),stk.pop();
            else if(x<=t.back())t.push_back(x),stk.pop();
            else if(q.size()){
                //说明栈不能放
                //从队列里面找
                x=q.front();
                //cout<<"x="<<x<<endl;
                if(x<=t.back())t.push_back(x),q.pop();
                else if(stk.size()<m)stk.push(x),q.pop();
                else ans.push_back(t),t.clear();
            }
            else ans.push_back(t),t.clear();
            if(t.size()==k)ans.push_back(t),t.clear();
            
        }
    }
    if(t.size())ans.push_back(t);
    for(auto t:ans){
        cout<<t[0];
        for(int i=1;i<t.size();i++)cout<<" "<<t[i];
        cout<<'\n';
    }
}

L2-2

垃圾题
傻逼题

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    int h,m,s,hh,mm,ss;
    bool operator<(const node&t){
        if(h!=t.h)return h<t.h;
        if(m!=t.m)return m<t.m;
        return s<t.s;
    }
}a[100010];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d:%d:%d - %d:%d:%d",&a[i].h,&a[i].m,&a[i].s,&a[i].hh,&a[i].mm,&a[i].ss);
    }
    sort(a+1,a+1+n);
    int ph=0,pm=0,ps=0;
    for(int i=1;i<=n;i++){
        int h=a[i].h,m=a[i].m,s=a[i].s,hh=a[i].hh,mm=a[i].mm,ss=a[i].ss;
        if(ph==h&&pm==m&&ps==s);//printf("%02d:%02d:%02d - %02d:%02d:%02d\n",a[i].h,a[i].m,a[i].s,a[i].hh,a[i].mm,a[i].ss);
        else printf("%02d:%02d:%02d - %02d:%02d:%02d\n",ph,pm,ps,a[i].h,a[i].m,a[i].s);
        ph=hh,pm=mm,ps=ss;
    }
    if(ph!=23||pm!=59||ps!=59)printf("%02d:%02d:%02d - %02d:%02d:%02d\n",ph,pm,ps,23,59,59);
}

L2-3

就是个典型的小树形dp，但是赛场上没思路，感觉把时间丢在这道题而不是L2-1的模拟应该可以冲
题目要求的是最后不用回来的总代价距离最小值
但是对确切的外卖点，往返各一次是确定的，所以很显然预处理到根的距离，剪掉要送外卖的地点集合的最大值就好了

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long
vector<int>g[N];
int vis[N],n,m,fa[N],ans,ma,f[N],x;
void dfs(int u){
    for(auto j:g[u]){
        f[j]=f[u]+1;
        dfs(j);
    }
}
int dfs(int x,int d){
    if(vis[x]){
        ma=max(ma,f[x]+d);
        return d*2;
    }
    vis[x]=1;
    return dfs(fa[x],d+1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int u;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        if(fa[i]==-1)u=i;
        else g[fa[i]].push_back(i);
    }
    dfs(u);
    vis[u]=1;
    while(m--){
        cin>>x;
        ans+=dfs(x,0);
        //cout<<"ans="<<ans<<" ma="<<ma<<endl;
        cout<<ans-ma<<'\n';
    }
}

L2-4

一样的代码，赛场上超时只有15分，现在一发满分，我tm当时还全删了重写浪费我时间！
傻逼东西rnm退钱！

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
#include<bits/stdc++.h>
using namespace std;
const int N=550;
int f[N][N],n,d[N],a[N];
int ans[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='M')a[i]=1;
        int m;
        cin>>m;
        while(m--){
            int x,y;
            cin>>x>>c>>y;
            f[i][x]=y;
        }
    }
    for(int k=1;k<=n;k++)f[k][k]=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                //f[j][i]=min(f[j][i],f[j][k]+f[k][i]);
            }
        }
    }
    vector<int>ans1,ans0;
    int a1=0x3f3f3f3f;
    int a0=0x3f3f3f3f;
    //memset(ans,0x3f,sizeof ans);
    //求到我的，且为异性的最大值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i]!=a[j])ans[j]=max(ans[j],f[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i])a1=min(a1,ans[i]);
        else a0=min(a0,ans[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]&&ans[i]==a1)ans1.push_back(i);
        if(!a[i]&&ans[i]==a0)ans0.push_back(i);
    }
    swap(ans1,ans0);
    cout<<ans1[0];
    for(int i=1;i<ans1.size();i++)cout<<" "<<ans1[i];
    cout<<'\n';
    cout<<ans0[0];
    for(int i=1;i<ans0.size();i++)cout<<" "<<ans0[i];
    
}

L3-1

比较裸的拓扑排序，根据数字的大小关系建边，如果我比你大，那么你会向我连一条边，我入度加加
入度相等的时候用字符串大小来排序，可以用优先队列来处理

我在打比赛的时候往L3瞄了一下，感觉第一题其实可以做，也对着样例一眼就看出来要纵向判断建边
但是“入度相等的时候用字符串大小来排序”，这里我脑抽了，没有想到用优先队列，加上前面的L2还没写完，因为分数没拿够L3不算分
所以跑去写L2了，这波属实是拉跨啊我靠，要是顺利切掉L2-1的话能水230分，百分百国二

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
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int>mp,d;
string S[100010];
vector<vector<string>>ans;
vector<int>g[10010];
int n,idx;
vector<string>v,res;
string s;
priority_queue<string,vector<string>,greater<string>>q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        s+='.';
        string t="";
        for(auto c:s){
            if(c=='.'){
                if(!mp.count(t))mp[t]=++idx,S[idx]=t;
                v.push_back(t),t="";
            }
            else t+=c;
        }
        
        ans.push_back(v);
        v.clear();
    }
//     for(auto v:ans){
//         for(auto t:v)cout<<t<<".";
//         cout<<endl;
//     }
    for(int i=1;i<n;i++){
        if(ans[i].size()!=ans[i-1].size())continue;
        for(int j=0;j<ans[i].size();j++){
            if(ans[i-1][j]!=ans[i][j]){
                int a=mp[ans[i-1][j]];
                int b=mp[ans[i][j]];
                g[a].push_back(b);
                d[ans[i][j]]++;
                //cout<<"aaa"<<endl;
                break;
            }
        }
    }
//     for(int i=1;i<=idx;i++){
//         cout<<S[i]<<": ";
//         for(auto j:g[i])cout<<i<<j<<" ";
//         cout<<endl;
//     }
    for(auto &[k,v]:mp){
        if(d[k]==0)q.push(k);
    }
    while(q.size()){
        string u=q.top();
        q.pop();
        res.push_back(u);
        for(auto t:g[mp[u]]){
            if(--d[S[t]]==0)q.push(S[t]);
        }
    }
    cout<<res[0];
    for(int i=1;i<res.size();i++)cout<<"."<<res[i];
}

经典题
首先，我们对于这个树上两个结点的关系分为两类，一类是有直接父子或祖先关系的结点对，这样的结点对在DFS序中的顺序是确定的，一定是父亲在前面，儿子在后面，那么这样的结点对，如果是逆序对，一定会出现在每一种DFS序中，所以，这样的逆序对的贡献就是这个树的DFS序的种类数。另外一类就是不具有直接父子或祖先关系的结点对，这样的结点对在每种DFS序中的顺序不固定，但是我们经过观察完全可以发现（我发现不了，杜喻皓大爹说了我才知道 ），这样的结点对要不然是逆序对，要不然不是逆序对，概率都是1/2，那么从期望的角度考虑，这样的结点对对于答案的贡献其实就是这个树的DFS序的种类数除以2

那么如何求解一颗树的DFS序种类数呢，其实很简单对于一颗子树u，它的DFS序的种类数就是它的所有子树的方案数的乘积，再乘上u的子树个数的全排列（也就是阶乘），然后向上递推就行。第二个问题，如何求解两种点对的数目。首先我们知道，对于n个点能组合出来的总点对数是n*(n-1)/2，那么只要求出其中一类的个数，另外一类就知道了，我们选择求解上述第一类的个数，令 d[i] 表示以 i 为根节点的子树第一类结点对的数目，很容易观察得到，其实就是以 i 为根节点的子树中 i 有多少个孩子or孙子，那么这个自然也可以向上递推。第三个问题，如何计算第一类结点对中逆序对的个数，我们令 mx[i] 表示从结点 i 出发往上遍历直到根节点，有多少个比它大的结点数，这个在DFS的过程中在值域上建立树状数组就可以统计。

L3-2

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
int n,root,tr[N],fac[N],A,B,K,son[N],f[N],mx[N],ans,d[N];
vector<int>g[N];
void add(int x,int c){
    for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
}
int sum(int x){
    int ans=0;
    for(int i=x;i;i-=i&-i)ans+=tr[i];
    return ans;
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return ans;
}
void dfs(int u,int fa){
    mx[u]=sum(n)-sum(u);
    add(u,1);
    f[u]=1;
    for(auto j:g[u]){
        if(j==fa)continue;
        son[u]++;
        dfs(j,u);
        f[u]=(f[u]*f[j])%mod;
        d[u]+=d[j];
    }
    d[u]+=son[u];
    f[u]=f[u]*fac[son[u]]%mod;
    add(u,-1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>root;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    dfs(root,-1);
    K=f[root];
    
    //计算第一类节点对的贡献
    for(int i=1;i<=n;i++)ans=(ans+mx[i]*K%mod)%mod;
    
    //计算第二类节点对的贡献
    int t=n*(n-1)%mod*qpow(2,mod-2)%mod;
    for(int i=1;i<=n;i++)A=(A+d[i])%mod;
    B=(t-A+mod)%mod;
    B=(B*qpow(2,mod-2)%mod)%mod;
    ans=(ans+B*K%mod)%mod;
    
    cout<<ans;
}

csoj还几乎有道原题传送门
求期望的话不要计算dfs序种类数，删去取模操作

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
int n,root,tr[N],fac[N],son[N],f[N],mx[N],d[N];
double A,B,K,ans;
vector<int>g[N];
void add(int x,int c){
    for(int i=x;i<=n;i+=i&-i)tr[i]+=c;
}
int sum(int x){
    int ans=0;
    for(int i=x;i;i-=i&-i)ans+=tr[i];
    return ans;
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=(ans*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return ans;
}
void dfs(int u,int fa){
    mx[u]=sum(n)-sum(u);
    add(u,1);
    for(auto j:g[u]){
        if(j==fa)continue;
        son[u]++;
        dfs(j,u);
        d[u]+=d[j];
    }
    d[u]+=son[u];
    add(u,-1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>root;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(root,-1);
    //计算第一类节点对的贡献
    for(int i=1;i<=n;i++)ans+=mx[i];
    
    //计算第二类节点对的贡献
    double t=(double)n*(n-1)/2;
    for(int i=1;i<=n;i++)A=(A+d[i]);
    B=(t-A)/2;
    ans+=B;
    printf("%.1lf",ans);
}

L3-3

1

文章作者: 胡耀文
文章链接: https://hyw200199.github.io/2022/04/27/2022-tian-ti-sai/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 胡耀文 !
拓扑排序 dfs序 记忆化搜索 剪枝
赏
  目录