「SOL」NOI2017Day2 T1T2 解题报告 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」NOI2017Day2 T1T2 解题报告

发表于 更新于 分类于 Valine：

就当我没做过这套题

而且 T3 也不会

Day2 A. 游戏

> Link 游戏 - LOJ

做过 2-sat 的读者应该能够一眼秒出这道题的正解 —— $\mathcal O(2^d)$ 枚举 x 的取值，其余还没有唯一确定方案的点是一个 2-sat 问题，总复杂度 $\mathcal O(2^dm)$，边搜索边剪枝，常数很小。

但是为什么这道题可以出在 NOI 里呢？因为它的细节简直恶心。

大概说一下我对几个细节的处理方法：

  • 若 $(i,h_i,j,h_j)$ 中 $S_i=h_i$，则该条件无效，在之后的搜索中保证不会访问 $i=S_i$ 这种不合法的点。

  • 若条件 $(i,h_i,j,h_j)$ 中 $h_j=S_j$，则说明 $i$ 不能取 $h_i$；处理方法是建出限制关系的反图，从每个 $ans_i=S_i$ 的状态往回找前驱状态，把这些状态都 ban 掉。

  • 非 x 的点本身只有两种取值，因此对于条件 $(i,h_i,j,h_j)$，若 $S_i\neq \text x$，则可以判断「当 $j$ 不取 $h_j$ 时，$i$ 取除了 $h_i,S_i$ 之外的值」。
  • 在 tarjan 缩点的过程中在搜到一个已确定方案的点 $v$ 时，经过上述处理，此时一定合法，可以跳过对 $v$ 的搜索；因为当前状态一定是一个只有两种取值（非真即假）的状态，而在上述第三条中，若 $v$ 的取值限制了当前点的值，则当前点必然已经固定取值。

Day2 B. 蔬菜

> Link 蔬菜 - LOJ

第一步非常关键的转化（也是我没想出正解的原因）：把一种蔬菜再拆成两种 —— 最后一个和其他。为什么是最后一个而不是第一个？因为最后一个的保质期最长，最容易放下来。

为了方便理解可以把「其他」再按保质期不同拆成若干种，但是实现代码时显然不会这么实现，存不下。

于是现在的问题就是「有若干类物品，物品 $i$ 有 $C_i$ 个，单位价值为 $V_i$，只能放在前 $T_i$ 个篮子里；每个篮子只能装 $m$ 个物品，最大化放入篮子的物品总价值」。这个贪心比较简单，先放单位价值大的物品，能放则放，不能放则跳过。反证即可说明。

判断能不能放，可以用并查集维护在某个篮子之前最靠后的未满篮子。

每次做一遍贪心复杂度 $\mathcal O(kpm)$ 或者 $\mathcal O(kpm\log p)$。

考虑增加一个篮子，放入的物品会如何变化。结论是在原来已放入物品的基础上再添加。本来可以直接拿拟阵证明，但是我不会，还是用常规的反证方法：假设原本最优解放入了物品 $x$，但在新最优解中不可能有物品 $x$，说明篮子 $1\sim T_x$ 中 的所有物品的单位价值都大于 $x$，与 $x$ 在原本最优解中矛盾。

所以说，每次询问 $p_i$ 其实只是限制了最优解的物品总数不超过 $mp_i$。可以贪心处理出最优解中有 $i$ 个（$1\le i\le m\cdot\max\{p\}$）物品的最优解，直接输出即可。

源代码

点击展开/折叠 game.cpp 
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>

#define con(typ) const typ &
const int N = 5e4 + 10, M = 1e5 + 10;

inline int rin(int &r) {
  int b = 1, c = getchar(); r = 0;
  while ( c < '0' || '9' < c ) b = c == '-' ? -1 : b, c = getchar();
  while ( '0' <= c && c <= '9' ) r = r * 10 + (c ^ '0'), c = getchar();
  return r *= b;
}
inline char rch(char &r) {
  char str[20] = {};
  scanf("%s", str);
  return r = str[0];
}

int n, m, nd, nrol;
char str[N];
int xpos[10], typ[N], mex[5][5], col[N], rol[N];

template<const int P, const int E> struct Graph {
  int head[P], to[E], nxt[E], ncnt;
  void addEdge(con(int) u, con(int) v) {
    int p = ++ncnt;
    to[p] = v, nxt[p] = head[u];
    head[u] = p;
  }
  inline int operator [] (con(int) u) {return head[u];}
};

Graph<N * 3, M * 3> gr, rg;
Graph<N * 3, N * 3> bel;

int nscc, ndfn, nstk;
int dfn[N * 3], low[N * 3], scc[N * 3], stk[N * 3];
bool bok[N * 3], ban[N * 3];

void init() {
  mex[0][0] = 1, mex[0][1] = 2, mex[0][2] = 1;
  mex[1][0] = 2, mex[1][1] = 0, mex[1][2] = 0;
  mex[2][0] = 1, mex[2][1] = 0, mex[2][2] = 0;
}
bool dfs(con(int) u) {
  int iu = u / 3, cu = u % 3;
  if ( cu == typ[iu] ) return false;
  if ( ~col[iu] ) return cu == col[iu];
  col[iu] = cu, rol[++nrol] = iu;
  for (int it = gr[u]; it; it = gr.nxt[it]) {
    int v = gr.to[it];
    if ( !dfs(v) )
      return false;
  }
  return true;
}
void tarjan(con(int) u) {
  if ( ~col[u / 3] ) return;
  dfn[u] = low[u] = ++ndfn;
  stk[++nstk] = u, bok[u] = true;
  for (int it = gr[u]; it; it = gr.nxt[it]) {
    int v = gr.to[it];
    if ( ~col[v / 3] ) continue;
    if ( !dfn[v] ) tarjan(v), low[u] = std::min(low[u], low[v]);
    else if ( bok[v] ) low[u] = std::min(low[u], dfn[v]);
  }
  if ( low[u] == dfn[u] ) {
    int tmp = -1; bel.head[++nscc] = 0;
    do {
      tmp = stk[nstk--];
      bok[tmp] = false;
      scc[tmp] = nscc;
      bel.addEdge(nscc, tmp);
    } while ( tmp != u );
  }
}
void fixXPos(con(int) d) {
  if ( d > nd ) {
    for (int i = 1; i <= n; ++i) if ( col[i] == -1 )
      for (int c = 0; c < 3; ++c)
        dfn[i * 3 + c] = 0;
    ndfn = nscc = bel.ncnt = 0;
    for (int i = 1; i <= n; ++i) if ( col[i] == -1 ) {
      int p = -1, q = -1;
      for (int c = 0; c < 3; ++c) if ( !ban[i * 3 + c] ) {
        if ( !dfn[i * 3 + c] ) tarjan(i * 3 + c);
        if ( ~p ) q = c;
        else p = c;
      }
      if ( scc[i * 3 + p] == scc[i * 3 + q] )
        return;
    }
    for (int i = 1; i <= nscc; ++i) {
      bool tag = true;
      for (int it = bel[i]; it; it = bel.nxt[it])
        if ( ~col[bel.to[it] / 3] ) {
          tag = false;
          break;
        }
      if ( !tag ) continue;
      for (int it = bel[i]; it; it = bel.nxt[it])
        col[bel.to[it] / 3] = bel.to[it] % 3;
    }
    for (int i = 1; i <= n; ++i)
      putchar('A' + col[i]);
    putchar('\n');
    exit(0);
  }
  int u = xpos[d];
  if ( ~col[u] ) {
    fixXPos(d + 1);
    return;
  }
  for (int c = 0; c < 3; ++c) {
    int mrol = nrol;
    if ( dfs(u * 3 + c) ) fixXPos(d + 1);
    while ( nrol > mrol ) col[rol[nrol--]] = -1;
  }
}
void doBan(con(int) u) {
  ban[u] = true;
  for (int it = rg[u]; it; it = rg.nxt[it] )
    if ( !ban[rg.to[it]] )
      doBan(rg.to[it]);
}
int main() {
  // freopen("input.in", "r", stdin);
  init();
  rin(n), rin(nd);
  scanf("%s", str + 1);
  for (int i = 1, tmp = 0; i <= n; ++i)
    if ( str[i] == 'x' )
      xpos[++tmp] = i, typ[i] = -1;
    else
      typ[i] = str[i] - 'a';
  rin(m);
  for (int i = 1; i <= m; ++i) {
    char tmp;
    int u = rin(u), ut = rch(tmp) - 'A', v = rin(v), vt = rch(tmp) - 'A';
    if ( ut == typ[u] ) continue;
    gr.addEdge(u * 3 + ut, v * 3 + vt);
    rg.addEdge(v * 3 + vt, u * 3 + ut);
    if ( ~typ[u] )
      for (int j = 0; j < 3; ++j)
        if ( j != vt ) {
          gr.addEdge(v * 3 + j, u * 3 + mex[typ[u]][ut]);
          rg.addEdge(u * 3 + mex[typ[u]][ut], v * 3 + j);
        }
  }
  for (int i = 1; i <= n; ++i)
    if ( ~typ[i] )
      doBan(i * 3 + typ[i]);
  for (int i = 1; i <= n; ++i)
    if ( ban[i * 3] && ban[i * 3 + 1] && ban[i * 3 + 2] ) {
      printf("-1\n");
      return 0;
    }
  memset(col, -1, sizeof col);
  fixXPos(1);
  printf("-1\n");
  return 0;
}
点击展开/折叠 vegetables.cpp 
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
/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>

#define con(typ) const typ &
typedef long long llong;
const int N = 1e5 + 10;

inline int rin(int &r) {
  int b = 1, c = getchar(); r = 0;
  while ( c < '0' || '9' < c ) b = c == '-' ? -1 : b, c = getchar();
  while ( '0' <= c && c <= '9' ) r = r * 10 + (c ^ '0'), c = getchar();
  return r *= b;
}

struct Item {
  int val, cnt, bad;
  Item() {}
  Item(con(int) _val, con(int) _cnt, con(int) _bad)
  : val(_val), cnt(_cnt), bad(_bad) {}
  static bool cmpToVal(con(Item) p, con(Item) q) {
    return p.val > q.val;
  }
} itm[N << 1];

struct Dsu {
  int fa[N];
  int fFind(con(int) u) {return fa[u] == u ? u : fa[u] = fFind(fa[u]);}
  bool mMerge(int u, int v) {
    u = fFind(u), v = fFind(v);
    if ( u == v ) return false;
    fa[u] = v;
    return true;
  }
  void init(con(int) siz) {
    for (int i = 1; i <= siz; ++i)
      fa[i] = i;
  }
} dsu;

int n, m, nq, nitm;
int ocnt[N];
llong ans[N * 10];

int main() {
  rin(n), rin(m), rin(nq);
  const int ED = N - 3;
  for (int i = 1; i <= n; ++i) {
    int per, ext, cnt, bad;
    rin(per), rin(ext), rin(cnt), rin(bad);
    int due = bad ? (cnt + bad - 1) / bad : ED;
    itm[++nitm] = Item(per + ext, 1, -due);
    if ( cnt > 1 ) itm[++nitm] = Item(per, cnt - 1, bad);
  }
  std::sort(itm + 1, itm + 1 + nitm, Item::cmpToVal);
  dsu.init(ED);
  int ncnt = 0;
  for (int i = 1; i <= nitm; ++i)
    if ( itm[i].bad >= 0 ) {
      while ( itm[i].cnt ) {
        int due = itm[i].bad ? (itm[i].cnt + itm[i].bad - 1) / itm[i].bad : ED;
        int k = dsu.fFind(due);
        if ( !k ) break;
        ++ocnt[k];
        if ( ocnt[k] == m ) dsu.mMerge(k, k - 1);
        ans[ncnt + 1] = ans[ncnt] + itm[i].val;
        ++ncnt;
        --itm[i].cnt;
      }
    } else {
      int k = dsu.fFind(-itm[i].bad);
      if ( k ) {
        ++ocnt[k];
        if ( ocnt[k] == m ) dsu.mMerge(k, k - 1);
        ans[ncnt + 1] = ans[ncnt] + itm[i].val;
        ++ncnt;
      }
    }
  while ( nq-- ) {
    int day; rin(day);
    printf("%lld\n", ans[std::min(day * m, ncnt)]);
  }
  return 0;
}

THE END

Thanks for reading!

我也曾 隐约想过 从这世界逃离
因为人总被缚于不明所以的意义
生日飘落杏花雨 虫鸣淹没住叹息
尽数凝固成往昔连存在都无从证明

——《我也曾想过一了百了(中文填词)》 By 洛天依

> Link 我也曾想过一了百了 - Bilibili