9-9華為筆試，3題AK

num1

大概思路：題目要求的是，第一個完美排列出現的位置，然后看資料范圍，給出的數值最大是5，那么我們可以考慮，把這兩個串合成一個，A[i] = a[i] * 6 + b[i];，
對于給出的大串也是如此B[i] = c[i] * 6 + d[i]; 然后就是直接kmp匹配，找到出現的第一個位置，變成kmp模板題

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

const int mn = 1e6 + 10;

int n, m;
int nx[mn];

void cal_next(int b[])
{
 memset(nx, 0, sizeof nx);
 nx[0] = -1;
 int k = -1;
 int j = 0;
 while (j < m)
 {
  if (k == -1 || b[j] == b[k])
  {
   j++; k++;
   nx[j] = k;
  }
  else
   k = nx[k];
 }
}

int KMP(int a[], int b[])
{
 cal_next(b);

 int i = 0, j = 0;
 while (i < n && j < m)
 {
  if (j == -1 || a[i] == b[j]) i++, j++;
  else j = nx[j];
 }
 if (j >= m) return i - m + 1;
 else return 0;
}

int a[mn], b[mn];
int c[mn], d[mn];
int A[mn], B[mn];

int main()
{
 cin >> m;
 for (int i = 0; i < m; i++) scanf("%d", &a[i]);
 for (int i = 0; i < m; i++) scanf("%d", &b[i]);
 for (int i = 0; i < m; i++)
  A[i] = a[i] * 6 + b[i];


 cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &c[i]);
    for (int i = 0; i < n; i++) scanf("%d", &d[i]);
 for (int i = 0; i < n; i++)
  B[i] = c[i] * 6 + d[i];

    cout << KMP(B, A) << endl;

    return 0;
}

/*
2
3 4
3 4
8
0 0 0 0 3 4 0 0
0 0 0 0 3 4 0 0

*/

num2

裸的記憶化搜索，由于有單調性，不難想到DP，要計算某點A為起點的最長水溝長度lenA，先計算A的上下左右四個點B1\B2\B3\B4中比A低的點如B1、B2的水溝長度，計B1、B2為起點的最長水溝長度為lenB1、lenB2，則lenA = max(lenB1, lenB2) + 1，如果四周沒有比A低的點則lenA = 1;

void DFS(int nowx,int nowy)
{
    if(dp[nowx][nowy]) return ;
    dp[nowx][nowy]=1;
    for(int i=0;i<=3;i++){
        int tx=nowx+x[i];
        int ty=nowy+y[i];
        if(tx>=1&&tx<=N&&ty>=1&&ty<=M&&a[nowx][nowy]>a[tx][ty]){
            DFS(tx,ty);
            dp[nowx][nowy]=max(dp[nowx][nowy],dp[tx][ty]+1);
        }
    }
    ans=max(ans,dp[nowx][nowy]);
}
for(int i=1;i<=N;i++)
   for(int j=1;j<=M;j++)
       DFS(i,j);

num3:

題意：給定一棵樹，問最大亦或路徑，
思路: 首先最大亦或，得需要用01Trie來做，如果你不會，那么這題應該就不會了，（勸退）
1，先介紹一下什么是Trie字典樹：給你一本字典，讓你查里面是否有某個單詞，比如‘bcd’，你應該會看是否有b開頭的單詞，然后看‘bc’，然后看‘bcd’， 這個的話，想象一個樹，從根往下，連起來就是這個單詞， 我們把單詞都插入這個樹里，就形成了一顆字典樹，如果查單詞，那么就從根向下查即可， 這個相比hash的好處：（1）不會出現hash那樣的差錯，（2）前綴重復的地方可以節省空間，

2，其次是要知道亦或的性質： a到b的亦或=a到根的亦或XORb到根的亦或， 所以我們求出每個點到根的亦或值，假設現在的亦或為a[]， 現在就是要在這些a[]里面找兩個數，使得他們的亦或最大，

3，知道的性質2,和字典樹， 我們就可以著手處理此題了，不過我們現在不是找單詞，而是找最大亦或，我們把a[]集合的數都變為2進制，按高位到地位一次插入樹里，現在要在集合里面找最大亦或，等效于高位盡可能不一樣， 所以得盡量走反向，即我如果是1，我就看兒子節點是否有0…這在query里面得到體現，

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int Laxt[maxn],Next[maxn],To[maxn],cnt;
int W[maxn],ch[maxn*30][2],ans,node;
void add(int u,int v)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}
void dfs(int u,int f)
{
    W[u]=W[f]^W[u];
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(To[i]==f) continue;
        dfs(To[i],u);
    }
}
int query(int x)
{
    int now=0,res=0;
    for(int i=30;i>=0;i--){
        int t=(x>>i)&1;
        if(ch[now][1-t]) res+=(1<<i),now=ch[now][1-t];
        else now=ch[now][t];
    }
    return res;
}
int insert(int x)
{
    int now=0;
    for(int i=30;i>=0;i--){
        int t=(x>>i)&1;
        if(!ch[now][t])  ch[now][t]=++node;
        now=ch[now][t];
    }
}
int main()
{
    int N,id,x;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%d",&id);
        scanf("%d",&W[id]);
        for(int j=1;j<=2;j++){
           scanf("%d",&x);
           if(x!=-1){
               add(id,x);
               add(x,id);
           }
        }
    }
    dfs(1,0);
    for(int i=1;i<=N;i++){
        if(i>1) ans=max(ans,query(W[i]));
        insert(W[i]);
    }
    printf("%d\n",ans);
    return 0;
}
/*
5
1 1 2 3
2 4 -1 -1
3 2 -1 4
4 5 -1 5
5 3 -1 -1
*/