2024年西安铁一中集训DAY1---- 杂题选讲

文章目录

    • 牛客练习赛125 E 联谊活动(枚举,分讨)
    • 牛客练习赛125 F 玻璃弹珠(类莫队,离线询问,数据结构)
    • 2024ccpc长春邀请赛 D Parallel Lines(随机化)
    • 2024ccpc长春邀请赛 E Connected Components(单调栈)
    • 2024ccpc长春邀请赛 B Dfs Order 0.5(动态规划)
    • 2024 CCPC东北邀请赛 H. Meet(二分答案,树上公共祖先,树上差分)
    • 2024 CCPC东北邀请赛 I. Password(动态规划)
    • 2024 CCPC东北邀请赛 K. Tasks(贪心,构造)
    • 2024 CCPC东北邀请赛 L. Bracket Generation(组合数学,数数)
    • 2024 CCPC东北邀请赛 G. Diamond(根号分治)

牛客练习赛125 E 联谊活动(枚举,分讨)

          题面:
在这里插入图片描述

题目

分析:

在这里插入图片描述
          发现选用距离矩形越近的关键点答案会越优。注意到 x , y x,y x,y 的取值范围很小,我们对于每一个位置处理出 在它所在的行中,离它最近的左边 / 右边 的关键点,然后每次询问可以扫描 S x ∼ E x S_x \sim E_x SxEx 行,设当前行是 l i n e line line,查询 ( l i n e , S y ) (line, S_y) (line,Sy) 这个位置左右最近的关键点,分别拿这两个关键点去更新答案即可。时间复杂度 O ( m × x + x × y ) O(m\times x + x \times y) O(m×x+x×y)
CODE:

#include<bits/stdc++.h>
using namespace std;
const int M = 1100;
const int N = 1e5 + 10;
int n, m, sx, sy, ex, ey, px[N], py[N];
int Left[M][M], Right[M][M];
bool f[M][M];
void pre_work() {memset(Left, -1, sizeof Left);memset(Right, -1, sizeof Right);for(int i = 1; i <= 1000; i ++ ) {int now = -1;for(int j = 1; j <= 1000; j ++ ) {if(f[i][j]) now = max(now, j);Left[i][j] = now;}now = 1001;for(int j = 1000; j >= 1; j -- ) {if(f[i][j]) now = min(now, j);Right[i][j] = (now == 1001 ? -1 : now);}}
}
int solve(int sx, int sy, int ex, int ey) {int res = 1e9, c = abs(sx - ex) + abs(sy - ey);for(int i = 1; i <= 1000; i ++ ) { // 扫描每一层 if(i < min(sx, ex)) {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (min(sx, ex) - i) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (min(sx, ex) - i) + c);else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (min(sx, ex) - i) + c);}}else if(i >= min(sx, ex) && i <= max(sx, ex)) {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) {res = min(res, c);break;}else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + c);}}else {int tx = i, ty = min(sy, ey);if(Left[tx][ty] != -1) res = min(res, 2 * (min(sy, ey) - Left[tx][ty]) + 2 * (i - max(sx, ex)) + c);if(Right[tx][ty] != -1) {if(Right[tx][ty] <= max(sy, ey)) res = min(res, 2 * (i - max(sx, ex)) + c);else res = min(res, 2 * (Right[tx][ty] - max(sy, ey)) + 2 * (i - max(sx, ex)) + c);}			}}return res;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &px[i], &py[i]);f[px[i]][py[i]] = 1;}pre_work();for(int i = 1; i <= m; i ++ ) {scanf("%d%d%d%d", &sx, &sy, &ex, &ey);printf("%d\n", solve(sx, sy, ex, ey));}return 0;
}

牛客练习赛125 F 玻璃弹珠(类莫队,离线询问,数据结构)

          题面:
在这里插入图片描述

题目

分析:
          在线处理很难在允许的时间复杂度内通过,我们考虑 离线:发现题目上给的 区间不相交 这一条性质,启示我们像莫队一样通过两个 指针 来不断更新当前维护区间的信息。具体来讲:设 l t lt lt r t rt rt 分别是当前区间的左右端点。将查询区间离线后按照左端点排序,通过指针的逐步跳转实现维护区间的改变。由于指针 只会向后跳,因此最多跳 n n n 次,这一部分复杂度是 O ( n ) O(n) O(n) 的。我们考虑怎样维护当前区间的信息:一个操作 1 1 1 显然会在它的左端点第一次被用到,在它的右端点处作用消失。因此我们将每一个操作 1 1 1 的信息分别存进区间的做右端点内。左端点处为 添加 信息,当 r t rt rt 经过左端点时将这个信息加入数据结构中。右端点处为 删除 信息,当 l t lt lt 经过右端点时将信息从数据结构中删除。这样就解决了 位置 这一偏序。每条信息形如 某种颜色 c c c 在时间 t t t 时出现。由于 只有最小的 t t t 有用,添加时我们把 t t t 插入 c c c 对应的 s e t set set 里, 删除时把它从 s e t set set 里删掉。然后在 以时间为下标的树状数组 里更新不同最早时间出现的颜色数量。查询时查找 小于当前查询区间时间的前缀和 即可。
时间复杂度: O ( m l o g 2 m ) O(mlog_2m) O(mlog2m)

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair< int, int > PII;
const int N = 5e5 + 10;
int n, m, op, l, r, col, tot;
struct BIT {int c[N];int lowbit(int x) {return x & -x;}void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}int ask(int x) {int res = 0;for(; x; x -= lowbit(x)) res += c[x];return res;}
}t;
vector< PII > A[N], D[N];
set< int > tc[N]; // 维护当前区间所有涉及的加颜色操作所带来的每种颜色的时间戳
struct range {int l, r, tim, ans;
}q[N];
bool cmp(range x, range y) {return x.l < y.l;
}
void add(int x) {for(auto v : A[x]) {int col = v.first, tim = v.second;if(!tc[col].empty()) {auto it = tc[col].begin();int Tim = (*it); t.add(Tim, -1);}tc[col].insert(tim);auto it = tc[col].begin();int T = (*it);t.add(T, 1);} 
}
void del(int x) {for(auto v : D[x]) {int col = v.first, tim = v.second;if(!tc[col].empty()) {auto it = tc[col].begin();int Tim = (*it);t.add(Tim, -1);}tc[col].erase(tim);if(!tc[col].empty()) {auto It = tc[col].begin();int Gm = (*It);t.add(Gm, 1);}}
}
bool cmp2(range x, range y) {return x.tim < y.tim;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++ ) {scanf("%d", &op);if(op == 1) {scanf("%d%d%d", &l, &r, &col);A[l].pb(make_pair(col, i));D[r].pb(make_pair(col, i));}else {scanf("%d%d", &l, &r);q[++ tot] = (range) {l, r, i};}}sort(q + 1, q + tot + 1, cmp);int lt = 1, rt = 0;for(int i = 1; i <= tot; i ++ ) {while(rt < q[i].r) {++ rt; add(rt);}while(lt < q[i].l) {del(lt); lt ++;}q[i].ans = t.ask(q[i].tim);}sort(q + 1, q + tot + 1, cmp2);for(int i = 1; i <= tot; i ++ ) {printf("%d\n", q[i].ans);}return 0;
}

启示:遇到存在 时间位置 两种限制的询问和修改,可考虑如果修改可以离线(与在线状态无关)。那么可以将操作离线,按照位置进行 双指针 或者 莫队 跳动,在满足位置限制的同时用 数据结构 来维护时间限制。

2024ccpc长春邀请赛 D Parallel Lines(随机化)

在这里插入图片描述

          题目

          分析:考虑如果我们求出一个 斜率,如何检验这个斜率是否正确。一个很好的思路是对每个点算出在这个斜率下经过该点的直线的纵截距,然后判断是否有 k k k 个不同的纵截距以及每个纵截距是否对应大于等于 2 2 2 个不同的点即可。时间复杂度 O ( n ) O(n) O(n)。如果枚举两个点去算斜率,那么时间复杂度为 O ( n 2 ) O(n^2) O(n2),显然不能接受。我们发现平行线的数量很少,意味着有较多的点在同一条直线上。直接随机出两个点算斜率并判断是否合法。可以证明随机出合法点对的最小概率为 O ( 1 k ) O(\frac{1}{k}) O(k1)。所以可以在 O ( k ) O(k) O(k) 次随机出合法的点对,总时间复杂度为 O ( n × k ) O(n \times k) O(n×k)

在这里插入图片描述

CODE:

#include<bits/stdc++.h>// 随机化 
#define pb push_back
using namespace std;
const int N = 1e4 + 10;
const int K = 51;
typedef double db;
int n, k, tot, cnt[N];
db X[N], Y[N];
const db INF = 1e18;
map< db, int > mp;
vector< int > node[N];
int random(int n) {return ((unsigned long long)rand() * rand() % n);
}
db B(int p, int q, db x, db y) {if(X[p] == X[q]) return x;else return (X[q] - X[p]) * y - (Y[q] - Y[p]) * x;
}
bool check(int p, int q) {tot = 0; memset(cnt, 0, sizeof cnt);for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);if(!mp[b]) mp[b] = ++ tot;cnt[mp[b]] ++;}bool f = 1;for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);if(cnt[mp[b]] == 1) {f = 0; break;}}if(tot == k && f) {for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);node[mp[b]].pb(i);}return 1;}for(int i = 1; i <= n; i ++ ) {db b = B(p, q, X[i], Y[i]);mp[b] = 0;}return 0;
}
int main() {srand(time(0));scanf("%d%d", &n, &k);for(int i = 1; i <= n; i ++ ) {scanf("%lf%lf", &X[i], &Y[i]);} while(true) {int i = random(n) + 1, j = random(n) + 1;if(i == j) continue;else if(check(i, j)) {for(int i = 1; i <= tot; i ++ ) {printf("%d", node[i].size());for(int j = 0; j < node[i].size(); j ++ ) printf(" %d", node[i][j]);puts("");}break;}}return 0;
}

2024ccpc长春邀请赛 E Connected Components(单调栈)

在这里插入图片描述
题目

          分析:
          不难想到将式子移项,将只含 i i i 的放一起,将只含 j j j 的放一起。我们可以得到 i i i j j j 之间有连边,当且仅当:

a i − i ≤ a j − j , b i − i ≥ b j − j a_i -i \leq a_j - j,b_i - i \geq b_j - j aiiajjbiibjj 或者 a i − i ≥ a j − j , b i − i ≤ b j − j a_i - i \geq a_j - j,b_i - i \leq b_j - j aiiajjbiibjj 。这两个式子可以看作 j j j i i i 连边 或 i i i j j j 连边。我们令 x i = a i − i x_i = a_i - i xi=aii y i = b i − i y_i = b_i - i yi=bii,那么 i i i j j j 连边的条件就是 x i ≥ x j , y i ≤ y j x_i \geq x_j,y_i \leq y_j xixjyiyj。将元素按照 x x x 从小到大排序,那么每种元素只可能往前边连边。我们使用 单调栈 维护 y y y。从前往后往栈里加入元素,那么只有 y i y_i yi 小于栈顶元素的 y y y i i i 才能往栈顶元素所在连通块连边。我们考虑此时将栈顶元素弹出,然后接着比较直到 y i y_i yi 大于栈顶元素的 y y y。接下来存在一个问题:由于栈顶元素的 y y y 越大越容易连边,而我们刚把 y y y 元素较大的栈顶元素弹出,此时 i i i 一定与刚刚弹出的栈顶元素在同一个连通块中,如果仅仅把 i i i 放进栈中,那么后面的元素就有可能没有连上原来和这个连通块的边。想到一个连通块的 y y y 只有最大的有用,因此我们每次拿 y i y_i yi 和栈顶元素所在联通块的的最大 y y y 比较来判断是否连边就不会错。注意连边的时候更新连通块的最大 y y y 值。
时间复杂度 O ( n ) O(n) O(n)

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, sz[N], bin[N], mh[N], p, q;
struct element {int x, y;
}a[N];
bool cmp(element u, element v) {return ((u.x < v.x) || (u.x == v.x && u.y > v.y));
}
stack< int > s;
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
void Merge(int x, int y) {int f1 = Find(x), f2 = Find(y);bin[f2] = f1; sz[f1] += sz[f2];mh[f1] = max(mh[f2], mh[f1]);
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &p, &q);a[i].x = p - i;a[i].y = q - i;}sort(a + 1, a + n + 1, cmp);for(int i = 1; i <= n; i ++ ) {bin[i] = i; sz[i] = 1;mh[i] = a[i].y;}for(int i = 1; i <= n; i ++ ) {while(!s.empty() && a[i].y <= mh[Find(s.top())]) {Merge(i, s.top());s.pop();}s.push(i);}int cnt = 0;for(int i = 1; i <= n; i ++ ) {if(Find(i) == i) cnt ++;}cout << cnt << endl;return 0;
}

2024ccpc长春邀请赛 B Dfs Order 0.5(动态规划)

在这里插入图片描述
题目

          分析:
          为了方便,我们把子树大小为 偶数 的点称作 偶点奇数 的点称作 奇点偶儿子奇儿子 的称呼类似。
          容易想到状态定义 d p i , 0 / 1 dp_{i,0/1} dpi,0/1 表示 i i i 点的 d f n dfn dfn 序为偶数/奇数时, 以 i i i 为根的子树的最大权值和。考虑转移,分两类情况:

  1. 存在 奇儿子:那么每个偶儿子可以选 0 / 1 0/1 0/1 中较大的。设点 i i i 的状态为 t t t,奇儿子的数量为 m m m,那么显然有 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil 2m 个奇儿子需要选 t ⊕ 1 t \oplus 1 t1,另外的选 t t t。那么只需要将所有 d p s o n , t ⊕ 1 − d p s o n , t dp_{son,t \oplus 1} - dp_{son, t} dpson,t1dpson,t 拿出来从大到小排序,选出前 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil 2m 大,并把所有 d p s o n , t dp_{son, t} dpson,t 累加即可。
  2. 不存在 奇儿子:那么所有儿子的状态都只能是 t ⊕ 1 t \oplus 1 t1,加起来就好了。

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 10; 
typedef long long LL;
int n, T, u, v, sz[N];
LL a[N], dp[N][2];
vector< int > E[N];
bool cmp(LL x, LL y) {return x > y;
}
void dfs(int x, int fa) {sz[x] = 1;if(E[x].empty()) {dp[x][0] = a[x];dp[x][1] = 0;return ;}bool flag = 0;for(auto v : E[x]) {if(v == fa) continue;dfs(v, x); sz[x] += sz[v];if(sz[v] & 1) flag = 1;}if(flag) { // 存在奇点   所有偶点取较大 LL tmp = 0, tg = 0, th = 0;int cnt = 0;vector< LL > g, h;for(auto v : E[x]) {if(v == fa) continue;if(sz[v] & 1) {g.pb(dp[v][0] - dp[v][1]);tg += dp[v][1];h.pb(dp[v][1] - dp[v][0]);th += dp[v][0];cnt ++;}else tmp += max(dp[v][0], dp[v][1]);}sort(g.begin(), g.end(), cmp);sort(h.begin(), h.end(), cmp);LL c = 0;for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += h[i - 1];dp[x][0] = tmp + th + c + a[x];c = 0;for(int i = 1; i <= ((cnt & 1) ? (cnt + 1) / 2 : cnt / 2); i ++ ) c += g[i - 1];dp[x][1] = tmp + tg + c;}else {dp[x][0] = dp[x][1] = 0;dp[x][0] += a[x];for(auto v : E[x]) {if(v == fa) continue;dp[x][0] += dp[v][1];dp[x][1] += dp[v][0];}}
}
void solve() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);for(int i = 1; i <= n; i ++ ) dp[i][0] = dp[i][1] = 0;	for(int i = 1; i <= n; i ++ ) {vector< int > tmp; swap(tmp, E[i]);}for(int i = 1; i < n; i ++ ) {scanf("%d%d", &u, &v);E[u].pb(v); E[v].pb(u);}dfs(1, 0);printf("%lld\n", dp[1][1]);
}
int main() {scanf("%d", &T);while(T -- ) {solve();}return 0;
}

2024 CCPC东北邀请赛 H. Meet(二分答案,树上公共祖先,树上差分)

在这里插入图片描述

题目

          分析:
          直接求解最优答案显然不好搞,我们发现答案越大越容易满足,因此具有单调性,可以二分答案。设 x x x 为二分的答案,考虑怎样检验:
在这里插入图片描述
          实际上这个问题等价于是否至少存在一个点 p p p,使得 p p p 作为根时所有点对到它们 l c a lca lca 的距离都小于 x x x

          由于 u , v u,v uv l c a lca lca 一定在它们的路径上,我们考虑选取不同点作为根时 u , v u,v uv l c a lca lca 有什么规律。

          如果以红色点为树根,那么 u , v u,v u,v l c a lca lca 就是 u − v u - v uv 路径上红色点的祖先。也就是说:如果我们首先以任意一个点为根,那么检验时选取作为根的点在 u − v u-v uv路径上哪个点的子树中,那个点就是真正的 l c a lca lca。如果选取的点在子树外,那么当前的 l c a lca lca 就是真正的 l c a lca lca

          对于二分出的答案 x x x,我们可以对于点对中的每个点算出 路径上那些点可以作为 l c a lca lca。那么这些点子树中的点都可以作为选定根。我们把包含这些点的最小子树加 1 1 1,最后判断上是否有点的权值等于 2 × m 2 \times m 2×m 即可。

时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

CODE:

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
inline int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int n, m, u, v, pu[N], pv[N], dfn[N], fat[N][25], dep[N], rk;
int L[N], R[N];
vector< int > E[N];
struct BIT {int c[N];void Clean() {memset(c, 0, sizeof c);}int lowbit(int x) {return x & -x;}void add(int x, int y) {for(; x < N; x += lowbit(x)) c[x] += y;}int ask(int x) {int res = 0;for(; x; x -= lowbit(x)) res += c[x];return res;}
}t;
void dfs0(int x, int fa) {dfn[x] = ++ rk; dep[x] = dep[fa] + 1;fat[x][0] = fa; L[x] = rk;for(int i = 1; i <= 20; i ++ ) fat[x][i] = fat[fat[x][i - 1]][i - 1];for(auto v : E[x]) {if(v == fa) continue;dfs0(v, x);} R[x] = rk;
}
int LCA(int x, int y) {if(dep[x] < dep[y]) swap(x, y);for(int i = 20; i >= 0; i -- ) {if(dep[fat[x][i]] >= dep[y]) x = fat[x][i];}if(x == y) return x;for(int i = 20; i >= 0; i -- ) {if(fat[x][i] != fat[y][i]) x = fat[x][i], y = fat[y][i];}return fat[x][0];
}
int Kth(int x, int k) {for(int i = 20; i >= 0; i -- ) {if((k >> i) & 1) x = fat[x][i];}return x;
} 
void OP(int u, int v, int len) {int lca = LCA(u, v);if(dep[u] + dep[v] - 2 * dep[lca] <= len) t.add(1, 1);else if(dep[u] - dep[lca] > len) {int ancestor = Kth(u, len);t.add(L[ancestor], 1);t.add(R[ancestor] + 1, -1);}else {int ancestor = Kth(v, dep[v] - dep[lca] - (len + 1 - (dep[u] - dep[lca])));t.add(1, 1);t.add(L[ancestor], -1);t.add(R[ancestor] + 1, 1); }
}
bool check(int len) {t.Clean();for(int i = 1; i <= m; i ++ ) {OP(pu[i], pv[i], len); OP(pv[i], pu[i], len);}for(int i = 1; i <= n; i ++ ) {if(t.ask(i) == m * 2) return 1;}return 0;
}
int main() {n = read(), m = read();for(int i = 1; i < n; i ++ ) {u = read(), v = read();E[u].pb(v); E[v].pb(u);}for(int i = 1; i <= m; i ++ ) {pu[i] = read(), pv[i] = read();}dfs0(1, 0);int l = 0, r = 1e5 + 10, mid, res = -1;while(l <= r) {mid = (l + r >> 1);if(check(mid)) res = mid, r = mid - 1;else l = mid + 1;}printf("%d\n", res);return 0;
}

2024 CCPC东北邀请赛 I. Password(动态规划)

在这里插入图片描述
题目

          分析:
          如果 [ i − k + 1 , i ] [i - k + 1, i] [ik+1,i] 是一个 1 1 1 k k k 的排列,我们称 i i i 是一个 结尾。那么由于每个位置都需要在一个排列的区间中,因此有一个性质:两个结尾的距离一定不超过 k k k。有了这个性质我们就可以 d p dp dp 了。 设 d p i dp_{i} dpi 表示只考虑前 i i i 个位置,每个位置都是好的的并且第 i i i 和位置是一个 结尾 的序列数。转移考虑枚举上一个结尾:

d p i = ∑ j = 1 k d p i − j × g j dp_i = \sum_{j = 1}^{k} dp_{i -j} \times g_j dpi=j=1kdpij×gj

          这里 g j g_j gj 是转移系数。因为如果直接乘 j ! j! j,那么一定会有重复。这是因为没有满足 i − j i - j ij 是上一个结尾的转移条件。如果乘 j ! j! j,那么会出现 ( i − j , i ) (i -j, i) (ij,i) 之间某个位置成为了一个结尾的情况,这样就会多算。

          考虑 g j g_j gj 如何计算。思考 g j g_j gj 的意义:现在有一个排列,你要在后面接 j j j 个数字,使得最后一个位置作为右端点长度为 k k k 的区间形成一个排列,并且前面没有别的位置能作为右端点形成排列。那么根据 g j g_j gj 的含义来容斥求 g g g

g i = i ! − ∑ j = 1 i − 1 g j g_i = i! - \sum_{j = 1}^{i - 1}g_j gi=i!j=1i1gj

          这个式子可以理解为 总方案数减去不合法的方案数,其中 ∑ j = 1 i − 1 g j \sum_{j = 1}^{i -1}g_j j=1i1gj 可以理解为 把不合法方案按照最前面能形成排列的位置分组 求贡献。因为 g j g_j gj 说明 j j j 位置能形成排列,但是前面不能形成形成排列。因此是一个天然的划分。这样就能把所有不合法方案不重不漏计算在内了。

时间复杂度 O ( n × k ) O(n \times k) O(n×k)

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 10;
const int K = 1e3 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, k;
LL dp[N], g[K], fac[N];
int main() {scanf("%d%d", &n, &k);if(k > n) {puts("0"); return 0;}else {fac[0] = 1LL;for(int i = 1; i < N; i ++ ) fac[i] = (fac[i - 1] * (1LL * i)) % mod;g[1] = 1LL;for(int i = 2; i <= k; i ++ ) {g[i] = fac[i];for(int j = 1; j < i; j ++ ) { // 枚举非法情况中,第一个提前匹配成排列的位置 g[i] = ((g[i] - g[j] * fac[i - j] % mod) % mod + mod) % mod;}}dp[k] = fac[k];for(int i = k + 1; i <= n; i ++ ) {for(int j = i - 1; j >= i - k; j -- ) {dp[i] = (dp[i] + dp[j] * g[i - j] % mod) % mod;}}printf("%lld\n", dp[n]);} return 0;
}

2024 CCPC东北邀请赛 K. Tasks(贪心,构造)

在这里插入图片描述
题目

          分析:感觉思路挺不好想的。考虑按照烦躁值分组。首先 对于同组的,不能出现区间包含的情况。因为这样会让更大的那个区间不成立。然后就是在区间不互相包含的情况下,每个区间越长 越好。这样可以让烦躁值更大的区间更容易被包含。并且由于只需要让每个区间的烦躁值等于包含它的区间的最大烦躁值 + 1 +1 +1 即可,因此 不需要考虑当前区间是否会包含烦躁值很大的区间从而影响合法性。知道了这两个性质我们就可以对从小到大对每一层进行构造了。注意 每一层按照左端点排序后应从大到小 考虑,这样才能构造出最优的方案。具体细节参见代码。

时间复杂度: O ( n ) O(n) O(n)

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
const int Limit = 1e6;
typedef pair< int, int > PII;
int n, l[N], b[N];
vector< int > F[N];
map< PII, int > ans;
inline int read() {int x = 0, f = 1; char c = getchar();while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}while(isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
void calc(int depth) {if(depth == 0) {int now = Limit;for(int i = F[depth].size() - 1; i >= 0; i -- ) {ans[make_pair(depth, F[depth][i])] = now;now --;}}else {if(F[depth - 1].empty()) {puts("-1");exit(0);}int nl = F[depth - 1].size() - 1; int nr = ans[make_pair(depth - 1, F[depth - 1][nl])];for(int i = F[depth].size() - 1; i >= 0; i -- ) {int p = F[depth][i];while(nl >= 0 && p < F[depth - 1][nl]) {nl --;if(nl != -1) nr = min(nr, ans[make_pair(depth - 1, F[depth - 1][nl])]);}if(nl == -1) {puts("-1"); exit(0);}else {if(p == F[depth - 1][nl] && nr == ans[make_pair(depth - 1, F[depth - 1][nl])]) nr --;if(nr >= p) {ans[make_pair(depth, p)] = nr;nr --;}else {puts("-1");exit(0);}}}}
}
int main() {n = read();for(int i = 1; i <= n; i ++ ) {scanf("%d%d", &l[i], &b[i]);F[b[i]].pb(l[i]);}for(int i = 0; i <= Limit; i ++ ) {sort(F[i].begin(), F[i].end());for(int j = 1; j < F[i].size(); j ++ ) {if(F[i][j] == F[i][j - 1]) {puts("-1");return 0;}}}for(int i = 0; i <= Limit; i ++ ) {if(F[i].empty()) continue;else calc(i);}for(int i = 1; i <= n; i ++ ) {printf("%d\n", ans[make_pair(b[i], l[i])]);}return 0;
}

2024 CCPC东北邀请赛 L. Bracket Generation(组合数学,数数)

在这里插入图片描述
题目

          分析:连续的一对的 ( ( ( ) ) ),那它肯定是由一个 1 1 1 操作产生的,其余的左括号和右括号肯定都是由 2 2 2 操作产生。我们注意到所有的 2 2 2 操作都有一个限制,那就是 必须在它括住的最后一个 1 1 1 后才能使用。因此我们可以统计出有多少个 1 1 1 操作,并统计出每个 1 1 1 操作由多少个 所属的 2 2 2 操作。这里 所属 就是必须在这个 1 1 1 后才能出现的意思。那么对于每个 1 1 1 操作内部的 2 2 2,首先有一个 阶乘 的贡献,表示内部不同的顺序。由于 1 1 1 操作只能向后面加,所以所有的 1 1 1 操作的顺序是定的,就是从左到右的顺序。我们只需要再累乘起分别插入每组 2 2 2 操作的贡献即可。

时间复杂度 O ( n ) O(n) O(n)

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL mod = 998244353;
int n, tot, cnt[N];
LL fac[N], inv[N], res;
char str[N];
LL Pow(LL x, LL y) {LL res = 1LL, k = x;while(y) {if(y & 1) res = (res * k) % mod;y >>= 1;k = (k * k) % mod;}return res;
}
LL C(int n, int m) {return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {scanf("%s", str + 1);n = strlen(str + 1);fac[0] = 1LL;for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * (1LL * i) % mod;inv[N - 1] = Pow(fac[N - 1], mod - 2LL) % mod;for(int i = N - 2; i >= 0; i -- ) inv[i] = inv[i + 1] * (1LL * (i + 1LL)) % mod; for(int i = 1; i <= n; i ++ ) {if(str[i] == '(' && str[i + 1] == ')') {tot ++; int c = 0;for(int j = i + 2; j <= n; j ++ ) {if(str[j] == ')') c ++;else break;}cnt[tot] = c;}}res = 1LL; int room = 0;for(int i = tot; i >= 1; i -- ) {res = (res * fac[cnt[i]]) % mod; // 内部2的贡献 res = res * C(room + cnt[i], cnt[i]) % mod;room = room + cnt[i] + 1;}printf("%lld\n", res);return 0;
}

2024 CCPC东北邀请赛 G. Diamond(根号分治)

在这里插入图片描述
题目

          分析:比较难的一道题。我们发现如果每次询问的 p p p q q q 数量比较少,那么每次询问就可以暴力做。如果比较多,那么这样的 p p p 或者 q q q 的数量就比较少。这启示我们 根号分治

          注意到逆序对就是 小数前面的大数数量。我们给数量大于 n \sqrt{n} n 的数编号,处理出 f i , j f_{i, j} fi,j 表示第 i i i 个位置前面编号为 j j j 的数字个数,这个可以在 O ( n n ) O(n\sqrt{n}) O(nn ) 的复杂度内处理出来。 然后我们处理出 S i , j S_{i, j} Si,j 表示前 i i i 个位置里每个值为 a i a_i ai 的位置前面编号为 j j j 的数字数量 的和。这个可以对每个位置记一个前驱求出来。最后计算答案是简单的:只需要 S S S 数组的前缀相减再减去 [ 1 , l − 1 ] [1, l-1] [1,l1] [ l , r ] [l, r] [l,r] 的贡献即可。比较恶心的是这道题卡空间,可以将阈值设大来减小大数的数量。这样可以优化空间。

时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn )

CODE:

          还没调过就不放了

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

昇思25天学习打卡营第14天|基于MindSpore的红酒分类实验

背景介绍 本文主要介绍使用MindSpore在部分wine数据集上进行KNN实验。 K近邻算法原理 K近邻算法&#xff08;K-Nearest-Neighbor, KNN&#xff09;是一种用于分类和回归的非参数统计方法&#xff0c;最初由 Cover和Hart于1968年提出(Cover等人,1967)&#xff0c;是机器学习最…

了解AsyncRotationController

概述 基于android 15.0, 以从强制横屏App上滑退回桌面流程来分析 frameworks/base/services/core/java/com/android/server/wm/AsyncRotationController.javaAsyncRotationController 是一种控制器&#xff0c;用于处理设备显示屏旋转时非活动窗口的异步更新。这种控制器通过…

国产化框架PaddleClas结合Swanlab进行杂草分类

1. 项目介绍 杂草是农业中的主要问题之一&#xff0c;对作物生长和产量造成严重威胁。传统的手动识别和管理方式效率低下且不够精确&#xff0c;因此需要借助先进的计算机视觉技术来提升农业生产的效率和质量。ResNet作为一种深度学习模型&#xff0c;在处理复杂的图像分类任务…

C++入门基础篇(1)

欢迎大家来到海盗猫鸥的博客—— 断更许久&#xff0c;让我们继续好好学习吧&#xff01; 目录 1.namespace命名空间 命名空间的存在价值&#xff1a; 命名空间的定义&#xff1a; 命名空间的使用&#xff1a; 2.C输入输出函数 使用&#xff1a; 3.缺省参数 4.函数重载…

可观察性优势:掌握当代编程技术

反馈循环是我们开发人员工作的关键。它们为我们提供信息&#xff0c;并让我们从用户过去和现在的行为中学习。这意味着我们可以根据过去的反应进行主动开发。 TestComplete 是一款自动化UI测试工具&#xff0c;这款工具目前在全球范围内被广泛应用于进行桌面、移动和Web应用的…

Redis+Caffeine 实现两级缓存实战

RedisCaffeine 实现两级缓存 背景 ​ 事情的开始是这样的&#xff0c;前段时间接了个需求&#xff0c;给公司的商城官网提供一个查询预计送达时间的接口。接口很简单&#xff0c;根据请求传的城市仓库发货时间查询快递的预计送达时间。因为商城下单就会调用这个接口&#xff…

【RHCE】系统服务综合实验

一、实验内容 现有主机 node01 和 node02&#xff0c;完成如下需求&#xff1a; 1、在 node01 主机上提供 DNS 和 WEB 服务 2、dns 服务提供本实验所有主机名解析 3、web服务提供 www.rhce.com 虚拟主机 4、该虚拟主机的documentroot目录在 /nfs/rhce 目录 5、该目录由 node02…

【Unity2D 2022:UI】制作主菜单

一、创建主菜单游戏场景 1. 在Scenes文件夹中新建一个游戏场景Main Menu 2. 为场景添加背景 &#xff08;1&#xff09;创建画布Canvas &#xff08;2&#xff09;在Canvas中创建新的空游戏物体Main Menu &#xff08;3&#xff09;在Main Menu中新建一个图像游戏物体Backgrou…

达梦数据库dm8安装步骤及迁移

目录 前言: 一、安装部署 1、下载 2、创建用户及安装目录 3、挂载下载的镜像 4、环境配置 5、安装 二、基本使用 1、DM工具使用 2、兼容性配置 2.1 兼容GBK字符集编码 2.2 兼容UTF-8字符集编码 3、创建用户和密码,表空间 4、整理数据库配置 5、启动脚本设置 …

普中51单片机:定时器与计数器详解及应用(七)

文章目录 引言定时器工作原理TMOD定时器/计数器工作模式寄存器定时器工作模式模式0(13位定时器/计数器)模式1(16位定时器/计数器)模式2(8位自动重装模式)模式3(两个8位计数器) 定时器配置流程代码演示——LED1间隔1秒闪烁代码演示——按键1控制LED流水灯状态代码演示——LCD160…

初始网络知识

前言&#x1f440;~ 上一章我们介绍了使用java代码操作文件&#xff0c;今天我们来聊聊网络的一些基础知识点&#xff0c;以便后续更深入的了解网络 网络 局域网&#xff08;LAN&#xff09; 广域网&#xff08;WAN&#xff09; 路由器 交换机 网络通信基础 IP地址 端…

法律咨询援助网站

1 项目介绍 1.1 摘要 随着互联网技术的飞速发展&#xff0c;公众对于便捷、高效的法律咨询服务需求日益增长。传统的法律咨询方式已难以满足人们即时性、多样化的咨询需求&#xff0c;促使法律咨询援助网站应运而生。这些平台旨在通过数字化手段&#xff0c;为用户提供法律知…

LayoutLMv2:视觉丰富文档理解的多模态预训练

文本和布局的预训练由于其有效的模型架构和大规模未标记扫描/数字出生文档的优势&#xff0c;在各种视觉丰富的文档理解任务中被证明是有效的。我们提出了具有新的预训练任务的LayoutLMv2架构&#xff0c;以在单个多模态框架中对文本、布局和图像之间的交互进行建模。具体而言&…

Apache防盗链、网页压缩、网页缓存

目录 网页压缩 类型 示例 动态添加模块操作步骤 重装Apache操作步骤 网页缓存 示例 操作步骤 隐藏版本信息 操作步骤 Apache防盗链 定义 原理 配置防盗链实验环境 实验环境 本地图片盗链示例 操作步骤 防盗链示例 操作步骤 网页压缩 网站的访问速度是由多个…

Golang | Leetcode Golang题解之第229题多数元素II

题目&#xff1a; 题解&#xff1a; func majorityElement(nums []int) (ans []int) {cnt : map[int]int{}for _, v : range nums {cnt[v]}for v, c : range cnt {if c > len(nums)/3 {ans append(ans, v)}}return }

oracle 23ai新的后台进程bgnn介绍

前言 昨天发文研究了哪些oracle 后台不能杀 具体文章如下链接 oracle哪些后台进程不能杀&#xff1f;-CSDN博客 其中23ai中新增了一个后台进程bgnn 但是在oracle 23ai database reference中并没有找到该后台进程 有点不甘心就开了个SR&#xff0c;找oracle 官方来看看这个后…

【鸿蒙学习笔记】元服务

官方文档&#xff1a;元服务规格 目录标题 什么是元服务特征第一个元服务-案例介绍创建项目源码启动模拟器启动entry创建卡片出发元服务 什么是元服务 特征 免安装分包预加载老化和更新机制 第一个元服务-案例介绍 创建项目 源码 Entry Component struct WidgetCard {buil…

如何做好IT类的技术面试?

我们在找工作时&#xff0c;需要结合自己的现状&#xff0c;针对意向企业做好充分准备。作为程序员&#xff0c;你有哪些面试IT技术岗的技巧&#xff1f; 方向一&#xff1a;分享你面试IT公司的小技巧 我分享一些基于广泛观察和用户反馈的面试IT公司的小技巧&#xff1a; 技术准…

BUG解决:postman可以请求成功,但Python requests请求报403

目录 问题背景 问题定位 问题解决 问题背景 使用Python的requests库对接物联数据的接口之前一直正常运行&#xff0c;昨天突然请求不通了&#xff0c;通过进一步验证发现凡是使用代码调用接口就不通&#xff0c;而使用postman就能调通&#xff0c;请求参数啥的都没变。 接口…

【JavaScript 算法】快速排序:高效的排序算法

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 一、算法原理二、算法实现三、应用场景四、优化与扩展五、总结 快速排序&#xff08;Quick Sort&#xff09;是一种高效的排序算法&#xff0c;通过分治法将数组分为较小的子数组&#xff0c;递归地排序子数组。快速排序通常…