「考试总结」ZROI-21-CSP7连-DAY2 总结

发表于 更新于 分类于
ZROI-21-CSP7连-DAY2 总结

#T1 IP 地址

#题意简述

一个合法的 IP 地址每位数字最小为 \(0\)，最大为 \(255\)，且不含前导零。每位数字中间有一个 "." 隔开。

给定一个文本串，其中最多包含 \(4\) 个整数（可能极大），问是否是合法的 IP 地址，如果不合法请更正为合法 IP，数字大于 \(255\) 则修改为 \(255\).

#大体思路

把快读魔改一下就好了，但是一定要注意细节，比如快读实际会向后多读一个字符，可以借此判断最后是否有多余字符。

#Code

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
const int N = 100010;
const int INF = 0x3fffffff;

int is_not_ip(0), cnt;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) {
        if (c == '.') ++ cnt;
        if (c != '.' || cnt > 3) is_not_ip |= 1;
    }
    for (; ; c = getchar())  {
        if (!isdigit(c)) {
            if (c != '.') is_not_ip |= 1;
            else if (++ cnt > 3) is_not_ip |= 1;
            break;
        }
        if (c == '0' && x == 0) is_not_ip |= 1;
        x = x * 10 + c - '0';
        if (x > 255) x = 255, is_not_ip |= 1;
    }
    x *= f;
}

int a[4];

int main() {
    for (int i = 0; i < 4; ++ i) read(a[i]);
    if (is_not_ip) printf("NO\n");
    else printf("YES\n");
    for (int i = 0; i < 4; ++ i) {
        printf("%d", a[i]);
        if (i < 3) printf(".");
    }
    return 0;
}

#T2 字符串

#题意简述

给定一个长度为 \(n\) 的字符串，其中一共包含两种字符：A 和 P，其中，AP 和 PP 可以消去，消去后剩下两段字符串会拼在一起，问经过若干次消除后能得到的最小字符串长度为多少。

#大体思路

注意到 A 只能由 AP 消去，而 P 可以由 PP 消去，考虑贪心：当前的 A 要么在后面被消去，要么无法消去，而多出来的 P 对答案的贡献最多是 \(1\)，所以优先消掉 A 一定是最优的选择。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 10010;
const int INF = 0x3fffffff;

char s[N];
int n, pcnt, acnt;

int main() {
    scanf("%s", s); n = strlen(s);
    for (int i = 0; i < n; ++ i) {
        if (s[i] == 'A') ++ acnt;
        else acnt ? -- acnt : ++ pcnt;
    }
    printf("%d", acnt + (pcnt & 1));
    return 0;
}

#T3 继承类

#题意简述

实在不好概述，这里直接粘来原题面。

现在发明了一种类似于 C++ 的面向对象编程语言中的类声明。

每个类声明的格式为 "\(K : P_1\ P_2\ \dots\ P_K;\)"

其中 \(K\) 是要声明的新类的名称，\(P_1\) 、\(P_2\) 、\(\dots\) 、\(P_k\) 类 \(K\) 继承的类的名称。

例如，"shape : ;" 是不继承任何其他类的类 “shape” 的声明，而 “square : shape rectangle;” 是继承类 “shape” 和 “rectangle” 的类 “square” 的声明。

如果类 \(K_1\) 继承类 \(K_2\) ，类 \(K_2\) 继承类 \(K_3\) ，依此类推，直到类 \(K_{m−1}\) 继承类 \(K_m\) ，那么我们说所有类 \(K_1,K_2,\dots,K_{m−1}\) 派生自类 \(K_m\) 。

编程语言的规则禁止循环定义，因此不允许从自身派生一个类。换句话说，类层次结构形成了一个有向无环图。此外，不允许在类层次结构中出现所谓的菱形。一个菱形由四个不同的类 \(A\)、\(B\)、\(X\)、\(Y\) 组成，而且它满足（如下图所示）：

  • 类 \(X\) 和 \(Y\) 派生自 \(A\)。
  • 类 \(B\) 派生自 \(X\) 和 \(Y\)。
  • 类 \(X\) 不是从 \(Y\) 派生的，类 \(Y\) 也不是从 \(X\) 派生的。
img

现在你会获得 \(n(n\le 1000)\) 个要按顺序处理的类声明，并确定每个类声明是否是正确声明。

正确声明的类被添加到层次结构中，而错误的类被丢弃。声明 “\(K : P_1\ P_2\ \dots\ P_K;\)” 如果满足以下条件，则认为是正确声明：

  1. 类 \(K\) 尚未声明。
  2. 所有类别 \(P_1,P_2,\dots,P_k\) 之前已经声明过。请注意，此条件可确保类永远不会从其自身派生，或者类层次结构中不能存在循环。
  3. 通过添加继承了 \(P_1,P_2,\dots,P_k\) 的类 \(K\) 以后，类层次结构保持有序，即没有形成任何菱形。

现在需要你分别处理上述声明并确定每个声明的正确性。

#大体思路

直接考虑性质三：简单分析“菱形”的性质，不难发现不存在菱形的前提是所有的 \(P_i\) 要么是严格的祖孙关系，要么毫无关系，总之不能为旁系亲属，发现如果当前语句合法，那么所有的 \(P_i\) 的旁系亲属都是当前 \(K\) 的旁系亲属，很好维护，但是直接用 bool 数组维护关系的话时间复杂度为 \(O(n^3)\)，不能接受，又发现维护的值要么是 \(0\) 要么是 \(1\)，且支持位运算，直接上 bitset，时间复杂度优化到 \(O(\dfrac{n^3}{w})\)，可以艹过去了。

#Code

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
const int N = 1010;
const int INF = 0x3fffffff;

string s, t;
int n, cnt, tcnt, q[N];

map <string, int> mp;
bitset <1010> f[N], b[N], tmp;

inline bool check() {
    tmp.reset();
    for (int i = 1; i <= tcnt; ++ i)
      tmp[q[i]] = 1;
    for (int i = 1; i <= tcnt; ++ i)
      if ((tmp & b[q[i]]).any()) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n; int is_wrong = 0;
    for (int i = 1; i <= n; ++ i) {
        is_wrong = tcnt = 0;
        cin >> s; cin >> t; cin >> t;
        while (t != ";") {
            if (!mp[t]) is_wrong |= 1;
            q[++ tcnt] = mp[t]; cin >> t;
        }
        if (!check()) is_wrong |= 1;
        if (is_wrong || mp[s]) {
            cout << "greska\n"; continue;
        }
        cout << "ok\n"; mp[s] = ++ cnt;
        f[cnt][cnt] = 1;
        for (int j = 1; j <= tcnt; ++ j)
          f[cnt] |= f[q[j]];
        for (int j = 1; j < cnt; ++ j)
          if (!f[cnt][j] && (f[j] & f[cnt]).any()) {
              b[cnt][j] = 1;
          }
    }
    return 0;
}

#T4 子图

#题意简述

依旧是不好简述，上原题面。

Cuber QQ 的研究兴趣是在图 \(G=(V(G),E(G))\) 中找到最好的 \(k\)-degree 子图。

子图 \(S\) 是 \(G\) 的 \(k\)-degree 子图需要满足以下要求：

  • 每个顶点 \(v(v\in S)\) 在 \(S\) 中至少有 \(k\) 度；
  • \(S\) 是连通的 ;
  • \(S\) 是极大的，即 \(S\) 的任何超图都不是 \(k\)-degree 子图，除了 \(S\) 本身。
img

然后 Cuber QQ 定义子图 \(S\) 的分数。在定义分数之前，他首先定义：

  • \(n(S)\)：子图 \(S\) 中的顶点数，即 \(n(S)=|V(S)|\)；
  • \(m(S)\)：子图 \(S\) 的边数，即 \(m(S)=|E(S)|\)；
  • \(b(S)\)：子图 \(S\) 中的边界边数，\(b(S)=|{(u,v)|(u,v)∈E(G),u∈V(S),v∉V(S),v∈V(G)}|\);

他定义一个子图的分数为 \(score(S)=M\cdot m(S)−N\cdot n(S)+B\cdot b(S)\)，其中 \(M,N,B\) 是给定的常数。

子图的分数越高，Cuber QQ 认为它越好。你需要在图 \(G\) 中找到最好的 \(k\)-degree 子图。如果有许多 \(k\)-degree 子图的分数相同，则应最大化 \(k\)。输出最大的分数及对应的 \(k\).

#大体思路

首先，如果不考虑连通性问题，那么 \((k+1)\)-degree 一定是 \(k\)-degree 的子图，于是我们可以先求得一个标记，如果一个点属于 \(k\)-degree 而不属于 \(k+1\)-degree，那么该点标记为 \(k\)，求得这个标记的过程可以通过像剥卷心菜一样将原图层层剥开，具体细节我们留到后面去说；

假设我们已经求得了每个点的标记，再来考虑通过将卷心菜原图一层层还原回去得到每个 \(k\)-degree 的 score；显然我们是通过加入标记为 \(k\) 的点得到 \(k\)-degree，考虑单个新加入的点，他们对 \(n,m,b\) 的贡献分别是什么。

先来引入一些新记号：

  • \(E(u,>)\) 表示 \(u\) 的边中另一个点标记比 \(u\) 大的边的集合；
  • \(E(u,<)\) 表示 \(u\) 的边中另一个点标记比 \(u\) 小的边的集合；
  • \(E(u,=)\) 表示 \(u\) 的边中另一个点 \(v\) 标记与 \(u\) 相等但 \(v>u\) 的边的集合；

现在不难写出新的贡献：

  • \(\Delta n=1\)；
  • \(\Delta m=|E(u,>)|+|E(u,=)|\)；
  • \(\Delta b=|E(u,<)|-|E(u,>)|\)；

在合并的过程中，可能会导致几个连通块合成一个连通块，可以采用并查集提前维护出各个连通块的代表元素，代表元应当是整个连通块中标记最小的点，这样才能正确地完成合并。为下面合并答案，同时记录每个小连通块合并后的大连通块的编号，以及当前连通块的 \(k\).

并查集采用按秩合并+路径压缩，总体时间复杂度为 \(O(m+n)\)，下面的代码仅采用了路径压缩，总体时间复杂度为 \(O(m\log n+n)\).

#一些细节实现

获取标记时，先用桶排将所有点按照度数从小到大排序，我们自小到大遍历这个序列，对于每个点，将与其相连的所有度数大于该点度数的点的度数减一，同时直接改变其在数列中的位置，将其放到原本度数的开头位置，对应度数的开头位置后移一位，这样维护可以保证在任意时刻队列中都是有序的。考虑为什么只有度数大于该点的点需要改变度数：小于该点的意味着已经被遍历，其度数就是其标记；等于该点的点，显然应当与该点属于同一层，直接保留度数作为标记；对于大于的，根据 \(k\)-degree 的定义，如果不在同一层，当前边贡献的度数显然不符合要求，应当减去，如果应当在同一层，那么由于处理完的度数对应的应当是正确的标记，而当前大于正确标记，应当减去。

详细见下方代码。

#Code

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#define ll long long
#define VI vector <int>
#define pii pair <ll, int>

const int N = 2000100;
const int INF = 0x3fffffff;

template <typename T>
inline T Min(const T a, const T b) {return a < b ? a : b;}

template <typename T>
inline T Max(const T a, const T b) {return a > b ? a : b;}

struct Edge {int u, v, nxt;} e[N];

struct UFS {
    int fa[N]; int *d_;

    inline void init(int x, int *d) {
        for (int i = 0; i <= x; ++ i) fa[i] = i;
        this->d_ = d;
    }

    inline int find(int x) {
        while (x != fa[x]) x = fa[x] = fa[fa[x]];
        return x;
    }

    inline void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y)  {
            if ((d_[x] > d_[y]) || (d_[x] == d_[y] && x > y))
              swap(y, x);
            fa[y] = x;
        }
    }
} ufs;

int n, m, d[N], head[N], ecnt(1), cbtot;
int frt, tal, q[N], pos[N], bin[N], max_k, cb_id[N];
int inq[N], kpc[N], kcnt; ll A, B, C;

vector <int> tk, pa;

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v; ++ d[u];
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

inline void Get_Tags() {
    int max_d = 0, st = 0, now = 0;
    for (int i = 1; i <= n; ++ i)
      ++ bin[d[i]], max_d = Max(max_d, d[i]);
    for (int i = 0; i <= max_d; ++ i)
      now = bin[i], bin[i] = st, st += now;
    for (int i = 1; i <= n; ++ i)
      pos[i] = bin[d[i]] ++, q[pos[i]] = i;
    for (int i = max_d; i; -- i) bin[i] = bin[i - 1];
    bin[0] = 0, bin[max_d + 1] = n;
    for (int i = 0; i < n; ++ i) {
        int v = q[i];
        for (int j = head[v]; j; j = e[j].nxt) {
            int u = e[j].v;
            if (d[u] > d[v]) {
                int du = d[u], pu = pos[u];
                int pw = bin[du], w = q[pw];
                if (u != w) {
                    pos[u] = pw, q[pu] = w;
                    pos[w] = pu, q[pw] = u;
                } ++ bin[du], -- d[u];
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
      max_k = Max(max_k, d[i]);
}

inline void Get_Connected_Blocks() {
    ufs.init(n, d); pa.push_back(0); tk.push_back(0);
    for (int k = max_k; k; -- k) {
        int l = bin[k], r = bin[k + 1] - 1; kcnt = 0;
        for (int i = l; i <= r; ++ i) {
            int v = q[i]; 
            for (int j = head[v]; j; j = e[j].nxt){
                int u = e[j].v;
                int fp = ufs.find(u);
                if (d[fp] > k) if (!inq[fp])
                  kpc[++ kcnt] = fp, inq[fp] = true;
                if (d[fp] >= k) ufs.merge(v, fp);
            }
        }
        for (int i = l; i <= r; ++ i) {
            int v = q[i], fp = ufs.find(v);
            if (!cb_id[fp]) {
                cb_id[fp] = ++ cbtot;
                pa.push_back(-1);
                tk.push_back(d[fp]);
            }
            cb_id[v] = cb_id[fp];
        }
        for (int i = 1; i <= kcnt; ++ i) {
            int v = kpc[i], fp = ufs.find(v);
            pa[cb_id[v]] = cb_id[fp]，inq[v] = false;
        }
    }
}

void Compute_the_Answer() {
    VI vert(cbtot + 1, 0), edge(cbtot + 1, 0), boun(cbtot + 1, 0);
    for (int i = 1; i <= n; ++ i) {
        int ci = d[i], lt = 0, eq = 0, gt = 0;
        for (int j = head[i]; j; j = e[j].nxt) {
            int nbr = e[j].v, cnbr = d[nbr];
            if (cnbr < ci) ++ lt;
            else if (cnbr == ci) {
                if (i < nbr) ++ eq;
            } else ++ gt;
        }
        int ti = cb_id[i]; ++ vert[ti];
        edge[ti] += gt + eq; boun[ti] += lt - gt;
    }
    pii ans(1ll * (-1e18), -1);
    for (int i = 1; i <= cbtot; ++ i) {
        int f = pa[i];
        if (f != -1)
          vert[f] += vert[i], edge[f] += edge[i], boun[f] += boun[i];
        ll score = A * edge[i] - B * vert[i] + C * boun[i];
        if (tk[i] > 0) ans = max(ans, {score, tk[i]});
    }
    printf("%d %lld\n", ans.second, ans.first);
}

int main() {
    scanf("%d%d%lld%lld%lld", &n, &m, &A, &B, &C);
    for (int i = 1; i <= m; ++ i) {
        int u, v; scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    Get_Tags(); Get_Connected_Blocks();
    Compute_the_Answer(); return 0;
}