2021-9-21 Test

发表于 分类于

100 + 100 + 0
倒是没什么好说的，开始一边在码 T2 一边在 hack lzh 双线作战，然后静下心来 Rush 完 T1 就弃考了，T3 也不是我考试时能写出来的 QwQ

game

模拟 2048 游戏

n≤8,m≤105n\le 8, m\le 10^5

Sol:

按题意模拟即可
感觉代码写的十分清新自然，贴一发

  #pragma GCC optimize(2)
  #pragma GCC optimize(3)

/* ==============================
 *  Author : Odalys 
 *
 *  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<<3)+(a<<1)+(ch^48);
  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;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
#define mck insert
#define era erase
const int N = 10;
int n, m;
int Id (int x, int y) { return (x - 1) * n + y; }
set <int> emp;
int val[N][N], res[N][N];
pii gra[N * N];
inline void cache () {
  For (i, 1, n) For (j, 1, n)
    res[i][j] = val[i][j];
}
inline bool diff () {
  For (i, 1, n) For (j, 1, n) 
    if (res[i][j] != val[i][j]) return true;
  return false;
}

inline void upd (int k, int v) {
  int top = 0;
  for (auto x : emp) {
    top++;
    if (top == k) {
      val[gra[x].fi][gra[x].se] = v;
      emp.era(x);
      break;
    }
  }
}

inline void Mckenna (int x, int y, int fx, int fy) {
  val[x][y] = val[fx][fy];
  emp.era(Id(x, y));
  emp.mck(Id(fx, fy));
  val[fx][fy] = 0;
} //move (fx, fy) to (x, y)

inline void move (int to) {
  if (to == 0) {
    For (i, 1, n - 1) For (j, 1, n) {
      if (!val[i][j]) 
        For (k, i + 1, n) 
          if (val[k][j]) { 
            Mckenna(i, j, k, j);	
            break;
          }
    }
  }
  if (to == 1) {
    foR (i, n, 2) For (j, 1, n) {
      if (!val[i][j]) {
        foR (k, i - 1, 1) 
          if (val[k][j]) {
            Mckenna(i, j, k, j);
            break;
          }
      }
    }
  }
  if (to == 2) {
    For (j, 1, n - 1) For (i, 1, n) {
      if (!val[i][j]) 
        For (k, j + 1, n) 
          if (val[i][k]) {
            Mckenna(i, j, i, k);
            break;
          }
        
    }
  }
  if (to == 3) {
    foR (j, n, 2) For (i, 1, n) {
      if (!val[i][j]) 
        foR (k, j - 1, 1) 
          if (val[i][k]) {
            Mckenna(i, j, i, k); 
            break;
          }
    }
  }
}

int tmp;

inline void merge (int to) {
  if (to == 0) {
    For (i, 1, n - 1) For (j, 1, n) {
      if (val[i][j] == val[i + 1][j] && val[i][j]) {
        tmp += val[i][j] * 2;
        val[i + 1][j] = 0;
        val[i][j] *= 2;
        emp.mck(Id(i + 1, j));
      }
    } 
  }
  if (to == 1) {
    foR (i, n, 2) For (j, 1, n) {
      if (val[i][j] == val[i - 1][j] && val[i][j]) {
        tmp += val[i][j] * 2;
        val[i - 1][j] = 0;
        val[i][j] *= 2;
        emp.mck(Id(i - 1, j));
      } 
    }
  }
  if (to == 2) {
    For (j, 1, n - 1) For (i, 1, n) {
      if (val[i][j] == val[i][j + 1] && val[i][j]) {
        tmp += val[i][j] * 2;
        val[i][j + 1] = 0;
        val[i][j] *= 2;
        emp.mck(Id(i, j + 1));
      }
    }
  }
  if (to == 3) {
    foR (j, n, 2) For (i, 1, n) {
      if (val[i][j] == val[i][j - 1] && val[i][j]) {
        tmp += val[i][j] * 2;
        val[i][j - 1] = 0;
        val[i][j] *= 2;
        emp.mck(Id(i, j - 1));
      }
    }
  }
}

inline void print () {
  For (i, 1, n) {
    For (j, 1, n) cout << val[i][j] << " ";
    puts("");
  }
  puts("");
}

int main() {
  read(n); read(m);
  For (i, 1, n) For (j, 1, n)
    emp.mck(Id(i, j)), gra[Id(i,j)] = mp(i, j); 	
  int x, y, v; 
  read(x), read(y), read(v);
  emp.era(Id(x, y)); val[x][y] = v;
  read(x), read(y), read(v);
  emp.era(Id(x, y)); val[x][y] = v;
  int Ans1 = 0, Ans2 = 0;
  For (i, 1, m) {
    int d, k, v; read(d); read(k); read(v);
    cache();  
    move(d); 
    tmp = 0;
    merge(d);
    move(d); 
    Ans2 += tmp;
    if ( diff () ) Ans1++; 
    else break;
    int r = emp.size();
    upd (1 + (k % r), v);  
  }
  printf ("%d\n%d", Ans1, Ans2);
  return 0;
}

复杂度是 O(n3m)\mathrm O(n^3m) 的

seq

一个长度为 nn 的序列，选出一个子序列，定义其权值为其和除以上升段 + 下降段总段数，最大化权值

n≤105n\le 10^5

Sol:

贪心地发现答案要不是一整段上升的，要不一段上升一段下降的

于是就正反跑一遍 LIS 枚举一个断点搞一搞就好

mst

一张无向图，边权为一个虚数，定义虚数比大小为模长的比较，求最大生成树。

Sol:

假如我们知道答案向量的方向，我们把每条边向其取投影长度，那么按这个跑 kruskl 就是最大生成树长度。

~所以我们就可以枚举每个方向求 max~

这样显然会 T，于是考虑 kruskl 的过程中，我们并不关注每条边具体有多长，我们只关注两条边的相对关系，于是考虑一个类似临界的问题，考虑枚举两条向量，我们能求出一条向量使这两条投影长度相同，那么这两个区间内，每条边权的相对大小不会改变，于是 kruskl 求出的生成树边也不会改变，于是每个区间内取个代表向量，然后直接做即可。