题目1:AcWing 4742.电

某城市有 N 个电力节点，编号 1∼N。

这些电力节点形成的电力网络，可以看作一个 N 个节点 N−1 条边的连通图。

每个电力节点都有一个固定的电容，其中第 i 个节点的电容为 Ai。

现在，可以选择其中一个节点进行供电，其它节点也可以根据实际连接以及具体电容情况接收电力。

具体来说，如果第 i 个节点通电，那么它也可以将电力传输给其它所有与它直接连接且电容严格小于 Ai 的节点。

我们希望通过合理选择初始供电节点，从而使得尽可能多的节点能够通电。

请你计算并输出可以通电的最大节点数量。

手搓邻接表 原文链接

h数组：表示每个顶点对应的链表的头节点的下标。

e数组：表示每个边的终点。

ne数组：表示与当前边起点相同的下一条边的下标。

需要注意的是,这些数组内存储的都是下标

具体来说，对于一条边(a, b)，我们将它插入到顶点a的链表中。我们需要先将新边的终点存入e数组中，将当前顶点a的链表的头节点下标存入ne数组中，然后将当前边的下标存入h数组中。同时，为了保证新插入的边在链表的头部，我们需要将当前边的下标作为新的头节点，将它存入h数组中，并更新ne数组中原来的头节点的值，使其指向当前边的下标。这样，就能够实现将新边插入到链表的头部，并更新该顶点的链表头节点。

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
#include<iostream>
using namespace std;
//DFS
const int N=2*1e5+10,M=N*2;

int n;
int h[N],e[M],ne[M],idx=0;
int w[N];

int res[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int n)
{
    res[n]=1;
    for(int i=h[n];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(w[n]>w[j])
        {
            if (res[j] == 0) dfs(j);
            res[n] += res[j];
        }
    }
}

int main()
{
    int t,n;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>n;
        for (int j = 1; j <= n; j ++) 
            scanf("%d", &w[j]), h[j] = -1, res[j] = 0;
        for (int j = 1; j < n; j ++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            add(a,b),add(b,a);
        }
        
        int ans=0;
        for(int j=1;j<=n;j++)
        {
            if(res[j]==0) dfs(j);
            if(res[j]>ans) ans=res[j];
        }

        printf("Case #%d: %d\n",i,ans);
        
        idx=0;

    }
    
    return 0;
}

题目2:AcWing 4740.跑圈

阿达正在一个长度为 L 的环形跑道上练习跑步。

为了更专注于跑步，阿达专门准备了一台机器来统计她跑的圈数。

机器放置在跑道的起跑线上，从 0 开始计数。

每当阿达离开起跑线时（直接越过起跑线或在起跑线位置处改变方向并离开起跑线），她的面朝方向就会被机器记录。

机器只会实时记录她最近一次离开起跑线时的面朝方向。
每当阿达到达起跑线位置时，只要其面朝方向与机器记录的上次离开起跑线时的面朝方向相同，机器计数就会加 1。

阿达从起跑线处开始跑步。她的耐力有限，无法将计划的训练量一口气完成。因此，每跑一段距离，她都会原地休息一段时间，用来恢复体力。

不幸的是，阿达的记忆力并不是很好，每当她休息完再次开始跑步时，她都会忘了之前面朝的方向。这时，她只能随意选择一个方向（顺时针或逆时针），并面朝该方向从她停下的位置开始继续跑步。

具体的说，她一共进行了 N 段跑步，其中第 i 段跑步的距离为 Di，跑步时的面朝方向为 Ci
。

请你计算，在阿达完成跑步后，机器最终记录的圈数。

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;



int main()
{
    int t;
    cin >> t;
    for (int m = 1; m <= t; m++)
    {
        int l, n;
        cin >> l >> n;
        //bool first = true;//记录第一次起跑
        char f, lf;//当前方向,上次方向
        int d;//本段跑步长度
        long long ans = 0;//圈数量  注意数据范围ll
        int rd = 0;//当前位置

        while (n--)
        {
            scanf("%d %c", &d, &f);
            //if(first) lf=f,first=false;
            if (rd == 0) lf = f;

            if (lf == f)
            {
                if ((rd + d) / l)
                {
                    ans += (rd + d) / l;
                    rd = (rd + d) % l;
                }
                else rd += d;
            }
            else {
                if (rd - d > 0) rd -= d;
                else
                {
                    rd = (d - rd), lf = f;
                    if (rd / l)
                    {
                        ans += rd / l;
                        rd = rd % l;
                    }
                }
            }
        }
        printf("Case #%d: %lld\n",m,ans);
    }

    return 0;
}