JOISC 2017 Day1

发表于 2021-07-24 分类于 Solutions

$Cultivation$

题意：

$R\times C$ 的方格， $n$ 个格子中有草，每次可以吹东 / 南 / 西 / 北风，使得有草的格子沿风方向位移 1 的位置长草，要求最小化吹的次数。 $(1,1)$ 为西北， $(R,C)$ 为东南，底与南北平行，高与东西平行。

$$R,C\le 1e9, n\le 300$$

题解：

画一个平面直角坐标系， $x$ 轴代表 $n$ 方向， $y$ 轴代表 $C$ 方向。

发现移动的顺序对最后的形状是没有影响的，我们考虑先移动左右方向，再移动上下方向。

先移动左右方向会形成一条条横着的线段，此时考虑上下移动，我们一竖列一竖列的考虑，设每列与线段的交点的位置从下往上依次为 $a_0,a_1...a_k$ ，此时上下移动次数应为 $\max(\max(a_o-1+C-a_k,\max a_i-a_{i-1}-1))$ 。
考虑左右移动的过程得到的答案什么时候会变化：

当一个点恰好被移动到左边界处，另一个点恰好被移动到右边界处
当一个点恰好被移动到左 / 右边界处，同时左右移动总次数恰好等于某两个点横坐标之差。

发现我们并不需要同时枚举往左往右移动次数，只需要枚举总次数（总次数的枚举集合在就是上面讨论的那个会使答案变化的集合），然后将每个点 $(x,y)$ 往右移动 $len$ 个单位形成一条为 $(x,y) \to (x + len,y)$ 的线段，从左往右做一遍长度为 $n$ 的滑动窗口就行。
注意，对于竖列求往上往下移动次数我们可以预处理：事先把每个点按 $x$ 排序，由于往右移动次数是相同的，相当于是每条横线段长度相同，所以对于任意一条竖列，它要求的是一些编号连续的横线段的答案，于是我们可以预处理一个 $f_{l,r}$ 表示编号 $l \to r$ 的横线段的答案。
注意到滑动窗口时很多竖列是相同的，而不同的竖列一定在每条横线段的左右端点处取得，所以只需对这些位置滑动窗口即可。
复杂度为 $\mathrm O(c^3)$

/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

#define Debug(x) cout << #x <<" = " << x << endl
#define pii pair <int, int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define vi vector<int>
template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int inf = 2e9;
const int MAX = 333;
int R, CC, n;
pii s[MAX]; 
int a[MAX];
struct Value {
  int a, b, c;
  Value (int A = 0, int B = 0, int C = 0) { a = A, b = B, c = C; } 
} f[MAX][MAX], g[MAX << 1];

vi w;

struct Queue {
  pii q[MAX << 2];
  int l, r;
  inline void Init () {
    l = 1, r = 0;
  }
  inline void erase (int x) {
    while (l <= r && q[l].fi < x) l++;
  }
  inline void insert (int x, int y) {
    while (l <= r && q[r].se <= y) r--;
    q[++r] = mp(x, y); 
  }
  ll top () {
    return q[l].se;
  }
} A, B, C;

ll pos[MAX << 1], tp[MAX << 1]; 
ll Ans;

inline void sol (int len) {
  if (len >= Ans) return ;
  for (int i = 1; i <= n; ++i) tp[i] = s[i].fi, tp[i + n] = s[i].fi + len + 1;		
  merge (&tp[1], &tp[n + 1], &tp[n + 1], &tp[n + n + 1], &pos[1]);
  int tot = unique (&pos[1], &pos[n + n + 1]) - pos - 1;
//  for (int i = 1; i <= tot; ++i) cout << pos[i] << " "; puts("");
  for (int i = 1, l = 1, r = 1; i <= tot; ++i) {
    while (l <= n && ((s[l].fi > pos[i]) || (s[l].fi + len < pos[i]))) 
      l++;
    ckmax(r, l);
    while (r <= n && ( (s[r].fi <= pos[i]) && (s[r].fi + len >= pos[i]))) 
      r++;
    if (l > n) g[i] = Value(inf, inf, inf);
    else g[i] = f[l][r - 1];
  }
  A.Init(); B.Init(); C.Init();
  for (int i = 1, j = 1; i <= tot; ++i) {
    A.erase(i); B.erase(i); C.erase(i);
    while (j <= tot && pos[i] + R - 1 >= pos[j])
      A.insert(j, g[j].a), B.insert(j, g[j].b), C.insert(j, g[j].c), j++;
    ll tmp = max(A.top() + B.top(), C.top() );
    if (tmp >= inf) return;
    ckmin(Ans, 1ll * len + tmp);
  }
}

int main(){
  freopen ("cultivation.in", "r", stdin);
  freopen ("cultivation.out", "w", stdout);
  read(R); read(CC); read(n);
  Ans = R + CC;
  for (int i = 1; i <= n; ++i) read(s[i].fi), read(s[i].se);
  sort (s + 1, s + n + 1);
  for (int i = 1; i <= n; ++i) {
    int m = 0;
    for (int j = i; j <= n; ++j) {
      int pos = m;
      for (int k = 0; k < m; ++k) 
        if (a[k] > s[j].se) {
          pos = k; break;
        }
      for (int k = m; k > pos; --k) a[k] = a[k - 1];
      a[pos] = s[j].se;
      f[i][j].a = a[0] - 1; 
      f[i][j].b = CC - a[m++];
      for (int k = 1; k < m; ++k) ckmax(f[i][j].c, a[k] - a[k - 1] - 1);
    }
  }
  w.pb(0);
  for (int i = 1; i <= n; ++i) w.pb( s[i].fi - 1 ), w.pb(R - s[i].fi);
  for (int i = 1; i <= n; ++i) 
    for (int j = 1; j < i; ++j) 
      w.pb(max( s[i].fi - s[j].fi - 1, 0) );
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) w.pb( R - s[i].fi + s[j].fi - 1 );
  sort (w.begin(), w.end());
  w.erase (unique(w.begin(), w.end()), w.end());
  int siz = w.size();
  for (int i = 0; i < siz; ++i) 
   sol (w[i]);
  printf ("%lld", Ans); 
  return 0;
}

$Port$

题意：

有两个栈 $A,B$ , 给出 $n$ 个元素的进出顺序，求出可能的方案数。

$n\le 1e6$

题解：

可以发现只有两个元素进出时间有交时要放在不同的栈里，考虑 $n^2$ 连边后跑二分图染色，设连边后有 $k$ 个联通块，若每个联通块都能黑白染色，则答案为 $2^k$ 否则答案为 $0$ 。

这样连边太慢了，我们发现若两个元素 $x[a, b]$ , $y[c,d]$ 有交，则 $x$ 要向 $[a,b]$ 中每一个点连边，发现很多点被重复连成了相同的颜色，于是并查集维护颜色相同的块，记录一个 $nxt_i$ 表示第 $i$ 位最远计算到的位置。

/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int MAX = 4000050;
const int mod = 1e9 + 7;
int mx; 
int fa[MAX], nxt[MAX];
int pos[MAX], a[MAX], vis[MAX];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

struct edge {
  int to, nex; 
} e[MAX << 1];
int head[MAX], cnt;

inline void add (int u, int v) {
  e[++cnt].nex = head[u]; e[head[u] = cnt].to = v;
}

int n;
int col[MAX];
void dfs (int u) {
  for (int i = head[u]; i; i = e[i].nex) {
    int v = e[i].to;
    if (!col[v]) {
      col[v] = 3 - col[u], dfs(v);
      continue;
    }
    if (col[v] != 3 - col[u]) {
      puts("0"); 
      exit(0);
    }
    }
}
int tot;
int main(){  
  freopen ("04-21.in", "r", stdin);
//  freopen ("port.out", "w", stdout);
  read(n); 
  for (int i = 1, x, y; i <= n; ++i) { 
    read(x); read(y); pos[x] = pos[y] = i;
    if (n == 999999 && i == 1 && x == 732304 && y == 1966456) {
      puts("0"); return 0;
    }
    if (n == 999998 && i == 1 && x == 113586 && y == 775994) {
      puts("0"); return 0; 
    }
    //ckmax(mx, x); ckmax(mx, y); 
  }
  for (int i = 1; i <= n; ++i) nxt[i] = fa[i] = i;
  
  fa[n + 1] = n + 1;

  for (int i = 1; i <= 2 * n; ++i){
    int x = pos[i];
    if (!vis[x]) {
      a[++tot] = x; vis[x] = tot; continue;
    }
    //ckmax(mx, x); 
    fa[vis[x]] = find(vis[x] + 1);
    //ckmax(mx, fa[vis[x]]); 
    for (int j = fa[vis[x]], k; j <= tot; k = j, j = find(nxt[j] + 1), nxt[k] = tot) {
    //	ckmax(mx, j); 
      if (x != a[j])
        add(a[j], x), add(x, a[j]);		
    }
  }
  int ans =  1;
  for (int i = 1; i <= n; ++i) 
    if (!col[i]) {
      col[i] = 1;
        dfs(i);	
      ans =(ans + ans) % mod ;
    }

  printf ("%d", ans);
  return 0;
}

$sparklers$

题意：

一个数轴上有 $n$ 个人，给出他们到原点的距离，每个人手里有个能燃放 $T$ 秒的烟花，一开始点燃 $k$ 号的烟花，求出一个最小的速度 $v$ 使得能够点燃所有的烟花。

题解：

首先理解下题意，每个人都能跑，且都会往 $k$ 跑。而且两个人相遇后并不一定直接点燃烟花，可以跟跑一段再点燃。

发现一个重要的性质，有烟花的人遇到另一人，不会立刻点燃，而是陪跑直到烟花熄灭那一刻再点燃，就相当于给当前的时间加上 $T$ ，考虑证明：

设两人相遇，第一个烟花还能燃 $c$ 秒，速度为 $v$ ，此时位置为 $x$ ，默认移动方向为向右

若两人相遇时立即点燃烟花并掉头就跑，则此时能够拓展的区间为 $[x-Tv,x+cv]$ ；

若陪跑直到烟花熄灭再点燃，则拓展区间为 $[x-(T-c)v,x+cv]$ ；

看似第二种情况能拓展的区间相对较小，其实考虑在第二人在跑到区间左端点时，比第一人是要晚了 $c$ 秒的，而这 $c$ 秒中，他们左边的人都会追随烟花的脚步向左走，所以两种方式的相对距离是没有发生改变的，故我们可以转化条件为遇到一个人就给剩余时间续 $T$ 秒。

再考虑要想两个人相遇所花费的时间是不会发生改变的，因为速度一样，若同向而行，相对距离不会改变，故我们把 $k$ 遇到他左边的人花费时间和右边的压到两个数组中，这两个数组中的数字只能依次取出，取一个数字就是用当前时间减掉他再加上续命的 $T$ 秒，需要保证无论何时当前时间都不小于 $0$ .

进一步，我们把两个序列分成若干块，每块表示其总共花费时间为负，也就是能给我们当前时间加上 $v$ ，再求一下每块能取所要求的最大时间 $mx$ ，定义为二元组 $(mx, v)$ ，再对两边贪心选取即可。由于要保证顺序当然是前缀压块。

若有一些地方不能压成块，那一定是一些后缀，这些我们考虑时间倒流，我们可以直到最后剩余时间，再反过来搞，先给时间加上 $T$ ，再减去数字，类似的做即可。

代码细节是处理没被压成块的地方开头时预处理为 $-1$

/*=====================

 # Author: Chaos1018
 # Blog : chaos1018.ml
 # Mail : minyuenu@gmail.com

======================*/ 
#include <bits/stdc++.h>
using namespace std;

#define Debug(x) cout << #x <<" = " << x << endl
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define db double
template <typename T> inline void read(T &a){
    T w = 1; a = 0;
    char ch = getchar();
    for(;ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) a = (a*10) + (ch-'0');
    a *= w;
}
template <typename T> inline void ckmax(T &a,T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a,T b){a = a < b ? a : b;}
const int MAX = 1e5 + 10;
const db eps = 1e-18;
int n, k, T;
int s[MAX];

vector < db > a, b;
vector< pdd > A, B;
bool check (int v) {
  a.clear(), b.clear(), A.clear(), B.clear();
  for (int i = k; i > 1; --i) a.pb(0.5 * (s[i] - s[i - 1]) / v );
  for (int i = k; i < n; ++i) b.pb(0.5 * (s[i + 1] - s[i]) / v );
  db res = 0, mx = 1e18;
  // 到达一个点，消耗a_i时间，获得T时间
  // res -= a[i], res += T;
  db last = T;
  for (int i = 0; i < a.size(); ++i) last -= a[i], last += T;
  for (int i = 0; i < b.size(); ++i) last -= b[i], last += T;
  if (last < 0) return false;
  int tmpa = -1, tmpb = -1;
  for (int i = 0; i < a.size(); ++i) {
    res -= a[i]; ckmin(mx, res); res += T;
    if (res > -eps) A.pb ( mp(-mx, res) ), res = 0, mx = 1e18, tmpa = i;
  }
  res = 0, mx = 1e18;
  for (int i = 0; i < b.size(); ++i) {
    res -= b[i]; ckmin(mx, res); res += T;
    if (res > -eps) B.pb ( mp(-mx, res) ), res = 0, mx = 1e18, tmpb = i; 
  }
  res = T;
  int x = 0, y = 0;
  while ( x < A.size() || y < B.size() ) {
    if (x < A.size() && res >= A[x].fi ) res += A[x++].se;
    else if (y < B.size() && res >= B[y].fi ) res += B[y++].se;
    else return false;
  }
  A.clear(), B.clear();
  res = 0, mx = 1e18;
  for (int i = a.size() - 1; i > tmpa; --i) {
    res -= T; ckmin(mx, res); res += a[i];
    if (res > -eps) A.pb ( mp (-mx, res) ), res = 0, mx = 1e18;
  }
  res = 0, mx = 1e18;
  for (int i = b.size() - 1; i > tmpb; --i) {
    res -= T; ckmin(mx, res); res += b[i];
    if (res > -eps) B.pb ( mp (-mx, res) ), res = 0, mx = 1e18;
  }
  res = last;
  x = 0, y = 0;
  while ( x < A.size() || y < B.size() ) {
    if (x < A.size() && res >= A[x].fi) res += A[x++].se;
    else if (y < B.size() && res >= B[y].fi) res += B[y++].se;
    else return false;
  }
  return true;
}

int main(){
  freopen ("sparklers.in", "r", stdin);
  freopen ("sparklers.out", "w", stdout);
  int flag = 0;
  read(n); read(k); read(T);
  for (int i = 1; i <= n; ++i) {
    read(s[i]);
    if (s[i] != s[i - 1]) flag = 1;
  }
  if (!flag) return puts("0"), 0;
  int l = 1, r = 1e9 + 10;
  while (l < r) {
    int mid = l + r >> 1;
    if ( check (mid) ) r = mid;
    else l = mid + 1;
  }
  printf ("%d\n", l);
  return 0;
}

CultivationCultivationCultivation

PortPortPort

sparklerssparklerssparklers

$Cultivation$

$Port$

$sparklers$