2024牛客暑期多校训练营5

标签：std 实链 fa int 多校 son 2024 牛客 now

写在前面
E
L
B
H
K
G
J
写在最后

写在前面

比赛地址：https://ac.nowcoder.com/acm/contest/81600。

以下按个人难度向排序。

妈的坐牢场啊前期除了日常战犯环节嗯吃三发之外顺的一批，后面 4h 一直在 J 上坐牢最后样例都没过呃呃呃呃，还剩 1.5h dztlb 大神说会 K 了但是以为 J 能调出来没给他来一发亏了妈的

最后 dztlb 大神直接打了半个小时法环哈哈

置顶广告：中南大学 ACM 集训队绝赞招新中！

有信息奥赛基础，获得 NOIP 省一等奖并达到 Codeforces rating 1900+ 或同等水平及以上者，可以直接私聊我与校队队长联系，免选拔直接进校集训队参加区域赛！

没有达到该水平但有志于 XPCX 赛事请关注每学年开始的 ACM 校队招新喵！

到这个时候了还缺队友实在不妙！求求求求快来个大神带我呜呜呜呜

E

签到。

dztlb 大神秒了，我看都没看。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t;
int a[N],b[N];
signed main(){
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int ans=0,cnt=0;
		for(int i=1;i<=n;++i){
			cin>>a[i];
		}
		for(int i=1;i<=n;++i){
			cin>>b[i];
		}
		for(int i=1;i<=n;++i){
			if(a[i]>b[i]) ++ans;
			if(a[i]==b[i]) ++cnt;
		}
		ans+=(cnt/2);
		if(cnt%2==1) ++ans;
		cout<<ans<<'\n';
	}
	return 0;
}

L

签到。

当 \(x=y\) 时，有 \((x + 1)(y - 1) = xy - x - y + 1 < xy\)，则应当尽可能使所有数平均从而最大化乘积。

发现数据范围很小，于是直接暴力模拟操作，从前往后枚举每个位置并对该位置操作，令他与之前的比他小的数平均即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL p = 998244353;
//=============================================================
int n;
LL a[10010];
//=============================================================
//=============================================================
int main() {
//   freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i];

    std::priority_queue<LL> q;
    for (int i = 1; i <= n; ++ i) {
      while (!q.empty() && (-q.top()) < a[i]) {
        LL x = -q.top(); q.pop();
        -- a[i], q.push(-(x + 1));
      }
      q.push(-a[i]);
    }
    LL ans = 1;
    while (!q.empty()) ans = ans * (-q.top()) % p, q.pop();
    std::cout << ans << "\n";
  }
  return 0;
}

B

讨论，结论。

神必分类讨论题，一块手玩了下就出来了，直接看代码吧。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t;
int n,m,a,b;
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>a>>b;
		if(n==1&&m==2){
			puts("Yes"); continue;
		}
		if(n==2&&m==1){
			puts("Yes"); continue;
		}
		if(a==1&&b==1){
			if(n%2==0||m%2==0){
				puts("Yes"); continue;
			}
		}
		if(a==1&&b==0){
			if(n==1&&m%2==0){
				puts("Yes"); continue;
			}
			if(m==1&&n%2==0){
				puts("Yes"); continue;
			}
		}
		if(a==0&&b==1){
			if(n%2==0&&m%2==0){
				puts("Yes"); continue;
			}
			if(n%2==0&&m>1){
				puts("Yes"); continue;
			}
			if(m%2==0&&n>1){
				puts("Yes"); continue;
			}
		}
		puts("No");
	}
	return 0;
}

H

暴力，结论。

两个人同时发现这个结论之后笑嘻了然后一发过了，本场最爽的一刻，后面就一直坐牢了。

显然经过的链上节点权值是单调递减的。对于一张已标号的图，每次进行移动 \(u\rightarrow v\) 时，\(v\) 的权值是最小的，则之后一定不会经过 \(u\) 的其他出边指向的点。即如果考虑枚举起点后直接搜索路径，每次转移后新增的合法状态数量并非指数级别，而仅有出度级别。于是想到直接枚举起点爆搜，并对于每个位置状压维护之后不能经过的点集，复杂度大概就是对的，随便写了发就过了哈哈。

实际理论复杂度上界为 \(O(n\times 3^{\frac{n}{3}})\) 级别，证明官方题解写得很详细不再赘述。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=20000;
int n,m;
int head[N],tot;
struct node{
	int to,nxt;
}e[N<<1];
void add(int u,int v){
	e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;
}
int ans=0;
void dfs(int u,int t,int len){
	int tmp=0;
	ans=max(ans,len);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		tmp+=(1ll<<v);
	}
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(((t>>v)&1)==0){
			dfs(v,t|tmp,len+1);
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(v,u);
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		int o=(1ll<<i);
		dfs(i,o,1);
	}
	cout<<ans;
	return 0;
}

K

DP，单调性。

神秘 DP 题，dztlb 大神场上发现了单调性之后秒了但是被我占着机子于是放弃，而我连提都看不懂直接弃疗。

G

结论，树上数据结构。

很有意思的题，感觉 LCT 学得还是不错的场上要是开了说不定能出，然而一直红温没开呃呃。

只有 access 操作，于是仅需考虑所有实链底的点是什么时候被操作的即可。发现对于一个给定的实链剖分方案，对于每条实链，当且仅当保证链上所有节点的虚边连接的子树中的所有点操作在该点之前，且实链底是实链上最后被操作的，即可保证该实链能够以给定形式存在。实链的操作顺序除了实链底必须最后操作之外其他点任意，考虑将每条实链缩成一个点，则仅需保证每个点比其子树中所有点更先操作即可。

发现上述条件是充要的。由组合意义，上述限制等价于在排列中，对于每条实链缩点后对应的点 \(u\) 的子树，其对应的大小为 \(\operatorname{size}_u\) 的集合，在排列中需要钦定实链底的点一定在该集合中所有数的最左侧，即会除掉 \(\operatorname{size}_u\) 的贡献。则总方案数即为：

\[\dfrac{n!}{\prod_{u\in S} \operatorname{size}_u} \]

其中 \(\operatorname{size}\) 为原树上子树大小，实链缩点后子树大小等价于实链顶的子树大小，则上述 \(S\) 为实链顶的点的集合。

初始时所有边均为虚边，由定义可知此时所有边均应看做长度为 2 的实链，即所有点均为实链顶对答案均有贡献，方案数即为 \(\frac{n!}{\prod_{1\le u\le n} \operatorname{size}_u}\)。在此之后需要一种数据结构来动态维护不断进行 access 操作时实链顶的点集。于是考虑直接用 LCT 做 access 来模拟该过程。access 过程中不断地断开之前的实链并接上新的实链，此时会被影响的点仅有之前的实链被断开部分的顶点，以及接上的实链的顶点，不断对这两个节点上的标记取反并直接计算对答案的影响即可。

总时间复杂度 \(O(n + q\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int p = 998244353;
//=============================================================
int n, q, sz[kN];
LL ans, fac[kN], invfac[kN], inv[kN];
std::vector<int> son[kN];
//=============================================================
LL qpow(LL x_, LL y_) {
  LL ret = 1;
  while (y_) {
    if (y_ & 1) ret = ret * x_ % p;
    x_ = x_ * x_ % p, y_ >>= 1ll;
  }
  return ret;
}
namespace LCT {
  #define f fa[now_]
  #define ls son[now_][0]
  #define rs son[now_][1]
  const int kNode = kN;
  int fa[kNode], son[kNode][2];
  bool tag[kNode];
  bool IsRoot(int now_) { //判断 now_ 是否为当前 Splay 的根
    return son[f][0] != now_ && son[f][1] != now_;
  }
  bool WhichSon(int now_) {
    return son[f][1] == now_;
  }
  void Rotate(int now_) {
    int fa_ = f, w = WhichSon(now_);
    if (!IsRoot(f)) son[fa[f]][WhichSon(f)] = now_;
    f = fa[f];
 
    son[fa_][w] = son[now_][w ^ 1];
    fa[son[fa_][w]] = fa_;
 
    son[now_][w ^ 1] = fa_;
    fa[fa_] = now_;
  }
  void modify(int now_) {
    tag[now_] ^= 1;
    if (tag[now_]) ans = ans * sz[now_] % p;
    else ans = ans * inv[sz[now_]] % p;
  }
  void Splay(int now_) {
    for (; !IsRoot(now_); Rotate(now_)) {
      if (!IsRoot(f)) Rotate(WhichSon(f) == WhichSon(now_) ? f : now_);
    }
  }
  int Find(int now_) { //找到 now_ 所在原树的根
    while (ls) now_ = ls; //使得树中由根->now 的链成为实链，构造出由它们组成的 Splay，再找到 Splay 中序遍历的第一个元素，即为原树的根。
    return now_; 
  }
  void Access(int now_) { //使得树中由根->now 的链成为实链，构造出由它们组成的 Splay，满足 Splay 的中序遍历深度递减的性质。
    //自下向上构建，舍弃父亲的原有右儿子，换成 -> last 的链。
    for (int last_ = 0; now_; last_ = now_, now_ = f) {
      Splay(now_);
      if (rs) modify(Find(rs));
      rs = last_;
      if (rs) modify(Find(rs));
    }
  }
  void Link(int x_, int y_) { //加边 (x,y)
    fa[x_] = y_;
  }
}
void dfs(int u_) {
  sz[u_] = 1;
  for (auto v_: son[u_]) dfs(v_), sz[u_] += sz[v_];
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> q;

  fac[0] = inv[0] = invfac[0] = 1;
  for (int i = 1; i <= n; ++ i) fac[i] = fac[i - 1] * i % p;
  invfac[n] = qpow(fac[n], p - 2);
  for (int i = n - 1; i >= 0; -- i) invfac[i] = invfac[i + 1] * (i + 1) % p;
  for (int i = 1; i <= n; ++ i) inv[i] = invfac[i] * fac[i - 1] % p;

  for (int i = 2; i <= n; ++ i) {
    int fa; std::cin >> fa;
    son[fa].push_back(i);
    LCT::Link(i, fa);
  }
  dfs(1);

  ans = fac[n];
  for (int i = 1; i <= n; ++ i) ans = ans * inv[sz[i]] % p;
  while (q --) {
    int x; std::cin >> x;
    LCT::Access(x);
    std::cout << ans << "\n";
  }
  return 0;
}

J

DP。

神必计数 DP，赛时光想着拉一条链出来往上接无标号有根树了呃呃，然而假假假假假会被重复情况卡死嗯控我 4h。

摆了。

写在最后

学到了什么：

H：发现决策之后会使之后的许多决策无效，则有用状态并不多，可考虑暴力。
G：挖掘给定过程性质，考虑从中发现固定的操作策略，对于操作顺序问题在此基础上考虑组合含义。

结尾广告：中南大学 ACM 集训队绝赞招新中！

有信息奥赛基础，获得 NOIP 省一等奖并达到 Codeforces rating 1900+ 或同等水平及以上者，可以直接私聊我与校队队长联系，免选拔直接进校集训队参加区域赛！

没有达到该水平但有志于 XPCX 赛事请关注每学年开始的 ACM 校队招新喵！

到这个时候了还缺队友实在不妙！求求求求快来个大神带我呜呜呜呜

标签：std,实链,fa,int,多校,son,2024,牛客,now
From： https://www.cnblogs.com/luckyblock/p/18341763

2024牛客暑期多校训练营5

写在前面

E

L

B

H

K

G

J

写在最后

相关文章

赞助商

阅读排行