就当我没做过这套题

而且 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 
/*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 
/*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

最新文章

  1. 微信后台开发第一步：nodeJS+express接入微信后台详细教程
  2. conda安装包
  3. ASP.NET MVC 路由(五)
  4. webpack配置es6开发环境
  5. Oracle Dataguard之Real-Time Apply
  6. ZOJ 1808 Immediately Decodable
  7. 有关C，C++,C#, Java的图形图像处理类库 整理（未完待续）
  8. FZU 2127 养鸡场
  9. Topcoder SRM 656 (Div.1) 250 RandomPancakeStack - 概率+记忆化搜索
  10. hdu1978How many ways (记忆化搜索+DFS)
  11. javaScript中获取鼠标位置的理解
  12. c++栈管理库TCMalloc、jeMalloc
  13. Codeforces 626C Block Towers(二分)
  14. haproxy快速安装
  15. 个人项目 Individual Project
  16. Mybatis-spring 传统dao开发
  17. 搭建Linux下Android程序开发环境
  18. Hexo NexT 博客本地搭建指南
  19. asp.net mvc session锁问题 （转载）
  20. TPCC-MySQL安装、使用及结果解读

热门文章

  1. C++知识整理
  2. DDL数据定义--Hive中数据可和表的基本操作（增删改查）
  3. python+ffmpeg,批量转换手机中的m3u8文件
  4. java异常信息打印
  5. JSONObject没有parseObject方法
  6. 【springboot】约定优于配置
  7. java8 利用 ConcurrentHashMap list根据 某个属性 去重
  8. this指向问题大全和call，apply,bind详解
  9. sass和less以及stylus的区别
  10. IBM服务器的2种IMM和1种raid管理方式