开开心心写

2020-05-03 23:23 已编辑西北工业大学 Java

关注

哈理工高年级院赛题解（非官方）

首先感谢NULL巨巨给大家提供了一个学习交流的机会

然后就得吐槽自己的中文读题水平了，总之，看到的基本都是能写的题，然而一直写不对就是自己弱和别人厉害的区别和差距了吧

先贴一发官方题解链接：

http://pan.baidu.com/s/1slMseWt#list/path=%2F

然后还是老规矩，对每个题的题意，解法和代码进行自己的分析

A题：凌波微步

一开始看题就被题意坑了：

缺点是只能走向高处

这里从左到右，共有n个木桩，这些木桩有高有低

但是，没有说！一定要从左走到右啊！加上数据大小是1e6

相信会有很多人直接一发nlogn的LIS就丢上去了，然后返回了一个WA！

很简单：因为题目中没说行走的方向，那么我们只需要考虑：给的数值中有多少个不同的就好！

从最小的走向第二小的，然后走向第三小的……最后走向最大的

所以sort+unique一发就好

B题：珠宝店

这个题是个水题，而且读题没有坑，从左到右扫一遍，挨个对字符所对应的数字加起来就好

C题：神奇的数字

题目太长，废话太多，其实总结起来就一句话：请从小到大输出8位长度的数字回文串

所以这个题不需要输入！！！我看到那个无字一脸懵逼，以为是不告诉我输入，要我判断输入的数字串是不是合法的8位回文

读题细节啊，可以直接四重循环搞，也可以一重循环

int main(){
    for(int i=1;i<=9;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                for(int l=0;l<=9;l++)
                    printf("%d%d%d%d%d%d%d%d\n",i,j,k,l,l,k,j,i);
    return 0;
}


int main(){
    for(int i=1000;i<=9999;i++){
        printf("%d",i);
        printf("%d",i%10);
        printf("%d",(i/10)%10);
        printf("%d",(i/100)%10);
        printf("%d\n",i/1000);
    }
    return 0;
}

就是当成蓝桥杯做，不要想太多，必定1A！

D题：经商

这个题是个综合性的好题（对大神来说应该很简单）

首先根据求最优值，应该能看出来是个DP，把精力值看作花费，利益值看作价值，那么就很明显：取或者不取，肯定是个DP！

结合题意，有多个物品，取或者不取，那不就是01背包吗？！

问题是，不是每个物品都能够取得到的（因为没有边到达的话，那么某个物品就取不到）

现在需要处理的问题是：如何判断，从节点1（开始节点）能够到达所有的能够取到的物品：并查集！（用图论的其他判断方法必然超时，而且并查集最经济实惠）

所以，在预处理输入之后，并查集+01背包，两个裸模板过题

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

const int maxn=100050;
int a[maxn],b[maxn],dp[550];
int T,n,m,c;
int fa[maxn];

int getfa(int x){
    if (fa[x]==-1) return x;
    return fa[x]=getfa(fa[x]);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&c);
        memset(dp,0,sizeof(dp));
        memset(fa,-1,sizeof(fa));
        for(int i=2;i<=n;i++)
            scanf("%d%d",&a[i],&b[i]);
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            int fau=getfa(u);
            int fav=getfa(v);
            if (fau!=fav) fa[fau]=fav;
        }
        int root=getfa(1);
        for(int i=2;i<=n;i++)
            if (root==getfa(i))
                for(int j=c;j>=a[i];j--)
                    dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        printf("%d\n",dp[c]);
    }
    return 0;
}

E题：音乐转换（没有题目链接，弱也不会DP，待补题）

F题：苦逼的单身狗

这个题，要求的是所有数值对【L，R】，其中区间【L，R】中包含了LOVE四个大写字母（不需要按顺序出现）

枚举L，然后从左到右不断扫描，直到找到了LOVE四个字母每个至少各一个，然后这就是R的起点，R的终点肯定是字符串的末尾

剪枝：

首先可以预处理，第一个有用的字母在哪儿，不需要从前往后扫，即：找到第一个可能的L

然后找到第一个有答案的地方，即LOVE四个字母每个至少各一个的R的最小值，即：找到第一个可能的R

那么在暴力枚举指针的时候，可以少很多次枚举

（当然，这个题不需要想这么多，直接搞就好）

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

int T,ans;
char s[100050];
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        int len=strlen(s+1);
        int l,o,v,e,R,L;
        ans=0;
        for(L=1;L<=len;L++){
            l=o=v=e=0;
            for(R=L;R<=len;R++){
                if (s[R]=='L') l++;
                if (s[R]=='O') o++;
                if (s[R]=='V') v++;
                if (s[R]=='E') e++;
                if (l&&o&&v&&e) break;
            }
            if (R<=len&&l&&o&&v&&e)
                ans=ans+len-R+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

G题：逃脱

这个题是赛场争议最大的一道题，得看你对题目怎么理解

已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）

首先，火是8个方向跑，人是4个方向跑，这个是固定的，没有问题

后面那个解释得这么理解才能过：

如果现在这个点是bfs的中间过程点（在图中的字符为点“.”），那么人需要比火先到这个点

如果现在这个点是bfs的终点，也就是出口点（在图中的字符为字母“E”），那么人可以和火同时到这个点

这样理解的大神，就能1A，我这种先跑火再跑人，wa了全场

这个题有个特殊性质：因为火是8个方向奔跑，而且墙对于火来说不是障碍，所以不需要去计算火的bfs，火到某个坐标点的时间可以直接用坐标计算得到

假设火的起点坐标为（fx，fy），需要判断的点的坐标为（x，y），那么花费的时间为max{abs（fx-x），abs（fy-y）}

意思是：能走对角线尽可能走对角线，走不动了再走直线，是最快的

这种方法的代码短，思路也更清晰：（因为只需要走人，一个bfs就搞定了）

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

const int maxn=50;
int vis[maxn][maxn];
char mp[maxn][maxn];
int T,n,m;
int sx,sy,fx,fy,ex,ey;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};

bool inmap(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}

int getdis(int x,int y){
    return max(abs(fx-x),abs(fy-y));
}

void bfs(){
    vis[sx][sy]=0;
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(sx);q.push(sy);
    int nx,ny;
    while(!q.empty()){
        sx=q.front();q.pop();
        sy=q.front();q.pop();
        for(int i=1;i<=4;i++){
            nx=sx+dx[i];
            ny=sy+dy[i];
            if (inmap(nx,ny)&&vis[nx][ny]==-1&&mp[nx][ny]!='#'&&mp[nx][ny]!='*'){
                if (nx==ex&&ny==ey){
                    if (vis[sx][sy]+1<=getdis(nx,ny)){
                        vis[nx][ny]=vis[sx][sy]+1;
                        return;
                    }
                }
                else if (vis[sx][sy]+1<getdis(nx,ny)){
                    q.push(nx);q.push(ny);
                    vis[nx][ny]=vis[sx][sy]+1;
                }
            }
        }
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if (mp[i][j]=='S') sx=i,sy=j;
                else if (mp[i][j]=='E') ex=i,ey=j;
                else if (mp[i][j]=='*') fx=i,fy=j;
        memset(vis,-1,sizeof(vis));
        bfs();
        if (vis[ex][ey]==-1) puts("T_T");
        else printf("%d\n",vis[ex][ey]);
    }
    return 0;
}

正常的方法就是：先把火的bfs跑出来，遍历全图；然后人在火中的地图上走，再次进行bfs，看能否找到一条有出口的路，代码如下：

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

const int maxn=50;
int vis1[maxn][maxn],vis2[maxn][maxn];
int dx[]={0,1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,0,1,-1,1,-1,1,-1};
char mp[maxn][maxn];
int T,n,m;
int sx1,sx2,sy1,sy2,ex,ey;

queue<int> q;

bool inmap(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}

void bfsfire(){
    vis1[sx2][sy2]=0;
    while(!q.empty()) q.pop();
    q.push(sx2);q.push(sy2);
    int nx,ny;
    while(!q.empty()){
        sx2=q.front();q.pop();
        sy2=q.front();q.pop();
        for(int i=1;i<=8;i++){
            nx=sx2+dx[i];
            ny=sy2+dy[i];
            if (inmap(nx,ny)&&vis1[nx][ny]==-1){
                q.push(nx);q.push(ny);
                vis1[nx][ny]=vis1[sx2][sy2]+1;
            }
        }
    }
}

void bfspeople(){
    vis2[sx1][sy1]=0;
    while(!q.empty()) q.pop();
    q.push(sx1);q.push(sy1);
    int nx,ny;
    while(!q.empty()){
        sx1=q.front();q.pop();
        sy1=q.front();q.pop();
        for(int i=1;i<=4;i++){
            nx=sx1+dx[i];
            ny=sy1+dy[i];
            if (inmap(nx,ny)&&vis2[nx][ny]==-1&&mp[nx][ny]!='*'&&mp[nx][ny]!='#'){
                if (nx==ex&&ny==ey){
                    if (vis2[sx1][sy1]+1<=vis1[nx][ny]){
                        vis2[nx][ny]=vis2[sx1][sy1]+1;
                        return;
                    }
                }
                else if (vis2[sx1][sy1]+1<vis1[nx][ny]){
                    q.push(nx);q.push(ny);
                    vis2[nx][ny]=vis2[sx1][sy1]+1;
                }
            }
        }
    }
}

void debugfire(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            printf("%d%c",vis1[i][j],j==m?'\n':' ');
    puts("");
}

void debugpeople(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            printf("%d%c",vis2[i][j],j==m?'\n':' ');
    puts("");
}

int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if (mp[i][j]=='E') ex=i,ey=j;
                else if (mp[i][j]=='S') sx1=i,sy1=j;
                else if (mp[i][j]=='*') sx2=i,sy2=j;
        memset(vis1,-1,sizeof(vis1));
        memset(vis2,-1,sizeof(vis2));
        bfsfire();
        bfspeople();
        //debugfire();
        //debugpeople();
        if (vis2[ex][ey]==-1) puts("T_T");
        else printf("%d\n",vis2[ex][ey]);
    }
    return 0;
}

H题：布置会场

这个题看到大数据n，哈哈，先猜一发

从小数据算出来：FIB数列，矩阵快速幂搞一发就行

说说原理：为什么这个题的答案是FIB数列，因为：

FIB（n）有两种构造方法：

方法1：在FIB（n-1）的所有构造方法后面加个字符A

方法2：在FIB（n-2）的所有构造方法后面加字符BB

得到答案

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

#define LL long long
#define mod 1000000007

typedef struct Matrix{
    LL mat[2][2];
}matrix;
matrix A,B;

Matrix mul(matrix a,matrix b){
    matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++){
                c.mat[i][j]+=a.mat[i][k]*b.mat[k][j];
                c.mat[i][j]%=mod;
            }
    return c;
}

Matrix qp(matrix a,LL k){
    matrix b;
    memset(b.mat,0,sizeof(b.mat));
    b.mat[0][0]=b.mat[1][1]=1;
    while(k){
        if (k%2) b=mul(a,b);
        k=k/2;
        a=mul(a,a);
    }
    return b;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        LL n;
        cin>>n;
        n++;
        A.mat[0][0]=A.mat[0][1]=A.mat[1][0]=1;
        A.mat[1][1]=0;
        B=qp(A,n);
        cout<<(B.mat[0][1]+mod)%mod<<endl;
    }
    return 0;
}

I题：旅行

一个很好的图论题，不难，但是很考虑思维，感谢各位大神对我的教育

题目抽象出来就是：找一条从a到b到c三个点的最长路

司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径

首先：我们需要考虑如何找任意两点之间的最短路径，需要用哪个最短路径算法？

请注意这是一个稀疏图.

注意到题目给的条件：稀疏图：说明边很少，那么意味着，我们要用以边来更新的单源最短路径算法：选择SPFA，对于每个点都单独跑一次就好了

然后，我们找从a到b到c的最长路

只需要枚举中间点，找到中间点到其他点距离最长和第二长的这两条边，取出来搞一发就好（自己写的是sort，但是其实不需要，维护最大值和次大值就可以了）

代码如下：

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

const int maxm=150050;
const int maxn=1500;
const int INF=0x3f3f3f3f;

struct node{
    int from,to,nxt,w;
}edge[maxm];
int n,m,tot;
int tmp[maxn],head[maxn],vis[maxn],dis[maxn][maxn];

void init(){
    tot=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w){
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}

void SPFA(int s){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) dis[s][i]=INF;
    dis[s][s]=0;
    vis[s]=1;
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(s);
    int u,v,w;
    while(!q.empty()){
        u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            v=edge[i].to;w=edge[i].w;
            if (dis[s][v]>dis[s][u]+w){
                dis[s][v]=dis[s][u]+w;
                if (vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    int T,u,v,w;
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d",&n,&m);
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        for(int i=1;i<=n;i++) SPFA(i);
        int ans=-1;
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=n;j++){
                if (i==j) continue;
                if (dis[i][j]==INF) continue;
                tmp[cnt++]=dis[i][j];
            }
            sort(tmp,tmp+cnt);
            if (cnt<=1) continue;
            ans=max(ans,tmp[cnt-1]+tmp[cnt-2]);
        }
        printf("%d\n",ans);
    }
    return 0;
}