牛客多校第五场题解

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;
}
全部评论

相关推荐

04-19 20:04
广州希音国际进出口有限公司_供应链管理(准入职员工)
SHEIN内推SHEIN内推码
shein供应商运营&nbsp;一面面经#运营人求职交流聚集地#shein国际物流管培生一面挂了，国庆后收到hr联系面试供应商专员的岗位（主要是供应商运营），这个岗位面了两面，一面是hr面，二面是业务面一面：10.12&nbsp;全程约35分钟1、自我介绍略2、详细说一下近两段实习的主要工作内容，以及有什么收获3、对shein这个岗位是否了解？对shein这个公司的了解？4、在xx公司管的sku有多少，直接对接的供应商类型有哪些5、xx公司的跨境模式是？6、如何做供应商管理啊？商家表现根据不同维度进行评级打分7、如何和供应商进行谈判，举具体事例说明8、为什么想来shein？说了一下有了解shein的人才培养模式以...
点赞 评论 收藏
分享
04-17 14:11
西安交通大学 后端
暑期实习总结-节孝子启动
楼主的BG是2本9硕，两段中厂实习，一段是大三，一段是去年9月到今年2月底，第一段纯java后端，第二段是做大模型训练平台后端，3月中开始投递暑期实习，目前拿到了字节和美团两个Offer，写一下自己暑期的总结，希望可以帮助到牛友们。一、Offer选择早早看到很多牛客的UU拿到了Offer面临着选择，分享下自己的选择的思路：1、Offer选择心态首先在三月或者四月初拿到大厂Offer的同学，无非是几种情况：学历比较好、实习比较硬、笔试面试基础比较扎实，不论暑期实习选择哪家，秋招应该都是乱杀，所以心态上不用慌张2、招聘趋势从今年的招聘趋势来看，美团、阿里等大厂纷纷喊出all&nbsp;in&nbsp;ai，在面试环节...
美团求职进展汇总 字节求职进展汇总
点赞 评论 收藏
分享
03-06 13:42
已编辑
四川大学 Java
中国最难入职的IT公司
今天上网看到个统计，中国最难入职的IT公司里拼多多排第一。它业务涉及高并发和分布式系统，技术难度大。面试有多轮技术面和系统设计考核，加上工作压力，筛选很严格。 我偶尔也用拼多多购物，东西价格是真便宜，就是部分质量不太好。 原本我以为字节跳动才是最难进的，毕竟字节算法考核超难，基本都是hard级别。现在看来，各有各的门槛，想进头部IT公司，还得努力提升自己技术才行。八股不知道咋记，不知道重点，可以看看我的神品八股专栏，全网40w粉大博主在看，鹅厂面试官也在看，介绍如下https://www.nowcoder.com/discuss/718273556131377152?sourceSSR=users
zhiyog：建议把小米扣掉
点赞 评论 收藏
分享
昨天 12:38
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 京东美团大战，你怎么看？ #
36986次浏览 239人参与
# 一觉醒来，我成论文导师了… #
5107次浏览 101人参与
# 平安产险科技中心求职汇总 #
244939次浏览 2613人参与
# 实习进度记录 #
176486次浏览 2006人参与
# 毕业论文怎么查AI率 #
5473次浏览 295人参与
# 读研or工作，哪个性价比更高？ #
53714次浏览 651人参与
# 哪个瞬间让你对大厂祛魅了？ #
285378次浏览 2002人参与
# 24届的你们都什么时候入职？ #
54715次浏览 421人参与
# 我的求职精神状态 #
6616次浏览 124人参与
# 海康威视求职进展 #
62316次浏览 350人参与
# 摸鱼打卡站 #
36355次浏览 669人参与
# 机械人还在等华为开奖吗？ #
210153次浏览 1084人参与
# 好未来求职进展汇总 #
7447次浏览 60人参与
# 大疆求职进展汇总 #
469099次浏览 3169人参与
# 如果公司降薪，你会跳槽吗？ #
60803次浏览 481人参与
# 大城市找工作会更容易吗 #
18460次浏览 137人参与
# 小红书求职进展汇总 #
49973次浏览 445人参与
# 金山WPS工作体验 #
22359次浏览 140人参与
# 第一份工作应该选择高薪还是大平台 #
128878次浏览 809人参与
# 大家每天通勤多久？ #
32255次浏览 246人参与
# 互联网行业现在还值得去吗 #
5651次浏览 38人参与
牛客网
牛客企业服务