首页 > 其他分享 >2024牛客暑期多校训练营6

2024牛客暑期多校训练营6

时间：2024-08-01 23:28:45浏览次数：10  
标签：std head fa int 多校 kN 2024 牛客 id

目录

写在前面

比赛地址：https://ac.nowcoder.com/acm/contest/81601#question

以下按个人难度向排序。

纯纯战犯场呃呃呃呃做题不看题小保底当成 100 抽一发我草太唐了开局吃五发呃呃呃呃中期口了三题出来写出来两道最后好歹没太烂呃呃

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

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

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

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

H

签到。

模拟即可。

小保底是 90 发非常不行啊，不如我们马娘和 BA 直接吃井妈的

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e6 + 10;
//=============================================================
int n, cnt[310];
std::string s;
std::vector<char> pos;
//=============================================================
//=============================================================
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 >> s; 
    n = s.length();

    s = "$" + s;
    pos.clear();
    int flag = 1;

    if (n >= 10) {
      for (int i = 0; i <= 'U'; ++ i) cnt[i] = 0;
      for (int i = 1; i <= 9; ++ i) ++ cnt[(int)s[i]];
      for (int l = 1, r = 10; r <= n; ) {
        ++ cnt[(int)s[r]];
        if (cnt[(int)'3'] == 10) flag = 0;
        -- cnt[(int)s[l]];
        ++ l, ++ r;
      }
    }
    if (n >= 90) {
      for (int i = 0; i <= 'U'; ++ i) cnt[i] = 0;
      for (int i = 1; i <= 89; ++ i) ++ cnt[(int)s[i]];
      for (int l = 1, r = 90; r <= n; ) {
        ++ cnt[(int)s[r]];
        if (cnt[(int)'5'] == 0 && cnt[(int)'U'] == 0) flag = 0;
        -- cnt[(int)s[l]];
        ++ l, ++ r;
      }
    }

    for (auto c: s) if (c == '5' || c == 'U') pos.push_back(c);
    for (int i = 1, sz = pos.size(); i < sz; ++ i) {
      if (pos[i] != 'U' && pos[i - 1] != 'U') flag = 0;
    }
    std::cout << (flag ? "valid\n" : "invalid\n");
  }
  return 0;
}

B

数学，模拟。

考虑按照给定顺序进行切分。发现第一刀下去会变成 2 块，在此之后每刀经过 \(i\) 条线，答案便增加 \(i+1\)。然后手玩了下发现每刀经过的线数变化规律为：

\[(0, 1, 2, \cdots, k - 2), k - 1, k - 1, \cdots, k - 1, (k, k + 1, k + 2, \cdots, 2k - 2) \]

赛时懒了就直接模拟了，实际上可以 \(O(1)\) 算，有关平面图的证明详见官方题解。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, ans; 
signed main(){
	cin >> n >> k;
	if(n == k * 2) {
		cout << n << endl;
		return 0;
	}
	k = min(k, n - k);
	ans = 2;
	for(int i = 1; i <= k - 1; ++ i) ans += i + 1;
	for(int i = k; i <= n - k; ++ i) ans += k - 1 + 1;
	for(int i = n - k + 1, j = 0; i <= n - 1; ++ i, ++ j) ans += k + j + 1;
	cout << ans << endl;
	return 0;
}

D

连通性问题，Tarjan

所有 Lun 都要在环中，所有 Qie 都不在环中，容易想到当删完边后剩下的子图使用边双连通分量缩完点后一定会很好看——所有 Lun 均在边双中，而所有 Qie 将缩完点后的子图连成树状结构。

发现可以分别处理 Lun 和 Qie。考虑仅对所有 Lun 运行边双连通分量算法，保留其中所有在不小于 3 的边双中的 Lun，并将他们使用并查集缩成一个点。然后再枚举所有 Qie 进行加边，在此过程中使用并查集维护连通性即可。

若最后可以得到一张连通图则 YES，否则 NO。

//
/*
By:Luckyblock

https://www.luogu.com.cn/problem/P8436
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const int kM = 1e6 + 10;
//=============================================================
struct Edge {int u, v;};
std::vector <Edge> qie, ans;

int n, m;
int edgenum = 1, head[kN], v[kM], ne[kM];
int dfnnum, dfn[kN], low[kN];
bool bridge[kM], inans[kM];
int dccnum, indcc[kN], bel[kN];
std::vector <int> dcc[kN];

int fa[kN];
//=============================================================
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Tarjan(int u_, int from_) {
  dfn[u_] = low[u_] = ++ dfnnum;
  for (int i = head[u_]; i > 1; i = ne[i]) {
    int v_ = v[i];
    if (!dfn[v_]) {
      Tarjan(v_, i);
      if (low[v_] > dfn[u_]) bridge[i] = bridge[i ^ 1] = 1;
      low[u_] = std::min(low[u_], low[v_]);
    } else if (i != (from_ ^ 1)) {
      low[u_] = std::min(low[u_], dfn[v_]);
    }
  }
}
void Dfs(int u_, int id_) {
  indcc[u_] = true;
  bel[u_] = id_;
  dcc[id_].push_back(u_);
  for (int i = head[u_]; i > 1; i = ne[i]) {
    int v_ = v[i];
    if (indcc[v_] || bridge[i]) continue;
    Dfs(v_, id_);
  }
}
int find(int x_) {
  return (fa[x_] == x_) ? x_ : (fa[x_] = find(fa[x_]));
}
void merge(int x_, int y_) {
  int fx = find(x_), fy = find(y_);
  if (fx == fy) return ;
  fa[fx] = fy;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++ i) {
    int u_, v_; std::string w_; std::cin >> u_ >> v_ >> w_;
    if (w_ == "Lun") {
      Add(u_, v_), Add(v_, u_);
    } else {
      qie.push_back((Edge) {u_, v_});
    }
  }
  for (int i = 1; i <= n; ++ i) if (!dfn[i]) Tarjan(i, 0);
  for (int i = 1; i <= n; ++ i) if (!indcc[i]) Dfs(i, ++ dccnum);

  int flag = 1;
  for (int i = 1; i <= n; ++ i) fa[i] = i;

  for (int id = 1; id <= dccnum; ++ id) {
    for (auto u_: dcc[id]) {
      for (int i = head[u_]; i > 1; i = ne[i]) {
        if (inans[i] || inans[i ^ 1] || bel[v[i]] != id) continue;
        inans[i] = inans[i ^ 1] = 1;
        ans.push_back((Edge) {u_, v[i]});
        merge(u_, v[i]);
      }
    }
  } 
  for (auto e: qie) {
    if (find(e.u) == find(e.v)) continue;
    ans.push_back(e);
    merge(e.u, e.v);
  }
  for (int i = 1; i <= n; ++ i) if (find(i) != find(1)) flag = 0;

  if (!flag) {
    std::cout << "NO\n";
  } else {
    std::cout << "YES\n";
    std::cout << ans.size() << "\n";
    for (auto e: ans) std::cout << e.u << " " << e.v << "\n";
  }
  // printf("%d\n", dccnum);
  // for (int i = 1; i <= dccnum; ++ i) {
  //   printf("%d ", dcc[i].size());
  //   for (int j = 0, sz = dcc[i].size(); j < sz; ++ j) {
  //     printf("%d ", dcc[i][j]);
  //   }
  //   printf("\n");
  // }
  return 0;
}
/*
5 6
1 2 Lun
1 3 Lun
2 3 Lun
3 4 Lun
4 5 Lun
5 3 Lun
*/

A

树形 DP。

赛时 dztlb 大神单刷的，我看不懂他在写啥。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const double eps=1e-10;
const int N=510000;
int T,n;
int head[N],tot;
struct node{
	int to,nxt,w;
}e[N<<1];
void add(int u,int v,int w){
	e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot;
	e[tot].w=w;
}
double ans[N];
void dfs(int u,int fa,int dep,int x,int y){
	int cnt=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		++cnt;
	}
	if(cnt!=0)ans[u]=0;
	else {ans[u]=(double)x/(double)(x+y); return;}
	if(dep%2==1){
		
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(v==fa) continue;
			int dx=x,dy=y;
			if(e[i].w==1) ++dx;
			else ++dy;
			dfs(v,u,dep+1,dx,dy);
			if(ans[u]<=ans[v]+eps) ans[u]=ans[v];
		}
		if((x+y)!=0) {
			if(ans[u]>=(double)x/(double)(x+y))
			ans[u]=(double)x/(double)(x+y);
		}
	}else{
		ans[u]=(double)x/(double)(x+y);
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(v==fa) continue;
			int dx=x,dy=y;
			if(e[i].w==1) ++dx;
			else ++dy;
			dfs(v,u,dep+1,dx,dy);
			if(ans[u]>=ans[v]+eps) ans[u]=ans[v];
		}
	}
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;++i){
			head[i]=0;
			ans[i]=0;
		}
		tot=0;
		for(int i=1,u,v,w;i<n;++i){
			cin>>u>>v>>w;
			add(u,v,w);
			add(v,u,w);
		}
		dfs(1,0,1,0,0);
		printf("%.12Lf\n",ans[1]);
	}
	return 0;
}
/*
1
9
1 2 1
2 3 1
3 4 0
4 5 0
5 6 0
6 7 0
7 8 1
8 9 0

4
3
1 2 1
1 3 0
4
1 2 0
1 3 1
3 4 0
5
1 2 0
1 3 0
3 4 1
4 5 1
9
1 2 1
2 3 1
3 4 0
4 5 0
5 6 0
6 7 0
7 8 1
8 9 0
*/

F

图论，构造

想了下完全图的情况就直接秒了呃呃，然而一直被卡最后 5min 被 dztlb 大神叉掉了过了，实在刺激！！！

首先考虑 \(m=0\) 的情况，此时没有任何限制可以随便走；然后考虑有多棵树的情况，发现此时对于不同树间的节点没有任何限制，也可以随便走，于是仅需考虑单棵树的情况，并将所有单棵树构造的通路连起来即可。

对于单棵树，发现仅有菊花图的情况是无解的，此时仅可以将所有叶子构造成哈密尔顿路径但会剩下一个根，除此之外一定可以构造出完整的哈密尔顿路径；然后发现若有多棵树，无论有多少菊花图都有解。若其中某棵树是菊花图，则可先将其中所有叶子构造成一条通路，然后将剩下的根塞到到其他树构造出的通路里，再把所有树的通路连起来即可。

然后考虑对于某棵树应当如何构造哈密尔顿通路：

  • 若点数为 1，此时相当于没有限制，不看做菊花图，通路即为自身。
  • 若为点数不小于 2 的菊花图，则将其中所有叶子构造成一条通路，并额外记录一下根。
  • 否则直径长度一定不小于 4，发现此时可以以直径端点为根对树进行分层，每层间可以随便连，且非相邻层也可以随便连。于是想到奇偶分层，分别将奇数偶数层按照层数连成一条通路，并将奇数层接到偶数层后面即可。

此时所有树都变成了一条通路，若菊花图则外加一个根。考虑将所有菊花图的根插入到下一棵树的通路的最后，再将所有通路首尾相连即可。注意若最后一棵树是菊花图，则需要特判将最后一棵树的菊花插到整个通路的开头。

特判仅有一棵树且为菊花图时无解。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n, m, treenum, fa[kN], du[kN], bel[kN];
int edgenum, head[kN], v[kN << 1], ne[kN << 1]; 
bool vis[kN];
int from[kN], dis[kN];
int asshole[kN];
std::vector<int> tree[kN], seq[kN];
//=============================================================
int find(int x_) {
  return (fa[x_] == x_) ? x_ : (fa[x_] = find(fa[x_]));
}
void merge(int x_, int y_) {
  int fx = find(x_), fy = find(y_);
  if (fx == fy) return ;
  fa[fx] = fy;
}
void addedge(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void dfs(int u_, int fa_, bool flag) {
  if (flag) from[u_] = fa_; 
	dis[u_] = dis[fa_] + 1;
	for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    dfs(v_, u_, flag);
  }
}
void solve(int id_) {
  int road[2] = {tree[id_][0], tree[id_][0]}, maxdis = 0;
  dfs(road[0], 0, 0);
  for (auto x: tree[id_]) if (dis[x] > maxdis) road[0] = x, maxdis = dis[x];
  dfs(road[0], 0, 1);
  maxdis = 0;
  for (auto x: tree[id_]) if (dis[x] > maxdis) road[1] = x, maxdis = dis[x];

  if (maxdis == 1) {
    seq[id_].push_back(road[0]);
    return ;

  } else if (maxdis == 2) {
    asshole[id_] = road[0];
    seq[id_].push_back(road[1]);
    return ;

  } else if (maxdis == 3) {
    for (auto x: tree[id_]) {
      if (du[x] == (int) tree[id_].size() - 1) asshole[id_] = x;
      else seq[id_].push_back(x);
    }
    return ;

  }
  
  std::vector<int> temp;
  std::queue<int> q; q.push(road[0]);
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    vis[u_] = 1;
    if (dis[u_] % 2 == 1) temp.push_back(u_);
    else seq[id_].push_back(u_);

    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (vis[v_]) continue;
      q.push(v_);
    } 
  }
  for (auto x: temp) seq[id_].push_back(x);
}
//=============================================================
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 >> m;
    edgenum = treenum = 0;
    for (int i = 1; i <= n; ++ i) {
      fa[i] = i; 
      du[i] = head[i] = bel[i] = asshole[i] = 0;
      dis[i] = from[i] = vis[i] = 0;
      tree[i].clear(), seq[i].clear();
    }

    for (int i = 1; i <= m; ++ i) {
      int u_, v_; std::cin >> u_ >> v_;
      addedge(u_, v_), addedge(v_, u_);
      ++ du[u_], ++ du[v_];
      merge(u_, v_);
    }
    for (int i = 1; i <= n; ++ i) {
      if (!bel[find(i)]) bel[find(i)] = ++ treenum; 
      tree[bel[find(i)]].push_back(i);
    }
    for (int i = 1; i <= treenum; ++ i) solve(i);

    if (treenum == 1 && asshole[1]) {
      std::cout << -1 << "\n";
      continue;
    }
    if (asshole[treenum]) std::cout << asshole[treenum] << " ";
    for (int i = 1; i < treenum; ++ i) if (asshole[i]) seq[i + 1].push_back(asshole[i]);
    
    for (int i = 1; i <= treenum; ++ i) {
      for (auto x: seq[i]) std::cout << x << " ";
    }
    std::cout << "\n";
  }
  return 0;
}
/*
1
3 1
2 3
*/

I

DP。

实际上 2h 就秒了这个状态太显然了呃呃，然而直到结束都在调代码红温于是没时间写呃呃呃呃，要是有三个人铁拿下妈的

写在最后

学到了什么：

  • F：对情况讨论分类时，应当尽可能考虑全面每种情况的具体限制，以防多加限制导致需要特判一堆不必要的东西。

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

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

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

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

标签：std,head,fa,int,多校,kN,2024,牛客,id
From： https://www.cnblogs.com/luckyblock/p/18337795

相关文章

  • Gromacs-2024.1 GPU版本编译，--以RockyLinux系统为例
    1、首先安装好gcc套件、gcc-toolset-9、cmake、nvidia_driver、cuda、openmpi等软件；2、解压gromacs的源码包；3、编译：a.节点内并行多线程版本，首先sclenablegcc-toolset-9bash加载gcc9以支持C++17特性，cdgromacs-2024.2&&mkdirbuild&&cmake…/-DGMX_BUILD_OWN_FF......
  • 2024牛客多校第5场
    很神奇的场hh，大家一起坐牢，多好啊！B找规律，这种题一般都是多模拟几个数据然后猜出来#include<bits/stdc++.h>usingnamespacestd;inlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');for(;......
  • 2024.8.1 总结（集训）
    今天和昨天都是学图论。wwlw给我们讲了Tarjan求强连通分量、（有向图）缩点、欧拉路径和欧拉回路、2-SAT和某个奇妙的容斥DP题。感觉有收获，但是没有理解透。感觉lr好强啊，好多题好像都有思路。xwb也好强啊，在洛谷团队里的图论题单里rank1，1200分。我今天的主要问题还是理解......
  • 2024.8.1随笔
    前言今天下午最后的时间不想写题了，于是就准备拿来随便写写什么。上午讲的是一些图论中常见的考点的应用（大概），题目难度都在蓝到紫，感觉也不是完全不可做，或多或少都能有一些想法，有时能想到点子上，但也常常乱整。今天讲了有关连通分量、欧拉路、2-sat等知识的题，其中2-sat我全部遗......
  • 河南萌新联赛2024第（三）场：河南大学
    河南萌新联赛2024第（三）场：河南大学前言这场应该算是比较简单的了，隔壁都有佬ak了，咱只有8t，还是得加训。A-圆周率日挑战_河南萌新联赛2024第（三）场：河南大学(nowcoder.com)思路Python最有用的一集。抄了个500行的浮点高精度代码爆内存了，改了两个小时也没过，崩溃。代码n=in......
  • 2024牛客暑期多校训练营6
    Abstract好难qwqA-CakeIdea全是博弈！首先来解释题目意思。phase1：给出一颗树，根节点为1，树上每一条边的权值为0或者1。初始时刻，根节点处有一只小马，小G和小O依次控制小马移动，每次只能向子节点移动，若当前节点是叶节点，phase1结束。在移动的过程中，需要记录经过的边的......
  • 2024牛客暑期多校训练营6 A Cake
    题目大意详细题目传送门\(A\)和\(B\)要从轮流走，从根到一个叶子节点位置，\(A\)先。树有边权\(0,1\)，按照顺序经过的边权按字符串拼接得到一个串\(S\)。现在\(B\)可以把\(1\)拆分成任意个分数（但不能超过\(S\)的长度，且分数可以为空,）两人按照\(S\)串的顺序选取，如果\(S_......
  • 喜报 | 极限科技入选北京市 2024 年第一批科技中小企业名单
    2024年7月24日，北京市科学技术委员会、中关村科技园区管理委员会发布《关于北京市2024年第一批拟入库科技型中小企业名单的公示》。根据《科技型中小企业评价办法》(国科发政〔2017〕115号)和《科技型中小企业评价服务工作指引》(国科火字〔2022〕67号)有关规定，极限数据（北......
  • 2024.8 - 做题记录与方法总结
    2024.8-RecordofQuestionsandSummaryofMethodology先分享一个歌单：永无止境的八月！2024/08/01先来点重量级的P4768[NOI2018]归程题面：[NOI2018]归程题目描述本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个\(n\)个节......
  • 2024暑假集训测试17
    前言比赛链接。T1没加记忆化莫名原因T飞了，T2没做过IO交互不知道咋测样例干脆没交，T3到现在还不知道为啥爆零了，赛时不知道咋合并背包根本不敢打，离线下来寻思快点结果全死了，T4不可做题。还是老毛病，遇到之前见的不多题型（尤其是T1、T2放）就寄，这次T1倒是没卡住（但是挂分......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99