hihocoder [Offer收割]编程练习赛19

题目1 : 大礼堂地毯

枚举

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
char pattern[51][51];
char map[101][801];
int n, m,k;
int work(int h,int w){
    for(int i = 0;i < h; i++){
        for(int j = 0;j < w;j ++){
            if(map[i][j] != map[i%n][j%m])
                return 0;
        }
    }

    for(int i = 0;i < n; i++){
        for(int j = 0;j < m;j ++){
            int flag = 1;
            for(int l = 0; l < min(n,h) && flag; l++){
                for(int p = 0;p < min(m,w) && flag; p++){
                    if(map[l][p] != pattern[(l+i)%n][(p+j)%m])
                        flag = 0;
                }
            }
            if(flag) return 1;
        }
    }
    return 0;

}
int main(){
    cin>>n>>m>>k;
    for(int i = 0;i < n; i++)
        scanf("%s",pattern[i]);
    for(int j = 0;j < k; j++){
        int h,w;
        cin>>h>>w;
        for(int i = 0;i < h; i++){
            scanf("%s",map[i]);
        }
        if(work(h,w) == 1)printf("YES\n");
        else printf("NO\n");
    }
}
           

题目2 : 数组重排3

从初始序列做bfs，然后给每个能到的序列标记步数。

如果目标序列被标记，输出

否则不可达

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
int n;
int num[10];
char input[10];
map<int,int> state;


int main(){
    int t,x;
    cin>>t;

    while(t--){
            getchar();
        scanf("%s",input);
        n = strlen(input);
        int need = 0;
        for(int i = 0;i < n; i++)
            need = need * 10 + input[i] - '0';

        state.clear();

        queue<int> Q;
        int u = 0;
        for(int i = 1;i <= n; i++){
            u =u * 10 + i;
        }
        int use[20],buf[20];
        Q.push(u);
        state[u] = 0;
        while(Q.size() > 0){
            u = Q.front();
            Q.pop();
            int p = u;
            for(int i = n;i > 0; i--){
                use[i] = u % 10;
                u /= 10;
            }

            for(int i = 1;i < n; i++){
                for(int j = 1;j < n; j++){
                    if(i == j) continue;
                    for(int k = 1;k <= n; k++){
                        if(k == i)
                            buf[j] = use[k];
                        else if(k == i + 1)
                            buf[j+1] = use[k];
                        else if(k >= min(i,j) && k <= max(i+1,j+1)){
                            if(j > i)
                                buf[k-2] = use[k];
                            else
                                buf[k+2] = use[k];
                        }
                        else buf[k] = use[k];
                    }
                    int v = 0;
                    for(int i = 1;i <= n; i++)
                        v = v * 10 + buf[i];
                    if(state.find(v) != state.end()) continue;
                    Q.push(v);
                    state[v] = state[p] + 1;
                }
            }

        }
        if(state.find(need) != state.end()) cout<<state[need]<<endl;
        else cout<<-1<<endl;


    }
    return 0;
}
           

题目4 : 相交的铁路线

最近公共祖先。

lca求法写的不好，复杂度是nlogn*logn的，实际可以少一个log

对于一条铁路上两个点的最近公共祖先F1,F2

F1,F2中深度较深的点，要么是交点，要么两条铁路没有交点。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
using namespace std;
int n;
#define maxn 100007
int rmq[20][100007];
vector<int>head[maxn];
int father[maxn],depth[maxn];
void dfs(int u,int f,int dep){
    if(father[u] != -1) return;
    father[u] = f;
    depth[u] = dep;
    for(int i = 0;i < head[u].size();i++){
        dfs(head[u][i],u,dep+1);
    }
}

void initRMQ(int n){
    for(int i = 1;i <= n; i++)
        rmq[0][i] = father[i];
    for(int i = 1;i <= 18;i ++){
        for(int j = 1;j <= n; j++){
            int u =rmq[i-1][j];
            rmq[i][j] = rmq[i-1][u];
        }
    }
//    for(int i = 0;i < 3; i++){
//        for(int j = 1;j <= n; j++)
//            cout<<rmq[i][j]<<" ";
//        cout<<endl;
//    }
}

int getDepFather(int id,int dep){
    dep = depth[id] - dep;
    if(dep == 0) return id;
    for(int i = 0; dep > 0; i++){
        int k = dep % 2;
        dep /= 2;
        if(k)
            id=rmq[i][id];
    }
    return id;
}
int getFather(int x1,int x2){
    int low = 1, high = min(depth[x1],depth[x2]);
    while(low <= high){
        int mid = (low + high) / 2;
//        cout<<x1<<" "<<mid<<" "<<getDepFather(x1,mid)<<endl;
//        cout<<x2<<" "<<mid<<" "<<getDepFather(x2,mid)<<endl;
        if(getDepFather(x1,mid) == getDepFather(x2,mid))
            low =  mid + 1;
        else
            high = mid - 1;
    }
    return getDepFather(x1,high);
}

int main(){
    int t,n,m,u,v,x1,x2,y1,y2;
    cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i = 0;i <= n; i++)
            head[i].clear();
        for(int i = 1;i < n; i++){
            scanf("%d%d",&u,&v);
            head[u].push_back(v);
            head[v].push_back(u);
        }
        memset(father,-1,sizeof(father));
        dfs(1,1,1);
        initRMQ(n);
        for(int i = 0;i < m; i++){
            scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
            int f1 = getFather(x1,x2);
            int f2 = getFather(y1,y2);

            if(depth[f1] < depth[f2])
                f1 = f2;
            f1 = depth[f1];
            int t1 = getDepFather(x1,f1);
            int t2 = getDepFather(x2,f1);
            int z1 = getDepFather(y1,f1);
            int z2 = getDepFather(y2,f1);
            if(t1 == z1 || t1 == z2 || t2 == z1 || t2 == z2)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }

    }
    return 0;
}