php做网站要多久网页广告投放

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

php做网站要多久,网页广告投放,徐州商城建站系统,友情链接代码文章目录 牛客练习赛125 E 联谊活动#xff08;枚举#xff0c;分讨#xff09;牛客练习赛125 F 玻璃弹珠#xff08;类莫队#xff0c;离线询问#xff0c;数据结构#xff09;2024ccpc长春邀请赛 D Parallel Lines#xff08;随机化#xff09;2024ccpc长春邀请赛 E… 文章目录 牛客练习赛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 Sx​∼Ex​ 行设当前行是 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×xx×y)。 CODE #includebits/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;}} } 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(mlog2​m)。 CODE: #includebits/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 {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: #includebits/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 - jb_i - i \geq b_j - j ai​−i≤aj​−jbi​−i≥bj​−j 或者 a i − i ≥ a j − j b i − i ≤ b j − j a_i - i \geq a_j - jb_i - i \leq b_j - j ai​−i≥aj​−jbi​−i≤bj​−j 。这两个式子可以看作 j j j 往 i i i 连边 或 i i i 往 j j j 连边。我们令 x i a i − i x_i a_i - i xi​ai​−i y i b i − i y_i b_i - i yi​bi​−i那么 i i i 往 j j j 连边的条件就是 x i ≥ x j y i ≤ y j x_i \geq x_jy_i \leq y_j xi​≥xj​yi​≤yj​。将元素按照 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 yi yi​ 和栈顶元素所在联通块的的最大 y y y 比较来判断是否连边就不会错。注意连边的时候更新连通块的最大 y y y 值。 时间复杂度 O ( n ) O(n) O(n) CODE: #includebits/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 为根的子树的最大权值和。考虑转移分两类情况 存在 奇儿子那么每个偶儿子可以选 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 t⊕1另外的选 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,t⊕1​−dpson,t​ 拿出来从大到小排序选出前 ⌈ m 2 ⌉ \left \lceil \frac{m}{2} \right \rceil ⌈2m​⌉ 大并把所有 d p s o n , t dp_{son, t} dpson,t​ 累加即可。不存在 奇儿子那么所有儿子的状态都只能是 t ⊕ 1 t \oplus 1 t⊕1加起来就好了。 CODE: #includebits/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 uv uv 的 l c a lca lca 一定在它们的路径上我们考虑选取不同点作为根时 u v uv uv 的 l c a lca lca 有什么规律。 如果以红色点为树根那么 u , v u,v u,v 的 l c a lca lca 就是 u − v u - v u−v 路径上红色点的祖先。也就是说如果我们首先以任意一个点为根那么检验时选取作为根的点在 u − v u-v u−v路径上哪个点的子树中那个点就是真正的 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(nlog2​n)。 CODE #includebits/stdc.h #define pb pushback using namespace std; const int N 1e5 10; inline int read() {int x 0, f 1; char c getchar();while(!isdigit©) {if(c -) f -1; c getchar();}while(isdigit©) {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] [i−k1,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 dpi \sum{j 1}^{k} dp_{i -j} \times g_j dpi​∑j1k​dpi−j​×gj​ 这里 g j g_j gj​ 是转移系数。因为如果直接乘 j j j那么一定会有重复。这是因为没有满足 i − j i - j i−j 是上一个结尾的转移条件。如果乘 j j j那么会出现 ( i − j , i ) (i -j, i) (i−j,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 gi i! - \sum{j 1}^{i - 1}gj gi​i!−∑j1i−1​gj​ 这个式子可以理解为 总方案数减去不合法的方案数其中 ∑ j 1 i − 1 g j \sum{j 1}^{i -1}g_j ∑j1i−1​gj​ 可以理解为 把不合法方案按照最前面能形成排列的位置分组 求贡献。因为 g j g_j gj​ 说明 j j j 位置能形成排列但是前面不能形成形成排列。因此是一个天然的划分。这样就能把所有不合法方案不重不漏计算在内了。 时间复杂度 O ( n × k ) O(n \times k) O(n×k) #includebits/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 ) faci % mod;g[1] 1LL;for(int i 2; i k; i ) {g[i] fac[i];for(int j 1; j i; j ) { // 枚举非法情况中第一个提前匹配成排列的位置 gi % mod;}}dp[k] fac[k];for(int i k 1; i n; i ) {for(int j i - 1; j i - k; j – ) {dpi % mod;}}printf(%lld\n, dp[n]);} return 0; }2024 CCPC东北邀请赛 K. Tasks贪心构造 题目 分析感觉思路挺不好想的。考虑按照烦躁值分组。首先 对于同组的不能出现区间包含的情况。因为这样会让更大的那个区间不成立。然后就是在区间不互相包含的情况下每个区间越长 越好。这样可以让烦躁值更大的区间更容易被包含。并且由于只需要让每个区间的烦躁值等于包含它的区间的最大烦躁值 1 1 1 即可因此 不需要考虑当前区间是否会包含烦躁值很大的区间从而影响合法性。知道了这两个性质我们就可以对从小到大对每一层进行构造了。注意 每一层按照左端点排序后应从大到小 考虑这样才能构造出最优的方案。具体细节参见代码。 时间复杂度 O ( n ) O(n) O(n) #includebits/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©) {if(c -) f -1; c getchar();}while(isdigit©) {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[makepair(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 #includebits/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(stri) {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,l−1] 对 [ l , r ] [l, r] [l,r] 的贡献即可。比较恶心的是这道题卡空间可以将阈值设大来减小大数的数量。这样可以优化空间。 时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn ​)。 CODE 还没调过就不放了。