华为9.9笔试 第二题第三题题解
第二题
将每个方格视为一个点 若两个相邻点满足一个点的值小于另外一个点 就连一条有向边 显然这个图肯定是个DAG(有向无环图） 在DAG跑一遍最长路dp就可以了 复杂度((4*n*n+n*n))
#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;
}
第三题 假设根为root，令从root到i节点路径的异或为sum[i]，那么路径(u,v)的异或值就是sum[u]^sum[v]
于是，可以从根节点dfs，并快速查询满足sum[u]^sum[v]的最大的v即可
查询可以采用01字典树完成
复杂度（（n+e)*30）
#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
*/ 
查看4道真题和解析