牛客编程巅峰赛S1第3场

巅峰赛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;}
};