巅峰赛S1第3场"/>
牛客编程巅峰赛S1第3场
A-找卧底
题意:
问给定的 n + 1 n+1 n+1个数中,哪个数出现了两次。
思路:
签到,直接做。
Code:
class Solution {
public:/*** * @param n int整型 * @param a int整型vector * @return int整型*/int search(int n, vector<int>& a) {// write code hereint cnt[200005];int ans=0;for(int i=0;i<=n;++i){cnt[a[i]]++;if(cnt[a[i]]==2){ans=a[i];}}return ans;}
};
B-父子情深
题意:
在一颗有 n n n 个结点且以 1 1 1 为根节点树上,起初每个结点的初始权值为 0 0 0 。
现在有 q q q 次操作,每次操作选择将以 r i r_i ri 为根节点的子树上的所有结点权值增加 x i x_i xi 。
求 q q q 次操作后从 1 1 1到 n n n 每个结点的权值。
思路:
比较经典的树上问题。这里仅抛出解法,不对代码思路进行讲解。
- 解法1: d f s dfs dfs序 + + +线段树区间修改、单点查询。
- 解法2:树剖。
d f s dfs dfs序 + + +线段树是老套路了,如果不了解的话可以做一下类似题:
Hdu-3974
Code:
class Solution {
public:/*** 从 1 到 n 每个结点的权值。* @param n int整型 * @param Edge Point类vector (u, v) 集合* @param q int整型 * @param Query Point类vector Point.x 为题中 r, Point.y为题中 v* @return long长整型vector*/long long tree[200005*4];long long lazy[200005*4];int d[200005];//Èint n,l,r;std::vector<int> v[200005];#define mid ((l+r)>>1)#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int cnt=0;int dfs_xu[200005];int st[200005*4];int ed[200005*4];void dfs(int x,int fa){st[x]=++cnt;for(int i=0;i<(int)v[x].size();++i){int y=v[x][i];if(y==fa)continue;dfs(y,x);}ed[x]=++cnt;}void pushdown(int l,int r,int rt){tree[rt<<1]+=1ll*(mid-l+1)*lazy[rt];tree[rt<<1|1]+=1ll*(r-mid)*lazy[rt];lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];lazy[rt]=0;} void pushup(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];}void build(int l,int r,int rt){if(l==r){tree[l]=0;return;}build(lson);build(rson);pushup(rt);}void update(int L,int R,int l,int r,int rt,int val){if(L<=l&&r<=R){tree[rt]+=(r-l+1)*val*1ll;lazy[rt]+=val*1ll;return ;}if(lazy[rt]!=0)pushdown(l,r,rt);if(L<=mid){update(L,R,lson,val);}if(R>mid){update(L,R,rson,val);}pushup(rt);}long long query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return tree[rt];}long long ans=0;if(lazy[rt]!=0)pushdown(l,r,rt);if(L<=mid){ans=query(L,R,lson);}if(R>mid){ans=query(L,R,rson);}return ans;}vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {// write code herefor(int i=0;i<n-1;++i){int l=Edge[i].x;int r=Edge[i].y;v[l].push_back(r);v[r].push_back(l);}dfs(1,1);build(1,cnt,1);for(int i=0;i<q;++i){int ri=Query[i].x;int vi=Query[i].y;update(st[ri],ed[ri],1,cnt,1,vi);}vector<long>ans;for(int i=1;i<=n;++i){//cout<<query(st[i],st[i],1,cnt,1)<<" ";ans.push_back(query(st[i],st[i],1,cnt,1));}return ans;}};
C-旋转跳跃
题意:
牛牛有一个长为 n n n 的排列 p p p ,与 m m m 对 ( x i , y i ) (x_i, y_i) (xi,yi)。
每对 ( x i , y i ) (x_i, y_i) (xi,yi) 表示可以将 p x i p_{x_i} pxi 的值与 p y i p_{y_i} pyi 的值互换。
m m m 对 ( x i , y i ) (x_i, y_i) (xi,yi) 的使用顺序与次数不限。
牛牛想知道,任意次操作之后他能得到的字典序最小的排列是什么。
输入:
第一个参数为 n n n, 1 ≤ n ≤ 100 , 000 1\leq n \leq 100,000 1≤n≤100,000
第二个参数为 m m m, 1 ≤ m ≤ 100 , 000 1\leq m \leq 100,000 1≤m≤100,000
第三个参数为初始排列 p p p, 1 ≤ p i ≤ n 1\leq p_i\leq n 1≤pi≤n
第四个参数为 m m m 对 ( x i , y i ) (x_i, y_i) (xi,yi), 1 ≤ x i , y i ≤ n , x i ≠ y i 1\leq x_i, y_i\leq n, x_i \neq y_i 1≤xi,yi≤n,xi=yi
思路:
- m m m对关系到最后会造成若干个联通块,一个联通块内的数字可以互相交换。不同联通块之间的数字无法交换。并查集维护。
- 要求字典序最小,即贪心,将联通块内的数字排序(小到大)即可,排序整体复杂度还是在 O ( n l o g n ) O(nlogn) O(nlogn)。
- 输出的时候用 c o n i con_i coni数组标记以 i i i为首的联通块目前输出了 c o n i con_i coni个。
Code:
/*** struct Point {* int x;* int y;* };*/class Solution {
public:/*** 返回牛牛所能得到的字典序最小的排列* @param n int整型 * @param m int整型 * @param perm int整型vector * @param Pair Point类vector * @return int整型vector*/int fa[200005];int con[200005];int find(int x){if(fa[x]!=x){fa[x]=find(fa[x]);}return fa[x];}void merge(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy){fa[fy]=fx;}}int num[200005];vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {// write code herefor(int i=1;i<=n;++i){fa[i]=i;}int cnt=0;for(int i=0;i<n;++i){num[++cnt]=perm[i];} for(int i=0;i<m;++i){int l=Pair[i].x;int r=Pair[i].y;merge(l,r);}vector<int>ans;vector<int>kep[100005];for(int i=1;i<=n;++i){int f=find(i);kep[f].push_back(num[i]);}for(int i=1;i<=n;++i){sort(kep[i].begin(),kep[i].end());}for(int i=1;i<=n;++i){int f=find(i);ans.push_back(kep[f][con[f]]);con[f]++;//cout<<kep[f][con[f]]<<" ";}return ans;}
};
更多推荐
牛客编程巅峰赛S1第3场
发布评论