当前位置: 开发笔记 > 编程语言 > 正文

CodeforcesRound#566(Div.2)A~F个人题解

作者：mobiledu2502916313 | 来源：互联网 | 2024-12-25 18:41

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你

Dashboard - Codeforces Round #566 (Div. 2) - Codeforces

A. Filling Shapes

题意&＃xff1a;给你一个 $3 \times n$ 的表格&＃xff0c;你要用小L型的瓷砖把整个表格填满&＃xff0c;问你有多少种方法&＃xff1f;

知识点&＃xff1a;数学&＃xff0c;思维

思路&＃xff1a;通过一点点观察发现&＃xff0c;想要满足宽度是3&＃xff0c;一定是俩个L型瓷砖交叉这放&＃xff0c;并且对于一个长度为2宽度为3的表格&＃xff0c;只有两种放法&＃xff0c;如下图

所以只有表格长度为偶数&＃xff0c;那么答案一定是2^n/2(有多少个长度为2的,每个有两种情况)

奇数一定不可能填满&＃xff0c;因为没有长度为1的图形来填&＃xff0c;也不可能凑出来。

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;6; void solve(){ll n;cin>>n;if(n&1)cout<<0<<&＃39;\n&＃39;;//奇数没有else cout<<(1ll<<(n/2))<<&＃39;\n&＃39;;//偶数 2^(n/2)个 } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;//cin>>_;while(_--){solve();}return 0; } /* */

B. Plus from Picture

题意&＃xff1a;有一个 $w \times h$ 大小的表格&＃xff0c;表格上每一个位置只会出现两种字符&＃xff0c;‘&＃43;’和‘.’&＃xff0c;问是否所有的‘&＃43;’连接成了一个大的 &＃43; 号&＃xff08;所有‘&＃43;’字符都在这个大的 &＃43; 号上&＃xff0c;大的 &＃43; 号四个延伸出去的边长度至少大于等于1&＃xff0c;宽度等于1&＃xff0c;中间不能是空的&＃xff09;&＃xff1f;

知识点&＃xff1a;搜索&＃xff0c;思维

思路&＃xff1a;我们先看每一个点是否可以是大 &＃43; 号中间那个点&＃xff0c;如果是放入我们的数组里&＃xff0c;然后先判断数组的大小&＃xff0c;如果大小大于1或者等于0&＃xff0c;就是说不满足所有的点都在大的 &＃43; 号上或者说大的 &＃43; 号的边的宽度大于1&＃xff0c;这些都是NO的&＃xff0c;现在只剩下了数组大小等于1&＃xff0c;我们搜4个方向上所能走的点打上标记&＃xff0c;最后看整个图&＃xff0c;如果存在没有打上标记的‘&＃43;’&＃xff0c;说明不是所有的‘&＃43;’构成了大的 &＃43; 号&＃xff0c;输出NO&＃xff0c;否则输出 YES

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;6; char mp[505][505]; ll n,m; bool vis[505][505]; vector >vp; ll dx[5]&＃61;{0,0,0,1,-1}; ll dy[5]&＃61;{0,1,-1,0,0}; bool check(ll x,ll y){for(int i&＃61;0;i<5;&＃43;&＃43;i)if(mp[x&＃43;dx[i]][y&＃43;dy[i]]!&＃61;&＃39;*&＃39;)return false;return true; } void solve(){cin>>n>>m;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){cin>>mp[i][j];if(mp[i][j]&＃61;&＃61;&＃39;.&＃39;)vis[i][j]&＃61;true;//先给&＃39;.&＃39;打上标记这样好判断一点}}for(int i&＃61;2;in||ty>m||vis[tx][ty])break;//如果遇到打标记的点&＃xff0c;说明遇到&＃39;.&＃39;了&＃xff0c;这个方向就不用看了vis[tx][ty]&＃61;true;}}for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){if(!vis[i][j]){//如果存在没有打标记的点&＃xff0c;输出NOcout<<"NO\n";return ;}}}cout<<"YES\n";//都成立了&＃xff0c;输出YES} } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;//cin>>_;while(_--){solve();}return 0; } /* */

C. Beautiful Lyrics

题意&＃xff1a;给你n个字符串&＃xff0c;现在问你能从中选出的美好的诗句有几条&＃xff1f;

美好的诗句满足&＃xff1a;

&＃xff08;1&＃xff09;美好的诗句由4个字符串组成&＃xff0c;分为左上&＃xff0c;左下&＃xff0c;右上&＃xff0c;右下。

&＃xff08;2&＃xff09;左上和左下的元音字母个数要相同。

&＃xff08;3&＃xff09;右上和右下的元音字母个数要相同&＃xff0c;并且右上和右下的最后一个元音字母一样。

&＃xff08;元音字母只包括 a,e,i,o,u&＃xff09;

知识点&＃xff1a;贪心&＃xff0c;排序

思路&＃xff1a;发现条件&＃xff08;3&＃xff09;是包含条件&＃xff08;2&＃xff09;的&＃xff0c;所以肯定是条件&＃xff08;3&＃xff09;满足的越多越好&＃xff0c;因为多余的可以退化成满足&＃xff08;2&＃xff09;&＃xff0c;所以现在问题转化成了问有多少个满足条件&＃xff08;3&＃xff09;的字符串对和剩下的有多少个满足条件&＃xff08;2&＃xff09;的字符串对。这个我们可以先按元音字母个数从小到大排序&＃xff0c;再按最后一个元音字母的大小从小到大排序&＃xff0c;然后按要求找就OK了&＃xff0c;具体实现可以看代码。

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;6; struct dd{ll cnt,last;//元音字母个数&＃xff0c;最后一个元音字母string s;//这个字符串是什么inline bool operator <(const dd &r)const{if(cnt&＃61;&＃61;r.cnt)return last}op[N]; bool vis[N];//打标记用 void solve(){ll n;cin>>n;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){string s;cin>>s;ll cnt&＃61;0,last&＃61;0;for(int i&＃61;0;i >ansr,ansl;//记录答案&＃xff0c;r是满足&＃xff08;3&＃xff09;&＃xff0c;l是满足&＃xff08;2&＃xff09;ll pre&＃61;-1,precnt&＃61;-1,preid&＃61;0;//上一个状态的最后一个元音字母&＃xff0c;元音字母个数&＃xff0c;下标for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){if(pre&＃61;&＃61;op[i].last&&precnt&＃61;&＃61;op[i].cnt){//如果满足条件&＃xff08;3&＃xff09;ansr.push_back({op[i].s,op[preid].s});//先扔进去vis[i]&＃61;true;//这个下标已经用过了&＃xff0c;打标记vis[preid]&＃61;true;//这个下标已经用过了&＃xff0c;打标记pre&＃61;-1;precnt&＃61;-1;preid&＃61;0;//这俩都已经用了&＃xff0c;说明没有上一个}else {//不满足&＃xff0c;更新pre&＃61;op[i].last;precnt&＃61;op[i].cnt;preid&＃61;i;}}//满足条件&＃xff08;3&＃xff09;的找完了&＃xff0c;找满足条件&＃xff08;2&＃xff09;的pre&＃61;-1;precnt&＃61;-1;preid&＃61;0;//上一个状态的最后一个元音字母&＃xff0c;元音字母个数&＃xff0c;下标for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){if(vis[i])continue;//用过&＃xff0c;说明不能用了if(precnt&＃61;&＃61;op[i].cnt){//条件&＃xff08;2&＃xff09;只用满足元音字母个数相同ansl.push_back({op[i].s,op[preid].s});//先扔进去pre&＃61;-1;precnt&＃61;-1;preid&＃61;0;//这俩都已经用了&＃xff0c;说明没有上一个}else {//不满足&＃xff0c;更新pre&＃61;op[i].last;precnt&＃61;op[i].cnt;preid&＃61;i;}}ll lsize&＃61;ansl.size(),rsize&＃61;ansr.size();if(lsize>&＃61;rsize){//如果满足条件&＃xff08;2&＃xff09;的比满足条件&＃xff08;3&＃xff09;的多cout<&＃61;rsize-tmp;--i){//然后把他们扔过去ansl.push_back(ansr[i]);}cout<} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;//cin>>_;while(_--){solve();}return 0; } /* */

D. Complete Mirror

题意&＃xff1a;给你一颗有n个结点的无根树&＃xff0c;问你是否能找到一个点作为根满足&＃xff1a;

对于任意两点 v_1,v_2 满足 dis(root,v_1)&＃61;dis(root,v_2) 并且 deg(v_1)&＃61;deg(v_2)

( dis(i,j) 表示点i到点j之间的边的数量&＃xff0c; deg(i) 表示点i和多少个点直接相连)

找到输出点的编号&＃xff0c;找不到输出-1

知识点&＃xff1a;DFS&＃xff0c;树的重心

思路&＃xff1a;如果暴力的想&＃xff0c;就是n个点都可能成为根&＃xff0c;每个都判一次&＃xff0c;复杂度O( n^2 )肯定是不可以的&＃xff0c;所以想尽可能减少判的次数&＃xff0c;发现有一些点是没有判的必要的&＃xff0c;所以现在就是考虑哪些点可能成为根

先考虑条件&＃xff0c;这两个条件要都满足一定是这个点孩子的子树都是同构的&＃xff0c;而想要满足这个条件&＃xff0c;那么这个点可能在树的重心位置上&＃xff0c;所以重心是可能成为根的一个点&＃xff0c;然后考虑重心的孩子&＃xff0c;如果孩子的子树是一个树型的&＃xff0c;那这个子树上的所有点都不可能是根&＃xff0c;因为上面所有点都不可能满足条件的。如果孩子的子树一个链型的&＃xff0c;那这个子树的叶子是可能成为根的&＃xff0c;但其实这里不用全判&＃xff0c;如果俩个链长度相同&＃xff0c;取其一就行&＃xff0c;毕竟是同构的&＃xff0c;所以我们要判断的就很少了。

&＃xff08;这道题其实多动手画图就能发现了&＃xff09;

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;7; ll n; ll siz[N],weight[N];//求重心用的 ll treefocus[2];//树的重心下标 vectormp[N];//存树的边 void dfs(ll u,ll root){//求树的重心siz[u]&＃61;1;weight[u]&＃61;0;for(auto v:mp[u]){if(v&＃61;&＃61;root)continue;dfs(v,u);siz[u]&＃43;&＃61;siz[v];weight[u]&＃61;max(weight[u],siz[v]);}weight[u]&＃61;max(weight[u],n-siz[u]);if(weight[u]<&＃61;n/2){//根据定义判断树的重心treefocus[treefocus[0]!&＃61;0]&＃61;u;} } vectorans;//要判断的数组 ll d[N],ye,Maxdeep;//度数&＃xff0c;叶子的下标&＃xff0c;链的长度 bool tp,in[N];//是不是链&＃xff0c;有没有放过 void DFS(ll u,ll root,ll deep){ll ge&＃61;1;//孩子个数Maxdeep&＃61;max(Maxdeep,deep);for(auto v:mp[u]){if(v&＃61;&＃61;root)continue;DFS(v,u,deep&＃43;1);ge--;}if(ge&＃61;&＃61;1)ye&＃61;u;//叶子没有孩子if(ge<0)tp&＃61;false;//个数小于0了&＃xff0c;说明不是链 } bool flag; ll op[N],maxdeep; void check(ll now,ll root,ll deep){//判断是不是满足条件maxdeep&＃61;max(maxdeep,deep);if(op[deep]){//同一深度&＃xff0c;度数要相等if(d[now]!&＃61;op[deep])flag&＃61;false;}else op[deep]&＃61;d[now];for(auto v:mp[now]){if(v&＃61;&＃61;root)continue;check(v,now,deep&＃43;1);} } void solve(){cin>>n;for(ll i&＃61;1,u,v;i>u>>v;mp[u].push_back(v);mp[v].push_back(u);d[u]&＃43;&＃43;;d[v]&＃43;&＃43;;}dfs(1,-1);//求树的重心ans.push_back(treefocus[0]);//放入要判断的数组中for(auto v:mp[ans[0]]){//判断重心的孩子tp&＃61;true;Maxdeep&＃61;0;DFS(v,ans[0],1);if(tp){if(in[Maxdeep])continue;//如果这个长度的链已经放入要判断的数组了&＃xff0c;就不用放了in[Maxdeep]&＃61;true;ans.push_back(ye);}}for(auto w:ans){flag&＃61;true;check(w,-1,1);for(int i&＃61;1;i<&＃61;maxdeep;&＃43;&＃43;i)op[i]&＃61;0;if(flag){//满足cout<} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;//cin>>_;while(_--){solve();}return 0; } /* */

E. Product Oriented Recurrence

题意&＃xff1a; $f_x&＃61;c^{2x-6}\times f_{x-1}\times f_{x-2}\times f_{x-3} ,4\leq x$ ,已知 f_1,f_2,f_3,c,n 的值&＃xff0c;求 f_n ?

知识点&＃xff1a;矩阵快速幂&＃xff0c;欧拉定理

思路&＃xff1a;发现 f_n 最后一定等于 $c^{x_1}\times f_1^{x_2}\times f_1^{x_3}\times f_1^{x_4}$ ,所以我们可以构造一个关于这几项幂的矩阵&＃xff0c;然后矩阵快速幂加速&＃xff0c;我是通过分别构造的矩阵和 f_1,f_2,f_3 的矩阵来写的。

$\begin{bmatrix} F_{n,1} & F_{n,2} & F_{n,3} \\ F_{n-1,1} & F_{n-1,2} & F_{n-1,3} \\ F_{n-2,1} & F_{n-2,2} & F_{n-2,3} \end{bmatrix}&＃61;{ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} }^{n-3}\times \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

其中 $F_{n,1},F_{n,2},F_{n,3}$ 分别表示答案中 f_3,f_2,f_1 的多少次幂

$\begin{bmatrix} C_n \\ C_{n-1} \\ C_{n-2}\\ n\\ 1 \end{bmatrix} &＃61; {\begin{bmatrix} 1&1&1&2&-4 \\ 1 & 0 & 0&0&0 \\ 0 & 1 & 0&0&0\\ 0&0&0&1&1\\ 0&0&0&0&1 \end{bmatrix}}^{n-3}\times \begin{bmatrix} 0\\ 0\\ 0\\ 3\\ 1 \end{bmatrix}$

其中 C_n 表示答案中的多少次幂

最后输出 $c^{C_n}\times f_3^{F_{n,1}}\times f_2^{F_{n,2}}\times f_1^{F_{n,3}}\mod 1e9&＃43;7$ 就可以了&＃xff08;矩阵里是对phi(1e9&＃43;7)取模&＃xff0c;因为欧拉定理&＃xff09;

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;6; const ll Mod &＃61;1e9&＃43;7; const int maxl&＃61;105; struct Matrix {ll a[maxl][maxl];int n,m;inline Matrix(int n,int m) : n(n) , m(m) {for(int i&＃61;0;in,this->m),a&＃61;*this;ans.init();while(b){if(b&1)ans&＃61;ans*a;a&＃61;a*a;b>>&＃61;1;}return ans;} }; ll ksm(ll a,ll b){ll ans&＃61;1;while(b){if(b&1)ans&＃61;ans*a%Mod;a&＃61;a*a%Mod;b>>&＃61;1;}return ans; } ll f[3],n,c; void solve(){cin>>n;for(int i&＃61;2;i>&＃61;0;--i)cin>>f[i];//倒着输入对标一下cin>>c;Matrix now(3,3);for(int i&＃61;0;i<3;&＃43;&＃43;i)now.a[0][i]&＃61;1;//构造f1,f2,f3now.a[1][0]&＃61;now.a[2][1]&＃61;1;// 矩阵矩阵里是对phi(1e9&＃43;7)取模now&＃61;now.ksm(n-3);ll ans&＃61;1;for(int i&＃61;0;i<3;&＃43;&＃43;i){f[i]&＃61;ksm(f[i],now.a[0][i]);ans&＃61;ans*f[i]%Mod;//更新答案}Matrix cl(5,5);for(int i&＃61;0;i<3;&＃43;&＃43;i)cl.a[0][i]&＃61;1; //构造ccl.a[0][3]&＃61;2;cl.a[0][4]&＃61;mod-4; //的cl.a[1][0]&＃61;cl.a[2][1]&＃61;cl.a[3][3]&＃61;cl.a[3][4]&＃61;cl.a[4][4]&＃61;1;//矩阵cl&＃61;cl.ksm(n-3);ll w&＃61;(cl.a[0][3]*3ll%mod&＃43;cl.a[0][4])%mod;//对phi(1e9&＃43;7)取模,因为是次幂cout<} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;//cin>>_;while(_--){solve();}return 0; } /* */

F. Maximum Sine

题意&＃xff1a;给你 a,b,p,q 四个整数&＃xff0c;问你函数 $y&＃61;|sin(\frac{p}{q}\pi x)|$ 在 $a\leq x\leq b$ 中找到最小的x让y最大&＃xff1f;

知识点&＃xff1a;类欧几里德&＃xff0c;扩展欧几里得&＃xff08;需要一定的数论基础

思路&＃xff1a;根据一点点高中知识&＃xff0c;可以知道 |sin(x)| 在 $x&＃61;(k&＃43;\frac{1}{2})\pi,k\in Z$ 时候取到最大值&＃xff0c;所以我们要 $\frac{p}{q}\pi x&＃61;(k&＃43;\frac{1}{2})\pi$

$\frac{px}{q}-\frac{1}{2}&＃61;k$ 也就是 $\frac{2px-q}{2q}&＃61;k$ 等价于 $2px\mod2q-q$ 尽可能趋近0或者2q,

我们可以考虑二分 $2px\mod2q$ 的对q的偏差&＃xff0c;

我们首先要知道一个定理&＃xff1a; $[x\mod p \in [l,r]]$ 等价于 $\left \lfloor \frac{x-l}{p} \right \rfloor-\left \lfloor \frac{x-r-1}{p} \right \rfloor$

这个也很好验证:如果 $0\leq x<l$ ,后面那个等于-1-(-1)&＃61;0

如果 $l\leq x\leq r$ ,后面那个等于0-(-1)&＃61;1

如果 r<x<p ,后面那个等于0-0&＃61;0

如果存在x满足 $2px\mod2q \in [l,r]$ ,那么一定满足 $\sum_{x&＃61;a}^{b}\frac{2px-l}{2q}-\frac{2px-r-1}{2q}\geq 0$

后面这个其实就是一个类欧几里德的东西&＃xff0c;(类欧几里德就不展开讲了&＃xff0c;这里就用了个板子)然后我们就能二分出来 $2px\mod2q$ 对q的最小偏差d

也就是我们知道 $2px\mod 2q &＃61;q-d$ 和 $2px\mod 2q &＃61;q&＃43;d$

现在我们要还原x的值&＃xff0c;发现这俩个就是个同余方程&＃xff0c;我们用扩展欧几里得解一下就好了

2px&＃43;2qy&＃61;q&＃43;d

2px&＃43;2qy&＃61;q-d

还原出来x记得要把x再更新到 [a,b] 这个区间里&＃xff0c;取两者的最小值就行了

代码

#include using namespace std; typedef long long ll; const ll N &＃61; 1e5&＃43;5; const ll mod &＃61;1e9&＃43;7; ll calc(ll a,ll b,ll c,ll n){//类欧几里德if(n<0)return 0;if(n&＃61;&＃61;0)return b/c;if(a>&＃61;c||b>&＃61;c)return n*(n&＃43;1)/2*(a/c)&＃43;(n&＃43;1)*(b/c)&＃43;calc(a%c,b%c,c,n);ll m&＃61;(a*n&＃43;b)/c;return m*n-calc(c,c-b-1,a,m-1); } ll a,b,p,q,Q,P,x,y,g; bool check(ll l,ll r){return calc(P,Q-l,Q,b)-calc(P,Q-l,Q,a-1)-calc(P,Q-r-1,Q,b)&＃43;calc(P,Q-r-1,Q,a-1);//这里的Q-l和Q-r-1和l,r-1是一样的&＃xff0c;只不过防止了负数 } ll exgcd(ll a,ll b,ll &x,ll &y){//扩展欧几里得if(!b){x&＃61;1;y&＃61;0;return a;}ll g&＃61;exgcd(b,a%b,x,y);ll tmp&＃61;x;x&＃61;y;y&＃61;tmp-(a/b)*y;return g; } void solve(){cin>>a>>b>>p>>q;Q&＃61;q<<1;P&＃61;p<<1;ll l&＃61;0,r&＃61;q,mid;while(l<&＃61;r){//二分偏差mid&＃61;l&＃43;r>>1;ll L&＃61;q-mid,R&＃61;q&＃43;mid;//偏差后的两个值if(check(L,R))r&＃61;mid-1;else l&＃61;mid&＃43;1;}g&＃61;exgcd(P,Q,x,y);ll ans&＃61;1e18;//默认最大值if((q-l)%g&＃61;&＃61;0){ll t&＃61;Q/g,now&＃61;(x*((q-l)/g)%t&＃43;t)%t;while(now>&＃61;a)now-&＃61;t;//限制成最小while(now&＃61;a)now-&＃61;t;//限制成最小while(now} int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _&＃61;1;cin>>_;while(_--){solve();}return 0; } /* */

推荐阅读

tree
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
tree
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
tree
C++实现经典排序算法

本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出，帮助读者全面了解这些排序方法的特点。 ... [详细]

蜡笔小新 2024-12-27 19:25:14
ip
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
string
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
string
火星商店问题：线段树分治与持久化Trie树的应用

本题涉及编号为1至n的火星商店，每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品，以及查询某段时间内某些商店中所有商品（含永久商品）与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]

蜡笔小新 2024-12-27 21:23:11
string
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
ip
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
string
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
tree
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
io
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
io
数据库内核开发入门 | 搭建研发环境的初步指南

本课程将带你从零开始，逐步掌握数据库内核开发的基础知识和实践技能，重点介绍如何搭建OceanBase的开发环境。 ... [详细]

蜡笔小新 2024-12-27 16:38:48
io
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
io
组合数学问题：棋盘上的组合数计算

本文探讨了如何在模运算下高效计算组合数C(n, m)，并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元，从而实现除法取余的计算。 ... [详细]

蜡笔小新 2024-12-26 21:41:44
io
Splay Tree 区间操作优化

本文详细介绍了使用Splay Tree进行区间操作的实现方法，包括插入、删除、修改、翻转和求和等操作。通过这些操作，可以高效地处理动态序列问题，并且代码实现具有一定的挑战性，有助于编程能力的提升。 ... [详细]

蜡笔小新 2024-12-26 18:47:12

mobiledu2502916313

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章