文章目录

USACO 2013 DEC, Sliver

发布于 2022-08-11

题目

题解

T1

算法 1

反悔贪心。
按照时间从小到大排序。从 $1$ 到 $N$ 枚举 $i$，如果当前时间可以让奶牛 $i$ 挤奶，那么就挤。否则我们找到产奶量最低的奶牛不挤，把时间腾出给当前这头。用堆维护产奶量即可。时间复杂度 $\mathcal O\left(N \log N\right)$。

算法 2

直接贪心。
按产奶量从大到小排序。从 $1$ 到 $N$ 枚举 $i$，第 $i$ 头奶牛如果可以挤奶，就把这头奶牛放在能挤奶的最后时间挤奶。这样使用并查集跳过这些已经被占用的点。时间复杂度 $\mathcal O\left(N \log N\right)$。

算法 3

直接贪心。
按照时间从大到小排序。从 $10000$ 到 $1$ 枚举时间，把所有在现在时间愿意挤奶的奶牛放进一个按产奶量排序的大根堆里。那么如果堆中有奶牛，就把答案加上堆顶奶牛的产奶量，并从堆中弹出。正确性显然。时间复杂度 $\mathcal O\left(N \log N\right)$。

代码写的是算法 3 的，因为最好写。

T2

算法 1

先对整个图跑 Floyd，对于每次询问，枚举每个枢纽，算 起点到当前枢纽的最短路 加上 当前枢纽到终点的最短路 的最小值。时间复杂度 $\mathcal O\left(N^3 + Q \cdot K\right)$。

算法 2

一个同学的思路。
先对整个图跑 Floyd，再枚举每个枢纽作为中间点，再跑一次 Floyd，这样每次询问是 $\mathcal O\left(1\right)$ 的。总时间复杂度 $\mathcal O\left(N^3 + Q\right)$。

代码写的算法 1。

T3

算法 1

在普通置换问题中，每个位置经过置换后都会到达一个互不相同的位置，而本题中，所有数置换后还会向前移一位，第 $1$ 个数被取出，有一个数被补到最后。仔细分析置换的过程，可以发现任意时刻在第 $M$ 个位置上的数，经过多次置换和向前移动的操作后，必然都会被取出，因为不会有一个已经出现过的数被替换到位置 $M$ 形成环。

所以我们可以将 $M$ 个位置分成两类，其中有一条从入口位置 $0$ 到位置 $M$ 的路径，这条路径不断的取出新的数并补充新的数进来。另一类就是各种大小不一的环，里面的数置换后就是环中不断变换的位置。

基于上述分析，我们可以将取数流程分为三段，假定从 $0$ 到 $M$ 的路径长度为 $t$。首先是 $N - M + 1$ 次置换后取出的数，其中又可以细分为两段，前 $t$ 个数时路径中已有的数，之后是从 $M + 1$ 开始的补充进来的数。最后一段是所有置换完成后剩下的 $M - 1$ 个数。

对于最后的 $M - 1$ 个数，路径的位留下的是最后进入路径的 $t - 1$ 个数，位置 $M$ 没有数，因为此时已经没有新的数补充进来。其他位置就是环，我们可以一次找一个环，用同余求出每个位置上的数。

我们可以求出整个取数序列，然后每次询问就可以直接求解了。

注意，有可能置换的操作次数很少，导致最初在路径中的数都没取出来，此时路径中可能会有一些最初就在路径中，但是位置变化的数，还有一些是新补充进来的数。

时间复杂度 $\mathcal O\left(N\right)$

算法 2

预处理出每个位置置换 $2^i$ 次时的倍增数组。

每次询问暴力跳倍增即可。

注意走到 $0$ 时应及时终止，因为已经离开了队列。

时间复杂度 $\mathcal O\left(N \log N\right)$

算法 3

倒推。从后往前 模拟每次置换，求出当前牌在本轮置换以前的位置。这样单次询问的复杂度就是 $\mathcal O\left(N\right)$。总时间复杂度 $\mathcal O(N \cdot Q)$，2013 年的老机器过不了。

代码写的是算法 2。

代码

Milk Scheduling

// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#define __FAST__ 1
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif

using tp = long long;
tp _Read_Int();
char _Read_Char();
char _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
}  // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 217'217'21;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

namespace __SOL__ {
struct Icecream {
  tp g, d;

  bool operator<(const Icecream& comp) const { return g < comp.g; }
};

void main([[maybe_unused]] size_t __CASE__) {  // :/
  constexpr tp Hat_N = 10003;
  tp n = ra, sum = 0;
  array<Icecream, Hat_N> a;
  priority_queue<Icecream> q;
  for (tp i = 1; i <= n; ++i) {
 a[i].g = ra;
 a[i].d = ra;
  }
  stable_sort(a.begin() + 1, a.begin() + n + 1,
           [](const Icecream& a, const Icecream& b) { return a.d > b.d; });
  for (tp time = a[1].d; time; --time) {
 static tp i = 1;
 while (i <= n && time <= a[i].d) {
   q.push(a[i++]);
 }
 if (q.size()) {
   sum += q.top().g;
   q.pop();
 }
  }
  printf("%lld\n", sum);
}  // :)
}  // namespace __SOL__

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp __MTCS__ = ::__MTCS__ ? ra : 1;
  for (tp __i = 1; __i <= __MTCS__; ++__i) {
 __SOL__::main(__i);
  }
  return EXIT_SUCCESS;
}

namespace _READ_RAW_ {
#if __FAST__
std::array<char, _BUF_SIZE_ + 1> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur = _BUF_.begin(), __End = __Cur + 1;

char _Rd() {
  if (++__Cur == __End) {
 __Cur = _BUF_.begin();
 __End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 *__End++ = 10;
  }
  return *__Cur;
}
}  // namespace _READ_RAW_

char _Get_IO_Top() {
  if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
 _READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
 _READ_RAW_::__End = _READ_RAW_::__Cur +
                     fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 if (_READ_RAW_::__Cur == _READ_RAW_::__End) {
   return --_READ_RAW_::__Cur, -1;
 } else {
   return *_READ_RAW_::__Cur--;
 }
  }
  return *(_READ_RAW_::__Cur + 1);
#else
char _Rd() {
  return getchar();
}
#endif
}  // namespace _READ_RAW_

tp _Read_Int() {
  bool __neg(0);
  char __c(_READ_RAW_::_Rd());
  tp __val;
  for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
 __neg = __c == 45;
  }
  __val = __c & 15;
  for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
 __val = __val * 10 + (__c & 15);
  }
  return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
  char __c(_READ_RAW_::_Rd());
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  return __c;
}
std::string _Read_String() {
  char __c(_READ_RAW_::_Rd());
  std::string __val;
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  do {
 __val.push_back(__c);
 __c = _READ_RAW_::_Rd();
  } while (__c != 32 && __c != 10 && __c != 13);
  return __val;
}

//\
 ___       ___         ___________     \
|\  \     |\  \       |\    ___   \
\ \  \    \ \  \      \ \   \|_\   \
 \ \  \  __\ \  \      \ \    ___   \
  \ \  \|\__\_\  \      \ \   \  \   \
\ \____________\      \ \___\  \___\
 \|____________|       \|___|  |___|

/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/

Vacation Planning

// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#define __FAST__ 1
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif

using tp = long long;
tp _Read_Int();
char _Read_Char();
char _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
}  // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 217'217'21;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

namespace __SOL__ {
void main([[maybe_unused]] size_t __CASE__) {  // :/
  constexpr tp Hat_N = 203;
  tp n = ra, m = ra, k = ra, q = ra, cnt = 0, sum = 0;
  array<array<tp, Hat_N>, Hat_N> f;
  for (auto&& i : f) {
 i.fill(-1ull >> 2);
  }
  while (m--) {
 tp u = ra, v = ra, w = ra;
 f[u][v] = min(f[u][v], w);
  }
  for (tp i = 1; i <= n; ++i) {
 f[i][i] = 0;
  }
  for (tp k = 1; k <= n; ++k) {
 for (tp i = 1; i <= n; ++i) {
   for (tp j = 1; j <= n; ++j) {
     f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
   }
 }
  }
  while (q--) {
 tp u = ra, v = ra, MIN = -1ull >> 2;
 for (tp i = 1; i <= k; ++i) {
   if (f[u][i] != (-1ull >> 2) && f[i][v] != (-1ull >> 2)) {
     MIN = min(MIN, f[u][i] + f[i][v]);
   }
 }
 if (MIN != (-1ull >> 2)) {
   ++cnt;
   sum += MIN;
 }
  }
  printf("%lld\n%lld\n", cnt, sum);
}  // :)
}  // namespace __SOL__

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp __MTCS__ = ::__MTCS__ ? ra : 1;
  for (tp __i = 1; __i <= __MTCS__; ++__i) {
 __SOL__::main(__i);
  }
  return EXIT_SUCCESS;
}

namespace _READ_RAW_ {
#if __FAST__
std::array<char, _BUF_SIZE_ + 1> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur = _BUF_.begin(), __End = __Cur + 1;

char _Rd() {
  if (++__Cur == __End) {
 __Cur = _BUF_.begin();
 __End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 *__End++ = 10;
  }
  return *__Cur;
}
}  // namespace _READ_RAW_

char _Get_IO_Top() {
  if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
 _READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
 _READ_RAW_::__End = _READ_RAW_::__Cur +
                     fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 if (_READ_RAW_::__Cur == _READ_RAW_::__End) {
   return --_READ_RAW_::__Cur, -1;
 } else {
   return *_READ_RAW_::__Cur--;
 }
  }
  return *(_READ_RAW_::__Cur + 1);
#else
char _Rd() {
  return getchar();
}
#endif
}  // namespace _READ_RAW_

tp _Read_Int() {
  bool __neg(0);
  char __c(_READ_RAW_::_Rd());
  tp __val;
  for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
 __neg = __c == 45;
  }
  __val = __c & 15;
  for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
 __val = __val * 10 + (__c & 15);
  }
  return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
  char __c(_READ_RAW_::_Rd());
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  return __c;
}
std::string _Read_String() {
  char __c(_READ_RAW_::_Rd());
  std::string __val;
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  do {
 __val.push_back(__c);
 __c = _READ_RAW_::_Rd();
  } while (__c != 32 && __c != 10 && __c != 13);
  return __val;
}

//\
 ___       ___         ___________     \
|\  \     |\  \       |\    ___   \
\ \  \    \ \  \      \ \   \|_\   \
 \ \  \  __\ \  \      \ \    ___   \
  \ \  \|\__\_\  \      \ \   \  \   \
\ \____________\      \ \___\  \___\
 \|____________|       \|___|  |___|

/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/

The Bessie Shuffle

// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#define __FAST__ 1
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif

using tp = long long;
tp _Read_Int();
char _Read_Char();
char _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
}  // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 217'217'21;

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

namespace __SOL__ {
void main([[maybe_unused]] size_t __CASE__) {  // :/
  constexpr tp Hat_LM = 30, Hat_M = 1e5 + 3;
  tp n = ra, m = ra, q = ra;
  array<array<tp, Hat_M>, Hat_LM> p;
  for (tp i = m; i; --i) {
 p[0][m - ra + 1] = i - 1;
  }
  for (tp i = 1; i < Hat_LM; ++i) {
 for (tp j = 1; j <= m; ++j) {
   p[i][j] = p[i - 1][p[i - 1][j]];
 }
  }
  while (q--) {
 tp q = ra, t = q < m ? m : q, l = n - t + 1, ql = 0;
 q = q < m ? q : m;
 for (tp i = Hat_LM - 1; ~i; --i) {
   if (tp loc = ql + (1ll << i); loc <= l && p[i][q]) {
     ql = loc;
     q = p[i][q];
     t += 1ll << i;
   }
 }
 printf("%lld\n", n - t + m - (ql != l ? p[0][q] : q - 1));
  }
}  // :)
}  // namespace __SOL__

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

signed main() {
  tp __MTCS__ = ::__MTCS__ ? ra : 1;
  for (tp __i = 1; __i <= __MTCS__; ++__i) {
 __SOL__::main(__i);
  }
  return EXIT_SUCCESS;
}

namespace _READ_RAW_ {
#if __FAST__
std::array<char, _BUF_SIZE_ + 1> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur = _BUF_.begin(), __End = __Cur + 1;

char _Rd() {
  if (++__Cur == __End) {
 __Cur = _BUF_.begin();
 __End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 *__End++ = 10;
  }
  return *__Cur;
}
}  // namespace _READ_RAW_

char _Get_IO_Top() {
  if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
 _READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
 _READ_RAW_::__End = _READ_RAW_::__Cur +
                     fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
 if (_READ_RAW_::__Cur == _READ_RAW_::__End) {
   return --_READ_RAW_::__Cur, -1;
 } else {
   return *_READ_RAW_::__Cur--;
 }
  }
  return *(_READ_RAW_::__Cur + 1);
#else
char _Rd() {
  return getchar();
}
#endif
}  // namespace _READ_RAW_

tp _Read_Int() {
  bool __neg(0);
  char __c(_READ_RAW_::_Rd());
  tp __val;
  for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
 __neg = __c == 45;
  }
  __val = __c & 15;
  for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
 __val = __val * 10 + (__c & 15);
  }
  return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
  char __c(_READ_RAW_::_Rd());
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  return __c;
}
std::string _Read_String() {
  char __c(_READ_RAW_::_Rd());
  std::string __val;
  for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
  }
  do {
 __val.push_back(__c);
 __c = _READ_RAW_::_Rd();
  } while (__c != 32 && __c != 10 && __c != 13);
  return __val;
}

//\
 ___       ___         ___________     \
|\  \     |\  \       |\    ___   \
\ \  \    \ \  \      \ \   \|_\   \
 \ \  \  __\ \  \      \ \    ___   \
  \ \  \|\__\_\  \      \ \   \  \   \
\ \____________\      \ \___\  \___\
 \|____________|       \|___|  |___|

/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/

分类：做题笔记
最后更新于：2022-12-31 21:50:26^UTC+8
标签： USACO 思维贪心反悔贪心最短路 Floyd 倍增 2013

红黑树的小屋

USACO 2013 DEC, Sliver

发布于 2022-08-11

题目

题解

T1

算法 1

算法 2

算法 3

T2

算法 1

算法 2

T3

算法 1

算法 2

算法 3

代码

暂无评论

发表评论