2022牛客寒假算法基础集训营4【解题报告】

本文主要是介绍2022牛客寒假算法基础集训营4【解题报告】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

戳我进入比赛

Problem A. R

题目大意

输入两个整数 $n, k$ 和一个长度为 $n$ 的字符串 $s$ .

问字符串 $s$ 中存在多少个子串满足该子串至少包含 $k$ 个 $^{'} R^{'}$ 字符，且不包含 $^{'} P^{'}$ 字符.

$\leq n \leq 2 \times 10^5, 1 \leq k \leq 20, s[i] \in \{'A'-'Z'\}$ .

分析

尺取或者二分都可以.

PS：赛时看到这种题总是不自觉地去写二分，大概因为我是二分大师吧（逃

代码

尺取

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n, k;
char s[M + 5];
int suf[M + 5];void work() {scan(n), scan(k);scanf("%s", s + 1);suf[n + 1] = n + 1; for(int i = n; i >= 1; --i) suf[i] = (s[i] == 'P' ? i : suf[i + 1]);ll ans = 0;for(int i = 1, pr = 0, cr = 0; i <= n; ++i) {while(pr + 1 <= n && cr < k) cr += (s[++pr] == 'R');if(cr == k && pr < suf[i]) ans += suf[i] - pr;if(s[i] == 'R') --cr;}print(ans, '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

二分

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n, k;
char s[M + 5];
int pre[2][M + 5];bool check(int l, int r) {return pre[0][r] - pre[0][l - 1] >= k &&pre[1][r] - pre[1][l - 1] == 0;
}int calL(int p) {int l = p, r = n + 1, mid;while(l < r) {mid = (l + r) >> 1;if(pre[0][mid] - pre[0][p - 1] >= k) r = mid;else l = mid + 1;}return r;
}int calR(int p) {int l = p, r = n, mid;while(l < r) {mid = (l + r + 1) >> 1;if(pre[1][mid] - pre[1][p - 1] == 0) l = mid;else r = mid - 1;}return r;
}int cal(int p) {int l = calL(p);if(l == n + 1 || pre[1][l] - pre[1][p - 1]) return 0;int r = calR(l);return r - l + 1;
}void work() {scan(n), scan(k);scanf("%s", s + 1);for(int i = 1; i <= n; ++i) {pre[0][i] = pre[0][i - 1] + (s[i] == 'R');pre[1][i] = pre[1][i - 1] + (s[i] == 'P');}ll ans = 0;for(int i = 1; i <= n; ++i) {ans += cal(i);}print(ans, '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem B. 进制

题目大意

输入两个整数 $n, q$ 和一个长度为 $n$ 的字符串 $s$ .

接下来 $q$ 次操作，每行输入 $o p, x, y$ .

若 $o p = 1$ 则表示令 $s_x=y \, (1 \leq x \leq n, 0 \leq y \leq 9)$ .

否则若 $o p = 2$ 则表示查询区间 $\, (1 \leq x \leq y \leq n)$ ，该区间子串所能表示的某进制的最小值（进制必须合法，且必须是二进制到十进制之间，可以包含前导零），对 $10^9+7$ 取模.

$\leq n,q \leq 10^5,s[i] \in \{0-9\}$ .

分析

显然对于查询操作，进制应该选为区间 $[x, y]$ 的最大值+1.

用线段树维护区间最小值和字符串 $s$ 在 $2 - 10$ 进制表示下的数，查询时即区间求和，再在对应进制下移位即可.

比如查询到的值为 $b^{l+x-y} + \cdots +s[y+1]b^{l+1}+s[y]b^l$ ，记为 $q$ ，那么答案即为 $\frac{q}{b^l}$ .

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}ll inv(ll n, ll p = mod)
{return quick(n, p - 2, p);
}int n, q;
char s[M + 5];struct segT {int mx[M * 4 + 5];int w[M * 4 + 5][11];int lc(int k) {return k<<1;}int rc(int k) {return k<<1|1;}void push_up(int k) {mx[k] = max(mx[lc(k)], mx[rc(k)]);for(int i = 2; i <= 10; ++i) w[k][i] = (w[lc(k)][i] + w[rc(k)][i]) % mod;}void nmsl() {printf("-----------------------\n");for(int i = 1; i <= 9; ++i) {printf("%d: mx=%d w4=%d\n", i, mx[i], w[i][4]);}printf("---------------------\n");}void build(int k, int l, int r) {if(l == r) {mx[k] = s[l] - '0';for(int i = 2; i <= 10; ++i) w[k][i] = (ll)mx[k] * quick(i, n - l) % mod;return;}int mid = (l + r) >> 1;build(lc(k), l, mid);build(rc(k), mid + 1, r);push_up(k);}void update(int k, int l, int r, int a, int b) {if(l == r) {mx[k] = b;for(int i = 2; i <= 10; ++i) w[k][i] = (ll)mx[k] * quick(i, n - l) % mod;return;}int mid = (l + r) >> 1;if(a <= mid) update(lc(k), l, mid, a, b);else update(rc(k), mid + 1, r, a, b);push_up(k);}int queryMx(int k, int l, int r, int a, int b) {if(l >= a && r <= b) return mx[k];int mid = (l + r) >>1, mx = 0;if(a <= mid) mx = max(mx, queryMx(lc(k), l, mid, a, b));if(mid < b)  mx = max(mx, queryMx(rc(k), mid + 1, r, a, b));return mx;}int query(int k, int l, int r, int a, int b, int c) {if(l >= a && r <= b) return w[k][c];int mid = (l + r) >>1, sum = 0;if(a <= mid) (sum += query(lc(k), l, mid, a, b, c)) %= mod;if(mid < b)  (sum += query(rc(k), mid + 1, r, a, b, c)) %= mod;return sum;}
} tr;/**5 5
56789
1 3 3
1 1 8
2 2 5
2 5 5
2 1 16389
9
8
**/void work() {scan(n), scan(q);scanf("%s", s + 1);tr.build(1, 1, n);for(int i = 1, op, x, y; i <= q; ++i) {scan(op), scan(x), scan(y);if(op == 1) tr.update(1, 1, n, x, y);else {int bs = max(2, tr.queryMx(1, 1, n, x, y) + 1);int pro = tr.query(1, 1, n, x, y, bs);int ans = (ll)pro * inv(quick(bs, n - y)) % mod;print(ans, '\n');}}
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem C. 蓝彗星

题目大意

输入两个正整数 $n$ 和 $t$ ，表示有 $n$ 颗彗星，第 $i$ 颗彗星的颜色为 $s [i]$ ，开始时刻为 $a [i]$ ，持续时间为 $t$ .

问有多少个单位时间可以观察到蓝彗星且看不到红彗星.

$\leq n,t,a[i] \leq 10^5, s[i] \in \{'B','R'\}$ .

分析

直接模拟就行了，枚举当前时间，维护红蓝彗星的个数.

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n, t;
char s[M + 5];
int a[M + 5];
int id[M + 5];struct qnode {int en; char ch;qnode(int _en, char _ch): en(_en), ch(_ch){}bool operator<(const qnode& b) const {return en > b.en;}
};
priority_queue<qnode> q;void work() {scan(n), scan(t);scanf("%s", s + 1);for(int i = 1; i <= n; ++i) scan(a[i]), id[i] = i;sort(id + 1, id + n + 1, [&](int x, int y) {return a[x] < a[y];});int bc = 0, rc = 0, ans = 0;for(int i = 1, j = 1; i <= 2 * M; ++i) {while(!q.empty() && q.top().en == i) {if(q.top().ch == 'B') --bc;else --rc;q.pop();}while(j <= n && a[id[j]] == i) {if(s[id[j]] == 'B') ++bc;else ++rc;q.push(qnode(a[id[j]] + t, s[id[j]]));++j;}if(bc && !rc) ++ans;}print(ans, '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem D. 雪色光晕

题目大意

有一个动点 $x_0,y_0)$ 和一个不动点 $(x, y)$ ，接下来 $n$ 个单位时间，每个单位时间该动点会从当前位置 $(x 0, y 0)$ 移动到 $x_0+x_i,y_0+y_i)$ .

问过程中动点与不动点的最短距离.

$\leq n \leq 2 \times 10^5, -10^9 \leq x_i,y_i \leq 10^9$ .

分析

其实就是求点到线段距离，板子一套就完事~

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;namespace Geo {typedef double db;const db eps = 1e-9, PI = acos(-1), inf = numeric_limits<db>::max();inline int sign(db a) {return a < -eps ? -1 : a > eps;}inline int cmp(db a, db b) {return sign(a - b);}inline bool inmid(db k, db a, db b) {return sign(a - k) * sign(b - k) <= 0;}struct Point {db x, y;Point(db _x, db _y): x(_x), y(_y){}Point() = default;Point operator+(const Point& b) const {return Point(x + b.x, y + b.y);}Point operator-(const Point& b) const {return Point(x - b.x, y - b.y);}Point operator*(const db& b) const {return Point(x * b, y * b);}Point operator/(const db& b) const {return Point(x / b, y / b);}bool operator==(const Point& b) const {return !cmp(x, b.x) && !cmp(y, b.y);}bool operator!=(const Point& b) const {return !(*this == b);}bool operator<(const Point& b) const {int c = cmp(x, b.x);if(c) return c == -1;return cmp(y, b.y) == -1;}bool operator>(const Point& b) const {return b < *this;}Point right(const db& len) {return Point(x + len, y);}Point up(const db& len) {return Point(x, y + len);}db length() const {return hypot(x, y);}db length2() const {return x * x +  y * y;}Point unit() const {return *this / this->length();}void print() const {printf("%.11f %.11f\n", x, y);}void scan() const {scanf("%lf %lf", &x, &y);}db dis(Point b) const {return (*this - b).length();}db dis2(Point b) const {return (*this - b).length2();}Point rotate(db ac) const {return Point(x * cos(ac) - y * sin(ac), y * cos(ac) + x * sin(ac));}Point rotate90() const {return Point(-y, x);}db dot(Point o) const {return x * o.x + y * o.y;}db det(Point o) const {return x * o.y - y * o.x;}};typedef Point Vector;typedef vector<Point> Polygon;struct Line {Point u, v;Line(const Point& _a, const Point& _b): u(_a), v(_b){}Line() = default;Vector getVec() const {return v - u;}Line go(Vector t) {return Line(u + t, v + t);}bool isPoint() const {return u == v;}db length() const {return u.dis(v);}db length2() const {return u.dis2(v);}void print() const {u.print(), v.print();}void scan() {u.scan(), v.scan();}};inline db dot(Point ab, Point ac) { //点积return ab.x * ac.x + ab.y * ac.y;} //|ab|*|ac|*cosainline int dotOp(Point c, Point a = {0, 0}, Point b = {0, 1e5}) {return sign(dot(b - a, c - a));} //+: 1,4  -: 2,3inline db cross(Point ab, Point ac) { //叉积return ab.x * ac.y - ab.y * ac.x;} //|ab|*|ac|*sinainline int crossOp(Point c, Point a = {0, 0}, Point b = {0, 1e5}) {return sign(cross(b - a, c - a));} //+: 1,2  -: 3,4inline int Op(Point c, Point a = {0, 0}, Point b = {0, 1e5}) { //相对象限int lr = dotOp(c, a, b), ud = crossOp(c, a, b);if(!lr || !ud) return 0;return lr + ud == 2 ? 1 : (lr + ud == -2 ? 3 : (lr == -1 ? 2 : 4));}inline int Quadrant(const Point& a) { //象限int x = cmp(a.x, 0), y = cmp(a.y, 0);if(x > 0 && y > 0) return 1;if(x < 0 && y > 0) return 2;if(x < 0 && y < 0) return 3;if(x > 0 && y < 0) return 4;return 0;}bool parallel(const Line& a, const Line& b) { //直线平行return sign(cross(a.getVec(), b.getVec())) == 0;}bool sameDir(const Line& a, const Line& b) { //直线同向return parallel(a, b) && sign(dot(a.getVec(), b.getVec())) == 1;}bool vertical(const Line& a, const Line& b) { // 直线垂直return sign(dot(a.getVec(), b.getVec())) == 0;}
//    bool compairAng(const Point& a, const Point& b) {
//    }
//    bool operator<(const Line& a, const Line& b) {
//    }inline db disPtoL(Point c, Line a) { //点到直线距离return fabs(cross(a.getVec(), c - a.u)) / a.length();}inline Point nearestPoint(Point c, Line ab) { //点到线段的最近点db t = dot(c - ab.u, ab.getVec()) / ab.length2();if(0 <= t && t <= 1) return ab.u + ab.getVec() * t;return c.dis(ab.u) > c.dis(ab.v) ? ab.v : ab.u;}inline db disPtol(Point c, Line a) { //点到线段距离return c.dis(nearestPoint(c, a));}inline Point pjPoint(Point c, Point a, Point b) { //投影点return a + (b - a).unit() * dot(c - a, b - a) / (b - a).length();}inline Point symPoint(Point c, Point a, Point b) { //对称点return pjPoint(c, a, b) * 2 - c;}inline Point getInsec(Point a, Point b, Point c, Point d) { //获取交点db w1 = cross(a - c, d - c), w2 = cross(d - c, b - c);return (a * w2 + b * w1) / (w1 + w2);}inline Point getInsec(Line a, Line b) { //直线交点return getInsec(a.u, a.v, b.u, b.v);}inline bool inseg(Point c, Point a, Point b) { //点在线段上if(c == a || c == b) return 1;return sign(cross(b - a, c - a)) == 0 && sign(dot(a - c, b - c)) == -1;}inline bool inseg(Point c, Line ab) { //点在线段上return inseg(c, ab.u, ab.v);}inline bool intersect(db l1, db r1, db l2, db r2) { //排斥实验 检查线段对角线矩形是否相交if(l1 > r1) swap(l1, r1);if(l2 > r2) swap(l2, r2);return cmp(r2, l1) != -1 && cmp(r1, l2) != -1;}inline int spanLine(Point a, Point b, Point c, Point d) { //线段ab跨立线段cd 跨立试验 <0成功 =0在直线上 >0失败return sign(cross(a - c, d - c)) * sign(cross(b - c, d - c));}inline int spanLine(Line a, Line b) { //线段a跨立线段b 跨立试验 <0成功 =0在直线上 >0失败return spanLine(a.u, a.v, b.u, b.v);}inline bool checkSSsp(Point a, Point b, Point c, Point d) { //线段严格相交return spanLine(a, b, c, d) < 0 && spanLine(c, d, a, b) < 0;}inline bool checkSS(Point a, Point b, Point c, Point d) { //线段非严格相交return intersect(a.x, b.x, c.x, d.x) && intersect(a.y, b.y, c.y, d.y)&& spanLine(a, b, c, d) <= 0 && spanLine(c, d, a, b) <= 0;}inline bool checkSS(Line a, Line b, bool Notsp = true) {if(Notsp) return checkSS(a.u, a.v, b.u, b.v);else      return checkSSsp(a.u, a.v, b.u, b.v);}inline db disltol(Line a, Line b) { //线段到线段距离if(checkSS(a, b, 1)) return 0;return min(min(disPtol(a.u, b), disPtol(a.v, b)),min(disPtol(b.u, a), disPtol(b.v, a)));}inline bool cmpAtan(Point a, Point b) { //极角排序if(cmp(atan2(a.y, a.x), atan2(b.y, b.x)) != 0) return atan2(a.y, a.x) < atan2(b.y, b.x);return a.x < b.x;}inline void sortACW(Polygon& v) { //逆时针排序Point g(0, 0);int n = v.size();for(int i = 0; i < n; ++i) g.x += v[i].x, g.y += v[i].y;g.x /= n, g.y /= n;sort(v.begin(), v.end(), [&](Point& a, Point& b) {return sign(cross(a - g, b - g)) == 1;});}inline db area(const Polygon& v) { //多边形面积 需要逆时针排序db ans = 0;int len = v.size();if(len < 3) return 0;for(int i = 0; i < len; ++i) ans += cross(v[i], v[(i + 1) % len]);return ans / 2;}inline bool isConvex(const Polygon& v) { //判断凸多边形 需要逆时针排序int n = v.size();if(n < 3) return 0;for(int i = 0; i < n; ++i) {if(cross(v[(i + 1) % n] - v[i], v[(i + 2) % n] - v[(i + 1) % n]) < 0) return 0;}return 1;}inline int contain(const Polygon& v, Point q) { //点和多边形位置关系 内部1 外部-1 多边形上0int n = v.size();int res = -1;for(int i = 0; i < n; ++i) {Vector a = v[i] - q, b = v[(i + 1) % n] - q;if(cmp(a.y, b.y) == 1) swap(a, b);if(sign(a.y) != 1 && sign(b.y) == 1 && sign(cross(a, b)) == 1) res = -res;if(sign(cross(a, b)) == 0 && sign(dot(a, b)) != 1) return 0;}return res;}inline Polygon ConvexHull(Polygon A, int flag = 1) { //凸包 不严格0 严格1int n = A.size();if(n <= 2) return A;Polygon ans(n * 2);int now = -1;sort(A.begin(), A.end());for(int i = 0; i < n; ans[++now] = A[i++])while(now > 0 && crossOp(A[i], ans[now - 1], ans[now]) < flag) --now;for(int i = n - 2, pre = now; i >= 0; ans[++now] = A[i--])while(now > pre && crossOp(A[i], ans[now - 1], ans[now]) < flag) --now;ans.resize(now);return ans;}inline db convexDimater(Polygon v) { //凸包直径int now = 0, n = v.size();db ans = 0;for(int i = 0; i < n; ++i) {now = max(now, i);while(1) {db k1 = v[i].dis(v[now % n]), k2 = v[i].dis(v[(now + 1) % n]);ans = max(ans, max(k1, k2));if(cmp(k2, k1) == 1) ++now;else                 break;}}return ans;}inline Polygon convexCut(Polygon v, Line a) { //凸包v被直线a分割成的逆时针凸包int n = v.size();Polygon ans;for(int i = 0; i < n; ++i) {int k1 = crossOp(v[i], a.u, a.v), k2 = crossOp(v[(i + 1) % n], a.u, a.v);if(k1 >= 0) ans.emplace_back(v[i]);if(k1 * k2 < 0) ans.emplace_back(getInsec(a, Line(v[i], v[(i + 1) % n])));}return ans;}db NPPD(int l, int r, const vector<Point>& v, vector<int>& tmp) {if(l == r) return inf;if(l + 1 == r) return v[l].dis(v[r]);int mid = (l + r) >> 1;db d = min(NPPD(l, mid, v, tmp), NPPD(mid + 1, r, v, tmp));int p = 0;for(int i = l; i <= r; ++i) if(fabs(v[mid].x - v[i].x) < d) tmp[p++] = i;sort(tmp.begin(), tmp.begin() + p, [&](int& a, int& b){return cmp(v[a].y, v[b].y) == -1;});for(int i = 0; i < p; ++i) {for(int j = i + 1; j < p && v[tmp[j]].y - v[tmp[i]].y < d; ++j) {d = min(d, v[tmp[j]].dis(v[tmp[i]]));}}return d;}db nearestPPDis(vector<Point> v) {//平面最近点对sort(v.begin(), v.end());int n = v.size();vector<int> tmp(n);return NPPD(0, n - 1, v, tmp);}struct Circle {Point o;db r;void scan() {o.scan();scanf("%lf", &r);}Circle(Point _o, db _r): o(_o), r(_r){}Circle() = default;bool operator==(const Circle b) const {return o == b.o && cmp(r, b.r) == 0;}db area() {return PI * r * r;}int contain(Point t) { //1圆外 0圆上 -1圆内return cmp(o.dis(t), r);}bool intersect(Circle b) {//两圆是否相交return cmp(o.dis(o), r + b.r) != 1&& cmp(o.dis(o), fabs(r - b.r)) != -1;}int posRela(Circle b) {//0外离 1外切 2相交 3内切 4内含db d = o.dis(b.o);if(cmp(d, r + b.r) == 1) return 0;if(cmp(d, r + b.r) == 0) return 1;if(cmp(d, r + b.r) == -1 && cmp(d, fabs(r - b.r)) == 1) return 2;if(cmp(d, fabs(r - b.r)) == 0) return 3;if(cmp(d, fabs(r - b.r)) == -1) return 4;assert(0);}int intersect(Line t) { //-1相交 0相切 1相离return cmp(disPtoL(o, t), r);}int intersect_seg(Line t) {Point k = nearestPoint(o, t);return cmp(o.dis(k), r);}};
}typedef Geo::Point point;
typedef Geo::Line line;
typedef Geo::Polygon polygon;
typedef Geo::Circle circle;
function<int(db)> sign = Geo::sign;
function<int(db, db)> cmp = Geo::cmp;const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n;
point p[M + 5];void work() {scan(n);for(int i = 0; i <= n + 1; ++i) p[i].scan();db mi = (ll)1e18;swap(p[0], p[1]);for(int i = 1; i <= n; ++i) {mi = min(mi,disPtol(p[0],line(p[1], p[1] + p[i + 1])));p[1] = p[1] + p[i + 1];}printf("%.12f\n", mi);
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem E. 真假签到题

题目大意

给了一份代码：

long long f(long long x){if(x==1)return 1;return f(x/2)+f(x/2+x%2);
}

给出正整数 $x$ ，求 $f (x)$ .

$\leq x \leq 10^{18}$ .

分析

直接跑一下前几项，可以发现 $f (x) = x$ .

代码

print(input())

Problem F. 小红的记谱法

题目大意

大模拟，懒得写的了…

分析

摸摸摸%%%

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int getID(char ch) {if(ch == 'C') return 1;if(ch == 'D') return 2;if(ch == 'E') return 3;if(ch == 'F') return 4;if(ch == 'G') return 5;if(ch == 'A') return 6;if(ch == 'B') return 7;assert(0);
}char s[M + 5];
vector<pair<int, int>> num;void work() {scanf("%s", s + 1);int n = strlen(s + 1);for(int i = 1, j = 0; i <= n; ++i) {if(s[i] == '<') --j;else if(s[i] == '>') ++j;else num.push_back(make_pair(getID(s[i]), j));}for(auto [a, b]: num) {print(a);while(b < 0) putchar('.'), ++b;while(b > 0) putchar('*'), --b;}putchar('\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem G. 子序列权值乘积

题目大意

给一个长度为 $n$ 的序列 $a$ ，求序列 $a$ 所有子序列的最大值与最小值乘积的乘积，答案对 $10^9+7$ 取模.

$\leq n \leq 2 \times 10^5, 1 \leq a[i] \leq 10^9$ .

分析

显然，对序列 $a$ 排个序对答案是不影响的. 由于求的是所有子序列的最大值与最小值乘积的乘积，所以我们可以单独考虑最大值与最小值的贡献，下面以求最大值为例，最小值同理.

枚举 $i$ ，表示 $a [i]$ 为最大值，那么 $i$ 必选， $[i + 1, n]$ 必不能选， $[1, i - 1]$ 可选可不选. 因此共有 $2^{i-1}$ 种方案， $a [i]$ 作为最大值的贡献即为 $a[i]^{2^{i-1}}$ .

由于 $2^{i-1}$ 很大，不可能先把 $2^{i-1}$ 求出来再快速幂求 $a[i]^{2^{i-1}}$ ，所以就该欧拉降幂登场啦~

因为 $a [i]$ 与 $10^9+7$ 互质，所以 $a[i]^{2^{i-1}} \% (10^9+7) = a[i]^{2^{i-1}\%\varphi(10^9+7)} \% (10^9+7)$ .

就完啦，就完啦，就完啦~~

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)2e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n;
int a[M + 5];ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}void work() {scan(n);for(int i = 1; i <= n; ++i) scan(a[i]);sort(a + 1, a + n + 1);int ans = 1;for(int i = 1; i <= n; ++i) ans = (ll)ans * quick(a[i], quick(2, i - 1, mod - 1)) % mod;for(int i = 1; i <= n; ++i) ans = (ll)ans * quick(a[i], quick(2, n - i, mod - 1)) % mod;print(ans, '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem H. 真真真真真签到题

题目大意

有一个正方体，A 先在正方体内选一个位置，B 再在正方体内选一个位置，A 希望离 B 尽可能近，B 希望离 A 尽可能远.

已知 A 与 B 的距离为 $x$ ，求正方体的体积.

分析

很明显，这题可以推柿子（但正经人谁推柿子啊

显然啊， $x^3$ 与答案一定成常数倍关系，那么把样例算一算，常数倍数就得到了（偷笑

在这里插入图片描述

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x)
{x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x)
{if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch)
{print(x), putchar(ch);
}typedef double db;
typedef long long ll;const int M = (int)1e5;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;void work()
{int x; scan(x);printf("%.12f\n", x * x * x * 1.5396007178425125170687300864816);
}int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem I. 爆炸的符卡洋洋洒洒

题目大意

有 $n$ 个物品，每个物品有两种属性， $a_i$ 表示消耗， $b_i$ 表示威力.

一组物品的消耗为该组物品消耗之和，威力为改组物品威力之和.

问选一组物品，在消耗为 $k$ 的倍数的条件下，威力最大值是多少.

$\leq n,k \leq 10^3, 1 \leq a_i,b_i \leq 10^9$ .

分析

分析啥，这不就无脑dp么

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)1e3;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n, k;
ll f[M + 5][M + 5];void work() {scan(n), scan(k);memset(f, -0x3f, sizeof f);f[0][0] = 0;for(int i = 1, a, b; i <= n; ++i) {scan(a), scan(b);for(int j = 0; j < k; ++j) {f[i][j] = f[i - 1][j];f[i][j] = max(f[i][j], f[i - 1][(j - a % k + k) % k] + b);}}if(f[n][0] <= 0) print(-1, '\n');else print(f[n][0], '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem J. 区间合数的最小公倍数

题目大意

给出 $l, r$ ，问区间 $[l, r]$ 所有合数的 lcm，答案对 $10^9+7$ 取模.

$\leq l \leq r \leq 3 \times 10^4$ .

分析

经典题了属于是.

对 $[l, r]$ 所有的合数做质因数分解，记录每个质因子的最大次幂，就完了.

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)1e5;
const int N = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];void init()
{memset(is_prime, 1, sizeof(is_prime));is_prime[0] = is_prime[1] = 0;for(int i = 2; i <= M; ++i){if(is_prime[i]){prime[++cnt] = i;v[i] = i;}for(int j = 1; j <= cnt && i * prime[j] <= M; ++j){is_prime[i * prime[j]] = 0;v[i * prime[j]] = prime[j];if(i % prime[j] == 0){break;}}}
}ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}map<int, int> mp;void work() {int l, r; scan(l), scan(r);for(int i = l; i <= r; ++i) if(!is_prime[i]) {int j = i;while(j > 1) {int x = v[j], c = 0;while(j % x == 0) j /= x, ++c;mp[x] = max(mp[x], c);}}if(mp.empty()) return print(-1, '\n'), void();int ans = 1;for(auto x: mp) ans = (ll)ans * quick(x.first, x.second) % mod;print(ans, '\n');
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);init();int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

Problem K. 小红的真真假假签到题题

题目大意

给一个正整数 $x$ ，要求构造正整数 $y$ ，满足：

$y$ 是 $x$ 的倍数，且 $x$ 和 $y$ 不能相等.
$x$ 在二进制表示下（为一个01串）是 $y$ 的二进制表示的一个子串。且 $x$ 和 $y$ 的二进制表示的1的个数不能相同.
$y$ 必须为不超过 $10^{19}$ 的正整数.

$\leq x \leq 10^9$ .

分析

性质种出现二进制，肯定从二进制上考虑，显然 $(x < < 30) + x$ 就可以.

代码

x=int(input())
print((x<<30)+x)

Problem L. 在这冷漠的世界里光光哭哭

题目大意

给一个长度为 $n$ 的字符串 $s$ 和 $q$ 次询问.

每次询问给出 $l$ , $r$ 和一个长度为 $3$ 的字符串 $t$ ，问字符串 $s [l, r]$ 中存在多少个子序列是 $t$ .

$\leq n \leq 8 \times 10^4, 1 \leq q \leq 5 \times 10^5, s[i],t[i] \in \{'a'-'z'\}$ .

分析

呜呜，这题想了好久，太久没训练，感觉脑袋傻掉了.

直接分块就行了，预处理一些信息，然后按照 $t$ 的三个字符在块的位置分讨论.

不过这貌似不是正解（乱搞

代码

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void scan(T& x) {x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch) {print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned long long ull;const db eps = 1e-6;
const int M = (int)8e4;
const int N = (int)3e2;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;int n, m, block;
char s[M + 5];
int id[M + 5];
int f[N + 5][26][26][26];
int sum[N + 5][26][26][26];
int g[N + 5][26][26];
int h[N + 5][26];
int L[N + 5], R[N + 5];void parse() {for(int i = 1; i <= n; ++i) id[i] = (i - 1) / block + 1;for(int l = 1, r = 0; l <= n; l = r + 1) {while(r + 1 <= n && id[l] == id[r + 1]) ++r;L[id[l]] = l, R[id[l]] = r;for(int i = l; i <= r; ++i) {for(int j = 0; j < 26; ++j) {for(int k = 0; k < 26; ++k) {f[id[l]][j][k][s[i] - 'a'] += g[id[l]][j][k];}g[id[l]][j][s[i] - 'a'] += h[id[l]][j];}h[id[l]][s[i] - 'a']++;}}for(int i = 0; i < 26; ++i) {for(int j = 0; j < 26; ++j) {for(int k = 0; k < 26; ++k) {for(int l = 1; l <= id[n]; ++l) sum[l][i][j][k] = sum[l - 1][i][j][k] + f[l][i][j][k];}}}
}ll bao(int l, int r, char t[]) {int pre = (s[l] == t[1]), suf = 0;for(int i = l + 2; i <= r; ++i) if(s[i] == t[3]) ++suf;ll ans = 0;for(int i = l + 1; i + 1 <= r; ++i) {if(s[i] == t[2]) ans += (ll)pre * suf;if(s[i] == t[1]) ++pre;if(s[i + 1] == t[3]) --suf;}return ans;
}ll cal_abc(int l, int r, char t[]) {ll ans = bao(l, R[id[l]], t) + bao(L[id[r]], r, t);ans += sum[id[r] - 1][t[1] - 'a'][t[2] - 'a'][t[3] - 'a'] - sum[id[l]][t[1] - 'a'][t[2] - 'a'][t[3] - 'a'];return ans;
}ll cal_ab_c(int l, int r, char t[]) {int pre = 0, suf = 0, cnt = 0;ll ans = 0;for(int i = L[id[r]]; i <= r; ++i) if(s[i] == t[3]) ++suf;for(int i = id[l] + 1; i < id[r]; ++i) suf += h[i][t[3] - 'a'];for(int i = l; i <= R[id[l]]; ++i) {if(s[i] == t[2]) cnt += pre;if(s[i] == t[1]) pre++;}ans += (ll)cnt * suf;for(int i = id[l] + 1; i < id[r]; ++i) {suf -= h[i][t[3] - 'a'];ans += (ll)g[i][t[1] - 'a'][t[2] - 'a'] * suf;}
//    printf("ab_c: %lld\n", ans);return ans;
}ll cal_a_bc(int l, int r, char t[]) {int pre = 0, suf = 0, cnt = 0;ll ans = 0;for(int i = L[id[r]]; i <= r; ++i) {if(s[i] == t[3]) cnt += pre;if(s[i] == t[2]) pre++;}pre = 0;for(int i = l; i <= R[id[l]]; ++i) if(s[i] == t[1]) ++pre;for(int i = id[l] + 1; i < id[r]; ++i) pre += h[i][t[1] - 'a'];ans += (ll)pre * cnt;for(int i = id[r] - 1; i > id[l]; --i) {pre -= h[i][t[1] - 'a'];ans += (ll)pre * g[i][t[2] - 'a'][t[3] - 'a'];}
//    printf("a_bc: %lld\n", ans);return ans;
}ll cal_a_b_c(int l, int r, char t[]) {int pre = 0, suf = 0;ll ans = 0;for(int i = l; i <= R[id[l]]; ++i) if(s[i] == t[1]) ++pre;for(int i = L[id[r]]; i <= r; ++i) if(s[i] == t[3]) ++suf;for(int i = id[l] + 2; i < id[r]; ++i) suf += h[i][t[3] - 'a'];for(int i = id[l] + 1; i < id[r]; ++i) {ans += (ll)pre * h[i][t[2] - 'a'] * suf;pre += h[i][t[1] - 'a'];suf -= h[i + 1][t[3] - 'a'];}
//    printf("a_b_c: %lld\n", ans);return ans;
}ll cal(int l, int r, char t[]) {return cal_abc(l, r, t)+ cal_ab_c(l, r, t)+ cal_a_bc(l, r, t)+ cal_a_b_c(l, r, t);
}void work() {scan(n), scan(m); block = (int)sqrt(n);scanf("%s", s + 1);parse();char t[5]; int l, r;for(int _ = 1; _ <= m; ++_) {scan(l), scan(r), scanf("%s", t + 1);if(id[r] - id[l] + 1 <= 2) {print(bao(l, r, t), '\n');} else {print(cal(l, r, t), '\n');}}
}int main() {/*ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);*/
//	freopen("big.out", "r", stdin);
//	freopen("out", "w", stdout);int T = 1; //scan(T);for(int ca = 1; ca <= T; ++ca) {work();}
//	cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}

这篇关于2022牛客寒假算法基础集训营4【解题报告】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

2022牛客寒假算法基础集训营4【解题报告】

戳我进入比赛

Problem A. R

题目大意

分析

代码

尺取

二分

Problem B. 进制

题目大意

分析

代码

Problem C. 蓝彗星

题目大意

分析

代码

Problem D. 雪色光晕

题目大意

分析

代码

Problem E. 真假签到题

题目大意

分析

代码

Problem F. 小红的记谱法

题目大意

分析

代码

Problem G. 子序列权值乘积

题目大意

分析

代码

Problem H. 真真真真真签到题

题目大意

分析

代码

Problem I. 爆炸的符卡洋洋洒洒

题目大意

分析

代码

Problem J. 区间合数的最小公倍数

题目大意

分析

代码

Problem K. 小红的真真假假签到题题

题目大意

分析

代码

Problem L. 在这冷漠的世界里光光哭哭

题目大意

分析

代码

相关文章