【题目记录】——2020ICPC·小米网络选拔赛第一场(重现赛)

﹏ヽ暗。殇╰゛Y 2022-09-11 03:18 165阅读 0赞

### 文章目录 ###

*  A Intelligent Warehouse DP+数论
 *  C Smart Browser 思维
 *  I Walking Machine 广搜
 *  J Matrix Subtraction 二维差分+思维

题目地址 [2020ICPC·小米 网络选拔赛第一场(重现赛)][2020ICPC_]  
这次我们只是做出了两个题目C题签到题和一个I题简单题  
题解参考 [2020ICPC·小米 网络选拔赛第一场 全部题解][2020ICPC_ _]

# A Intelligent Warehouse DP+数论 #

题目地址[A Intelligent Warehouse][]  
题意：给一个序列，找到一个符合条件的集合，条件如下  
集合中任意两个数，其中一个是另一个的整数倍。  
思路：dp\[i\]表示序列中i的约数的最大个数,进行状态转移

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e7+7;
    bool isPrime[N*2];
    int Prime[N*2],cntt;
    int cnt[N];
    int dp[N];
    void ola(int n)
    { 
        memset(isPrime,1,sizeof(isPrime));
        isPrime[1] = isPrime[0] = 0;
        for(int i = 2;i <= n;i++)
        { 
            if(isPrime[i])
            { 
                Prime[++cntt] = i;
            }
            for(int j = 1;j <= cntt&&i*Prime[j]<=n;j++)
            { 
                isPrime[i*Prime[j]]=0;
                if(!(i%Prime[j]))
                { 
                    break;
                }
            }
        }
    }
    void solve()
    { 
    	int n,mx = 0;
    	scanf("%d",&n);
    	for(int i = 1;i <= n;i ++)
        { 
            int t;
            scanf("%d",&t);
            cnt[t]++;
            mx = max(t,mx);
        }
        ola(mx);
        int ans=0;
        for(int i = 1;i <= mx;i++)
        { 
            dp[i]+=cnt[i];
            for(int j = 1;j <= cntt&&Prime[j]*i<=mx;j++)
            { 
                dp[i*Prime[j]]=max(dp[i*Prime[j]],dp[i]);
            }
            ans = max(ans,dp[i]);
        }
        cout << ans << endl;
    }
    int main()
    { 
    	int t = 1;
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# C Smart Browser 思维 #

题目地址[C Smart Browser][]  
题意：就是连续的w中含有多少个"/"符号，只有w字符组成的“/\\”才计算  
思路：数数有几个连续的w就行了，连续w的个数乘2减一然后再求和即可，签到题。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    
    void solve()
    { 
        int res=0,ans=0;
        char ch;
        while((ch=getchar())!='\n')
        { 
            if(ch=='w')
                res++;
            else if(res>0)
            { 
                 ans+=res*2-1;
                 res=0;
            }
        }
        if(res)
            ans+=res*2-1;
        cout <<ans;
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t = 1;
    // int t;
    // scanf("%d",&t);
        while(t--)
        { 
            solve();
        }
        return 0;
    }

# I Walking Machine 广搜 #

题目地址[ I Walking Machine][I Walking Machine]  
题意：一个字符矩阵，由wasd组成，w向上走，a向左走，s向下走，d向右走，机器人只能根据矩阵的字符移动，问有多少个位置是可以离开这个矩阵的。  
思路：先找矩阵边界能够离开矩阵的点，每找到一个就开始BFS所有能到达此点的位置，同时技术，遍历完整个矩阵的四个边界即可。  
AC代码：

#include <bits/stdc++.h>
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <algorithm>
    //#include <vector>
    //#include <map>
    //#include <stack>
    //#include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1002;
    char mm[N][N];
    //int vis[N][N];
    queue<pair<int,int>> p;
    int n, m;
    int BFS(int x, int y)
    { 
        int ans = 1;
        p.push(make_pair(x,y));
        while(!p.empty())
        { 
            pair<int,int> pi = p.front();
            p.pop();
            if(pi.first-1>0&&mm[pi.first-1][pi.second]=='S')
            { 
                ans+=1;
                p.push(make_pair(pi.first-1,pi.second));
            }
            if(pi.first+1<=n&&mm[pi.first+1][pi.second]=='W')
            { 
                ans+=1;
                p.push(make_pair(pi.first+1,pi.second));
            }
            if(pi.second+1<=m&&mm[pi.first][pi.second+1]=='A')
            { 
                ans +=1;
                p.push(make_pair(pi.first,pi.second+1));
            }
            if(pi.second-1>0&&mm[pi.first][pi.second-1]=='D')
            { 
                ans+=1;
                p.push(make_pair(pi.first,pi.second-1));
            }
        }
        return ans;
    }
    
    void solve()
    { 
    	scanf("%d%d",&n,&m);
    	for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                char c;
                scanf("%c",&c);
                while(c=='\n')
                scanf("%c",&c);
                mm[i][j] = c;
            }
        }
        int ans = 0;
        for(int i = 1;i <= m;i++)
        { 
            if(mm[1][i]=='W')
            { 
                ans += BFS(1,i);
    // vis[1][i]=1;
            }
            if(mm[n][i]=='S')
            { 
                ans += BFS(n,i);
            }
        }
        for(int i = 1;i <= n;i++)
        { 
            if(mm[i][1]=='A')
            { 
                ans += BFS(i,1);
    // vis[1][i]=1;
            }
            if(mm[i][m]=='D')
            { 
                ans+=BFS(i,m);
    // vis[1][i]=1;
            }
        }
        printf("%d\n",ans);
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int t = 1;
    // int t;
    // scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# J Matrix Subtraction 二维差分+思维 #

题目地址[J Matrix Subtraction][]  
题意：给一个二维矩阵大小为n*m，给一个子矩阵大小a*b,每次操作一个子矩阵，给子矩阵上每一个值减一，问能不能使得最后的大矩阵的值全部为0。  
思路：我们直接 n 2 n^2 n2暴力枚举a\*b的子矩阵，每一块都减去**当前值**使之变为 0，利用二维差分可以快速实现这个操作。如果中途出现了负数或最后不全为 0，则输出 QAQ。

#include <bits/stdc++.h>
    //#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <algorithm>
    //#include <vector>
    //#include <map>
    //#include <stack>
    //#include <queue>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1004;
    int mm[N][N],k[N][N];
    void add(int i,int j,int a,int b,int z)
    { 
        mm[i][j]+=z;
        mm[i+a][j]-=z;
        mm[i][j+b]-=z;
        mm[i+a][j+b]+=z;
    }
    bool check(int n,int m)
    { 
        for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                if(mm[i][j]!=0)
                { 
                    return false;
                }
            }
        }
        return true;
    }
    void solve()
    { 
    	int n,m,a,b;
    	scanf("%d%d%d%d",&n,&m,&a,&b);
    	for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                scanf("%d",&k[i][j]);
                mm[i][j]=k[i][j]+k[i-1][j-1]-k[i][j-1]-k[i-1][j];
            }
        }
        int f = 0;
        for(int i = 1;i <= n;i++)
        { 
            for(int j = 1;j <= m;j++)
            { 
                mm[i][j]+=mm[i-1][j]+mm[i][j-1]-mm[i-1][j-1];//求前缀和
                if(mm[i][j] < 0)    //如果前面处理过后的二维数组有一个负数，就说明不能达到要求，如果继续计算的话，会将这个负数加到0，然而对子矩阵的操作只能是减一，而不能加数字，因而出现负数必然是不对的
                { 
                    f = 1;
                    break;
                }
                if(i+a-1>n||j+b-1>m)
                { 
                    break;
                }
                add(i,j,a,b,-mm[i][j]);
            }
            if(f)
            { 
                break;
            }
        }
        if(f)
        { 
            puts("QAQ");
        }
        else
        { 
            if(check(n,m))
            { 
                puts("^_^");
            }
            else
            { 
                puts("QAQ");
            }
        }
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[2020ICPC_]: https://ac.nowcoder.com/acm/contest/7501
[2020ICPC_ _]: https://blog.csdn.net/weixin_45697774/article/details/109318881
[A Intelligent Warehouse]: https://ac.nowcoder.com/acm/contest/7501/A
[C Smart Browser]: https://ac.nowcoder.com/acm/contest/7501/C
[I Walking Machine]: https://ac.nowcoder.com/acm/contest/7501/I
[J Matrix Subtraction]: https://ac.nowcoder.com/acm/contest/7501/J