您的位置:首页 > 房产 > 建筑 > 吴忠网络推广怎么做_义乌小商品批发网_佛山seo培训机构_微信朋友圈推广平台

吴忠网络推广怎么做_义乌小商品批发网_佛山seo培训机构_微信朋友圈推广平台

2024/12/23 16:16:56 来源:https://blog.csdn.net/white__ice/article/details/142371219  浏览:    关键词:吴忠网络推广怎么做_义乌小商品批发网_佛山seo培训机构_微信朋友圈推广平台
吴忠网络推广怎么做_义乌小商品批发网_佛山seo培训机构_微信朋友圈推广平台

[ABC266F] Well-defined Path Queries on a Namori

题面翻译

题目描述

给定一张有 N N N 个点、 N N N 条边的简单连通无向图和 Q Q Q 次询问,对于每次询问,给定 x i , y i x_i,y_i xi,yi,表示两点的编号,请你回答第 x i x_i xi 个点和第 y i y_i yi 个点之间是否有且仅有一条简单路径。

  • 什么是简单路径?

如果路径上的各顶点均不重复,则称这样的路径为简单路径。

输入格式

第一行包含一个整数 N N N

接下来 N N N 行,每行两个整数 u i , v i u_i,v_i ui,vi,表示第 i i i 条边连接的两个点;

再接下来一行包含一个整数 Q Q Q

最后 Q Q Q 行,每行两个整数 x i , y i x_i,y_i xi,yi,含义见题目描述。

输出格式

对于每次询问,输出一个字符串 YesNo,分别表示两点之间是否仅存在一条简单路径,每个询问分别输出一行。

样例

见原题面。

样例解析

样例 #1 解析:

对于第一次询问,从 1 1 1 2 2 2 有两条简单路径 ( 1 , 2 ) (1,2) (1,2) ( 1 , 3 , 2 ) (1,3,2) (1,3,2),所以输出 No

对于第二次询问,从 1 1 1 4 4 4 仅有一条路径 ( 1 , 4 ) (1,4) (1,4),所以输出 Yes

对于第三次询问,从 1 1 1 5 5 5 有两条简单路径 ( 1 , 2 , 5 ) (1,2,5) (1,2,5) ( 1 , 3 , 2 , 5 ) (1,3,2,5) (1,3,2,5),所以输出 No

数据范围

对于 30 % 30\% 30% 的数据, N ≤ 100 N \le 100 N100 Q ≤ N ( N − 1 ) 2 Q \le \frac{N(N-1)}{2} Q2N(N1)

对于 100 % 100\% 100% 的数据, 3 ≤ N ≤ 2 × 1 0 5 3 \le N \le 2 \times 10^5 3N2×105 1 ≤ u i < v i ≤ N 1 \le u_i<v_i \le N 1ui<viN 1 ≤ Q ≤ 2 × 1 0 5 1 \le Q \le 2 \times 10^5 1Q2×105 1 ≤ x i < y i ≤ N 1 \le x_i < y_i \le N 1xi<yiN,保证图没有重边或自环,且给定询问均不重复。

翻译 by @CarroT1212

题目描述

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ N $ 辺の連結な単純無向グラフ $ G $ が与えられます。$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に結んでいます。

以下の $ Q $ 個のクエリに答えてください。

  • 頂点 $ x_i $ から頂点 $ y_i $ に向かう単純パス(同じ頂点を $ 2 $ 度通らないパス)が一意に定まるか判定せよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_N $ $ v_N $ $ Q $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_Q $ $ y_Q $

输出格式

$ Q $ 行出力せよ。

$ i\ (1\ \leq\ i\ \leq\ Q) $ 行目には、頂点 $ x_i $ から頂点 $ y_i $ に向かう単純パスが一意に定まる場合 Yes、そうでない場合 No を出力せよ。

样例 #1

样例输入 #1

5
1 2
2 3
1 3
1 4
2 5
3
1 2
1 4
1 5

样例输出 #1

No
Yes
No

样例 #2

样例输入 #2

10
3 5
5 7
4 8
2 9
1 2
7 9
1 6
4 10
2 5
2 10
10
1 8
6 9
8 10
6 8
3 10
3 9
1 10
5 8
1 10
7 8

样例输出 #2

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No

提示

制約

  • $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
  • $ 1\ \leq\ u_i\ <\ v_i\leq\ N $
  • $ i\ \neq\ j $ ならば $ (u_i,v_i)\ \neq\ (u_j,v_j) $
  • $ G $ は $ N $ 頂点 $ N $ 辺の連結な単純無向グラフ
  • $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $
  • $ 1\ \leq\ x_i\ <\ y_i\leq\ N $
  • 入力は全て整数

Sample Explanation 1

頂点 $ 1 $ から $ 2 $ に向かう単純パスは $ (1,2),(1,3,2) $ と一意に定まらないので、 $ 1 $ 個目のクエリの答えは No です。 頂点 $ 1 $ から $ 4 $ に向かう単純パスは $ (1,4) $ と一意に定まるので、$ 2 $ 個目のクエリの答えは Yes です。 頂点 $ 1 $ から $ 5 $ に向かう単純パスは $ (1,2,5),(1,3,2,5) $ と一意に定まらないので、$ 3 $ 個目のクエリの答えは No です。

//2024.9.19
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 200005;
int n,q;int tag[oo],fa[oo];
bool vis[oo],is[oo];
struct nod{int v,nxt;}st[oo<<1];int head[oo],cnt;
__inline void add(int x,int y){st[++cnt]=(nod){y,head[x]};head[x]=cnt;}
main(void){//fre();cin.tie(0)->sync_with_stdio(0);cin >> n;for(int x,y,i=1;i<=n;++i){cin >> x >> y;add(x,y);add(y,x);}function<void(int,itn)>dfs1=[&](itn x,itn fat){if(vis[x]){int now=x; is[x]=1; x=tag[x];while(now!=x){is[x]=1;x=tag[x];}return void();} vis[x]=1;for(int i=head[x];i;i=st[i].nxt){int y=st[i].v;if(y==fat) continue;tag[y]=x; dfs1(y,x);}   };function<void(int,int)>dfs2=[&](int x,int fat){if(!is[x]) fa[x]=fa[fat];for(int i=head[x];i;i=st[i].nxt){int y=st[i].v;if(y==fat||is[y]) continue;dfs2(y,x);}}; dfs1(1,0);for(int i=1;i<=n;++i) if(is[i]){fa[i]=i;dfs2(i,0);}cin >> q;while(q--){int x,y;cin >> x >> y;cout << (fa[x]==fa[y]?"Yes":"No") << '\n';} cout << flush;exit (0);
}

直接在基环树上dfs,直接记录在环上各个点上分支的父亲即可


[ABC253F] Operations on a Matrix

题面翻译

存在 $ n $ 行 $ m $ 列的矩阵,给定 $ q $ 次操作,有 $ 3 $ 种格式。

  • 1 l r x:将 $ [l, r] $ 列的所有元素全部加上 $ x $。
  • 2 i x:将第 $ i $ 行的元素全部变为 $ x $。
  • 3 i j:输出矩阵 $ (i, j) $ 位置的元素值。

题目描述

縦 $ N $ 行、横 $ M $ 列の行列があり、はじめ全ての成分は $ 0 $ です。

以下のいずれかの形式で表されるクエリを $ Q $ 個処理してください。

  • 1 l r x : $ l $ 列目、$ l+1 $ 列目、$ \ldots 、 、 r $ 列目の成分全てに $ x $ を足す。
  • 2 i x : $ i $ 行目の成分全てを $ x $ で置き換える。
  • 3 i j : $ (i,\ j) $ 成分を出力する。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ Q $ $ \mathrm{Query}_1 $ $ \vdots $ $ \mathrm{Query}_Q $

$ i $ 番目に与えられるクエリを表す $ \mathrm{Query}_i $ は以下のいずれかの形式である。

$ 1 $ $ l $ $ r $ $ x $

$ 2 $ $ i $ $ x $

$ 3 $ $ i $ $ j $

输出格式

3 i j の形式の各クエリについて、答えを一行に出力せよ。

样例 #1

样例输入 #1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

样例输出 #1

1
2
2
5
3
4

样例 #2

样例输入 #2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

样例输出 #2

9000000000

样例 #3

样例输入 #3

10 10 10
1 1 8 5
2 2 6
3 2 1
3 4 7
1 5 9 7
3 3 2
3 2 8
2 8 10
3 8 8
3 1 10

样例输出 #3

6
5
5
13
10
0

提示

制約

  • $ 1\ \leq\ N,\ M,\ Q\ \leq\ 2\ \times\ 10^5 $
  • 1 l r x の形式のクエリについて、$ 1\ \leq\ l\ \leq\ r\ \leq\ M $ かつ $ 1\ \leq\ x\ \leq\ 10^9 $
  • 2 i x の形式のクエリについて、$ 1\ \leq\ i\ \leq\ N $ かつ $ 1\ \leq\ x\ \leq\ 10^9 $
  • 3 i j の形式にクエリについて、$ 1\ \leq\ i\ \leq\ N $ かつ $ 1\ \leq\ j\ \leq\ M $
  • 3 i j の形式のクエリが一個以上与えられる
  • 入力は全て整数

Sample Explanation 1

行列は次のように変化します。 $ \begin{pmatrix}\ 0\ &\ 0\ &\ 0\ \ 0\ &\ 0\ &\ 0\ \ 0\ &\ 0\ &\ 0\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 1\ &\ 0\ \ 1\ &\ 1\ &\ 0\ \ 2\ &\ 2\ &\ 2\ \ \end{pmatrix}\ \rightarrow\ \begin{pmatrix}\ 1\ &\ 4\ &\ 3\ \ 1\ &\ 4\ &\ 3\ \ 2\ &\ 5\ &\ 5\ \ \end{pmatrix} $

#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) (x & -x)
using namespace std;const int N = 200010;int n, m, Q, last[N];
LL tr[N], ans[N];
vector<int> v[N];struct query {int op, a, b, c;
} q[N];void add(int x, int c)
{for(int i = x; i <= m; i += lowbit(i)) tr[i] += c;
}LL sum(int x)
{LL res = 0;for(int i = x; i; i -= lowbit(i)) res += tr[i];return res;
}int main()
{cin >> n >> m >> Q;for(int i = 1; i <= Q; i++) {scanf("%d%d%d", &q[i].op, &q[i].a, &q[i].b);if(q[i].op == 1) scanf("%d", &q[i].c);else if(q[i].op == 2) last[q[i].a] = i;else v[last[q[i].a]].push_back(i);}for(int i = 1; i <= Q; i++) {if(q[i].op == 1) add(q[i].a, q[i].c), add(q[i].b + 1, -q[i].c);else if(q[i].op == 2) for(auto item : v[i]) ans[item] = q[i].b - sum(q[item].b);  else printf("%lld\n", ans[i] + sum(q[i].b));}return 0;
}

多板的主席树题呢


[ABC259F] Select Edges

题面翻译

给定一棵 n n n 个节点的树,每条边有一个权值 w i w_i wi

现要求选择一些边,使得每个节点 i i i 相邻的边中被选中的不超过 d i d_i di 条,请求出最大边权和。

题目描述

$ N $ 頂点の木が与えられます。 $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、$ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結ぶ重み $ w_i $ の辺です。

$ N-1 $ 本の辺のうちのいくつか( $ 0 $ 本または $ N-1 $ 本すべてでも良い)を選ぶことを考えます。 ただし、$ i\ =\ 1,\ 2,\ \ldots,\ N $ について、頂点 $ i $ に接続する辺は $ d_i $ 本までしか選べません。 選ぶ辺の重みの総和としてあり得る最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ d_1 $ $ d_2 $ $ \ldots $ $ d_N $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ w_{N-1} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

7
1 2 1 0 2 1 1
1 2 8
2 3 9
2 4 10
2 5 -3
5 6 8
5 7 3

样例输出 #1

28

样例 #2

样例输入 #2

20
0 2 0 1 2 1 0 0 3 0 1 1 1 1 0 0 3 0 1 2
4 9 583
4 6 -431
5 9 325
17 6 131
17 2 -520
2 16 696
5 7 662
17 15 845
7 8 307
13 7 849
9 19 242
20 6 909
7 11 -775
17 18 557
14 20 95
18 10 646
4 3 -168
1 3 -917
11 12 30

样例输出 #2

2184

提示

制約

  • $ 2\ \leq\ N\ \leq\ 3\ \times\ 10^5 $
  • $ 1\ \leq\ u_i,\ v_i\ \leq\ N $
  • $ -109 \leq w_i \leq 109 $
  • $ d_i $ は頂点 $ i $ の次数以下の非負整数
  • 与えられるグラフは木である
  • 入力はすべて整数

Sample Explanation 1

$ 1,\ 2,\ 5,\ 6 $ 番目の辺を選ぶと、選ぶ辺の重みは $ 8\ +\ 9\ +\ 8\ +\ 3\ =\ 28 $ となります。これがあり得る最大値です。

//2024.9.19
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr int oo = 300005;
int n,k;int d[oo];
itn mx[oo],f[oo],g[oo];
int cmp(itn x,itn y){return x>y;}
struct nod{itn v,w,nxt;}st[oo<<1];int cnt,head[oo];
__inline void add(int x,int y,itn z){st[++cnt]=(nod){y,z,head[x]};head[x]=cnt;}
main(void){//fre();cin.tie(0)->ios::sync_with_stdio(0);cin >> n;for(int i=1;i<=n;i++) cin>>d[i];for(int x,y,z,i=1;i<n;i++){cin >> x >> y >> z;add(x,y,z);add(y,x,z);}function<void(itn,int)>dfs=[&](int x,int fa){for(int i=head[x];i;i=st[i].nxt){int v=st[i].v;if(v==fa) continue;dfs(v,x); g[x]+=f[v];}int k=0;for(int i=head[x];i;i=st[i].nxt){int v = st[i].v;if(v!=fa) mx[++k]=g[v]+st[i].w-f[v];}sort(mx+1,mx+k+1,cmp);for(int i=1;i<d[x];i++){if(mx[i]<=0) break;g[x]+=mx[i];}f[x] = g[x];if(mx[d[x]]>0) f[x]+=mx[d[x]];if(!d[x]) g[x] = -1e9;for(int i=1;i<=k;i++) mx[i]=0;};dfs(1,0);cout << f[1] << '\n' << flush;exit (0);
}

考虑树上DP,在每个点枚举向父亲连边或向儿子连边

结合贪心,优先选大边权的,同时不选负边权的

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com