noip模拟57

TLEer

09-24-2021 约 1689 字预计阅读 4 分钟

联考题水爆了，挂分挂爆了

T1 ip

000.0.0.0不是个合法地址，因为有前导零。然后因为没带眼睛，没去前导0，又把Yes和No的大小写打错了直接爆蛋。

直接用快读读出4个数再加上点匹配就行了，快读板题。~~不会真有人没A吧，不会吧不会吧~~

T2 PPAP

这道题以为有多么牛B呢，结果是两个while循环就能搞定的事。一定是先删AP最好，因为只有它能删掉一个A，所以就一个while找AP删AP，另一个while找PP删PP就行

T3 class

前面两个条件都好说，恶心就恶心在第三个条件不能有菱形上了。

考虑暴力艹过去，直接用bitset存每个类的父亲，每加入一个类就遍历它的父亲并取与，最后如果有1，就判断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
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 10010;

int n, totNames = 0;
bitset<1010> vis[maxn];
unordered_map<string, int> mp;
string tmp, name, fas[maxn];

int main() {
  freopen("class.in", "r", stdin);
  freopen("class.out", "w", stdout);
  cin >> n;
  For(i, 1, n) {
    int cnt = 0;
    bool flg = 0;
    while (1) {
      cin >> tmp;
      if (tmp == ";") break;
      if (tmp == ":") {
        flg = 1;
        continue;
      }
      if (flg) {
        fas[++cnt] = tmp;
      } else {
        name = tmp;
      }
    }
    if (mp.find(name) != mp.end()) {
      cout << "greska" << endl;
      continue;
    }
    bool OK = 1;
    For(j, 1, cnt) {
      if (mp.find(fas[j]) == mp.end()) {
        cout << "greska" << endl;
        OK = 0;
        break;
      }
    }
    if (OK) {
      For(j, 1, cnt - 1) {
        For(k, j + 1, cnt) {
          if (OK == 0) break;
          bitset<1010> tmp = vis[mp[fas[j]]] & vis[mp[fas[k]]];
          if (tmp.count() != 0) {
            if (vis[mp[fas[j]]][mp[fas[k]]] != 1 &&
                vis[mp[fas[k]]][mp[fas[j]]] != 1) {
              cout << "greska" << endl;
              OK = 0;
              
            }
          }
        }
      }
    }

    if (OK) {
      mp[name] = ++totNames;
      For(j, 1, cnt) {
        vis[mp[name]] = vis[mp[name]] | vis[mp[fas[j]]];
      }
      vis[mp[name]].set(mp[name]);
      cout << "ok" << endl;
    }
  }
  return 0;
}

T4 k-degree graph

(k + 1)-degree 一定是 k-degree 的子图，我们可以考虑找到 k 最大的 k-degree子图，然后考虑不断的拓展这个子图，去得到 k 比较小的 k-degree子图显然每一次加入一批相同标记的点，可以拓展得到 k 减小的 k-degree 假设我们已经知道了当前图的 score ，我们考虑新增点/边会带来的 score 变化我们首先给所有的节点一个 rank

$rank(v) \ rank(u)$ 当且仅当

– $v$ 的标记 $> u$ 的标记

– $v$ 的标记 $= u$ 的标记且 $v > u$
这个部分可以用 bin-sort 完成我们可以根据边两边点的 rank 对边分类，用 $E(v, >)$ 表示 $v$ 的边中另一个端点比 $v$ rank 大的边，其余的表示以此类推于是，考虑新增一批点（标记相同的点）：对于每一个新加入的点 $u$：
$\Delta n = 1$
$\Delta m = |E(u, >)|+ \frac{1}{2}|E(u, =)|$
$\Delta b = |E(u, <)|−|E(u, >)|$

于是从标记大的点到小的点依次加入计算 score，得到最大 score 的 k 即可因为不断加入点，可能使得本来不连通的两个子图联通起来，这部分可以用并查集维护时间复杂度 $O(m + n)$

  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
142
143
144
145
146
147
148
149
150


#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 2000010;

#define int int64_t

template <typename LDXIN>
LDXIN read() {
  LDXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int n, m;

struct EDGE {
  int nxt, to;
} edge[maxn];
int tote, head[maxn], degree[maxn];
void addEdge(int from, int to) {
  edge[++tote].to = to;
  edge[tote].nxt = head[from];
  head[from] = tote;
}

struct PNT {
  int id, vis;
} bkt[maxn];

int rk[maxn], c[maxn], line[maxn];
// ps point number
// ds degree number
// ls line number
int ps[maxn], ds[maxn], ls[maxn];

class DJU {
 public:
  int fa[maxn];
  void init(int n) { For(i, 1, n) fa[i] = i; }
  int findFa(int x) { return fa[x] == x ? x : fa[x] = findFa(fa[x]); }
  void join(int a, int b) {
    a = findFa(a);
    b = findFa(b);
    fa[a] = b;
    ps[b] += ps[a];
    ls[b] += ls[a];
    ds[b] += ds[a];
  }
} dj;

int ans = -0x7f7f7f7f7f7f7f7f, ansk = -0x7f7f7f7f7f7f7f7f;
int M, N, B;
int deg[maxn];

class Solution {
 public:
  void getMaxGraph() {
    For(i, 1, n) c[deg[i]]++;
    For(i, 1, n) c[i] += c[i - 1];
    Fordown(i, n, 1) rk[i] = c[deg[i]]--;
    For(i, 1, n) bkt[rk[i]] = (PNT){i, deg[i]};
    For(i, 1, n - 1) if (bkt[i].vis != bkt[i + 1].vis) line[bkt[i].vis] = i;
    For(i, 1, n) {
      for (int id = head[bkt[i].id]; id; id = edge[id].nxt) {
        int to = edge[id].to;
        if (bkt[rk[to]].vis <= bkt[i].vis) continue;
        bkt[rk[to]].vis--;
        int posi = line[bkt[rk[to]].vis] + 1;
        line[bkt[rk[to]].vis]++;
        int bktid = bkt[posi].id;
        swap(bkt[rk[to]], bkt[rk[bktid]]);
        swap(rk[to], rk[bktid]);
      }
    }
    for (int i = 1; i <= n; i++) degree[bkt[i].id] = bkt[i].vis;
  }
  void getAns() {
    Set(rk, 0);
    Set(c, 0);
    For(i, 1, n) c[degree[i]]++;
    For(i, 1, n) c[i] += c[i - 1];
    Fordown(i, n, 1) rk[i] = c[degree[i]]--;
    For(i, 1, n) c[rk[i]] = i;
    For(i, 1, n) ps[i] = 1, ds[i] = deg[i];
    dj.init(n);
    Fordown(i, n, 0) {
      int now = c[i];
      int fa = dj.findFa(now);
      for (int id = head[now]; id; id = edge[id].nxt) {
        int to = edge[id].to;
        if (rk[to] < rk[now]) continue;
        int fto = dj.findFa(to);
        if (fa != fto) {
          if (ps[fa] <= ps[fto]) {
            swap(fa, fto);
          }
          dj.join(fto, fa);
        }
        ls[fa]++;
      }

      if (degree[now] != degree[c[i - 1]]) {

        for (int j = i; j <= n && degree[c[j]] == degree[now]; j++) {
          int nowfa = dj.findFa(c[j]);
          long long val =
              M * ls[nowfa] - N * ps[nowfa] + B * (ds[nowfa] - (ls[nowfa] * 2));
          if (val > ans) {
            ans = val;
            ansk = degree[now];
          }
        }
      }
    }
  }
} sol;

int32_t main() {
  freopen("kdgraph.in", "r", stdin);
  freopen("kdgraph.out", "w", stdout);
  n = read<int>();
  m = read<int>();
  M = read<int>();
  N = read<int>();
  B = read<int>();
  For(i, 1, m) {
    int from, to;
    from = read<int>();
    to = read<int>();
    addEdge(from, to);
    addEdge(to, from);
    deg[to]++;
    deg[from]++;
  }
  sol.getMaxGraph();
  sol.getAns();
  cout << ansk << ' ' << ans << endl;
  return 0;
}

目录

noip模拟57

T1 ip

T2 PPAP

T3 class

T4 k-degree graph