（完结）牛客编程巅峰赛S1第12场 - 黄金&钻石总结

以你之姓@ 2022-11-28 00:54 153阅读 0赞

# 牛客编程巅峰赛S1第12场 - 黄金&钻石总结 #

最后还是没能上王者，害，还是太菜了

## A：牛牛质数 ##

[**题目链接**][Link 1]

#### 题意 ####

牛牛有一个质数p，和两个区间\[a,b\]，\[c,d\]，分别在两个区间中取一个数x，y。求有多少对(x,y)使得x∗y是p的倍数。给定你两个区间，求从区间中取出数相乘是p的倍数的个数。

#### 题解 ####

分别求出区间\[a,b\]，\[c,d\]有多少个p的倍数x，y，然后最终结果为：x*len(cd）+y*len(ab-1)由于重复了所以减一。

#### AC代码（cpp） ####

class Solution {
        
    public:
        /**
         * 返回两个区间内各取一个值相乘是p的倍数的个数
         * @param a int整型 第一个区间的左边界
         * @param b int整型 第一个区间的右边界
         * @param c int整型 第二个区间的左边界
         * @param d int整型 第二个区间的右边界
         * @param p int整型 质数
         * @return long长整型
         */
        long long numbers(int a, int b, int c, int d, int p) {
        
            // write code here
            long long ans=0;
            long long cnt=b/p-(a-1)/p;
            long long cnt2=d/p-(c-1)/p;
            ans=cnt*(d-c+1)+cnt2*(b-a+1-cnt);
            return ans;
        }
    };

## B：锻炼身体 ##

[**题目链接**][Link 2]

#### 题意 ####

疫情期间，牛牛整天摊在床上沉溺于手机，身体日渐虚胖，因此牛妹拿走家中的 wifi 路由器，迫使牛牛下床来拿到路由器。在这过程中，牛牛想要在尽可能短的时间内拿到路由器，而牛妹却希望牛牛多走一会儿。现假设牛妹家中有 nn 个房间，任意两个房间有且仅有一条路径，起初路由器在编号为 xx 的房间内，牛牛在编号为 1 的房间内，牛牛与牛妹速度相同，当俩人同时开始移动，牛牛要经过几个房间才能拿到路由器。  
只要牛牛和路由器处在同一房间，便看作牛牛已拿到路由器。

#### 题解 ####

这题比赛的时候并没有想出来，等赛后看题解才明白。首先需要注意的是：牛牛和牛妹会同时移动，而且牛妹想要牛牛多走一会儿，而牛牛想要尽快拿到路由器，要想牛牛能追上牛妹，那么牛妹必须得比牛牛先到某一房间。于是可以分别对牛牛和牛妹跑一次dfs，然后如果牛牛到某一房间的距离大于牛妹到某一房间的距离，则视为有效房间，从中选出最大值。

#### AC代码（cpp） ####

/**
     * struct Point {
     *	int x;
     *	int y;
     * };
     */
    
    class Solution {
        
        vector<int> edge[100010];
        int dis1[100010],dis2[100010];
        bool vis[100010];
    public:
        void dfs1(int u,int dis){
        
            for(int i=0;i<edge[u].size();i++){
        
                int v=edge[u][i];
                if(vis[v]==0){
        
                    vis[v]=1;dis1[v]=dis+1;
                    dfs1(v,dis+1);
                }
            }
        }
        void dfs2(int u,int dis){
        
            for(int i=0;i<edge[u].size();i++){
        
                int v=edge[u][i];
                if(vis[v]==0){
        
                    vis[v]=1;dis2[v]=dis+1;
                    dfs2(v,dis+1);
                }
            }
        }
        /**
         * 牛牛经过的房间数。
         * @param n int整型
         * @param x int整型
         * @param Edge Point类vector
         * @return int整型
         */
        int solve(int n, int x, vector<Point>& e) {
        
            // write code here
            if(x==1){
        
                return 0;
            }
            for(int i=0;i<n-1;i++){
        
                int u=e[i].x,v=e[i].y;
                edge[u].push_back(v);
                edge[v].push_back(u);
            }
            memset(vis,0,sizeof(vis));
            vis[1]=1;dis1[1]=0;
            dfs1(1,1);
            memset(vis,0,sizeof(vis));
            vis[x]=1;dis2[x]=0;
            dfs2(x,1);
            int ans=0;
            for(int i=1;i<=n;i++){
        
                if(dis1[i]>dis2[i]){
        
                    ans=max(ans,dis1[i]);
                }
            }
            return ans;
        }
    };

## C：上上下下 ##

[**题目链接**][Link 3]

#### 题意 ####

牛牛是一位优秀的程序员。最近，牛牛在的公司要办年会了。  
牛牛所在的组要表演一个比较有意思的大合唱，程序员们站在第一排，产品经理们站在第二排。为了让年会节目更有吸引力，牛牛在设计站位上下了功夫：从左往右，程序员们由高到矮进行站位，而产品经理们则按由矮到高进行站位，两个队列的上下场方向也不一样，这样从上场、演唱到下场，整个队列看起来就像一个波浪开合，非常有趣。  
牛牛他们排练完就回去工作了，转眼就来到了年会当天。当大家换上了表演用的服装后，牛牛傻了眼：之前排练的时候大家穿的都是自己的鞋，这下统一更换成演出用的鞋之后，原来两个排好的队列不再按身高有序了！然而，表演马上就要开始了，由于站位和演出效果有关，大家的站位又不能进行调整，这可怎么办？  
聪明的牛牛想到了一个补救办法：如果能让相对站在同一列的产品经理和程序员互换位置，最后也能满足从左往右第一排从高到矮，第二排从矮到高，那也能满足演出效果。然而，就在这个关头，牛牛被叫去核对音乐和灯光了，他只好把这个任务交给你。他会把现在第一排和第二排的身高数据给你，请你告诉他最少需要交换几对演出成员才能满足之前的要求。如果怎么交换都不能满足，请你返回 -1。

#### 题解 ####

动态规划。  
dp\[i\]\[j\]：表示处理完前i列，第i列是否交换（j=0表示不交换，j=1表示交换）使得前i列合法的最少操作数。

#### AC代码（cpp） ####

class Solution {
        
        int inf=0x3f3f3f3f;
        int dp[100010][2];   //dp[i][j]：处理完前i列，第i列是否交换（j=0为不交换，j=1为交换）使得前i列合法的最少操作次数
    public:
        /**
         * 计算最小交换次数
         * @param firstRow int整型vector 第一行的身高数据
         * @param secondRow int整型vector 第二行的身高数据
         * @return int整型
         */
    
        int arrange(vector<int>& a, vector<int>& b) {
        
            memset(dp,inf,sizeof(dp));
            int n=a.size();
            dp[1][0]=0,dp[1][1]=1;
            for(int i=2;i<=n;i++){
        
                if(a[i-1]<a[i-2]&&b[i-1]>b[i-2]){
        
                    dp[i][0]=min(dp[i][0],dp[i-1][0]);
                }
                if(a[i-1]<b[i-2]&&b[i-1]>a[i-2]) {
        
                    dp[i][0]=min(dp[i][0],dp[i-1][1]);
                }
                if(b[i-1]<a[i-2]&&a[i-1]>b[i-2]){
        
                    dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
                }
                if(b[i-1]<b[i-2]&&a[i-1]>a[i-2]){
        
                    dp[i][1]=min(dp[i][1],dp[i-1][1]+1);
                }
            }
            int ans=min(dp[n][0],dp[n][1]);
            if(ans==inf) return -1;
            return ans;
        }
    };

[Link 1]: https://ac.nowcoder.com/acm/contest/6915/A
[Link 2]: https://ac.nowcoder.com/acm/contest/6915/B
[Link 3]: https://ac.nowcoder.com/acm/contest/6915/C