牛科小白月赛86

lzywakaka / 2024-01-20 / 原文

A：比较一下两杯盐水浓度大小即可，第一杯盐水浓度较大就输出S，否则输出Y

void solve() {
    double a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a/b>c/d) cout << 'S' << endl;
    else cout << 'Y' << endl;
}

B：判断一下原有字符串是否出现和答案字符串不一样的选项，如果有，直接0分；否则我都可以帮他选对，10分。不存在5分的情况。

void solve() {
    string s1,s2;
    cin >> s1 >> s2;
    for(int i=0;i<s1.size();i++) {
        int cnt=0;
        for(int j=0;j<s2.size();j++) if(s1[i]==s2[j]) cnt=1;
        if(!cnt) {
            cout << 0 << endl;
            return ;
        }
    }
    cout << 10 << endl;
}

C：给出某一段连续的定义是：该连续子段的每一个数字都相同

问：m个询问，每次给出一个区间 [l , r] ，问该区间内有多少个连续的子段。

解：我们预处理原数组，将原数组处理为连续递增区间。

例如数组k：

2 2 3 4 5 5 6 2 1 1 1

我们预处理之后k'：

1 1 2 3 4 4 5 6 7 7 7

现在如果我要查询区间[2 , 6] 之间又多少个连续子段：那么答案就是 k'[6] - k'[2] = (4 - 1) + 1 ，一共有4个区间

这样，每次都可以O(1)的查询一个区间内有多少连续不同的区间

void solve() {
    int n,m;
    cin >> n >> m;
    vector<int> k(n+10) , vis(n+10);
    for(int i=1;i<=n;i++) cin >> k[i];
    for(int i=1;i<=n;i++) {
        if(k[i]==k[i-1]) vis[i]=vis[i-1];
        else vis[i]=vis[i-1]+1;
    }
    while(m--) {
        int l,r;
        cin >> l >> r;
        cout << vis[r]-vis[l]+1 << endl;
    }
}

D：题目就是要我们求有多少个由 ‘ . ’ 组成的长方体。

实现不难，我们可以用dfs或者bfs搜索被裁剪下来的连通块。

对于每一个连通块，我们记录该连通块的大小，以及左上的(x , y)坐标以及右下的(x , y)坐标。

知道一个长方体的左上角和右下角坐标之后，我们就可以用长方体的体积和连通块的大小进行比较，如果长方体体积正好等于连通块大小，ans++。

//　／l、
//（ﾟ､ 。 ７
//　l、 ~ヽ
//　じしf_, )ノ
//  不要放弃！猫猫会为你加油！
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5+10 , M = 1e6+10 , INF = 1e9+7;

int n,m;
int cnt=0,w=0,x_,y_,x2,y2;
int g[1010][1010];

struct node {
    int xx,yy,xt,yt;
}k[1000010];

void dfs(int x,int y) {
    x_=min(x_,x) , x2=max(x2,x);
    y_=min(y_,y) , y2=max(y2,y);
    w++;
    g[x][y]=cnt;
    if(x-1>=1 && g[x-1][y]==0) dfs(x-1,y);
    if(x+1<=n && g[x+1][y]==0) dfs(x+1,y);
    if(y-1>=1 && g[x][y-1]==0) dfs(x,y-1);
    if(y+1<=m && g[x][y+1]==0) dfs(x,y+1);
}

void solve() {
    cin >> n >> m;
    map<int , int> mp;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            char t;
            cin >> t;
            if(t=='*') g[i][j]=-1;
            else g[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(g[i][j]==0) {
                cnt++ , w=0;
                x_=INF , y_=INF , x2=0 , y2=0;
                dfs(i,j);
                mp[cnt]=w;
                k[cnt]={x_,y_,x2,y2};
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++) {
        if((k[i].xt-k[i].xx+1)*(k[i].yt-k[i].yy+1) == mp[i]) ans++;
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int T = 1;
//    cin >> T ;
    while(T--) solve();
    return 0;
}

E：我们知道要在满足饱食度W的情况下，使得可口值最大。

n*n暴力肯定是不行的，会狠狠滴TLE！

那么我们要怎么办呢，题目要求吃的是一段连续的食物使得饱食度达到W对吧！

那说明什么？说明饱食度是递增的！所以我们可以用二分来解决这个问题。

我们首先求一个关于w的前缀和数组。然后我们去枚举以当前点为吃东西的起点，寻找最优的满足饱食度大于等于W的情况下的最大可口度。

首先枚举起点，然后二分出饱食度大于等于W的另一个右端点。自这个右端点往后，都是满足饱食度大于等于W的。

那么还有一个问题，我们怎么保证，可口度最大呢？我们可以将可口值先求一个前缀和数组，然后求一个可口度的后缀最大值！

这样，对于每一个点，我们都知道以他为起点的可以达到的最大可口度。

那么答案就出来了，用二分出的右端点后面的最大可口度减去当前起点之前的可口度，答案在取个min就行。

void solve() {
    int n,m;
    cin >> n >> m;
    vector<int> k(n+10) , d(n+10) , visk(n+10) , visd(n+10) , suf(n+10);
    for(int i=1;i<=n;i++) cin >> k[i] , visk[i]=visk[i-1]+k[i];
    for(int i=1;i<=n;i++) cin >> d[i] , visd[i]=visd[i-1]+d[i];
    suf[n]=visd[n];
    for(int i=n-1;i>=1;i--) suf[i]=max(suf[i+1],visd[i]);
    int ans=-INF;
    for(int i=1;i<=n;i++) {
        int l=i , r=n;
        while(l<=r) {
            int mid = l+r >> 1;
            if(visk[mid]-visk[i-1]>=m) r=mid-1;
            else l=mid+1;
        }
        if(l==n+1) break;
        ans=max(ans,suf[l]-visd[i-1]);
    }
    cout << ans << endl;
}