比赛地址：Dashboard - 2024 Xian Jiaotong University Programming Contest - Codeforces

记录下一个人vp整场比赛。

西交校赛蒸不错。

A、B、C、F

签到

D

题意：给出 $n$ 个点与 $m$ 个形如 $i,j$ 的限制条件，表示 $i$ 是 $j$ 的直接父亲。限构造一棵树，对于每个条件，若满足分数+1，若不满足分数-1，若两者互不支配那么分数不变。最终要使分数非负。

考虑构造“菊花树”，即设 $i$ 为根节点，则其有 $n-1$ 个儿子。那么应该满足在所有的 $m$ 个关系 $i,j$ 中，根节点出现在 $i$ 的次数应大于等于出现在 $j$ 次数，这样可以保证分数非负。

简单分析知一定存在一个点满足。

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
#include<bits/stdc++.h>
using namespace std;

int t[100005];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        t[x]++;
        t[y]--;
    }
    int rt;
    for(int i=1;i<=n;i++)
    {
        if(t[i]>=0)
        {
            rt=i;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
       cout<<(i==rt?0:rt)<<" ";
    }
    return 0;
}

E

题意：有 $n$ 座房子从左到右排成一排，然后依次登上每一座房子，并记下所有之前登过的房子中，比当前房子矮的房子中最高的房子的编号。若没有即为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
#include<bits/stdc++.h>
using namespace std;

int nxt[200005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        nxt[i]=nxt[x];
        nxt[x]=i;
    }

    int i=0;
    while(nxt[i]!=0)
    {
        cout<<nxt[i]<<" ";
        i=nxt[i];
    }
    return 0;
}

链表

I

题意：有 $n$ 个互不相同的小写字母模式串 $t_i$，输入区是一个字符串 $s$ ，接受小写字母与 $E,T,B$ 。$E$ 表示若存在 $t_i=s$ ，那么输出 $i$ 并清空 $s$；$B$ 表示删除 $s$ 最后一个字符；若为 $T$ ，那么将所有以 $s$ 为前缀的字符串存为集合 $A$ ，将 $s$ 变成所有 $A$ 的最长公共前缀。

字典树的题。对于 $E,B$ 很好实现，只需要在字典树上多维护一个每个节点的父亲是谁，那么在 $B$ 的时候指针 $p$ 就可以直接回到父亲。

对于 $T$ ，在字典树上额外维护下一次跳转节点 $nxt[]$ 数组：若当前节点只有一个儿子，那么直接跳转到儿子；如果有多个儿子，那么跳转到本身。特别的如果当前节点是一个模式串的结束，那么也跳转到本身。

但是注意在实际输入 $s$ 进行跳转时要利用好路径压缩，不然会超时。

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
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

int tr[1000001][26];
int tot=1;
int jp[1000006];
int n,m;
int al[1000006];
int ed[1000006];
int son[1000006];
int lian[1000006];
char ans[1000006];
int fa[1000006];
int cnt;

void build(int id,char *str)
{
    int p=1;
    int len=strlen(str);
    for(int i=0;i<len;i++)
    {
        int ch=str[i]-'a';
        if(tr[p][ch]==0)
        {
            son[p]++;
            tr[p][ch]=++tot;
        }

        if(son[p]==1 && !ed[p])jp[p]=tr[p][ch];
        else jp[p]=p;

        fa[tr[p][ch]]=p;
        p=tr[p][ch];   
    }
    ed[p]=id;
    jp[p]=p;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    fa[1]=1;
    for(int i=1;i<=n;i++)
    {
        char str[1000006];
        cin>>str;
        al[i]=strlen(str);
        build(i,str);
    }

    int p=1;
    for(int i=1;i<=m;i++)
    {
        char c;
        cin>>c;

        if(c>='a' && c<='z')
        {
            if(tr[p][c-'a']==0)
            {
                tr[p][c-'a']=++tot;
                fa[tr[p][c-'a']]=p;
            }
            
            p=tr[p][c-'a'];
        }

        if(c=='B')
        {
            cnt--;
            p=fa[p];
        }

        if(c=='T')
        {
            int tp=p;
            while(jp[p]!=p && jp[p])
            {
                p=jp[p];
            }
            jp[tp]=p;
        }

        if(c=='E')
        {
            if(ed[p])cout<<ed[p]<<" ";
            else cout<<-1<<" ";
            p=1;
        }
    }
    return 0;
}

字典树

K

题意：一个队伍有四个人，三种职业，一共有五个技能存储点，普攻增加一点技能点，放技能消耗一点技能点，每一回合按照人物顺序操作，每一回合一个人操作。职业1只能普攻，职业2有技能点一定放技能，否则普攻，职业3随意。现在初始有 $k$ 技能点，问 $n(n\leq1e18)$ 回合中一共有多少种不同的操作方案。

在 $n$ 小时可以直接写出 $dp$ 方程递推，但是 $n$ 特别大，因此考虑矩阵加速。

设 $f_i(n)$ 表示当前技能点为 $i$ ，且经过了 $n$ 回合后的方案数。那么有：

设 $P=\Pi_{i=1}^{4}A_i$ ，$A_i$ 为人物对应的矩阵。那么就有：
$$
f(n)=f(0)P^{\lfloor \frac{n}{4}\rfloor}\Pi_{i=1}^{n\ mod\ 4}A_i
$$

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
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod=998244353;
const int N=6;

int m1[6][6]={{0,1,0,0,0,0},
              {0,0,1,0,0,0},
              {0,0,0,1,0,0},
              {0,0,0,0,1,0},
              {0,0,0,0,0,1},
              {0,0,0,0,0,1}};

int m2[6][6]={{0,1,0,0,0,0},
              {1,0,0,0,0,0},
              {0,1,0,0,0,0},
              {0,0,1,0,0,0},
              {0,0,0,1,0,0},
              {0,0,0,0,1,0}};

int m3[6][6]={{0,1,0,0,0,0},
              {1,0,1,0,0,0},
              {0,1,0,1,0,0},
              {0,0,1,0,1,0},
              {0,0,0,1,0,1},
              {0,0,0,0,1,1}};            

int n,k;
int p[5];
int ini[6];
int a[N][N];
int ans[6][6];

int tmp[N][N];
void multi(int a[][N],int b[][N],int nn)
{
    memset(tmp,0,sizeof tmp);
    for(int i=0;i<nn;i++)
        for(int j=0;j<nn;j++)
            for(int k=0;k<nn;k++)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j]%mod)%mod;
    for(int i=0;i<nn;i++)
        for(int j=0;j<nn;j++)
            a[i][j]=tmp[i][j];
}

int res[N][N];

void Pow(int a[][N],int nn)
{
    while(nn)
    {
        if(nn&1)
            multi(res,a,N);//res=res*a;复制直接在multi里面实现了；
        multi(a,a,N);//a=a*a
        nn>>=1;
    }
}

signed main()
{
    cin>>n>>k>>p[1]>>p[2]>>p[3]>>p[4];
    ini[k]=1;
    a[0][0]=a[1][1]=a[2][2]=a[3][3]=a[4][4]=a[5][5]=1;

    for(int i=1;i<=4;i++)
    {
        if(p[i]==1)multi(a,m1,6);
        if(p[i]==2)multi(a,m2,6);
        if(p[i]==3)multi(a,m3,6);
    }
    
    for(int i=0;i<N;i++) res[i][i]=1;
    if(n/4>0)Pow(a,n/4);

    for(int i=1;i<=n%4;i++)
    {
        if(p[i]==1)multi(res,m1,6);
        if(p[i]==2)multi(res,m2,6);
        if(p[i]==3)multi(res,m3,6);
    }

    int sum=0;
    for(int i=0;i<N;i++)
        sum=(sum+res[k][i])%mod;
    cout<<sum;
    return 0;
}

math，dp

M

题意：给出一棵树，每一轮将度为 $k$ 的点以及相连的边同时删去，问无穷多轮后连通块的个数。

直接模拟即可。每次删除只会影响相邻的点的度，每次删除后把相邻点度变为 $k$ 的点纳入集合下一轮删除即可。

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
#include<bits/stdc++.h>
using namespace std;

int n,k;
vector<int>g[1000006];
vector<int>s;
int d[1000006];
int del[1000006];
int cnt;
int v[1000006];

void dfs(int now)
{
    for(auto to:g[now])
    {
        if(del[to])continue;
        del[to]=1;
        dfs(to);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;

    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        d[u]++;
        d[v]++;
    }

    for(int i=1;i<=n;i++)
    {
        if(d[i]==k)
        {
            s.push_back(i);
        }
    }

    while(s.size())
    {
        vector<int>tmp;
        for(auto p:s)
        {
            del[p]=1;
            for(auto to:g[p])
            {
                d[to]--;
                if(d[to]==k)tmp.push_back(to);
            }
            
        }
        
        s.clear();
        for(auto p:tmp)
        {
            if(d[p]==k)s.push_back(p);
        }
    }

    // for(int i=1;i<=n;i++)
    // {
    //     if(!del[i])cout<<i<<" ";
    // }cout<<endl;

    for(int i=1;i<=n;i++)
    {
        if(del[i]==0)cnt++,del[i]=1,dfs(i);
    }
    cout<<cnt;
    return 0;
    
}

O

题意：给定 $n$ ，求 $\sum_{i=1}^n\sum_{j=1}^n\lfloor\frac n{\max(i,j)}\rfloor[i\perp j]$ 的值。

打表可知答案即 $n^2$ 。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long x;
    cin>>x;
    x*=x;
    cout<<x;
    return 0;
}