牛客多校第五场题解

Away from College

https://ac.nowcoder.com/acm/contest/11256/A

B - Boxes

solved by Tryna.(-)

题意： 给出若干个盒子，盒子里面只有一个球，颜色为黑或白，每拆开一个盒子有一个花费，还可以通过花费一次来知道盒子内总共有多少黑球，求知道所有盒子中是什么球的花费的最小期望

题解：

  • 不询问，所有盒子都开一遍，花费为
  • 询问一遍，按花费从大到小开盒子，开到第个盒子能直接判定的前提是后面全部同色并且第个盒子与后面异色，所以一共需要个球为或者，这两种情况出现的概率都为,相加后为，排序后处理一下前缀和即可 
#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-10;
const int maxn = 1e5 + 10;
const int maxm = 6e2 + 10;
const int mod = 998244353;
// const int P = 131;
const int S = 5;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}

int n;
double c, a[maxn], sum[maxn];

void solve(){
    scanf("%d %lf", &n, &c);
    for(int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    double minn = sum[n];
    double base = 0.5;
    double ans = c;
    for(int i = n - 1; i >= 1; i--) {
        ans += base * sum[i];
        base *= 0.5;
    }
    printf("%.6f\n", min(ans, minn));
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    PAUSE;
    return 0;
}

D - Double Strings

题意：
从、两个串中各选取两个相同大小的子集（就算字母相同，只要选取的位置不同，就算作不一样的），要求存在一个位置，使得前面的字母都相同，并且第位上从选取的字母要小于中选取的。问这样的子集有多少对。

思路：
很明显的题，我们需要做的是，当选取一对，时，若，我就要计算出,之前能凑出多少个相等的字符串，之后能凑出多少个长度相同的字符串。

第一部分的和最长公共子序列很像。我可以用去匹配，用去匹配。因为是求数量，这里把取改成相加。但是这样重复计算了既不用第位，也不用第位的情况，所以要减去。如果，我就能让它俩匹配，又能将的情况加上去了。

第二部分，我们设，，且可以马上列出一个排列组合的式子。可以转换成。我们带回原式子，发现是每次在里选个，b里选个，这个总和就相当于在里选个。所以我们只需要计算了。

比较大，组合数可以预处理一下，降个的复杂度，不过加上去也能刚好卡过去。

#include <bits/stdc++.h>

using namespace std;

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 7;
const ll mod = 1e9 + 7;
ll powmod(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
ll inv[N << 1], fac[N << 1];
ll C(int n, int m) {
    assert(n >= 0 && m >= 0);
    assert(n >= m);
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
char a[N], b[N];
ll dp[N][N];

void solve() {
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    int lena = strlen(a + 1), lenb = strlen(b + 1);
    assert(lena < N - 1 && lenb < N - 1);
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        dp[i][0] = dp[0][i] = 1;
    }
    for (int i = 1; i <= lena; ++i) {
        for (int j = 1; j <= lenb; ++j) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            dp[i][j] %= mod;
            if (a[i] == b[j]) dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] += mod;
            dp[i][j] %= mod;
            if (a[i] < b[j]) {
                ans += dp[i - 1][j - 1] * C(lena - i + lenb - j, lena - i) % mod;
                ans %= mod;
            }
        }
    }
    printf("%lld\n", ans);
}

int main() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < N * 2; ++i) {
        fac[i] = fac[i - 1] * (ll)i % mod;
    }
    inv[0] = 1;
    for (int i = 1; i < N * 2; ++i) {
        inv[i] = powmod(fac[i], mod - 2);
    }

    int t = 1;
    while (t--) solve();
    return 0;
}

F - Finding Points

题意： 给出一个凸包的顶点集，要求在凸包内找一点，令为中的最小值，求的最大值

题解： 一种很明显的思路就是三分套三分，分别枚举坐标和坐标，然后枚举坐标的时候我认为需要确定在当前值的情况下的范围，不知道为啥很多码不用判断这个也能过，还是说这么枚举点一定在凸包内部

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-10;
const int maxn = 1e2 + 10;
const int maxm = 6e2 + 10;
const int mod = 998244353;
const int S = 5;

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}

int sgn(double x){
    if(fabs(x) < eps) return 0;
    else return x < 0?-1:1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x + B.x,y + B.y);}
    Point operator - (Point B){return Point(x - B.x,y - B.y);}
    Point operator * (double k){return Point(x*k,y*k);}
    Point operator / (double k){return Point(x/k,y/k);}
    bool operator == (Point B){return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    bool operator < (const Point &b)const{
        if(x == b.x) return y < b.y;
        return x < b.x;
    }
}P[maxn];

struct Line{
    Point p1,p2;
    Line(){};
    Line(Point p1,Point p2):p1(p1),p2(p2){}
}L[maxn];
double Dot(Point A, Point B){return A.x*B.x + A.y*B.y;}  
double Cross(Point A, Point B){return A.x*B.y - A.y*B.x;} 
bool Point_on_seg(Point p, Line v){  //0为不在线段上，1为在线段上
    return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && 
    sgn(Dot(p - v.p1, p - v.p2)) <=0;
}
bool Cross_segment1(Point a, Point b, Point c, Point d){   
 //两线段是否非规范相交
    if(a == c || a == d) return 0;
    if(b == c || b == d) return 0;
    return 
    max(a.x, b.x) >= min(c.x, d.x)&&
    max(c.x, d.x) >= min(a.x, b.x)&&
    max(a.y, b.y) >= min(c.y, d.y)&&
    max(c.y, d.y) >= min(a.y, b.y)&&
    sgn(Cross(b - a, c - a)) * sgn(Cross(b - a, d - a)) <= 0&&
    sgn(Cross(d - c, a - c)) * sgn(Cross(d - c, b - c)) <= 0;
}
Point Cross_point(Point a, Point b, Point c, Point d){         
    double s1 = Cross(b - a, c - a);
    double s2 = Cross(b - a, d - a);
    return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}

int Point_in_polygon(Point pt, Point *p, int n){         //判断点和多边形的位置关系
    for(int i = 0; i < n; i++){
        if(p[i] == pt) return 3;          //点在多边形的顶点上
    }
    for(int i = 0; i < n; i++){
        Line v = Line(p[i], p[(i + 1) % n]);
        if(Point_on_seg(pt, v)) return 2;      //点在多边形边上
    }
    int num = 0;
    for(int i = 0; i < n; i++){
        int j = (i + 1) % n;
        int c = sgn(Cross(pt - p[j], p[i] - p[j]));
        int u = sgn(p[i].y - pt.y);
        int v = sgn(p[j].y - pt.y);
        if(c > 0 && u < 0 && v >= 0) num++;
        if(c < 0 && u >= 0 && v < 0) num--;
    }
    return num != 0;      //1点在内部； 0点在外部
}

int n;

double getangle(double X1, double Y1, double X2, double Y2, double X3, double Y3) {
    double theta = atan2(X1 - X3, Y1 - Y3) - atan2(X2 - X3, Y2 - Y3);
    if(theta > Pi)
        theta -= Pi * 2;
    if (theta < -Pi)
        theta += Pi * 2;
    theta = abs(theta * 180.0 / Pi);
    return theta;
}

double cal(double x, double y) {
    double minn = 180.0;
    for(int i = 0; i < n; i++) {
        int id = (i + 1) % n;
        double angle = getangle(P[i].x, P[i].y, P[id].x, P[id].y, x, y);
        minn = min(minn, angle);
    }
    return minn;
}

double ly, ry, L1, R;

double f(double x) {
    Line l = Line({x, 10000}, {x, -10000});
    double ly = INF, ry = -INF;
    for(int i = 0; i < n; i++) {
        if(Cross_segment1(l.p1, l.p2, L[i].p1, L[i].p2) != 1) continue;
        Point tmp = Cross_point(l.p1, l.p2, L[i].p1, L[i].p2);
        ly = min(ly, tmp.y);
        ry = max(ry, tmp.y);
    }
    double midl, midr;
    L1 = ly, R = ry;
    while(R - L1 > eps) {
        midl = L1 + (R - L1) / 3.0;
        midr = R - (R - L1) / 3.0;
        if(cal(x, midl) > cal(x, midr)) R = midr;
        else L1 = midl;
    }
    return cal(x, L1);
}

void solve(){
    scanf("%d", &n);
    double lx = inf, rx = -inf;
    ly = inf, ry = -inf;
    for(int i = 0; i < n; i++) {
        scanf("%lf %lf", &P[i].x, &P[i].y);
        lx = min(lx, P[i].x);
        rx = max(rx, P[i].x);
        ly = min(ly, P[i].y);
        ry = max(ry, P[i].y);
    }
    for(int i = 0; i < n; i++) {
        L[i] = Line(P[i], P[(i + 1) % n]);
    }
    double midl, midr;
    while(rx - lx > eps){
        midl = lx + (rx - lx)/ 3.0;
        midr = rx - (rx - lx)/ 3.0;
        if(f(midl) > f(midr)) rx = midr;
        else lx = midl;
    }
    printf("%.14f\n", f(lx));   
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // t = rd();
    // scanf("%d", &t);
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

题解： 用三分套三分能过那么用模拟退火肯定也能过。但我的模拟退火似乎不是很优秀，在小样例并且点与点之间的距离较远时误差会较大，测试了一下平均六发过一次，可能算欧了。

#include<bits/stdc++.h>
using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {   cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...);}

#define ll long long
#define ull unsigned long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define PII pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PAUSE system("pause");
const double Pi = acos(-1.0);
const double eps = 1e-10;
const int maxn = 1e2 + 10;
const int maxm = 6e2 + 10;
const int mod = 998244353;
const double startT = 100000;
const int S = 5;
const int dx[]= {-1,-1,-1,0,0,1,1,1};
const int dy[]= {-1,0,1,-1,1,-1,0,1};

inline ll rd() {
    ll f = 0; ll x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}
void out(ll a) {if(a<0)putchar('-'),a=-a;if(a>=10)out(a/10);putchar(a%10+'0');}
#define pt(x) out(x),puts("")
inline void swap(ll &a, ll &b){ll t = a; a = b; b = t;}
inline void swap(int &a, int &b){int t = a; a = b; b = t;}
inline ll min(ll a, ll b){return a < b ? a : b;}
inline ll max(ll a, ll b){return a > b ? a : b;}
ll qpow(ll n,ll k,ll mod) {ll ans=1;while(k){if(k&1)ans=ans*n%mod;n=n*n%mod;k>>=1;}return ans%mod;}
int sgn(double x){
    if(fabs(x) < eps) return 0;
    else return x < 0?-1:1;
}

struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator + (Point B){return Point(x + B.x,y + B.y);}
    Point operator - (Point B){return Point(x - B.x,y - B.y);}
    Point operator * (double k){return Point(x*k,y*k);}
    Point operator / (double k){return Point(x/k,y/k);}
    bool operator == (Point B){return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    bool operator < (const Point &b)const{
        if(x == b.x) return y < b.y;
        return x < b.x;
    }
}P[maxn];

int n;

double getangle(double X1, double Y1, double X2, double Y2, double X3, double Y3) {
    double theta = atan2(X1 - X3, Y1 - Y3) - atan2(X2 - X3, Y2 - Y3);
    if(theta > Pi)
        theta -= Pi * 2;
    if (theta < -Pi)
        theta += Pi * 2;
    theta = abs(theta * 180.0 / Pi);
    return theta;
}

double cal(double x, double y) {
    double minn = 180.0;
    for(int i = 0; i < n; i++) {
        int id = (i + 1) % n;
        double angle = getangle(P[i].x, P[i].y, P[id].x, P[id].y, x, y);
        minn = min(minn, angle);
    }
    return minn;
}


void solve(){
    scanf("%d", &n);
    double maxx = -inf, minn = inf;
    for(int i = 0; i < n; i++) {
        scanf("%lf %lf", &P[i].x, &P[i].y);
        maxx = max(maxx, max(P[i].x, P[i].y));
        minn = min(minn, min(P[i].x, P[i].y));
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int times = 5;
    double bas = maxx - minn + 1;
    if(n <= 4)
        times = 80;
    else if(n <= 5)
        times = 70;
    else if(n <= 10) {
        times = 25;
    }
    else if(n <= 20) times = 10;
    double T = startT, delta = 0.985, x, y;
    double ans = -inf;
    x = 0, y = 0;
    double base = 0.02 / times;
    while(times--) {
        T = startT, delta = 0.980 + times * base - 0.001;
        while(T > eps) {
            int a = rng() % 2;
            int b = rng() % (int)startT;
            double next_x, next_y;
            if(a == 0)
                next_x = x + b * T;
            else next_x = x - b * T;
            a = rng() % 2, b = rng() % (int)startT;
            if(a == 0)
                next_y = y + b * T;
            else next_y = y - b * T;
            if(cal(x, y) < cal(next_x, next_y)) {
                x = next_x;
                y = next_y;
            }
            ans = max(ans, cal(x, y));
            T *= delta;
        }
        // x = 0, y = 0;
        T = startT, delta = 0.98 + times * base - 0.001;
        while(T > eps) {
            int a = rng() % 2;
            int b = rng() % 500;
            double next_x, next_y;
            if(a == 0)
                next_x = x + b * T;
            else next_x = x - b * T;
            a = rng() % 2, b = rng() % 500;
            if(a == 0)
                next_y = y + b * T;
            else next_y = y - b * T;
            if(cal(x, y) < cal(next_x, next_y)) {
                x = next_x;
                y = next_y;
            }
            ans = max(ans, cal(x, y));
            T *= delta;
        }             
    }


    // printf("%.5lf %.5lf\n", x, y);
    printf("%.14lf\n", ans);
}

int main() {
//    freopen("in.txt","r",stdin);
//    freopen("out.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}

H - Holding Two

题意： 构造一个的矩阵，满足没有三个连续(行、列、斜线)的元素相同

题解：
这样构造即可
krwtdxod.png

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define dbg(x...) do { cerr << "\033[32;1m" << #x << " -> "; err(x);} while(0)
void err() { cerr << "\033[39;0m" << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}

typedef long long ll;
const int maxn = 1e3 + 7;

int n, m, a[maxn][maxn];

void run() {
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        int tmp = 1;
        if(i % 2 == 0) tmp = 0;
        for(int j = 1; j <= m; j += 2) {
            a[i][j] = a[i][j + 1] = tmp;
            tmp = 1 - tmp;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            printf("%d", a[i][j]);
        }
        puts("");
    }
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) run();
    return 0;
}

J - Jewels

题意：
三维坐标，人在，每整数秒可以选择一个宝石，花费为宝石到人的距离的平方，在第秒时宝石的的坐标为，问最小花费。

思路：
,不会变化，直接算入答案。都为正，答案只会越来越大，所以每秒都要取一个，就转换成了模型。

费用流麻了，拉了份行的板子才能过。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define dbg(x...) do { cerr << "\033[32;1m" << #x << " -> "; err(x);} while(0)
void err() { cerr << "\033[39;0m" << endl;}
template<class T, class... Ts> void err(const T& arg, const Ts&... args) { cerr << arg << " "; err(args...);}

typedef long long ll;
const int N = 3e2 + 7;

const ll INF = 0x3f3f3f3f3f3f3f3f;
ll cap[N][N];
ll slack[N], wx[N], wy[N];
int n, m, k, tot;
int match[N], pre[N], used[N], vis[N];
void bfs(int u) {
    ll px, py = 0, yy = 0, d;
    memset(pre, 0, sizeof(pre));
    memset(slack, 0x3f, sizeof(slack));
    used[py] = u;
    while (used[py]) {
        px = used[py] ,d = INF, vis[py] = 1;
        for (int i = 1; i <= tot; ++i) {
            if (!vis[i]) {
                if (slack[i] > wx[px] + wy[i] - cap[px][i]) {
                    slack[i] = wx[px] + wy[i] - cap[px][i], pre[i] = py;
                }
                if (slack[i] < d) d = slack[i], yy = i;
            }
        }
        for (int i = 0; i <= tot; ++i) {
            if (vis[i]) wx[used[i]] -= d, wy[i] += d;
            else slack[i] -= d;
        }
        py = yy;
    }
    while (py) used[py] = used[pre[py]], py = pre[py];
}
ll km() {
    memset(wx, 0, sizeof(wx));
    memset(wy, 0, sizeof(wy));
    memset(used, 0, sizeof(used));
    for (int i = 1; i <= tot; ++i) {
        memset(vis, 0, sizeof(vis));
        bfs(i);
    }
    ll ans = 0;
    for (int i = 1; i <= tot; ++i) {
        ans += cap[used[i]][i], match[used[i]] = i;
    }
    return ans;
}
void run() {
    scanf("%d", &n);
    ll ans = 0;
    tot = n;
    for (int i = 1; i <= n; ++i) {
        ll x, y, z, v;
        scanf("%lld %lld %lld %lld", &x, &y, &z, &v);
        ans += x * x;
        ans += y * y;
        for (int j = 1; j <= n; ++j) {
            cap[j][i] = -((ll)(j - 1) * v + z) * ((ll)(j - 1) * v + z);
        }
    }
    ans += -km();
    printf("%lld\n", ans);
}

int main() {
    int t = 1;
    while (t--) run();
    return 0;
}

K - King of Range

题意：
给定序列，求多有少对不同的数对(, )，使得区间内的最大值和最小值的差值大于。

思路：
假设我们从出发，一路向右走，走到时刚好满足条件，那么 ~ 都是满足要求的。这时候把l向右移动一位，能正好满足它的肯定会大于等于先前求得的，符合决策单调性。所以用个双指针，区间求最大最小值就行了。

序列是给定的，但是有多组询问，带个一直跑很容易。所以上就能实现求区间最大最小值了。

之前骂RMQ没用有多狠，现在就有多惨

#include <bits/stdc++.h>

using namespace std;

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;
int n, m, k;
int mx[N][20], mn[N][20];

void st(int n){
    for(int l=1;(1<<l)<=n;l++){
        for(int i=1;i+(1<<l)-1<=n;i++){
            mx[i][l]=max(mx[i][l-1],mx[i+(1<<(l-1))][l-1]);
            mn[i][l]=min(mn[i][l-1],mn[i+(1<<(l-1))][l-1]);
        }
    }
}

int RMQ(int l,int r,int w)
{
    int k = __lg(r - l + 1);
    int ans;
    if(!w) ans=max(mx[l][k],mx[r-(1<<k)+1][k]);
    else ans=min(mn[l][k],mn[r-(1<<k)+1][k]);
    return ans;
}

bool check(int l, int r) {
    return RMQ(l, r, 0) - RMQ(l, r, 1) > k;
}


void solve() {
    n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        mx[i][0] = rd();
        mn[i][0] = mx[i][0];
    }
    st(n);
    while (m--) {
        ll ans = 0;
        k = rd();
        int head = 1, rear = 1;
        while (head <= n) {
            while (rear <= n && !check(head, rear)) rear++;
            if (rear > n) {
                head++;
                continue;
            }
            ans += n - rear + 1;
            head++;
        }
        printf("%lld\n", ans);
    }

}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}
全部评论

相关推荐

10-20 09:45
顺丰集团_大数据挖掘与分析工程师(准入职员工)
顺丰内推，顺丰内推码
已经来工作一个多月啦，感觉幸福度很高，顺丰真的是很值得来的一家公司！公司里的氛围很好，同事们很nice很好沟通，和大家私下相处也贼融洽。工作很充实但是没什么压力，领导带教都不push，感觉每天来公司都很开心~💼&nbsp;公司岗位数据分析💢&nbsp;工作强度在整个集团里算卷的，顺丰科技大多数部门965美滋滋，但是我进的部门业务多975，双休基本可以保证，需求多的话周末也要赶一下进度。🫶️&nbsp;团队氛围进的团队好，前辈都很热心教人，有问必答。❤️&nbsp;职场感受希望我这次转正能通过吧，能过的话会来报喜😊顺丰集团2026届校招启动！【公司简介】：顺丰集团是世界500强企业第377位，中国第一大、世界第四大快递物流服务...
顺丰集团工作强度 274人发布
点赞 评论 收藏
分享
10-20 10:48
门头沟学院 广告设计
放弃铁饭碗的我如何从零开始？
不知道被问了多少次，你为什么不当老师？为什么不考几乎点击就送的编制？专业很冷门，给不了解的牛友简单科普一下，就是教一些智力低下、有自闭症、听障视障的小孩；编制有多好考，教师“秋招”才开始一个月，班里已经有一半的同学拿到事业编的offer了。家里人也不理解，爸爸是搞磨具加工的，妈妈在制造业干物流，家里人对教师职业充满幻想，在知道我决定转行时都是不支持，不仅是游戏行业的压力大，也有父母帮不到忙的无奈。（不过现在决定去上海了，为了双休。）背景简单介绍完，讲一下怎么从双非本师范专业，转行到游戏行业（注意：美术岗有一定特殊性，除严格的学历厂，对背景要求不会那么严。）1.提升学习我从大一开始就一直自学，现...
迷茫的大四🐶：父母如果几十年了社会地位不高的话，建议很多事情还是自己做打算比较好，毕竟他们也没有成功过，虽然扎心，但事实就是这样
没有家庭托举的我是怎么找...
点赞 评论 收藏
分享
10-24 20:50
滴滴_金融_测开(实习员工)
点赞 评论 收藏
分享
10-21 12:44
西南交通大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 牛客树洞，我想对你说 #
14787次浏览 117人参与
# 求职中的尴尬瞬间 #
6377次浏览 53人参与
# 快手技术岗信息交流阵地 #
6756次浏览 52人参与
# 牛客周边新品开箱 #
11559次浏览 91人参与
# 大学最后一个寒假，我想…… #
55098次浏览 600人参与
# 牛友的志愿填报指南 #
36274次浏览 188人参与
# 应届生被毁约被毁意向了怎么办 #
47592次浏览 280人参与
# 如何KTV领导 #
73928次浏览 505人参与
# 研究所笔面经互助 #
97589次浏览 550人参与
# 怎么给家人解释你的工作？ #
14928次浏览 87人参与
# 国企还是互联网，你怎么选？ #
172331次浏览 1305人参与
# 得物app工作体验 #
29802次浏览 69人参与
# 硬件人的春招flag #
52806次浏览 435人参与
# 机械人避雷的岗位/公司 #
29901次浏览 249人参与
# 你的mentor是什么样的人？ #
18718次浏览 119人参与
# 帮我看看，领导说这话什么意思？ #
24840次浏览 107人参与
# 打工人锐评公司红黑榜 #
175836次浏览 1023人参与
# 大疆工作体验 #
19869次浏览 85人参与
# 校招泡的最久的公司是哪家？ #
15446次浏览 92人参与
# 机械人集合！你是什么工程师？ #
21035次浏览 91人参与
# 今年形式下双非本找得到工作吗 #
239610次浏览 1435人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务