2017.7.26 機房測試（KMP/Hash，分塊+可持久化Trie樹貪心，主席樹+AC自動機）

1 無盡的矩陣(matrix.c/cpp/pas)

1.1 題目描述

從前有一個的小矩陣，矩陣的每個元素是一個字母(區分大小寫)，突然有一天它發生了變異，覆寫了整個二維空間，即不停自我複制産生相同的矩陣然後無隙放置。現在二維空間已經被它占領了，但你隻被告知了大小為R*C空間的内容(可能包含不完整的原矩陣)，為了将它恢複原狀，你需要找到滿足條件的面積最小的原矩陣。

奇怪的是，同時有 T 個二維空間發生了變異，你需要盡快解決這些變異。

1.2 輸入格式

第一行為一個整數T，表示二維空間數目。

接下來T組資料。每組資料第一行包含兩個數 R，C，表示你被告知的空間大小；接下來 R 行，每行包含

C 個字母，表示你被告知的空間内容。

1.3 輸出格式

對于每一組資料輸出一行，每行隻包含一個數，表示最小的原矩陣面積。

1.4 樣例輸入

2 5

ABABA

2 8

ABCDEFAB

AAAABAAA

1.5 樣例輸出

1.6 資料範圍與約定

對于前20％的資料R<=20，C<=20；

對于前40％的資料R<=400，C<=100；

對于100％的資料R<=5000 ，C<=100，T<=50。

【解題報告】

做法1：hash求出每一行可能的循環節長度，取公共的最小循環節長度即可，列同理。将兩次求得的最小循環節長度相乘即為答案。較慢，可能會逾時。

代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;

unsigned long long base1= , base2= , pow1[] , pow2[] , h[][] ;
int R , C ;
char mat[][] ; 

char get_c(){
    char c;
    while((c=(char)getchar())!=EOF) if(!isspace(c)) break ;
    return c;
}
unsigned long long get_h(int x1,int y1,int x2,int y2){
    return h[x2][y2]-h[x1-][y2]*pow1[x2-x1+]-h[x2][y1-]*pow2[y2-y1+]+h[x1-][y1-]*pow1[x2-x1+]*pow2[y2-y1+] ;
}
bool check(int a,int b){
    for(int i=;i<=R;i+=a){
        for(int j=;j<=C;j+=b){
            int ti=min(i+a-,R) , tj=min(j+b-,C) ;
            if(get_h(,,ti-i+,tj-j+)!=get_h(i,j,ti,tj)) return false ;
        }
    }
    return true ;
}
void solve(){
    scanf("%d%d",&R,&C) ;
    memset(h,,sizeof(h)) ;
    for(int i=;i<=R;++i) for(int j=;j<=C;++j) mat[i][j]=get_c() , h[i][j]=h[i-][j]*base1+h[i][j-]*base2-h[i-][j-]*base1*base2+mat[i][j] ;
    int ans=(<<)- ;
    for(int i=;i<=R;++i){
        for(int j=;j<=C;++j){
            if(i*j>=ans) continue ;
            if(check(i,j)) ans=i*j ;
        }
    }
    cout << ans << '\n' ;
}
int main(){
    freopen("matrix.in","r",stdin) ;
    freopen("HASH_matrix.out","w",stdout) ;
    int T;
    pow1[]=pow2[]= ;
    for(int i=;i<=;++i) pow1[i]=pow1[i-]*base1 ;
    for(int i=;i<=;++i) pow2[i]=pow2[i-]*base2 ;
    scanf("%d",&T) ;
    while(T--) solve() ;
    fprintf(stderr,"%d\n",clock()) ;
    return  ;
}

做法 2：将每一行hash為一個數，對得到的新數組直接跑KMP求最小循環節長度，列同理。将兩次求得的最小循環節長度相乘即為答案。這就是std做法。

代碼如下：

#include<iostream>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int R , C ;
char A[][] ;
unsigned long long base= , h_r[] , h_c[] , zj[] ;
int len , fail[] ;
char get_c(){
    char c;
    while((c=(char)getchar())!=EOF) if(!isspace(c)) break ;
    return c;
}
int get_it(){
    memset(fail,,sizeof(fail)) ;
    for(int i=;i<=len;++i){
        int t=fail[i-] ;
        while(t && zj[t+]!=zj[i]) t=fail[t] ;
        if(zj[t+]==zj[i]) fail[i]=t+ ;
    }
    return len-fail[len] ;
}
void solve(){
    scanf("%d%d",&R,&C);
    memset(h_r,,sizeof(h_r)) ; memset(h_c,,sizeof(h_c)) ;
    for(int i=;i<=R;++i) for(int j=;j<=C;++j) A[i][j]=get_c() , h_r[i]=h_r[i]*base+A[i][j] ;
    for(int j=;j<=C;++j) for(int i=;i<=R;++i) h_c[j]=h_c[j]*base+A[i][j] ;
    for(int i=;i<=R;++i) zj[i]=h_r[i] ;
    len=R ;
    int ans=get_it() ;
    for(int i=;i<=C;++i) zj[i]=h_c[i] ;
    len=C ;
    ans*=get_it() ;
    cout << ans << '\n' ;
}
int main(){
    freopen("matrix.in","r",stdin) ;
    freopen("matrix.out","w",stdout) ;
    int T; 
    scanf("%d",&T) ;
    for(int i=;i<=T;++i) solve() ;
    //fprintf(stderr,"std: %d\n",clock()) ;
    return  ;
}

做法3，水過去，可能是資料太水了

然而最後被卡掉了，（可以試一試随機找一個位置開始for或者倒着for，應該比較難卡）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int t,R,C,nxt[];
char s[][], tp[];

int Kmp(char *s,int len)
{
    memset(nxt,,sizeof(nxt));
    int i=,j=-;
    nxt[]=-;
    while(i<len)
    {
        if(j==-||s[i]==s[j])
        {
            ++i;++j;
            nxt[i]=j;
        }
        else j=nxt[j];
    }
    return len-nxt[len];
}
int main()
{
    freopen( "matrix.in", "r", stdin );
    freopen( "matrix.out", "w", stdout );
    for(scanf("%d",&t);t;--t)
    {
        scanf("%d%d",&R,&C);
        for(int i=;i<=R;++i)
            scanf("%s",s[i]);
        int ans1=;
        for(int i=;i<=R;++i)
            ans1=max(ans1,Kmp(s[i],C));
        int ans2=;
        for(int i=;i<=C;++i)
        {
            for(int j=;j<=R;++j) tp[j-]=s[j][i];
            ans2=max(ans2,Kmp(tp,R));
        }
        printf("%d\n",ans1*ans2);       
    }
    return ;
}

2 異或(xor.c/cpp/pas)

2.1 題目描述

給出 n 個數，Q次詢問，每次問[l,r]中最大連續異或和。

為了展現線上操作，對于每次詢問(x,y)：

l=min( ((x+lastans) mod n)+1 , ((y+lastans) mod n)+1 )

r=max( ((x+lastans) mod n)+1 , ((y+lastans) mod n)+1 )

2.2 輸入格式

第一行為兩個整數n，m，分别表示數的個數和詢問次數。

接下來一行 n個數，再接下來 m行，每行兩個數 x，y，表示給出詢問(x,y)，通過上述操作得到l和r，查詢[l,r]中最大連續異或和。

2.3 輸出格式

輸出m行，每行一個整數表示該次詢問的答案。

2.4 樣例輸入

3 3

1 4 3

0 1

4 3

2.5 樣例輸出

2.6 資料範圍與約定

對于30％的資料，n<=500，Q<=500。

對于100％的資料，n<=12000 , Q<=6000 , 給出的數均在signed longint 範圍内。

【解題報告】

将 n 個數分成sqrt(n)個塊。考慮用 w[i][j] 表示從第 i 個塊開頭元素到第 j 個元素這個區間中，最大連續異或和。建可持久化Trie樹并且預處理出w數組。預處理複雜度為 O(n * sqrt(n) * 位數)。

查詢[l,r]時，令 p 為 l 以右第一個塊開頭元素，那麼首先可以直接得到 p 到 r 區間的答案。再考慮上 [l,p-1] 區間中的元素，逐個在可持久化Trie上貪心即可。查詢總複雜度為O(Q * sqrt(n) * 位數)。

代碼如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 12005
#define maxbit 31

int N,M,A[maxn];
int tr[maxn];

struct PerTrie
{
    int next[][],num[];
    int id;
    void init() 
    {
        id=next[][]=next[][]=num[]=;
    }
    int f(int x,int i) 
    {
        return (x>>i)&;
    }
    void Insert(int& rt,int pre,int x,int pos) //插入
    {
        rt=++id;
        next[rt][]=next[pre][];
        next[rt][]=next[pre][];
        num[rt]=num[pre]+;
        if(pos==-) return;
        int d=f(x,pos);
        Insert(next[rt][d],next[pre][d],x,pos-);
    }
    int MaxXor(int l,int r,int x) //查詢最大異或值，因為A[i]儲存
    {                             //的是字首異或值，是以得到的結果就是某一段區間的異或值
        int ret=;
        for(int i=maxbit;i>=;--i)
        {
            int d=f(x,i);
            int a=next[l][d^],b=next[r][d^];
            if(num[b]-num[a]>) ret|=(<<i),l=a,r=b;
            else l=next[l][d],r=next[r][d];
        }
        return ret;
    }
}PT;
int block,num,bel[maxn],dp[][maxn]; //dp儲存第幾塊到第幾個數的區間最大異或值
void init()
{
    tr[]=;
    PT.init();
    for(int i=;i<=N;++i) PT.Insert(tr[i],tr[i-],A[i],maxbit); //插入
    block=(int)sqrt(N);
    num=N/block;
    if(N%block) num++; //加
    memset(dp,,sizeof(dp));
    bel[]=;
    for(int i=;i<=N;++i) bel[i]=(i-)/block+; //記錄下屬于哪個塊
    for(int i=;i<=num;++i)
    {
        int st=(i-)*block+;
        for(int j=st;j<=N;++j)
        {
            dp[i][j]=max(dp[i][j-],A[j]^A[st-]); //可能是[st,j]這段區間
            dp[i][j]=max(dp[i][j],PT.MaxXor(tr[st-],tr[j],A[j])); //再找最大的
        }
    }
}
int GetAns(int l,int r)
{
    l--;
    int s=bel[l],ret=;
    if(bel[r]>s) ret=dp[s+][r]; //查詢從後面一個塊開始的
    for(int i=l;i<=min(r,s*block);++i)
    {
        ret=max(ret,PT.MaxXor(tr[l-],tr[r],A[i]));
    }
    return ret;
}

int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    scanf("%d%d",&N,&M);
    A[]=;
    int x;
    for(int i=;i<=N;++i)
    {
        scanf("%d",&x);
        A[i]=A[i-]^x;
    }
    init();
    int last=,l,r;
    while(M--)
    {
        scanf("%d%d",&l,&r);
        l=(l+last)%N+;
        r=(r+last)%N+;
        last=GetAns(l,r);
        printf("%d\n",last);
    }
    return ;
}

3魔法串(magic.c/cpp/pas)

3.1 題目描述

給你一棵n+1個結點的有根樹，結點從0到n标号，其中0為根結點。

這是一棵魔法樹。這棵樹的每條邊有一個魔力值，同一個結點連向不同子結點的邊的魔力值不同。一個結點所代表的魔法串是從根一直走到這個結點，經過的魔力值依次排列形成的有序序列，另外，一個串是魔法串當且僅當它被一個結點所代表。

現在，為了使用強大的魔法，你需要對每個魔法串，找到最長的是它字尾的魔法串。為了友善輸出，你隻需要輸出代表這個魔法串的結點的标号即可。若沒有這個魔法串，請輸出0。

3.2 輸入格式

第一行一個整數n，代表除根以外的結點個數。

第二行 n個整數，第i個整數P_i代表标号為i的結點的父親标号。

第三行 n個整數，第i個整數C_i代表标号為i的結點連向父親的邊的魔力值。

3.3 輸出格式

輸出一行n個整數，第i個整數表示第i個結點代表的魔法串的答案。

3.4 樣例輸入

0 0 1 1 2 4 5

1 2 3 2 1 1 3

3.5 樣例輸出

0 0 02 1 5 3

3.6 資料範圍與約定

對于30％的資料，保證1<=n<=2000。

對于100％的資料，保證1<=n<=200000，0<=P_i

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200010
#define M 6000010

struct Edge {int p,v,w;}e[N];
struct Node {int l,r,v;}t[M];
int f[N],q[N],ql,qr,rt[N],n,p[N],c[N],hed[N],e_cnt,tot;

void addedge(int x,int y,int w) 
{
    e[++e_cnt].p=y;
    e[e_cnt].v=hed[x];
    e[e_cnt].w=w;
    hed[x]=e_cnt; 
}
void modify(int &x,int l,int r,int p,int v)
{
    int y=x;x=++tot;t[x]=t[y];
    if(l==r)
    {
        t[x].v=v;
        return;
    }
    int mid=(l+r)>>;
    if(p<=mid) return modify(t[x].l,l,mid,p,v);
    else return modify(t[x].r,mid+,r,p,v);
}
int query(int x,int l,int r,int p)
{
    if(l==r) return t[x].v;
    int mid=(l+r)>>;
    if(p<=mid) return query(t[x].l,l,mid,p);
    return query(t[x].r,mid+,r,p);
}
int main()
{
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    scanf("%d",&n);
    for(int i=;i<=n;++i) scanf("%d",&p[i]);
    for(int i=;i<=n;++i) scanf("%d",&c[i]),addedge(p[i],i,c[i]);
    for(q[qr ++]=;ql^qr;ql++)
    {
        int x=q[ql];
        rt[x]=rt[f[x]];
        for(int i=hed[x];i;i=e[i].v)
        {
            f[q[qr++]=e[i].p]=query(rt[f[x]],,n,e[i].w);
            modify(rt[x],,n,e[i].w,e[i].p);
        }
    }
    for(int i=;i<=n;i++) printf("%d ",f[i]);
    return ;
}

2017.7.26 機房測試（KMP/Hash，分塊+可持久化Trie樹貪心，主席樹+AC自動機）

1 無盡的矩陣(matrix.c/cpp/pas)

2 異或(xor.c/cpp/pas)

3魔法串(magic.c/cpp/pas)

繼續閱讀

20條程式設計經驗

【觀點】風雨20年：我所積累的20條程式設計經驗【觀點】風雨20年：我所積累的20條程式設計經驗

【轉載】風雨20年：我所積累的20條程式設計經驗

恢複Linux作業系統的GRUB引導程式

淺談---測試Native Windows Command與Native PowerShell Command哪個效率高

回文樹學習小結

Xcode中建立Target的步驟

利用Fiddler進行移動端弱網測試

各種二分查找

【原創】程式設計之美之二分搜尋

查找檔案中的字元串

CentOS7下TestLink環境的部署

軟體測試基礎_對應TestLink整理的測試計劃流程步驟

七牛雲-C#SDK-上傳-前期準備

[轉]iOS微信小視訊優化心得

測試面試題整理