牛客欢乐赛1

忘是亡心i 2022-10-14 15:45 188阅读 0赞

# 牛客欢乐赛1 #

[比赛地址][Link 1]

## A ##

自己最开始想着这什么鬼，把石子在数轴上排序，然后枚举距离看是否满足条件，再一看距离好家伙任意实数，属实不能做。就放弃了。

正确的做法倒是也很简单，我们举一个例子来说的话

![在这里插入图片描述][20210522104443514.png_pic_center]

我们不用考虑具体的中心位置设置在哪里，对于上图而言我只需要把中心位置设置的离第一个红色球更近就可以满足条件，求出来最大是4个。所以问题就转化成了，需要考虑在两个相邻的蓝球中的最多红球的个数。但是需要注意左边没有蓝球以及右边没有蓝球的两种特殊情况。

得到上述的结论之后就是来计算了，最开始自己写的是蓝红分为两个数组，然后进行遍历。最后超时。这里采用分组过后可以采用STL中的lower\_bound与upper\_bound

> lower\_bound
> 
> lower\_bound(起始地址，结束地址，要查找的数值) 返回的是数值 **第一个** 出现的位置。
> 
> upper\_bound
> 
> upper\_bound(起始地址，结束地址，要查找的数值) 返回的是 第一个大于待查找数值 出现的位置。

#include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    vector<int> red;
    vector<int> blue;
    
    int t,n,m;
    bool cmp(int a,int b){
        return a < b;
    }
    
    void work(){
        sort(red.begin(),red.end(),cmp);
        sort(blue.begin(),blue.end(),cmp);
        int cnt = 0;
        int ans = -1;
        for(int i = 0;i < blue.size() - 1;i++){
            int l = blue[i];
            int r = blue[i + 1];
            cnt = lower_bound(red.begin(),red.end(),r) - lower_bound(red.begin(),red.end(),l + 1);
            ans = max(ans,cnt);
        }
        if(ans == 0){
            printf("Impossible\n");
        }else{
            printf("%d\n",ans);
        }
    }
    
    void input(){
        scanf("%d",&t);
        int s;
        while(t--){
            scanf("%d%d",&n,&m);
            red.clear();
            blue.clear();
            for(int i = 0;i < n;i++){
                scanf("%d",&s);
                red.push_back(s);
            }
            for(int i = 0;i < m;i++){
                scanf("%d",&s);
                blue.push_back(s);
            }
          	//处理两种特殊情况
            blue.push_back(0);
            blue.push_back(1e9+10);
            work();
        }
    }
    
    
    int main(){
        input();
        return 0;
    }

除了两个数组排序之外，还可以使用map的方法解决

#include <cstdio>
    #include <map>
    using namespace std;
    map<int,int> pos,cnt;
    int t,n,m;
    
    
    void work(){
        int max = -1;
        int ans = 0;
        for(auto &it:pos){
            if(it.second == 1){
                ans += cnt[it.first];
            }else{
                max = max > ans ? max : ans;
                ans = 0;
            }
        }
        max = max > ans ? max : ans;
        if(max == 0){
            printf("Impossible\n");
        }else{
            printf("%d\n",max);
        }
    }
    
    void input(){
        scanf("%d",&t);
        while(t--){
            pos.clear();
            cnt.clear();
            scanf("%d%d",&n,&m);
            for(int i = 0;i < n;i++){
                int s;
                scanf("%d",&s);
                pos[s] = 1;
                cnt[s]++;
            }
            for(int i = 0;i < m;i++){
                int s;
                scanf("%d",&s);
                pos[s] = 0;
                cnt[s] = 0;
            }
            work();
        }
    
    
    }
    
    int main(){
        input();
        return 0;
    }

## B ##

对于这道题来说，我们可以很方便地根据上一行的数据来推断出这一行的状态，例如

![在这里插入图片描述][2021052210484254.png_pic_center]

比如这里我们假设第一列第一行有雷，那么根据第二列的第一行我们可以知道第二行是没有雷的，根据第二行我们可以得到第三行是有雷的，那么第四行就是没雷的。那么我们还可以假设第一行是没有雷的。这样的流程过后，我们会发现，只要第一行的状态是确定的，那么其余行的状态是可以推出的，也就是确定的。所以答案要么是1要么是2（第一行没雷或者有雷）。假定完之后，判断一下是否冲突即可。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int n;
    int a[10010];
    int l[10010];
    
    int cal(){
    	for(int i = 0;i < n - 1;i++){
    		int left;
    		if(i == 0){
    			left = a[i] - l[i];
    		}else{
    			left = a[i] - l[i] - l[i - 1];
    		}
    		if(left == 1){
    			l[i + 1] = 1;
    		}else if(left == 0){
    			l[i + 1] = 0;	
    		}else{
    			return 0;
    		}
    	}
    	if(a[n - 1] == l[n - 1] + l[n - 2]){
    		return 1;
    	}else{
    		return 0;
    	}
    }
    
    void work(){
    	int ans = 0;
    	l[0] = 1;
    	if(cal()) ans++;
    	l[0] = 0;
    	if(cal()) ans++;
    	printf("%d",ans);
    }
    
    void input(){
    	scanf("%d",&n);
    	for(int i = 0;i < n;i++){
    		scanf("%d",&a[i]);
    	}
    }
    
    int main(){
    	input();
    	work():
    	return 0;
    }

## C ##

在这里我们首先考虑没有施法的情况，对于每一个糖糖，只要有跟他不同组的糖糖在他的后面，且能力值大于它，它就会死。那么我们只需要从后往前遍历，同时维护两个组的最大值。每次遇到一个糖糖的时候就用它和另一组的最大值进行比较，只要小于，糖糖就会死。

我们再考虑施法的情况，在施法的时候，其实是对前面的序列造不成影响的，因为这部分的大小关系是不会改变的，改变的只有后半部分之间的关系。而我们每一次是只判断前半部分的关系。所以这里逐步施法跟放在一起施法是没有影响的。

每次施法的处理，这里如果使用for循环的话就会导致超时，这里就用到了差分数组，记录下相邻两个数字的差值，每一次施法的时候，施法处的差值-1，由于每一次都是从1到x加1，所以这里就使最开头的差值++就可以了

#include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    typedef struct{
        int no;
        int ability;
    }child;
    
    vector<child> temp;
    int delta[50007];
    
    
    int t,n,m,ans;
    
    void change(int time){
        for(int i = 0;i < time;i++){
            temp[i].ability++;
        }
    }
    
    void work(){
        int t[2] = {-1,-1};
        for(int i = n - 1;i >= 0 ;i--){
            int group = temp[i].no;
            if(t[1 - group] > temp[i].ability){
                ans--;
            }
            t[group] = max(t[group],temp[i].ability);
        }
        printf("%d\n",ans);
    }
    
    void input(){
        scanf("%d",&t);
        while(t--){
            temp.clear();
            scanf("%d%d",&n,&m);
            ans = n;
            for(int i = 0;i < n;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                child s;
                s.no = a;
                s.ability = b;
                temp.push_back(s);
                if(i > 0){
                    delta[i] = temp[i].ability - temp[i - 1].ability;
                }
            }
            for(int i = 0;i < m;i++){
                int time;
                scanf("%d",&time);
                delta[0]++;
                delta[time]--;
            }
            for(int i = 0;i < n;i++){
                if(i == 0){
                    temp[i].ability = delta[i] + temp[i].ability;
                }else{
                    temp[i].ability = temp[i - 1].ability + delta[i];
                }
            }
            work();
        }
    }
    
    
    int main(){
        input();
        return 0;
    }

## D ##

最开始看到还以为是搜索题，直接上手深度搜索，最后超时了。正解为动态规划题目。每次走到一个格子之后的状态与该格子之前的状态无关，仅与之后的状态相关，所以考虑用动态规划。这里走到的位置我们可以用$ i*1+j*2+k*3+l*4$来表示

d p \[ i \] \[ j \] \[ k \] \[ l \] = m a x ( d p \[ i − 1 \] \[ j \] \[ k \] \[ l \] , d p \[ i \] \[ j − 1 \] \[ k \] \[ l \] , d p \[ i \] \[ j \] \[ k − 1 \] \[ l \] , d p \[ i \] \[ j \] \[ k \] \[ l − 1 \] ) + a \[ i ∗ 1 + j ∗ 2 + k ∗ 3 + l ∗ 4 \] dp\[i\]\[j\]\[k\]\[l\] = max(dp\[i-1\]\[j\]\[k\]\[l\],dp\[i\]\[j-1\]\[k\]\[l\],dp\[i\]\[j\]\[k-1\]\[l\],dp\[i\]\[j\]\[k\]\[l-1\])+a\[i\*1+j\*2+k\*3+l\*4\] dp\[i\]\[j\]\[k\]\[l\]=max(dp\[i−1\]\[j\]\[k\]\[l\],dp\[i\]\[j−1\]\[k\]\[l\],dp\[i\]\[j\]\[k−1\]\[l\],dp\[i\]\[j\]\[k\]\[l−1\])\+a\[i∗1\+j∗2\+k∗3\+l∗4\]

i,j,k,l分别表示的就是1，2，3，4四张卡片的数量，

#include <cstdio>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    
    int a[357];
    int dp[43][43][43][43];
    int cnt[5];
    int n,m;
    
    int dfs(int i,int j,int k,int l){
        if(i < 0 || j < 0 || k < 0 || l < 0) return 0;
        if(dp[i][j][k][l] != 0) return dp[i][j][k][l];
        dp[i][j][k][l] = max(max(dfs(i - 1,j,k,l),dfs(i,j- 1,k,l)),
                             max(dfs(i,j,k - 1,l),dfs(i,j,k,l - 1)))
                        +a[i * 1 + j * 2 + k * 3 + l * 4];
        return dp[i][j][k][l];
    }
    
    void work(){
        printf("%d\n",dfs(cnt[1],cnt[2],cnt[3],cnt[4]));
    }
    
    void input(){
        scanf("%d%d",&n,&m);
        for(int i = 0;i < n;i++){
            scanf("%d",&a[i]);
        }
        memset(cnt,0,sizeof(cnt));
        for(int i = 0;i < m;i++){
            int temp;
            scanf("%d",&temp);
            cnt[temp]++;
        }
    }
    
    int main(){
        input();
        work();
        return 0;
    }

## E ##

我们在这里假定给定的区间为\[l,r\]，假设我们知道从l开始经过s个区间后的位置t,如果r大于t，那么我们就还需要向后找。当然这里不可能一个一个地找过去。在这里我们可以用二进制的表示。我们假设想找的范围在第一个数的第7个区间里。我们可以先到第一个数的第四个区间。从第四区间到第六区间，从第六区间到第七区间。即7 = 4 + 2 + 1。所以这里我们需要求的就是每一l第0，1，2，4。。。区间右边的位置。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    
    int n,m,k;
    int a[1000100];
    int f[1000100][23];
    
    void input(){
        scanf("%d%d%d",&n,&m,&k);
        for(int i = 1;i <= n;i++){
            scanf("%d",&a[i]);
        }
    }
    
    void prework(){
        long long sum = 0;
        for(int j = 0;j <= 20;j++){
            for(int i = 1;i <= n + 1;i++){
                f[i][j] = n + 1;
            }
        }
        //求第0个区间
        for(int i = 1,j = 0;i <= n;i++){
            while(sum <= k && j <= n){
                ++j;
                sum += a[j];
            }
            f[i][0] = j;
            sum -= a[i];
        }
        //8 = 4 + 4
        //也就是为了求第i个区间转变成求j的i-1区间
        //和从i-1区间右边开始的i-1区间的和
        for(int i = 1;i <= 20;i++){
            for(int j = 1;j <= n;j++){
                f[j][i] = f[f[j][i-1]][i-1];
            }
        }
    }
    
    void calc(int l,int r){
        long long ans = 0;
        for(int i = 20;i >= 0;i--){
            if(r >= f[l][i]){
                ans += 1 << i;
                l = f[l][i];
            }
        }
        if(f[l][0] <= r) ans = -1;
        if(ans == -1){
            printf("Chtholly\n");
        }else{
            printf("%lld\n",ans + 1);
        }
    }
    
    void work(){
        for(int i = 0;i < m;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            calc(l,r);
        }
    }
    
    
    int main(){
        input();
        prework();
        work();
        return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/16416
[20210522104443514.png_pic_center]: /images/20221014/b26683187dda49f2a04404a981852f15.png
[2021052210484254.png_pic_center]: /images/20221014/c0ae20dc8d81431aa35c81ea326c6363.png