华为9.9笔试 第二题第三题题解

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1000 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
struct Edge {
  int u, v, next;
} edge[maxn * maxn * 4];
int head[maxn * maxn];
int tot = 0;
int in[maxn * maxn];
void init() {
  cl(head, -1);
  cl(in, 0);
  tot = 0;
}
void addedge(int u, int v) {
  edge[tot] = Edge{u, v, head[u]};
  head[u] = tot++;
  in[v]++;
}
int n, m;
int a[maxn][maxn];
int id[maxn][maxn];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int legal(int x, int y) { return (x >= 1 && x <= n && y >= 1 && y <= m); }
int dp[maxn * maxn];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  }
  int now_id = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) id[i][j] = ++now_id;
  }
  init();
  for (int x = 1; x <= n; x++) {
    for (int y = 1; y <= m; y++) {
      for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (legal(xx, yy) && a[x][y] < a[xx][yy]) {
          addedge(id[x][y], id[xx][yy]);
        }
      }
    }
  }
  std::queue<int> q;
  cl(dp, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (!in[id[i][j]]) {
        q.push(id[i][j]);
        dp[id[i][j]] = 1;
      }
    }
  }
  int Max = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    Max = std::max(Max, dp[u]);
    for (int i = head[u]; ~i; i = edge[i].next) {
      int v = edge[i].v;
      dp[v] = std::max(dp[v], dp[u] + 1);
      in[v]--;
      if (!in[v]) {
        q.push(v);
      }
    }
  }
  printf("%d\n", Max);
  return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
const int N = 1e5 * 30 + 10;
struct Trie {
  using LL = long long;
  LL ch[N][2], sz;
  LL val[N], ed[N];
  void Init() {
    memset(ch[0], 0, sizeof(ch[0]));
    ed[0] = 0;
    sz = 1;
  }
  void Insert(LL x) {
    int u = 0;
    for (int i = 40; i >= 0; i--) {
      int v = (x & (1ll << i)) > 0 ? 1 : 0;
      if (!ch[u][v]) {
        memset(ch[sz], 0, sizeof(ch[sz]));
        val[sz] = 0;  //每个节点的附加信息
        ed[sz] = 0;
        ch[u][v] = sz++;  //存储该节点的编号sz
      }
      u = ch[u][v];
      val[u]++;
    }
    ed[u] = x;  //最后一个节点记录数值
  }
  void Delete(LL x) {
    int u = 0;
    for (int i = 40; i >= 0; i--) {
      int v = (x & (1ll << i)) > 0 ? 1 : 0;
      u = ch[u][v];
      val[u]--;
    }
    // ed[u]=0;//可能有重复数字，若置为0后该位置的另一个数字也被删除了
  }
  LL Search(LL x) {
    int u = 0;
    for (int i = 40; i >= 0; i--) {
      int v = (x & (1ll << i)) > 0;  //判断条件
      if (ch[u][!v] && val[ch[u][!v]]) {
        u = ch[u][!v];
      } else if (ch[u][v] && val[ch[u][v]]) {
        u = ch[u][v];
      } else
        return x ^ ed[u];
    }
    return x ^ ed[u];
  }
} trie;
int n;
ll w[maxn];
vector<int> g[maxn];
int in[maxn];
ll Max = 0;
ll sum[maxn];
void dfs(int u, int fa) {
  if (fa == -1) {
    sum[u] = w[u];
  } else {
    sum[u] = sum[fa] ^ w[u];
  }
  // cout << u << " " << sum[u] << endl;
  ll query = trie.Search(sum[u]);
  trie.Insert(sum[u]);
  Max = max(Max, query);
  Max = max(Max, sum[u]);
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (fa == v) continue;
    dfs(v, u);
  }
  trie.Delete(sum[u]);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i <= n; i++) g[i].clear();
  cl(in, 0);
  for (int i = 1; i <= n; i++) {
    int id, l, r;
    ll weight;
    scanf("%d %lld %d %d", &id, &weight, &l, &r);
    w[id] = weight;
    if (l != -1) {
      g[id].push_back(l);
      g[l].push_back(id);
      in[l]++;
    }
    if (r != -1) {
      g[id].push_back(r);
      g[r].push_back(id);
      in[r]++;
    }
  }
  int rt = -1;
  for (int i = 1; i <= n; i++) {
    if (!in[i]) {
      rt = i;
      break;
    }
  }
  trie.Init();
  // trie.Insert(0);
  dfs(rt, -1);
  printf("%lld\n", Max);
  return 0;
}
/*
5
1 1 2 3
2 4 -1 -1
3 2 -1 4
4 5 -1 5
5 3 -1 -1
*/