当前位置: 首页 > news >正文

2021牛客暑期多校训练营5

B、Boxes

题目大意

你有nnn个盒子,每个盒子内存在可能有黑球和白球中的一种,打开每个盒子都有一个代价wiw_iwi,你还有一次询问裁判的机会,当然询问裁判代价为CCC,你需要告诉裁判这nnn个盒子每个盒子里面的球颜色,你需要花费的最小代价是多少?

Solution

考点:思维

首先我们不询问裁判的话,我们就要把nnn个盒子全部打开,代价为∑i=1nwi\sum\limits_{i=1}^nw_ii=1nwi

如果我们询问裁判,那么想想我们是不是最多只需要打开n−1n-1n1个盒子,并且如果用000代表白球111代表黑球如下分析。

考虑开000次盒子结束,如果裁判告诉我们有nnn个白球或者nnn个黑球用二进制表示那就是000000000000111111111111这样的时候结束,那么我们这次代价就只有CCC

考虑开111次盒子结束,那么我们要先开最小花费的那个,并且结束的要求是100010001000或者011101110111,并且还需要对上裁判给你的颜色,所以这里应该概率多乘一个12\frac{1}{2}21,那么这种概率计算为12n−1\frac{1}{2}^{n-1}21n1

考虑开222次盒子结束,那么我们结束的要求就是.100.100.100或者.011.011.011,那么这种概率计算为12n−2\frac{1}{2}^{n-2}21n2

以此类推,把开盒子代价排序然后求前缀和处理就行了。

const int N = 1e6 + 7;
int n;
double C;
double p[N];int solve() {cin >> n >> C;for (int i = 1; i <= n; ++i) cin >> p[i];sort(p + 1, p + 1 + n);for (int i = 1; i <= n; ++i) p[i] += p[i - 1];double res = C;for (int i = 1; i < n; ++i)  res += p[i] * pow(0.5, n - i);res = min(res, p[n]);printf("%.12f\n", res);return 1;
}

C、Cheating and Stealing

题目大意

你和对手进行乒乓球比赛,你们原本进行了n(1≤n≤106)n(1\le n\le 10^6)n(1n106)局比赛,WWW代表你赢下了第iii局,LLL代表你输掉了第iii局。

现在我可以操控这个比赛规则,让游戏赛制变成在赢下iii球制,也就是我在赢下iii球后,如果和对手比分差值大于等于222我就拿下一个小分,否则就是对手拿下一个小分,如果差值为000或者111那么接着进行下一局,那么我在iii球赛制下,进行完nnn局比赛我能赢得的小分用f(i)f(i)f(i)表示。

题目求∑i=1nf(i)∗(n+1)i−1\displaystyle \sum\limits_{i=1}^nf(i)*(n+1)^{i-1}i=1nf(i)(n+1)i1

Solution

考点:预处理模拟题

首先我们可以预处理出从[1,i][1,i][1,i]这些位置里面有多少个WWW和多少个LLL,这样用前缀和的形式就可以找到任意区间内WWWLLL的数量。

并且我们可以知道第iiiWWW出现的下标在哪里,以及第iiiLLL出现的下标在哪里。

那么当我们枚举这个iii球赛制的时候,我们就可以知道上一次加小分的位置在哪里,从这个位置往后iiiWWW就是我下一次赢球的最小下标,同理可以找到对手赢球的最小下标。

将这两个下标取min⁡\minmin之后局面就会出现两种;

  1. 要么有人已经拿下了这一个小分,那么直接看下是不是我赢下了这局比赛就行。
  2. 要么两人差距为111,那么这时候再看下一局是谁赢下,如果比完下一局比分差值为222了,同理统计下是不是我赢下了这局比赛,如果比完差值为000了,我们就不能简单的再慢慢一步步往后挪,我们要预处理一个平局数组,找到当第jjj局比赛平局的时候下一次分出胜负在那个局面下,用这个数组跳跃查找就行了。这个数组预处理也很容易,只需要倒序的处理nnn局比赛的情况即可。

这样我们发现每次枚举iii球赛制的话pospospos最小往后移动iii步,那么总的移动次数大概就是n1+n2+n3...nn=nlog⁡n\displaystyle \frac{n}{1}+\frac{n}{2}+\frac{n}{3}...\frac{n}{n}=n\log n1n+2n+3n...nn=nlogn

时间复杂度就是O(nlog⁡n)O(n\log n)O(nlogn)

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
const int N = 1e6 + 7;
ll n, m;
char s[N];
int cntw[N], cntl[N];
int posw[N << 1], posl[N << 1];int tiebreak[N];int solve() {n = read();scanf("%s", s + 1);ms(posw,0x3f);ms(posl,0x3f);for (int i = 1; i <= n; ++i) {cntw[i] = cntw[i - 1];cntl[i] = cntl[i - 1];if (s[i] == 'W') {++cntw[i];posw[cntw[i]] = i;}else {++cntl[i];posl[cntl[i]] = i;}}tiebreak[n - 1] = tiebreak[n] = n + 1; // 平局数组for (int i = n - 2; i >= 1; --i) {tiebreak[i] = s[i + 1] == s[i + 2] ? i + 2 : tiebreak[i + 2];}int res = 0, xs = 1;for (int i = 1; i <= n; ++i) {int l = 0, r = 0;int cnt = 0;while (l < n) {int W = posw[cntw[r] + i];int L = posl[cntl[r] + i];r = min(L, W);if (r > n)	break;if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {if (cntw[r] - cntw[l] > cntl[r] - cntl[l])++cnt;l = r;continue;}// 之前的r一定有人领先1分++r; // 要么平局 要么赢下if (r > n)	break;if (abs((cntw[r] - cntw[l]) - (cntl[r] - cntl[l])) >= 2) {if (cntw[r] - cntw[l] > cntl[r] - cntl[l])++cnt;l = r;continue;}r = tiebreak[r];if (r > n)	break;if (cntw[r] - cntw[l] > cntl[r] - cntl[l])++cnt;l = r;}res = (res + cnt * xs) % MOD;xs = xs * (n + 1) % MOD;}print(res);return 1;
}

D、Double Strings

题目大意

给你两个字符串A,BA,BA,B,长度在5⋅1035·10^35103级别,询问在两者的全部子序列中,长度相等,并且a<ba<ba<b的数量有多少个?

Solution

考点:相同子序列数量

如果直接考虑a<ba<ba<b,因为子序列并不知道第几个位置不同,所以这个并不好处理,但是我们一定可以把这个的子序列分成333段。

第一段:子序列前i−1i-1i1个字符都相同。

第二段:ai<bia_i<b_iai<bi

第三段:剩余长度任意挑选子序列。

先考虑如何求解任意两个位置A[1:i],B[1:j]A[1:i],B[1:j]A[1:i],B[1:j]相同子序列数量,这个用动态规划处理。

我们用fi,jf_{i,j}fi,j代表以AAAiii个字符,BBBjjj个字符的相同子序列数量,那么我们可以写出下面的转移方程。

fi,j=fi−1,j+fi,j−1−fi−1,j−1Ai≠Bjfi,j=fi−1,j+fi,j−1−fi−1,j−1+(fi−1,j−1+1)Ai=Bjf_{i,j} = f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1} \ \ \ \ \ \ \ A_i\neq B_j\\f_{i,j}=f_{i-1,j}+f_{i,j-1}-f_{i-1,j-1}+(f_{i-1,j-1}+1)\ \ \ \ \ \ \ \ A_i=B_jfi,j=fi1,j+fi,j1fi1,j1       Ai=Bjfi,j=fi1,j+fi,j1fi1,j1+(fi1,j1+1)        Ai=Bj

Ai≠BjA_i\neq B_jAi=Bj的时候减掉的是重复计算的,当Ai=BjA_i=B_jAi=Bj的时候加上的是一定选他们结尾的时候前面相同的,加上前面一个不选。

好了我们已经O(∣A∣⋅∣B∣)O(|A|·|B|)O(AB)预处理出了fi,jf_{i,j}fi,j数组了,下面就要考虑后面长度任选怎么处理。

如果我们枚举到AAA串后面还剩长度为xxxBBB串后面长度为yyy,那么等价与求∑i=0min⁡(x,y)Cxi∗Cyi\displaystyle \sum\limits_{i=0}^{\min(x,y)}C_x^i*C_y^ii=0min(x,y)CxiCyi

上面这个式子可以做个等价变换,首先我们知道Cxi=Cxx−iC_x^i=C_x^{x-i}Cxi=Cxxi,那么就变成了我有两堆球,我要在左边拿出x−ix-ixi个球,右边拿出iii个球的方案数总和,并且提供这个乘法之后求合我们可以判断这些球都是完全不一样的,那不就等价于我一共有x+yx+yx+y个球,要拿出xxx个球的方案数吗,所以我们得到∑i=0min⁡(x,y)Cxi∗Cyi=Cx+yx\displaystyle\sum_{i=0}^{\min(x,y)}C_x^i*C_y^i=C_{x+y}^xi=0min(x,y)CxiCyi=Cx+yx

接下来就只要计算答案就行了,总的时间复杂度是O(∣A∣⋅∣B∣)O(|A|·|B|)O(AB)

const int N = 5e3 + 7;
ll n, m;
int f[N][N];ll jc[N << 1], inv[N << 1];
void init() {jc[0] = 1;for (int i = 1; i < N * 2; ++i)	jc[i] = jc[i - 1] * i % MOD;inv[N * 2 - 1] = qpow(jc[N * 2 - 1], MOD - 2, MOD);for (int i = N * 2 - 2; ~i; --i)	inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m) {return jc[n] * inv[m] % MOD * inv[n - m] % MOD;
}char s[N], t[N];int solve() {scanf("%s", s + 1);scanf("%s", t + 1);n = strlen(s + 1), m = strlen(t + 1);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (s[i] == t[j]) {f[i][j] = (f[i - 1][j] + f[i][j - 1] + 1) % MOD;}else {f[i][j] = ((f[i - 1][j] + f[i][j - 1]) % MOD - f[i - 1][j - 1] + MOD) % MOD;}}}int res = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (s[i] < t[j]) {res = (res + (f[i - 1][j - 1] + 1) * C(n - i + m - j, n - i) % MOD) % MOD;}}}print(res);return 1;
}

F、Finding Points

题目大意

按逆时针给出凸包上的nnn个点,你要在凸包里面找到一个点PPP,让∠AiPAi+1\angle A_iPA_{i+1}AiPAi+1的最小值最大,然后输出这个最大的最小值。

Solution

考点:三分

比较明显的容易发现如果我们固定xxx,那么yyy的相关函数一定是一个单峰函数。

同理固定yyy,那么xxx的相关函数也一定是单峰函数。

那么就直接用三分套三分就可以求解了,复杂度O(nlog⁡32W)O(n\log_3^2 W)O(nlog32W)

const int INF = 0x3f3f3f3f;
const int N = 100 + 7;
const double PI = acos(-1);
ll n, m;
pai p[N];double xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;pai operator - (const pai& a, const pai& b) {return { a.first - b.first,a.second - b.second };
}double operator * (const pai& a, const pai& b) {return a.first * b.first + a.second * b.second;
}double getLen(pai a) {return sqrt(a * a);
}double getAngle(pai a, pai b) {return acos(a * b / getLen(a) / getLen(b));
}double check(pai x) {double res = INF;for (int i = 1; i <= n; ++i) {res = min(res, getAngle(p[i] - x, p[i + 1] - x));}return res;
}double calc(double x) {double l = ymin, r = ymax;for (int i = 1; i <= 100; ++i) {double lmid = l + (r - l) / 3.0;double rmid = r - (r - l) / 3.0;if (check({ x,lmid }) > check({ x,rmid })) {r = rmid;}else {l = lmid;}}return check({ x,l });
}int solve() {n = read();for (int i = 1; i <= n; ++i) {auto& [x, y] = p[i];x = read(), y = read();xmax = max(xmax, x);xmin = min(xmin, x);ymax = max(ymax, y);ymin = min(ymin, y);}p[n + 1] = p[1];double l = xmin, r = xmax;for (int i = 1; i <= 100; ++i) {double lmid = l + (r - l) / 3.0;double rmid = r - (r - l) / 3.0;if (calc(lmid) > calc(rmid)) {r = rmid;}else {l = lmid;}}printf("%.12f\n", calc(l) * 180 / PI);return 1;
}

G、Greater Integer, Better LCM

题目大意

给你a,b,ca,b,ca,b,c,你要让lcm(a+x,b+y)=clcm(a+x,b+y)=clcm(a+x,b+y)=c的前提下,最小的x+yx+yx+y是什么,并且给出的ccc是分解质因数的形式,c=∏piqic=\prod\limits p_i^{q_i}c=piqi

1≤a,b,c≤1032,∑i=1nqi≤181\le a,b,c\le 10^{32},\sum\limits_{i=1}^nq_i\le181a,b,c1032,i=1nqi18

Solution

考点:二进制枚举

看到这个ccc给的这么形式化,就要围绕这个去弄,而且幂次之和不超过181818,很明显的让我们去二进制枚举。

那么我们就可以暴力的dfsdfsdfs预处理出当前状态sss,可以的全部花费,那么要更新还有一个前提,就是之前的prodprodprod最起码应该大于aaa,才可以更新前半部分,大于bbb才可以更新后半部分,我们这样暴力乱搞之后对于花费大于a,ba,ba,b的全部状态的最小花费都可以找出来。

接下来我们只需要再把这些东西的子集更新一下,注意因为我们dfsdfsdfs乱搞的时候有一个≥a\ge aa的条件,可能001001001这个状态就无法大于等于aaa,这时候保留的仍然是一个无穷大的值,但是我们用001001001这个状态更新应该可以由111111111转移来的,所以我们要倒序的枚举一下子集,保证每个状态都找到最小值。

接下来去枚举这nnn个幂次,左右怎么分保证nnn个数都是111的最小值了。

找出这个最小值,再减掉a+ba+ba+b就是最终答案了。

#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
inline __int128 read() { __int128 s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())	s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(__int128 x, int op = 10) { if (!x) { putchar('0'); if (op)	putchar(op); return; }	char F[40]; __int128 tmp = x > 0 ? x : -x;	if (x < 0)putchar('-');	int cnt = 0;	while (tmp > 0) { F[cnt++] = tmp % 10 + '0';		tmp /= 10; }	while (cnt > 0)putchar(F[--cnt]);	if (op)	putchar(op); }
const int N = (1<<18) + 7;
int n, m;
int p[20], q[20];
__int128 fa[N], fb[N], a, b, c;void dfs(int dep, __int128 prod, int s) {if (dep == n) {if (prod >= a)	fa[s] = min(fa[s], prod);if (prod >= b)	fb[s] = min(fb[s], prod);return;}for (int i = 0; i <= q[dep]; ++i) {if (i == q[dep])	s |= (1 << dep);dfs(dep + 1, prod, s);prod *= p[dep];}
}int solve() {n = read();m = (1 << n) - 1;for (int i = 0; i < n; ++i) {p[i] = read(), q[i] = read();}a = read(), b = read(), c = 1;for (int i = 0; i < n; ++i) {for (int j = 0; j < q[i]; ++j)	c *= p[i];}__int128 inf = c * 2;ms(fa, 0x3f), ms(fb, 0x3f);dfs(0, 1, 0);for (int i = m; i >= 1; --i) {for (int j = 0; j < n; ++j) {if (i & (1 << j)) {fa[i ^ (1 << j)] = min(fa[i ^ (1 << j)], fa[i]);fb[i ^ (1 << j)] = min(fb[i ^ (1 << j)], fb[i]);}}}__int128 res = inf;for (int i = 0; i <= m; ++i) {res = min(res, fa[i] + fb[i ^ m]);}print(res - a - b);return 1;
}

H、Holding Two

题目大意

你要构造一个n⋅mn·mnm010101矩阵,保证同行同列同对角的333个位置不能是同一个字符。

Solution

考虑下面这样的构造

001100110011
110011001100
001100110011
110011001100
int solve() {int n = read(), m = read();for (int i = 0; i < n; ++i) {if (i & 1) {for (int j = 0; j < m; ++j) {char ch = j % 4 <= 1 ? '0' : '1';putchar(ch);}}else {for (int j = 0; j < m; ++j) {char ch = j % 4 <= 1 ? '1' : '0';putchar(ch);}}puts("");}return 1;
}

J、Jewels

题目大意

你有n(1≤n≤300)n(1\le n\le 300)n(1n300)个宝藏,他们分布在一些三维点(xi,yi,zi)(x_i,y_i,z_i)(xi,yi,zi),他们还有一个各自的上升速度tit_iti,他们第kkk秒所在的位置为(xi,yi,zi+k⋅ti)(x_i,y_i,z_i+k·t_i)(xi,yi,zi+kti)。你拿掉宝藏的代价为xi+yi+zi+k⋅tix_i+y_i+z_i+k·t_ixi+yi+zi+kti,你每秒只可以拿掉一个宝藏,问拿完nnn个宝藏的最小代价是多少?

Solution

考点:最小权值匹配

很明显每秒只可以拿掉一个宝藏,拿完nnn个宝藏一定要n−1n-1n1秒,那么我们把0→n−10\to n-10n1秒看成nnn个点,这nnn个物品也看成nnn个点,那么就变成了一张有完全图的二分图。跑最小权值匹配问题,可以用KMKMKM算法,我先用了下我自己的mcmfmcmfmcmf算法跑最小费用最大流给TTT飞了……枯了。然后就去听群友的建议抄了一个常数比较优秀的mcmf算法

封装的还是很好的,常数非常优秀只跑到400ms400ms400ms左右。

const int N = 600 + 7;
namespace atcoder {template <class Cap, class Cost> struct mcf_graph {public:mcf_graph() {}mcf_graph(int n) : _n(n), g(n) {}int add_edge(int from, int to, Cap cap, Cost cost) {assert(0 <= from && from < _n);assert(0 <= to && to < _n);int m = pos.size();pos.push_back({ from, g[from].size() });int from_id = g[from].size();int to_id = g[to].size();if (from == to) to_id++;g[from].push_back(_edge{ to, to_id, cap, cost });g[to].push_back(_edge{ from, from_id, 0, -cost });return m;}struct edge {int from, to;Cap cap, flow;Cost cost;};edge get_edge(int i) {int m = pos.size();assert(0 <= i && i < m);auto _e = g[pos[i].first][pos[i].second];auto _re = g[_e.to][_e.rev];return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,};}std::vector<edge> edges() {int m = pos.size();std::vector<edge> result(m);for (int i = 0; i < m; i++) {result[i] = get_edge(i);}return result;}std::pair<Cap, Cost> flow(int s, int t) {return flow(s, t, std::numeric_limits<Cap>::max());}std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {return slope(s, t, flow_limit).back();}std::vector<std::pair<Cap, Cost>> slope(int s, int t) {return slope(s, t, std::numeric_limits<Cap>::max());}std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {assert(0 <= s && s < _n);assert(0 <= t && t < _n);assert(s != t);std::vector<Cost> dual(_n, 0), dist(_n);std::vector<int> pv(_n), pe(_n);std::vector<bool> vis(_n);auto dual_ref = [&]() {std::fill(dist.begin(), dist.end(),std::numeric_limits<Cost>::max());std::fill(pv.begin(), pv.end(), -1);std::fill(pe.begin(), pe.end(), -1);std::fill(vis.begin(), vis.end(), false);struct Q {Cost key;int to;bool operator<(Q r) const { return key > r.key; }};std::priority_queue<Q> que;dist[s] = 0;que.push(Q{ 0, s });while (!que.empty()) {int v = que.top().to;que.pop();if (vis[v]) continue;vis[v] = true;if (v == t) break;for (int i = 0; i < g[v].size(); i++) {auto e = g[v][i];if (vis[e.to] || !e.cap) continue;Cost cost = e.cost - dual[e.to] + dual[v];if (dist[e.to] - dist[v] > cost) {dist[e.to] = dist[v] + cost;pv[e.to] = v;pe[e.to] = i;que.push(Q{ dist[e.to], e.to });}}}if (!vis[t]) {return false;}for (int v = 0; v < _n; v++) {if (!vis[v]) continue;dual[v] -= dist[t] - dist[v];}return true;};Cap flow = 0;Cost cost = 0, prev_cost_per_flow = -1;std::vector<std::pair<Cap, Cost>> result;result.push_back({ flow, cost });while (flow < flow_limit) {if (!dual_ref()) break;Cap c = flow_limit - flow;for (int v = t; v != s; v = pv[v]) {c = std::min(c, g[pv[v]][pe[v]].cap);}for (int v = t; v != s; v = pv[v]) {auto& e = g[pv[v]][pe[v]];e.cap -= c;g[v][e.rev].cap += c;}Cost d = -dual[s];flow += c;cost += c * d;if (prev_cost_per_flow == d) {result.pop_back();}result.push_back({ flow, cost });prev_cost_per_flow = d;}return result;}private:int _n;struct _edge {int to, rev;Cap cap;Cost cost;};std::vector<std::pair<int, int>> pos;std::vector<std::vector<_edge>> g;};}
using namespace atcoder;
mcf_graph<int64_t, int64_t> mc(N);int solve() {int n = read();int be = 0, ed = 2 * n + 2;long long res = 0;for (int i = 1; i <= n; ++i) {int x = read(), y = read(), z = read(), v = read();mc.add_edge(0, i, 1, 0);mc.add_edge(n + i, ed, 1, 0);res += x * x + y * y;long long dep = z;for (int j = 1; j <= n; ++j) {mc.add_edge(i, n + j, 1, dep * dep);dep += v;}}print(res + mc.flow(be, ed).second);return 1;
}

K、King of Range

题目大意

给你长度为n(1≤n≤105)n(1\le n\le 10^5)n(1n105)的序列aia_iai,并且有Q(1≤Q≤200)Q(1\le Q\le 200)Q(1Q200)次查询,每次查询给出一个k(1≤k≤109)k(1\le k\le 10^9)k(1k109),询问在aaa中有多少个区间的最大值减掉最小值严格大于kkk

Solution

考点:双指针+STSTST

考虑到区间不会修改,那么查找区间最值这个问题就用STSTST表维护就可以。

然后再看最大值减掉最小值严格大于kkk,如果在[i,r][i,r][i,r]这个区间符合要求,那么是不是在[r,n][r,n][r,n]这些右区间都是合法的,因为随着数的加入,区间最大值一定不会变小,区间最小值一定不会变大,所以并不会变得不符合要求。

那么我们从左到右枚举iii,可以看出这个rrr也是单调的,我们用STSTST表维护这个rrr就可以了。

时间复杂度O(n⋅m+nlog⁡n)O(n·m+n\log n)O(nm+nlogn)

const int N = 1e5 + 7;int st1[N][21], st2[N][21], Log2[N], a[N];void pre() {Log2[1] = 0;Log2[2] = 1;for (int i = 3; i < N; ++i)    Log2[i] = Log2[i >> 1] + 1;
}int queryMax(int l, int r) {int s = Log2[r - l + 1];return max(st1[l][s], st1[r - (1 << s) + 1][s]);
}int queryMin(int l, int r) {int s = Log2[r - l + 1];return min(st2[l][s], st2[r - (1 << s) + 1][s]);
}void sol() {pre();int n = read(), m = read();for (int i = 1; i <= n; ++i)   a[i] = st1[i][0] = st2[i][0] = read();int t = Log2[n]; //区间最长的2次方for (int j = 1; j <= t; ++j)for (int i = 1; i + (1 << j) - 1 <= n; ++i)st1[i][j] = max(st1[i][j - 1], st1[i + (1 << (j - 1))][j - 1]),st2[i][j] = min(st2[i][j - 1], st2[i + (1 << (j - 1))][j - 1]);while (m--) {int k = read();ll ans = 0;int r = 1;for (int i = 1; i <= n; ++i) {while (r <= n && queryMax(i, r) - queryMin(i, r) <= k)++r;if (r == n + 1)	break;//cout << r << endl;ans += n - r + 1;}print(ans);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-35112.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

MySQL数据库从小白到小菜04

MySQL数据库从小白到小菜04MySQL进阶补充插入聚合查询COUNTSUMAVGMAXMINGROUP BYHAVING联合查询内连接外连接MySQL进阶补充 插入 在表中插入数据时用的是INSERT&#xff0c;在MySQL中&#xff0c;是可以插入(查找结果表)的数据&#xff0c;但是结果表每一列的顺序类型都必须与…...

Linux高级存储管理

Linux高级存储管理1.lvm定义1.1 逻辑卷2.lvm的建立3.lvm的拉伸4. lvm缩减5.lvm快照6.lvm设备的删除7.管理vdo设备1.lvm定义 1.1 逻辑卷 逻辑卷主要适用于解决存储空间扩展问题&#xff0c;逻辑卷可以利用软件实现无限扩展。LVM可以实现把新的物理分区重组成物理卷&#xff0c…...

2021-06-11 VMware centos7 无线网络配置

一、虚拟机设置 VMware界面最上面&#xff0c;选择虚拟机->设置&#xff1a;将网络连接改为桥接模式&#xff0c;如下图所示&#xff1a; 二、查看主机DNS地址 winR 输入cmd&#xff0c;启动命令行界面&#xff0c;输入ipconfig/all&#xff0c;查看主机DNS服务器地址&#…...

Anime+Vue<svg画线动画>从安装到入门使用

1.安装Anime并全局使用 npm install animejs --saveimport anime from "animejs";2.在阿里巴巴矢量图标库复制&#xff08;或者下载&#xff09;svg到页面中,注意&#xff1a;画线动画svg图标stroke属性必须有颜色值。不然看到个毛线! <template> <div> …...

2021多校第二场F 简单计算几何模板(球体相交体积)

简单板子题题意代码题意 [原题链接](https://ac.nowcoder.com/acm/contest/11253/F) 大致题意&#xff1a; 有A&#xff0c;B&#xff0c;C&#xff0c;D四个点&#xff08;三维坐标&#xff09;和k1&#xff0c;k2两个常数 在空间上取一点P1使 |AP1|/|BP1|k1 &#xff08;所有…...

NoSQL NewSQL

OldSQLNewSQLNoSQL分类关系型关系型非关系型非关系型应用场景交易型&#xff1a;实时&#xff0c;面向应用&#xff0c;关注热数据交易型&#xff1a;实时&#xff0c;面向应用&#xff0c;关注热数据分析型&#xff1a;非实时&#xff0c;面向统计分析&#xff0c;关注全部数据…...

BUUCTF 逆向工程(reverse)之Java逆向解密

程序员小张不小心弄丢了加密文件用的秘钥&#xff0c;已知还好小张曾经编写了一个秘钥验证算法&#xff0c;聪明的你能帮小张找到秘钥吗&#xff1f; 注意&#xff1a;得到的 flag 请包上 flag{} 提交 下载好题目后&#xff0c;发现它是个以.class为后缀的。所以用JD-GUI打开这…...

用 Python 进行游戏开发

1. pgzero python在各个领域都有着丰富的第三方库,pygame是python在游戏领域的应用库,可以用来开发各种不同的游戏。但是对于初学者来说,还是存在一定的门槛。 而今天要和大家分享的pgzero(pygame zero)是在pygame基础上做了进一步的封装,使得设计一款游戏十分的方便,…...

C语言之重定向和文件(更新中)

一、C程序中要包含stdio.h头文件才可以直接使用putchar()、getchar()函数、printf()函数&#xff0c;scanf()函数&#xff0c;它们都是C语言标准I/O包的成员。 二、ANSI C 和后续的C标准都规定输入是缓冲的。缓冲区的大小取决于系统&#xff0c;常见大小512字节和4096字节。 缓…...

开发手札:git日常抽风记录

今天一大早代码提交不上github&#xff0c;各种方法解决不了&#xff0c;虽然最终不知道是否根治解决了&#xff0c;但是起码目前没问题&#xff0c;所以记录一下。 今天来公司三台开发机&#xff08;两台window、一台macos&#xff09;全部ssh connect timeout errorcode 22或…...

链表 + 数组模拟链表

链表的指针实现 1.指针 #include<iostream> using namespace std; int main(){int a 5;int *p; // int 型的指针double *q; //double 型的指针p &a;// cout << p 指向 acout << *p << endl; //间接输出 areturn 0; }2.申请动态内存&#xff08…...

第一次动手构建 Linux 内核(未完待续)

目录背景机器参数参考链接操作流程步骤1&#xff1a;下载 Linux 内核源码步骤 2&#xff1a;解压源码步骤 3&#xff1a;下载所需软件包步骤 4&#xff1a;内核配置步骤 5&#xff1a;开始构建&#xff01;未完待续背景 这两天读《UNIX传奇&#xff1a;历史与回忆》这本书&…...

Spring学习:工厂方法创建 Bean

目录通过调用静态工厂方法创建 Bean通过调用实例工厂方法创建 Bean通过调用静态工厂方法创建 Bean 调用静态工厂方法创建 Bean是将对象创建的过程封装到静态方法中。当客户端需要对象时, 只需要简单地调用静态方法, 而不同关心创建对象的细节。 要声明通过静态方法创建的 Bean:…...

运行时数据区-虚拟机栈

文章目录谈谈你对虚拟机栈的理解栈帧什么是栈帧&#xff08;Stack Frame)当前栈帧栈帧的内部结构局部变量表Slot操作数栈Operand Stack动态链接方法返回地址一些附加信息虚方法和非虚方法方法的调用&#xff1a;虚方法表面试题方法中定义的局部变量是否线程安全&#xff1f;运行…...

常见运维问题(打印机、重装系统、IE)

连接打印机与驱动安装 制作U盘系统盘 新系统没有网卡时离线驱动安装 IE浏览器安全级别设置 IP地址的查询 处理操作来源于网络资源&#xff08;尊重原创&#xff09;&#xff1a;原创博客链接...

活动目录备份和灾难恢复之自动备份与授权还原

前言 由于服务器系统状态总在变化&#xff0c;因该增加对系统状态备份的频率&#xff0c;来减少备份对服务器工作环境的影响&#xff0c;所以最好是每天晚上对服务器系统状态进行备份&#xff0c;但是单独使用wbadmin命令无法创建系统状态的自动备份计划&#xff0c;此时可以使…...

TCP“三次挥断”的原因TCP延迟确认机制

在学习wireshark抓包的时候&#xff0c;一般都从最简单的三次握手和四次挥断看起&#xff0c;因为这两步对于每一个完整健康的TCP交互流来说都是必不可少的&#xff0c;通过抓包我们可以更清楚的了解其工作机制。 一、四次挥断和“三次挥断” 1、第一种情况 比如在电脑cmd发…...

2021年Java开发爆款推荐!docker部署tomcat

一.java基础面试知识点 java中和equals和hashCode的区别 int、char、long各占多少字节数 int与integer的区别 探探对java多态的理解 String、StringBuffer、StringBuilder区别 什么是内部类&#xff1f;内部类的作用 抽象类和接口区别 抽象类的意义 抽象类与接口的应用…...

阿里P8大牛亲自讲解!java静态变量和实例变量

Redis主从复制 概念 Redis的主从复制概念和MySQL的主从复制大概类似。一台主机master&#xff0c;一台从机slaver。master主机数据更新后根据配置和策略&#xff0c;自动同步到slaver从机&#xff0c;Master以写为主&#xff0c;Slave以读为主。 主要用途 读写分离&#xff1…...

Angular中NgOnInit和Constructor方法之间的主要区别

参考链接&#xff1a;https://chudovo.com/main-differences-between-ngoninit-and-constructor-methods-in-angular/...

剑指 Offer 11. 旋转数组的最小数字

class Solution:def minArray(self, numbers: List[int]) -> int:left 0right len(numbers) - 1while left < right:# 取中点mid left (right - left) // 2# 如果 numbers[mid] > numbers[right] ,分界点落在 (mid, right]if numbers[mid] > numbers[right]:le…...

python视频操作——python实现将视频分解为图片序列

python将视频分解为图片序列 内容参考自博客~ 详细实现代码如下&#xff1a; import cv2# 读取视频&#xff0c;方法是来自cv2库的VideoCapture cap cv2.VideoCapture("C:/Users/xxx/Desktop/sweet.mp4") # 计数 i 0 # 循环判断视频是否打开 while cap.isOpened…...

Kubernetes解决了Docker使用中的哪些问题?

Kubernetes解决了Docker使用中的哪些问题&#xff1f;参考文章&#xff1a; &#xff08;1&#xff09;Kubernetes解决了Docker使用中的哪些问题&#xff1f; &#xff08;2&#xff09;https://www.cnblogs.com/jiangshanhot/p/10414196.html 备忘一下。...

jquery--动画效果

show() : 显示隐藏的匹配元素。 这个就是 show( speed, [callback] ) 无动画的版本。如果选择的元素是可见的&#xff0c;这个方法将不会改变任何东西。无论这个元素是通过hide()方法隐藏的还是在CSS里设置了display:none;&#xff0c;这个方法都将有效。 hide()&#xff1a…...

leetcode刷题笔记 322.零钱兑换【中等】

1、广度优先搜索 int coinChange(vector<int>& coins, int amount) {if (amount 0)return 0;int n coins.size();vector<int> flags(amount);queue<int> q;q.push(amount);int count 0;while (!q.empty()) {count;int s q.size();for (int i 0; i …...

HMS Core助力同程旅行,打造更贴心的用户出行体验

作为中国在线旅行行业的创新者&#xff0c;同程旅行聚焦年轻、时尚、个性的消费群体&#xff0c;致力于为用户提供更便捷、聪明、安全的出行服务。近年来&#xff0c;同程旅行通过人工智能等创新科技的应用将平台原本的交易撮合角色转变为“管家”和“助手”的角色&#xff0c;…...

移动端开发

移动端应用 H5 移动端页面App小程序 移动端开发方式 原生开发&#xff08;Native App&#xff09;网页开发&#xff08;Web App&#xff09;混合开发&#xff08;Hybrid App&#xff09;跨平台移动端框架 跨 App 平台&#xff1a;React Native、weex、Flutter跨 App、小程序、…...

海大09-10.3题:编程计算并输出1*2+3*4+5*6+...+(n-1)*n的值,其中,n的值由键盘输入。(8分)

题目 本题是中国海洋大学《C语言程序设计》2009-2010年第一学期编程题第3题。 题目&#xff1a; 编程计算并输出12345*6…&#xff08;n-1&#xff09;*n的值&#xff0c;其中&#xff0c;n的值由键盘输入。&#xff08;8分&#xff09; 以下是本篇文章正文内容&#xff0c;欢…...

Angular中NgOnInit和Constructor方法之间的主要区别

参考链接&#xff1a;https://chudovo.com/main-differences-between-ngoninit-and-constructor-methods-in-angular/...

项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法

项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法参考文章&#xff1a; &#xff08;1&#xff09;项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法 &#xff08;2&#xff09;https://www.cnblogs.com/itrena/p/59271…...

dbc2000 注册机|dbc2000 注册码注册机下载

点击下载来源&#xff1a;dbc2000 注册机 dbc2000 注册机是同名源程序软件的注册机软件&#xff0c;该源程序软件是一款应用于数据库搭建以及数据写入的数据库架设工具&#xff0c;它拥有强大的数据写入功能&#xff0c;在作为应用程序使用时&#xff0c;它不仅可以充当数据属性…...

秋招面经第八弹:网易二面-数据开发工程师

秋招第八弹&#xff1a;网易二面-数据开发工程师 写在最前&#xff1a;秋招以来一直在冲&#xff0c;因为事情比较多&#xff0c;对于笔试面试一直没有复盘&#xff0c;现在靠仅存的记忆把面试的一些问题记录下来&#xff0c;尽可能记录出能回忆到的问题&#xff0c;但可能记的…...

安卓课程格子APP

https://download.csdn.net/download/weixin_57836618/73810452 功能演示&#xff1a; 查看所有课程 点击主页面空白处即可添加课程 添加课程之后查看课程 查看双周课程 查看单周课程 6.查看课程详情...

强化学习——格子世界

强化学习——格子世界 项目源码地址&#xff1a;https://gitee.com/infiniteStars/machine-learning-experiment 1. 实验内容 2. 实验代码 import numpy as np import matplotlib.pyplot as plt from matplotlib.table import Table from xml.dom.minidom import Document #手…...

华为机试 - 跳格子游戏

目录 题目描述 输入描述 输出描述 用例 题目解析 算法源码 题目描述 地上共有N个格子&#xff0c;你需要跳完地上所有的格子&#xff0c;但是格子间是有强依赖关系的&#xff0c;跳完前一个格子后&#xff0c;后续的格子才会被开启&#xff0c;格子间的依赖关系由多组st…...

php 爬课程表信息,Ruby爬取教务系统生成课程表

我为什么要虐自己最近觉得课程格子广告越来越多&#xff0c;乱七八糟的东西越来越多&#xff0c;完全失去了一开始的存在价值&#xff0c;并且没有电脑端app&#xff0c;想查看课程必须拿出手机&#xff0c;而我使用电脑频率要比手机高&#xff0c;所以才有了折腾的动力。于是我…...

android 课程表 ui,UICollectionViewLayout实现课程表布局

因为项目中有课程表的相关模块&#xff0c;第一时间想到用UICollectionView。然而后期的需求越来越复杂&#xff0c;每个格子需要展示的内容越来越多&#xff0c;所以不得不寻找合适的解决方案。最后发现自定义UICollectionViewLayout可以实现我的需求。先放效果图&#xff1a;…...

Android自定义View课程表,Android 自定义View课程表表格

自己闲下来时间写的一个课表控件使用的自定义LinearLayout 里面View都是用代码实现的 最终效果如下图 写的可能有问题希望多多指点创建一个自定义LinearLayout 控件用来装载课程的信息和课程的周数 和节数大概的布局三这样的根据上面的看来觉得总体布局我分了两个 上面的星期是…...

java课程设计设计_java课程设计

1. 团队课程设计博客链接https://www.cnblogs.com/choco1ate/p/12172223.html2.本组课题及本人任务本组课题&#xff1a;泡泡堂(炸弹人)游戏本人任务&#xff1a;Box类(游戏地图中的每个方格)Bomb类(游戏过程中的)游戏玩家输赢信息的文件储存3.需求分析Box类&#xff1a;该类为…...

《课程格子》的一个笔试题目

题目如下&#xff0c;感觉很适合喜欢琢磨的程序员&#xff0c;也是考验你编码风格的时候。 Lets make a tower defense game&#xff08;塔防游戏):1. You have 1 tower, with H health and D dps(damage per second).2. There are n attackers, each with h_i health and d_i …...

Android仿照超级课程表 or 课程格子 一键提取课表功能(方正系统)

参考文章http://blog.csdn.net/sbsujjbcy ,本文仿照‘ 安卓弟 提供的android 项目实战——打造超级课程表一键提取课表功能文章&#xff0c;对他的代码进行了修改和补充&#xff0c;为什么要修改呢&#xff1f;原因是安卓弟的那个源码版本过于老旧&#xff0c;很多方法已经过…...

Go语言原子操作

一. 原子操作 什么是原子操作呢&#xff1f;原子操作就是具备原子性的操作&#xff0c;一个或者多个操作在cpu的执行过程中不被中断的特性&#xff0c;称为原子性&#xff0c;这些操作对外表现为一个不可分割的整体&#xff0c;要么全部执行&#xff0c;要么全部不执行&#x…...

处理器如何实现原子操作

处理器如何实现原子操作一、并发和并行概念二、单核原子操作解决方法三、多核原子操作总线锁方式缓存锁方式&#xff08;缓存一致性&#xff09;存储器结构多核cpu的存储关系缓存一致性MESI协议CAS一、并发和并行概念 原子&#xff08;atomic&#xff09;&#xff1a;是“不能…...

go 原子操作 atomic

1. 什么是原子操作 我们已经知道&#xff0c;原子操作即是进行过程中不能被中断的操作。也就是说&#xff0c;针对某个值的原子操作在被进行的过程当中&#xff0c;CPU绝不会再去进行其它的针对该值的操作。无论这些其它的操作是否为原子操作都会是这样。为了实现这样的严谨性&…...

JAVA操作REDIS执行原子操作

JAVA操作REDIS执行原子操作JAVA操作REDIS执行原子操作为什么要使用原子操作JAVA操作REDIS执行原子操作 为什么要使用原子操作 众所周知&#xff0c;redis 作为数据库的前置库&#xff0c;给数据库使用节省了很多请求&#xff0c;很多请求再查询缓存后就可以直接返回需要的数据…...

原子操作底层实现与上层应用

什么是原子操作 所谓原子操作,就是“不可中断的一个或一系列操作”。 原子操作的目的:保护资源。 这里的“中断”并不翻译成操作被中断停止执行,更确切地应该指在执行的整个过程中,对所用到的资源是独占的。 单核系统的原子操作 在单核CPU中,能够在一条指令(机器指令…...

Linux 内核同步(一):原子操作

原子操作 原子操作&#xff0c;指的是一段不可打断的执行。也就是你不可分割的操作。 在 Linux 上提供了原子操作的结构&#xff0c;atomic_t &#xff1a; typedef struct {int counter; } atomic_t; 把整型原子操作定义为结构体&#xff0c;让原子函数只接收atomic_t类型的…...

操作系统之原子操作

原子操作是指不会被线程调度机制打断的操作&#xff1b;原子操作(atomic operation)是不需要同步&#xff08;synchronized&#xff09; 这种操作一旦开始&#xff0c;就一直运行到结束&#xff0c;中间不会有任何线程切换。 定义 如果这个操作所处的层(layer)的更高层不能发…...

原子操作 - linux内核锁(一)

“原子”是不可分割的意思&#xff0c;原子操作是指一个实际运行的操作不可分割&#xff0c;这个运行必然会被执行并完成而不会被另外一个任务或者事件打断。也就说&#xff0c;它是最小的执行单位&#xff0c;不可能有比它更小的执行单位。linux原子操作的问题来源于中断、进程…...

原子操作类AtomicInteger详解

为什么需要AtomicInteger原子操作类&#xff1f; 对于Java中的运算操作&#xff0c;例如自增或自减&#xff0c;若没有进行额外的同步操作&#xff0c;在多线程环境下就是线程不安全的。num解析为numnum1&#xff0c;明显&#xff0c;这个操作不具备原子性&#xff0c;多线程并…...