HNUCM 2020年春季ACM集训队热身赛-第2场总结

拼搏现实的明天。 2023-07-19 05:51 30阅读 0赞

# HNUCM 2020年春季ACM集训队热身赛-第2场总结 #

### 文章目录 ###

*  HNUCM 2020年春季ACM集训队热身赛-第2场总结
 *   *  前言
     *  A：河畔军训
     *  B：不高兴的津津
     *  C：花生采摘
     *  D：FBI树
     *  E：火星人
     *  F：小B旅游
     *  G：括号匹配
     *  H：报数游戏
     *  I：小A的烦恼
     *  J：一步之遥

## 前言 ##

不会写题解，只爱写总结（hhh）  
感觉这套题整体还可以，没啥难题，但是又都有点意思，蒟蒻的我很多题都不是一发才过，还是太急了点，没怎么检查，立马就交了

## [A：河畔军训][A] ##

比赛延长了一个小时，还是没做出来。。。  
看题目就知道是**三向bfs**，但是奈何我的bfs太过于暴力，赛后看晖晖大佬的代码才A过

需要注意的是：  
**1、小h能走八个方向；小z和小y只能走四个方向  
2、小h一秒最多能走3步；小z和小y一秒最多只能走1步**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<set>
    #include<stack>
    #include<queue>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const ll mod=1e9+7;
    const double eps=1e-8;
    const int maxm=5000010;
    const int maxn=1e5+5;
    char mp[1010][1010];
    bool vis[3][1010][1010];
    int n,m;
    int dir[8][2]={
        0,1,0,-1,-1,0,1,0,-1,1,-1,-1,1,1,1,-1};
    struct node{
        
        int x,y;
        node(int xx,int yy){
        
            x=xx,y=yy;
        }
    };
    queue<node>q[3];
    int check(int x,int y,int id){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&vis[id][x][y]==0&&mp[x][y]!='#')
            return 1;
        return 0;
    }
    int bfs(int x){
        
        int num=q[x].size();
        while(num--){
        
            node now=q[x].front();
            q[x].pop();
            for(int i=0;i<8;i++){
        
                if(i>=4&&(x==0||x==1)){
        
                   break;
                }
                int fx=now.x+dir[i][0];
                int fy=now.y+dir[i][1];
                if(check(fx,fy,x)){
        
                    vis[x][fx][fy]=1;
                    q[x].push(node(fx,fy));
                    if(vis[0][fx][fy]&&vis[1][fx][fy]&&vis[2][fx][fy]){
        
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    int solve(){
        
        int dis=0;
        while(!q[0].empty()||!q[1].empty()||!q[2].empty()){
        
            ++dis;
            if(bfs(0)){
        
                return dis;
            }
            if(bfs(1)){
        
                return dis;
            }
            for(int i=1;i<=3;i++){
        
                if(bfs(2)){
        
                    return dis;
                }
            }
        }
        return -1;
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
            }
            while(!q[0].empty()){
        
                q[0].pop();
            }
            while(!q[1].empty()){
        
                q[1].pop();
            }
            while(!q[2].empty()){
        
                q[2].pop();
            }
            memset(vis,0,sizeof(vis));
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(mp[i][j]=='z'){
        
                        vis[0][i][j]=1;
                        q[0].push(node(i,j));
                    }
                    else if(mp[i][j]=='y'){
        
                        vis[1][i][j]=1;
                        q[1].push(node(i,j));
                    }
                    else if(mp[i][j]=='h'){
        
                        vis[2][i][j]=1;
                        q[2].push(node(i,j));
                    }
                }
            }
            //printf("%d %d\n",p1.x,p1.y);
            //printf("%d %d\n",p2.x,p2.y);
            //printf("%d %d\n",p3.x,p3.y);
            int ans=solve();
            if(ans==-1){
        
                printf("lack of junxun\n");
            }
            else{
        
                printf("%d\n",ans);
            }
        }
        return 0;
    }

## [B：不高兴的津津][B] ##

不光是津津不高兴了，我也不高兴了。这题输入居然是**字符串**，我也是醉了，搞的wa了三发

重点注意下这个即可，然后可能还有一个地方就是如果不高兴程度相同，则选择前面的

## [C：花生采摘][C] ##

虽然题目有点长，但是不难发现其实就是**贪心**的思想，我们用一结构体存花生的坐标和值；然后对值从大到小排序；然后再找。

需要注意的是：当选择对排序后的下一堆花生采摘时，**需要考虑：采摘完之后能否回到道路**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<set>
    #include<stack>
    #include<map>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const ll mod=1e9+7;
    const double eps=1e-8;
    const int maxn=1e5+5;
    int mp[30][30];
    struct node{
        
        int x,y;
        int num;
    };
    node a[410];
    int n,m,k;
    bool cmp(node xx,node yy){
        
        return xx.num>yy.num;
    }
    int main(){
        
        int t=0;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&mp[i][j]);
                if(mp[i][j]!=0){
        
                    a[t].x=i,a[t].y=j;
                    a[t].num=mp[i][j];
                    t++;
                }
            }
        }
        sort(a,a+t,cmp);
        int prex=0,prey=a[0].y;
        int ans=0,cnt=0;
        for(int i=0;i<t;i++){
        
            int dis=abs(a[i].x-prex)+abs(a[i].y-prey);
            if((dis+cnt+a[i].x+1)<=k){
        
                cnt+=dis+1;
                ans+=a[i].num;
                prex=a[i].x,prey=a[i].y;
            }
            else{
        
                break;
            }
        }
        printf("%d\n",ans);

## [D：FBI树][D_FBI] ##

很明显的建树，遍历树，但是如果按照传统的建树之后再遍历似乎显得有点麻烦，而且没有必要；本来建树和遍历的过程就是递归的过程，那我们为何不用**递归**的思想直接求呢

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const ll mod=1e9+7;
    const double eps=1e-8;
    const int maxn=1e5+5;
    char s[maxn];
    void solve(int l,int r){
        
        int mid=(l+r)/2;
        if(l!=r){
        
            solve(l,mid);
            solve(mid+1,r);
        }
        int flag1=0,flag2=0;
        for(int i=l;i<=r;i++){
        
            if(s[i]=='0')
                flag1=1;
            else
                flag2=1;
        }
        if(flag1&&flag2){
        
            printf("F");
        }
        else if(flag1){
        
            printf("B");
        }
        else{
        
            printf("I");
        }
    }
    int main(){
        
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        solve(1,strlen(s+1));
        printf("\n");
        return 0;
    }

## [E：火星人][E] ##

**全排列问题**，但是需要注意的是：当得到结果后，需要结束全排列，不然肯定会超时。  
有两种方法：  
1、[C++全排列函数][C 1]，有时候比赛中，为了节省时间，这何尝不是一种好方法  
2、递归，也很简单

C++全排列函数版本

## [F：小B旅游][F_B] ##

这题可能题意会有点小难理解，它是求将多种方案能经过的城市去重求和

可能还是比较容易想到用**BFS**，但是发现城市数很大，不能用链接矩阵存，那我们就用邻接链表吧，链表可能比较麻烦，于是我们就用数组模拟链表：**链式向前星存图**

[**链式向前星（数组模拟邻接表）**][Link 1]

## [G：括号匹配][G] ##

还是很容易想到**栈应用**的，我们可以开三个栈，分别存\{、\[、(、

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<set>
    #include<stack>
    #include<map>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const ll mod=1e9+7;
    const double eps=1e-8;
    const int maxn=1e5+5;
    string s;
    int main(){
        
        cin>>s;
        stack<int>st1,st2,st3;
        int len=s.length();
        for(int i=0;i<len;i++){
        
            if(s[i]=='{'){
        
                st1.push(i);
            }
            else if(s[i]=='['){
        
                st2.push(i);
            }
            else if(s[i]=='(')
                st3.push(i);
            else if(s[i]=='}'){
        
                printf("%d %d\n",st1.top(),i);
                st1.pop();
            }
            else if(s[i]==']'){
        
                printf("%d %d\n",st2.top(),i);
                st2.pop();
            }
            else if(s[i]==')'){
        
                printf("%d %d\n",st3.top(),i);
                st3.pop();
            }
        }
        return 0;
    }

## [H：报数游戏][H] ##

约瑟夫环，数据比较弱，我们用**模拟**完全可以过，但是也可以找下**小规律**

模拟法：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const ll mod=1e9+7;
    const double eps=1e-8;
    const int maxn=1e5+5;
    int t,n,m;
    vector<int>ve;
    int flag[maxn];
    int main(){
        
        vector<int>::iterator it;
        scanf("%d",&t);
        while(t--){
        
            ve.clear();
            memset(flag,0,sizeof(flag));
            scanf("%d%d",&n,&m);
            int cnt=0;
            int ans=0;
            while(flag[1]==0){
        
                for(int i=1;i<=n;i++){
        
                    if(flag[i]==0){
        
                        cnt++;
                    }
                    if(flag[i]==0&&cnt==m){
        
                        cnt=0;
                        flag[i]=1;
                        //cout<<i<<" ";
                        ans++;
                    }
                    if(flag[1]){
        
                        break;
                    }
                }
                if(flag[1])
                    break;
            }
            //cout<<endl;
            printf("%d\n",ans-1);
        }
        return 0;
    }

找规律，直接得答案（一个学弟想出来的）：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int t,n,m;
        cin>>t;
        while(t--)
        {
        
            cin>>n>>m;
            int num=1,ans=0,len=n;
            while(num!=m)
            {
        
                int w=num;
                ans+=(len+num-1)/m;
                num=(len+num-1)%m+1;
                len-=(len+w-1)/m;
            }
            cout<<ans<<endl;
        }
    }

## [I：小A的烦恼][I_A] ##

和F题很像，也是数比较大，我们只能用**链式向前星存图**，然后这里是求每个城市与其相邻的城市，按照输入顺序输出；我们只要在创建图的时候，同时开个数组存下每个城市相邻的城市即可，具体见代码：

## [J：一步之遥][J] ##

这题就有点离谱，我用了个**set**，然后这题就特别水了

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<map>
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const double eps=1e-8;
    const int maxn=1e3+10;
    const ll mod=1e9+7;
    int n,m,p;
    set<int>st;
    int main() {
        
        while(~scanf("%d%d%d",&n,&m,&p)) {
        
            st.clear();
            int u,v;
            for(int i=1; i<=m; i++) {
        
                scanf("%d%d",&u,&v);
                if(u==p){
        
                    st.insert(v);
                }
                else if(v==p){
        
                    st.insert(u);
                }
            }
            printf("%d\n",st.size());
        }
        return 0;
    }

[A]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=0
[B]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=1
[C]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=2
[D_FBI]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=3
[E]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=4
[C 1]: https://blog.csdn.net/boliu147258/article/details/89376953
[F_B]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=5
[Link 1]: https://blog.csdn.net/Ven21959/article/details/99057467
[G]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=6
[H]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=7
[I_A]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=8
[J]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1088&pid=9