xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

codeforces 1272F dp+记录路径

题意给出两个括号序列 \(S\) 和 \(T\)，让你构造一个最短的合法括号序列使 \(S\) 和 \(T\) 是它的子序列。分析设 \(dp[i][j][k]\) 为这个最短的合法括号序列的前缀包含 \(S\) 的前 \(i\) 个字符，T的前 \(j\) 个字符且左括号的数量大于右括...

DP

2019-12-18

0 325

牛客练习赛55 E-树树形DP

题意你有一颗大小为\(n\)的树，点从\(1\)到\(n\)标号。设\(dis⁡(x,y)\)表示\(x\)到\(y\)的距离。求\(\sum_{i=1}^{n}\sum_{j=1}^{n}dis^2(i,j)\)对\(998244353\)取模的结果。分析设\(d_x\)为点\(x...

树形DP

2019-12-15

0 362

Codeforces 1272 A-E

Codeforces 1272 A-E A Three Friends 直接枚举所有情况，共\(3\times 3\times 3=27\)种。 code #include<bits/stdc++.h> #define fi first #define se second #de...

2019-12-13

0 322

2018CCPCFINAL B Balance of the Force 枚举最大值

题意 n个人能选择黑暗面和光明面，选择两个面分别能获得\(L_i\)和\(R_i\)的力量，有m对人不能选择同一面，问n个人的力量中的最大值-最小值尽可能小为多少。 \(1<=n<=2\times 10^5\) \(0<=m<=2\times 10^5\) \(1&l...

枚举

2019-10-26

0 395

Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集

题意给一个$ n \times m$ 的网格，每个格子里有一个数字，非 \(0\) 即 \(1\)，行从上往下依次编号为 \(1, 2, \cdots, n\)，列从左往右依次编号为 \(1, 2, \cdots, m\)。给 \(q\) 次操作，每次给定一个以 \((x_1,y_1)\) ...

并查集

2019-10-25

0 402

codeforces 1249 D2 Too Many Segments (hard version) 贪心+树状数组

题意给定n个线段，线段可以相交，第\(i\)个线段覆盖的区间为\([l_i,r_i]\)，问最少删除多少个线段让覆盖每个点的线段数量小于等于k。分析从左往右扫每个点\(x\)，若覆盖点\(x\)的线段数cnt大于k，则贪心的删去覆盖点\(x\)的线段中\(r_i\)前\(cnt-k\)大...

树状数组贪心

2019-10-24

0 414

codeforces1213G Path Queries 并查集

题意给定n个结点的树，每条边有边权，有m个询问，每个询问给一个\(q_i\)输出树上有多少点对的简单路径上最大的边权不超过\(q_i\)。分析用并查集维护点集，同时维护大小。将所有边按边权排序，考虑每次从小到大加边，图中经过当前边的所有路径一定是以当前边的边权为最大值的，用并查集维护...

并查集

2019-10-23

0 411

codeforces1213F tarjan缩点+拓扑排序

题意给定两个长度为n的排列p和q，构造一个字符串s满足\(s[p_i]<=s[p_{i+1}]\)和\(s[q_i]<=s[q_{i+1}]\)，且满足字符串中不同字符的个数不少于k。分析建一个有向图，\(p_i\)到\(p_{i+1}\)连一条有向边，\(q_i\)到\(q...

tarjan 拓扑排序

2019-10-23

0 399

【模板】线性基求交

线性基求交 struct lb{ ll p[63]; lb(){ memset(p,0,sizeof(p)); } void clear(){ memset(p,0,sizeof(p)); } void ins(ll x){ for(int i=60;i>...

线性基

2019-10-05

0 433

大数模板

class BigNum { public: static const int MOD = 100000000; static const int BIT = 8, SIZE = 105; mutable int n,o; long long u[SIZE]; ...

高精度/大数

2019-09-27

0 377