首页 > 其他分享 >牛客暑假多校 2023 第三场

牛客暑假多校 2023 第三场

时间：2023-07-25 12:14:14浏览次数：43  
标签：ch num int 多校 kN 牛客 le include 第三场

写在前面

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

发生了这种事……气槽她气得吐槽了啊！

以下按个人向难度排序。

A

签到。

除非 \(x=0\) 否则可以调整为任意数，步数即两数之差。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
//=============================================================
LL a, b;
int n1, n2;
char s1[110], s2[110];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  scanf("%s", s1 + 1), scanf("%s", s2 + 1);
  n1 = strlen(s1 + 1), n2 = strlen(s2 + 1);

  for (int i = 1; i <= n1; ++ i) {
    a = 2ll * a + s1[i] - '0';
  }
  for (int i = 1; i <= n2; ++ i) {
    b = 2ll * b + s2[i] - '0';
  }

  if (a == 0ll && b != 0ll) printf("-1\n");
  else printf("%lld\n", b > a ? b - a : a - b);
  return 0;
}

H

发现给定操作不会影响 \(\sum a_i\)，显然只通过给定操作可以构造出所有和为 \(\sum a_i\) 的数列 \(a\)。问题变为是否能将 \(\sum a_i\) 分解为 \(n\) 个质数之和。

显然考虑哥德巴赫猜想：

  • \(n=1\)：直接判质数。
  • \(n=2\)：若 \(a_1+a_2\) 为奇数，由于奇数为偶数和奇数之和，则这个偶数只能为 2，可行当且仅当 \(a_1+a_2-2\) 为质数；若 \(a_1+a_2\) 为偶数则由哥德巴赫猜想可行当且仅当 \(a_1 + a_2\ge 4\)。
  • \(n>2\)：由哥德巴赫猜想当且仅当 \(\sum a_i \ge 2\times n\) 时可行。

D

手玩一下发现当且仅当矩阵全 0 或全 1 时才满足 \(\min(r_i)\ge \max(c_j)\)。

又发现如果矩阵可以转换为全 0 或全 1，那么所有行与第一行一定是相同或相反的关系；所有列与第一列一定是相同或相反的关系。将所有行/列翻转到与第一行/列相同后，再在另一个方向翻转即可得到全 0/全 1。

检查上述性质是否存在，如果存在再考虑操作步数最少的方案进行翻转即可。

J

发现如果是 DAG 拓扑序即答案，主要问题在如何处理环。

又发现对于一个有向完全图仅需构造正序和反序两个序列即可，则答案一定不超过两个序列。

于是还是考虑拓扑序。先 Tarjan 缩点，然后在缩点后的 DAG 上跑出拓扑序，连通块内部的点顺序任意，然后将拓扑序正序倒序输出即可。

//知识点：缩点
/*
By:Luckyblock
*/
#include <queue>
#include <stack>
#include <vector>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int kMaxn = 1e6 + 10;
const int kMaxm = 2e6 + 10;
//=============================================================
int n, m;
int e_num, head[kMaxn], v[kMaxm], ne[kMaxm];
int d_num, b_num, dfn[kMaxn], low[kMaxn], bel[kMaxn], sz[kMaxn];
int into[kMaxn];
std::vector <int> newv[kMaxn];
std::stack <int> st;
std::vector <int> node[kMaxn];

int ansnum = 1;
std::vector <int> ans1;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_) {
  v[++ e_num] = v_;
  ne[e_num] = head[u_];
  head[u_] = e_num;
}
void Tarjan(int u_) {
  dfn[u_] = low[u_] = ++ d_num;
  st.push(u_);
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (! dfn[v_]) {
      Tarjan(v_);
      Chkmin(low[u_], low[v_]);
    } else if (! bel[v_]) {
      Chkmin(low[u_], dfn[v_]);
    }
  }
  if (dfn[u_] == low[u_]) { //
    ++ b_num;
    for (int now = 0; now != u_; st.pop()) {
      now = st.top();
      bel[now] = b_num;
			node[b_num].push_back(now);
			++ sz[b_num];
			
			if (sz[b_num] > 1) ansnum = 2;
    }
  }
}
void Topsort() {
  std::queue <int> q;
  for (int i = 1; i <= b_num; ++ i) {
    if (! into[i]) {
      q.push(i);
    }
  }
  while (! q.empty()) {
    int u_ = q.front(); q.pop();
		for (int i = 0; i < sz[u_]; ++ i) ans1.push_back(node[u_][i]);

    for (int i = 0, lim = newv[u_].size(); i < lim; ++ i) {
      int v_ = newv[u_][i];
      into[v_] --;
      if (! into[v_]) {
        q.push(v_);
      }
    }
  }
}
//=============================================================
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read();
    AddEdge(u_, v_);
  }
  for (int i = 1; i <= n; ++ i) {
    if (! dfn[i]) Tarjan(i);
  }
  for (int u_ = 1; u_ <= n; ++ u_) {
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (bel[u_] == bel[v_]) continue ;
      newv[bel[u_]].push_back(bel[v_]);
      into[bel[v_]] ++;
    }
  }
  Topsort();
	if (ansnum == 1) {
		printf("1\n");
		for (int i = 0; i < n; ++ i) printf("%d ", ans1[i]);
		return 0;
	}

	printf("2\n");
	for (int i = 0; i < n; ++ i) printf("%d ", ans1[i]);
	printf("\n");
	for (int i = n - 1; i >= 0; -- i) printf("%d ", ans1[i]);
  return 0;
}

E

\(T\) 组数据，每组数据给定一 \(n\) 个节点 \(m\) 条边的有向图，边权均为 1，保证从节点 1 出发可以到达其他任意节点。判断以节点 1 为根的所有可能的 DFS 树是否均为以顶点 1 为根的最短路树。
\(1\le T\le 5\times 10^5\)，\(1\le n,m\le 5\times 10^5\)，\(1\le \sum n,\sum m\le 5\times 10^5\)。
3S，512MB。

乱搞题把、、、

首先考虑跑出最短路树，也就是 BFS 树对原图进行分层，然后考虑原图中每条边 \(<u, v>\) 的两个端点：

  1. 如果 \(v\) 在 \(u\) 的下一层：这条边本身合法，但这条边可能会对第 3 类边产生影响。
  2. 如果 \(u\) 和 \(v\) 在同一层：太好了，这条边一定会影响 DFS 树，直接 No。
  3. 如果 \(v\) 在 \(u\) 前面的层：如果 \(v\) 是 \(u\) 的支配点，即到达 \(u\) 之前一定会经过 \(v\)，那么这条边本身合法；否则可以不到达 \(v\) 而到达 \(u\)，进而影响到达 \(v\) 的最短路，即受到了第 1 类边的影响。

然而 DFS 求最短路实在是太假了，非常容易构造出非法的 DFS 树，而且这题数据还水，于是一车随机化和暴力都跑过去了。

赛时写了个啥那是，带着暴力的乱搞。对于 1、2 类边直接判，并且标记第 1 类边的终点；对于第三类边枚举 \(1\rightarrow u\) 上所有标记检查该边是否受到了影响。似乎可以证明最多只会跳 \(n\) 次？不太懂。

正解应当是支配树。

支配树板子怎么是黑题啊，跑了。

//
/*
By:Luckyblock
*/
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 5e5 + 10;
const int kM = 5e5 + 10;
//=============================================================
int n, m;
int edgenum, head[kN], v[kM], ne[kM];
bool vis[kN];
int near[kN], topnear[kN];
int dis[kN];

int fa[kN], size[kN], son[kN], top[kN], dep[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Init() {
  n = read(), m = read();
  edgenum = 0;
  for (int i = 1; i <= n; ++ i) {
    head[i] = fa[i] = 0;
    size[i] = top[i] = son[i] = dep[i] = 0;
    dis[i] = 0;

    vis[i] = 0;
    near[i] = 0;
  }

  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read();
    Add(u_, v_);
  }
}
void Bfs() {
  std::queue <int> q;
  dis[1] = 0;
  vis[1] = 1;

  q.push(1);
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (!vis[v_]) {
        dis[v_] = dis[u_] + 1;
        vis[v_] = 1;
        q.push(v_); 

        fa[v_] = u_;
      }
    }
  }
  // for (int i = 1; i <= n; ++ i) printf("%d ", dis[i]);
}
namespace Cut {
  void Dfs1(int u_, int fa_) {
    size[u_] = 1;
    dep[u_] = dep[fa_] + 1;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (fa[v_] != u_) continue;
      Dfs1(v_, u_);
      if (size[v_] > size[son[u_]]) son[u_] = v_;
      size[u_] += size[v_];
    }
  }
  void Dfs2(int u_, int top_) {
    top[u_] = top_;
    if (son[u_]) Dfs2(son[u_], top_);
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (fa[v_] != u_) continue;
      if (v_ == son[u_]) continue ;
      Dfs2(v_, v_);
    }
  }
  int Lca(int u_, int v_) {
    for (; top[u_] != top[v_]; u_ = fa[top[u_]]) {
      if (dep[top[u_]] < dep[top[v_]]) {
        std::swap(u_, v_);
      }
    }
    return dep[u_] < dep[v_] ? u_ : v_;
  }
}
void Dfs3(int u_, int fa_,int near_) {
  if (near[u_]) {
    near_ = u_;
  } else {
    near[u_] = near_;
  }
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (fa[v_] != u_) continue;
    Dfs3(v_, u_, near_);
  }
}
//=============================================================
int main() {
  freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    Bfs();
    Cut::Dfs1(1, 0), Cut::Dfs2(1, 1);

    int flag = 1;
    for (int u_ = 1; u_ <= n; ++ u_) {
      for (int i = head[u_]; i; i = ne[i]) {
        int v_ = v[i], lca = Cut::Lca(u_, v_);
        if (v_ == 1) continue;
        if (lca != u_ && lca != v_) {
          if (dis[u_] + 1 != dis[v_]) flag = 0;
          else near[v_] = v_, topnear[v_] = lca;
        } 
      }
    }
    Dfs3(1, 0, 0);

    for (int u_ = 1; u_ <= n; ++ u_) {
      for (int i = head[u_]; i; i = ne[i]) {
        int v_ = v[i], lca = Cut::Lca(u_, v_);
        if (v_ == 1) continue;
        if (lca == v_) {
          int fuck = near[u_];
          while (fuck) {
            if (dep[fuck] > dep[v_] && dep[v_] > dep[topnear[fuck]]) 
              flag = 0;
            fuck = near[fa[fuck]];
          }
        } else {
          if (dis[u_] + 1 != dis[v_]) flag = 0;
        }
      }
    }
    printf("%s\n", flag ? "Yes" : "No");
  }
  return 0;
}
/*
1
5 5
1 2
1 3
2 5
3 4
4 5

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

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

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

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

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

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

*/

B

赌狗啊船正在玩抽牌游戏。游戏规则如下：

  1. 牌堆可以看做一个由 \(1\sim 2\times n\) 组成的排列。
  2. 啊船首先抽出第一张牌。
  3. 根据最后抽出的牌的点数，啊船会猜测抽到的下一张牌的点数：如果这张牌点数不大于 \(n\) 她会猜测下一张牌点数大于 \(n\)，否则她猜测下一张牌点数不大于 \(n\)。
  4. 啊船抽出下一张牌并检验自己的猜测是否正确。如果正确则回到步骤 3，如果错误则结束游戏，啊船的得分为当前手中的牌数（包括现在猜错的这张）。
    显然牌堆的种类数共有 \((2\times n)!\) 种。

\(T\) 组数据，每组数据给定整数 \(n, m\)，表示啊船对 \((2\times n)!\) 种牌堆都玩了一次上述游戏，求她的得分总和对 \(m\) 取模的值。
\(1\le t\le 300\)，\(1\le n\le 300\)，\(2\le m\le 10^9\)，\(\sum n\le 300\)。
3S，256MB。

场上口了但是没时间写了。

DP。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 310;
//=============================================================
int n;
LL p;
LL C[kN << 1][kN << 1], fac[kN << 1];
LL ans, f[kN << 1][kN][2];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  fac[0] = 1, C[0][0] = 1;
  for (int i = 1; i <= 2 * n; ++ i) fac[i] = 1ll * fac[i - 1] * i % p;
  for (int i = 1; i <= 2 * n; ++ i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++ j) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      C[i][j] %= p;
    }
  }
  ans = 0;
}
void DP() {
  for (int i = 1; i <= 2 * n; ++ i) {
    for (int j = 0; j <= n; ++ j) {
      f[i][j][0] = f[i][j][1] = 0;
    }
  }
  f[0][0][0] = f[0][0][1] = 1;

  for (int i = 0; i <= 2 * n; ++ i) {
    for (int j = 0; j <= std::min(i, n); ++ j) {
      int k = i - j;
      if (k > n) continue;
      for (int l = 1; j + l <= n; ++ l) {
        if (i + l > 2 * n) continue;
        f[i + l][j + l][0] += f[i][j][1] * C[n - j][l] % p;
        f[i + l][j + l][0] %= p;
        
        ans += f[i][j][1] * C[n - j][l] % p * (l - 1) % p * (i + l) % p * fac[2 * n - i - l] % p;
        ans %= p;
      }
      for (int l = 1; k + l <= n; ++ l) {
        if (i + l > 2 * n) continue;
        f[i + l][j][1] += f[i][j][0] * C[n - k][l] % p;
        f[i + l][j][1] %= p;
      
        ans += f[i][j][0] * C[n - k][l] % p * (l - 1) % p * (i + l) % p * fac[2 * n - i - l] % p;
        ans %= p;
      }
    }
  }

  ans += 2 * (f[2 * n][n][0] + f[2 * n][n][1]) % p * n % p;
  ans %= p;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), p = read();
    Init();
    DP();
    printf("%lld\n", ans);
  }
  return 0;
}

标签：ch,num,int,多校,kN,牛客,le,include,第三场
From： https://www.cnblogs.com/luckyblock/p/17579541.html

相关文章

  • 牛客多校2023 第三场
    A签到，注意$0$的特判#include<bits/stdc++.h>usingnamespacestd;longlongx,y;intmain(){strings1,s2;cin>>s1;cin>>s2;intLen1=s1.length();intLen2=s2.length();for(inti=0;i<Len1;i++)......
  • 牛客多校 Day3
    H哥德巴赫J诈骗A签到D要么全\(0\)，要么全\(1\)B不得不说我真的纯纯SB真的。考场做法是先转成概率，然后就是计算长度大于等于\(i\)概率之和。\(f(i,j,0/1)\)前\(i+j\)个位置填\(i\)个小于等于\(n\)的数，\(j\)个大于\(n\)的数，最后一段是上升/下降的......
  • 牛客小白月赛 47 题解
    牛客小白月赛47A.牛牛的装球游戏标签暴力思路显然，答案为\(\pir^2l-[\frac{l}{2r}]*\frac{4\pir^3}{3}\)。时间复杂度为\(\mathcalO(1)\)。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;intT;doubleans,pi=3.141592653589;intt,h,r;int......
  • 牛客周赛Round4(java)
     Java组代码importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intn=scanner.nextInt();intm=scanner.nextInt();StringBuildersb=newStringB......
  • 牛客多校第二场-H
    H-0and1inBIT op1-->-x-1op2-->x+1由线性代数知识推每次操作要乘的矩阵，线段树维护一个矩阵信息 [op,d,1]就是代表一个f(x)=kx+b的方程，根据线性代数知识用矩阵表示该方程->f(x)=op*x+d,最后一个1只是凑矩阵用的，f代表该矩阵，因为刚开始就是x，所以op=1，d=0 #inclu......
  • 牛客多校1
    A.AlmostCorrect题意:给出一个长度为\(n\)的\(01\)串\(s\)，他一定是没有被排序的，构造不超过\(120\)对的操作序列，使得他不能对\(s\)排序，但可以对长度为\(n\)的其他\(01\)序列排序。思路：设\(s\)中最左边的位置为\(p\)，首先先让所有不在\(p\)位置的\(1\)与\(p\)操作，这样对原串没......
  • 牛客多校第二场补题
    牛客多校2I.LinkwithGomoku题意：两个人下五子棋，给出棋盘大小，构造一种方案，使得平局。思路：考虑这样构造xxxxooxxxxxxxxooooox以五一个为一个循环，多出来的部分也以这种方式构造，唯一的问题就是当有奇数行时会导致先手的棋子太多，因此当n为奇数时，让最后一行这样填充xoxoxox.......
  • 牛客第一场补题
    牛客多校1D.Chocolate题意：A、B轮流吃巧克力，当一个人选择一个点吃的时候，会把这个点及其左下的所有全部吃完，谁先吃完谁就输了，给出巧克力的大小，问谁会赢。思路：考虑当一个人吃完只剩一行或一列时，那么下一个吃的人就可以控制把最后一块留给这个人，因此当一个人吃完剩一行和一列的......
  • 杭电多校第一场补题
    杭电多校第一场1001Hide-And-SeekGame题意：给出一棵树，每次询问第一个人从Sa-Sb之间来回走，第二个人在Ta-Tb之间来回走，最早相遇的节点，如果无法相遇就输出-1做法：由于数据量是1e3级别，因此对于每一条路径都可以使用暴力找祖先的方法求出路径，然后对于路径上的每一个节点，其出现的时间......
  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99