学校网站建设与维护,成都个人兼职做网站,网站建设报价单及项目收费明细表,提供网站建设的公司1#x1f40b;#x1f40b;史莱姆融合#xff08;钻石#xff1b;并查集#xff09;
时间限制#xff1a;1秒
占用内存#xff1a;128M
#x1f41f;题目描述 #x1f41f;题目思路
这道题目使用并查集#xff0c;同一集合的所有元素的最顶上的祖父节点是统一的。…1史莱姆融合钻石并查集
时间限制1秒
占用内存128M
题目描述 题目思路
这道题目使用并查集同一集合的所有元素的最顶上的祖父节点是统一的。这里记录每个集合的最左端元素最顶上的祖父节点和最右端元素便于集合更新。
MT3052 史莱姆融合_哔哩哔哩_bilibili
代码
#includebits/stdc.h
using namespace std;
const int N1e65;
int n,fa[N],so[N],nxt[N];//集合最左端fa集合最右端so下一个元素nxt
int find(int x) {return xfa[x]?x:(fa[x]find(fa[x]));}//找集合最左端元素
void merge(int i,int j)//集合合并
{int xfind(i),yfind(j);//两个集合的最左端if(x!y){nxt[so[x]]y;//第一个集合的最右端的下一个元素就是第二个集合的最左端元素fa[y]x;//更新最左端so[x]so[y];//更新最右端}
}
int main( )
{int x,y;cinn;for(int i1;in;i) fa[i]so[i]i;for(int i0;in-1;i){cinxy;merge(x,y);}for(int ifind(1);i;inxt[i]) couti ;return 0;
} 2区间最小值钻石ST表
时间限制1秒
占用内存128M
题目描述 题目思路
ST表用于解决区间最值问题基于分治和倍增思想。 ST表中定义了一个二维数组mn[N] [M]mn[i] [j]表示区间[i, i 2^j 1]内的最大值 根据倍增思想给出状态转移方程mn[i] [j] max(mn[i] [j - 1], mn[i 2^j - 1^] [j - 1])
ST表详解推荐ST表详解-CSDN博客
代码
#includebits/stdc.h
using namespace std;
const int N1e55;
int m,n,a[N],mn[N][50],Lg[N],ans;
void pre()
{Lg[1]0;for(int i2;in;i) Lg[i]Lg[i1]1;//求对数得到每段的区间结束位置
}
void ST_create()
{for(int i1;in;i) mn[i][0]a[i];//mn[i][j]当j为0时区间长度2^j为0则区间最大值就是区间的唯一元素a[i]for(int j1;jLg[n];j)//之前已经计算过区间长度为0的情况这里区间长度由2^1 到 2^Lg[n] {for(int i1;in-(1j)1;i)//确定区间左端点区间范围为[i, i 2^j - 1],所以 i 2^j - 1 n{mn[i][j]min(mn[i][j-1],mn[i(1(j-1))][j-1]);//状态转移方程}}
}
int ST_query(int l,int r)//区间查询
{int kLg[r-l1];return min(mn[l][k],mn[r-(1k)1][k]);
}
int main( )
{int a1,a2;cinnm;for(int i1;in;i) cina[i];pre();ST_create();while(m--){cina1a2;coutST_query(a1,a2)endl;}return 0;
} 3区间gcd钻石ST表
时间限制1秒
占用内存64M
题目描述 题目思路
这道题目也是使用ST表pre、create和query除了将min改成gcd没有变化gcd使用递归的方式求取。
MT3051 区间gcd_哔哩哔哩_bilibili
代码
用时少
#includebits/stdc.h
using namespace std;
const int N2e55;
int m,n,a[N],mn[N][50],Lg[N],ans;
int read()
{int ans0;char chgetchar();while(ch0||ch9) chgetchar();while(ch0ch9){ansans*10ch-0;chgetchar();}return ans;
}
void write(int x)
{if(x10) write(x/10);putchar(x%100);
}
int gcd(int a,int b){return b0?a:gcd(b,a%b);}
void pre()
{Lg[1]0;for(int i2;in;i) Lg[i]Lg[i1]1;//求对数得到每段的区间结束位置
}
void ST_create()
{for(int i1;in;i) mn[i][0]a[i];//mn[i][j]当j为0时区间长度2^j为0则区间最大值就是区间的唯一元素a[i]for(int j1;jLg[n];j)//之前已经计算过区间长度为0的情况这里区间长度由2^1 到 2^Lg[n] {for(int i1;in-(1j)1;i)//确定区间左端点区间范围为[i, i 2^j - 1],所以 i 2^j - 1 n{mn[i][j]gcd(mn[i][j-1],mn[i(1(j-1))][j-1]);//状态转移方程}}
}
int ST_query(int l,int r)//区间查询
{int kLg[r-l1];return gcd(mn[l][k],mn[r-(1k)1][k]);
}
int main( )
{int a1,a2;nread();mread();for(int i1;in;i) a[i]read();pre();ST_create();while(m--){a1read();a2read();ansST_query(a1,a2);write(ans);putchar(\n);}return 0;
}
占内存少
摘自——小码_63705
#includebits/stdc.h
using namespace std;
const int N3e55;
int gcd(int a,int b)
{if(!b) return a;else return gcd(b,a%b);
}
int dp[N][20],a[N],len[N];
int query(int l,int r)
{int klen[r-l1];return gcd(dp[l][k],dp[r-(1k)1][k]);
}
inline int read()
{char cgetchar();int x0,f1;while(c0||c9){if(c-) f-1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}
int main( )
{len[0]1;for(int i2;iN-2;i) len[i]len[i/2]1;int n;nread();int ncase;ncaseread();for(int i1;in;i) {*(ai)read();dp[i][0]a[i];}for(int j1;jlen[n];j){for(int i1;in;i){dp[i][j]gcd(dp[i][j-1],dp[i(1j-1)][j-1]);}}while(ncase--){int lread(),rread();printf(%d\n,query(l,r));}return 0;
} 4检测敌人钻石贪心
时间限制1秒
占用内存128M
题目描述 题目思路
贪心思路一个设备检测尽可能多的敌人。
不同于用设备找敌人这道题目需要用敌人找设备以敌人为圆心画圈找到可用检测到我的x轴上的所有范围那么在这个范围内放设备都可以检测到我。
贪心的实现就是通过对比两个区间是否有重叠得知可否共用设备。
【码蹄集进阶塔全题解08】算法基础贪心 MT2080 – MT2092_哔哩哔哩_bilibili
代码
#includebits/stdc.h
using namespace std;
const int N1005;
struct node
{double x,y,l,r;bool v;
}e[N];
bool cmp(node a,node b)
{return a.rb.r;
}
int main( )
{int n;double r;while(cinnr!(n0r0)){bool flagfalse;memset(e,0,sizeof(e));for(int i1;in;i){cine[i].xe[i].y;if(r*re[i].y*e[i].y) flagtrue;//以每个敌人为圆心画圆圆圈范围内的仪器能检测到敌人else//计算能检测到敌人的x轴坐标范围{e[i].l-sqrt(r*r-e[i].y*e[i].y)e[i].x;e[i].rsqrt(r*r-e[i].y*e[i].y)e[i].x;e[i].vfalse;}}if(flag){cout-1endl;continue;}sort(e1,e1n,cmp);int ans0;for(int i1;in;i){if(e[i].vfalse)//表示这个敌人还没能被检测到{for(int ji;jn;j){if(e[j].vfalsee[j].le[i].re[j].re[i].r) e[j].vtrue;//我们有重叠区域用一个设备就行了}e[i].vtrue;ans;//所需设备数加一}}coutansendl;}return 0;
} 5小码哥的福利钻石贪心
时间限制1秒
占用内存128M
题目描述 题目思路
贪心思路每次分甜品都要尽可能地达到平均值。
这道题目的思路就是将所有手下按耐受度排序将所有甜品按甜度排序找到能吃掉这个甜品的手下让他全部吃掉然后对所有手下吃掉的甜品数量进行分配。根据耐受度限制甜品只能往右分也就是往耐受度高的手下那里分那么每次都计算出来从我到最后一个手下我们吃的甜品数量的平均值然后如果我吃的比这个平均值多就把多的甜品分给下一个人以此类推我从头遍历到尾。
【码蹄集进阶塔全题解08】算法基础贪心 MT2080 – MT2092_哔哩哔哩_bilibili
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N55;
ll n,m,a[N],sum[N],ans;
struct node
{ll b,c;
}sweet[N];
int cmp(node a,node b){return a.bb.b;}
ll add(int l,int r)
{ll ans0;for(int il;ir;i) anssum[i];return ans;
}
int main( )
{cinn;ll maxm0;for(int i1;in;i){cina[i];maxmmax(maxm,a[i]);}sort(a1,a1n);cinm;for(int i1;im;i){cinsweet[i].b;if(sweet[i].bmaxm)//甜品的甜度超过手下的最大甜品耐受度了无法吃完{cout-1endl;return 0;}}for(int i1;im;i) cinsweet[i].c;sort(sweet1,sweet1m,cmp);//按照甜度大小排列for(int i1;im;i)//遍历所有甜品i{for(int j1;jn;j)//遍历所有手下j{if(sweet[i].ba[j]){sum[j]sweet[i].c;//手下j吃掉甜度为i的所有甜品break;}}}//平均化吃掉的数量//甜品转移只能向右转移也就是转移给耐受度更高的手下for(int i1;in;i)//遍历所有手下{ll tmp(add(i,n))/(n-i1);//将往右的这些所有吃的甜品数量平均if(tmpsum[i])//这个人吃多了分走甜品{sum[i1]sum[i]-tmp;sum[i]tmp;}}for(int i1;in;i) ansmax(ans,sum[i]);//找出最大sumcoutansendl;return 0;
} 6屠龙勇者黄金贪心
时间限制1秒
占用内存128M
题目描述 题目思路
贪心思想用最强的勇士砍最大的头。
那么就是将d和w数组分别排序最多有m-n个spare的勇士可以用来砍这个头所以对i来说最强的勇士就是第im-n个勇士如果这个最强的勇士都没法砍这个头那么就失败了。同样的贪心思想这些spare的勇士也是能力值低的那些。
代码
#includebits/stdc.h
using namespace std;
const int N1e55;
int d[N],w[N],n,m;
int main( )
{cinnm;for(int i1;in;i) cind[i];for(int i1;im;i) cinw[i];sort(d1,d1n);sort(w1,w1m);if(nm){coutNO;return 0;}for(int in;i1;i--){if(w[im-n]d[i])//最多有m-n个spare的勇士{coutNO;return 0;}}coutYES;return 0;
} 有问题我们随时评论区见~
⭐点赞收藏不迷路~
