2024牛客寒假算法基础集训营1（视频讲解全部题目）

2024牛客寒假算法基础集训营1（题目全解）

• A
• B
• C
• D
• E
• F
• G
• H
• I
• J
• K
• L
• M

  2024牛客寒假算法基础集训营1（视频讲解全部题目）

  

  A

  #include
  #define endl '\n'
  #define deb(x) cout 
  	int n; cin  n;
  	string s; cin  s;
  	bool f = false, F = false;
  	for(int i = 0; i  
  C
   
  #include
  #define endl '\n'
  #define int long long
  #define deb(x) cout 
  	int n, q, tc; cin  n  q >> tc;
  	vectort(n + 1);
  	vectors(n + 1);
  	vectorss(n + 1);
  	for(int i = 1; i 
  		cin > t[i];
  	}
  	sort(t.begin() + 1, t.end());
  	for(int i = 1; i 
  		s[i] = s[i - 1] + t[i];
  	}
  	for(int i = 1; i 
  		ss[i] = ss[i - 1] + s[i];
  	}
  	while(q--){
  		int M; cin  M;
  		int l = 1, r = n;
  		while(l > 1;
  			int cnt = n - mid + 1;
  			if(cnt * tc 
  				r = mid;
  			}else{
  				l = mid + 1;
  			}
  		}
  		if(l == n){
  			if(tc  M){
  				cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	t = 1;
  	//cin  t;
  	while(t--)
  	solve();
  }
  
  	int n, m; cin  n  m;
  	vector
  		cin  a[i];
  		cnt[a[i]] += 1;
  	}
  	if(n >= 30){
  		//一定要减少绝对值不等于1的数字个数。
  		for(auto [x, y]: cnt){
  			if(n - cnt[x] - cnt[x - 2] > 30)
  				continue;
  			int mul = 1;
  			bool flag = true;
  			for(int i = 0; i  1e9){
  					flag = false;
  					break;
  				}
  			}
  			if(flag)
  				ans.insert(mul);
  			mul = 1, flag = true;
  			for(int i = 0; i  1e9){
  					flag = false;
  					break;
  				}
  			}
  			if(flag)
  				ans.insert(mul);
  		}
  	}else{
  		//如果n 
  			a[i] -= tmp;
  		}
  		for(int i = -1e6; i 
  			int mul = 1;
  			bool flag = true;
  			for(int j = 0; j  x;
  		if(ans.count(x)){
  			cout 
  			cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	t = 1;
  	//cin  t;
  	while(t--)
  	solve();
  }
  
  	int n, m; cin  n  m;
  	vector
  		cin  a[i];
  	}
  	for(int i = 0; i > u >> v;
  		u --, v --;
  		b[i] = {u, v};
  	}
  	int ans = 11;
  	function dfs = [&](int u)->void{
  		
  		if(u >= m){
  			int sc = a[0];
  			int top = 1;
  			for(int i = 1; i  sc){
  					top ++;
  				}
  			}
  			ans = min(ans, top);
  			return;
  		}
  	
  		int x = b[u].first, y = b[u].second;
  		a[x] += 3;
  		dfs(u + 1);
  		//回溯
  		a[x] -= 3;
  		a[y] += 3;
  		dfs(u + 1);
  		
  		a[y] -= 3;
  		a[x] += 1, a[y] += 1;
  		dfs(u + 1);
  		a[x] -= 1, a[y] -= 1;
  	};
  	dfs(0);
  	cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	//t = 1;
  	cin  t;
  	while(t--)
  	solve();
  }
   
  F
   
  #include
  #define endl '\n'
  #define int long long
  #define deb(x) cout 
  	int res = 1;
  	while(b){
  		if(b & 1)
  			res = res * a % p;
  		a = a * a % p;
  		b = 1;
  	}
  	return res;
  }
  void init(){
  	fact[0] = infact[0] = 1;
  	for(int i = 1; i > m;
  	int res = 0;
  	for(int i = 0; i 
  		if((m - i) % 2){
  			res = ((res - (qmi(i, n, mod) * infact[i] % mod * infact[m - i] % mod)) % mod + mod) % mod;
  		}else{
  			res = (res + (qmi(i, n, mod) * infact[i] % mod * infact[m - i] % mod)) % mod;
  		}
  	}
  	cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	t = 1;
  	// cin  t;
  	init();
  	while(t--)
  	solve();
  }
  
  	int n, m; cin  n  m;
  	vector
  		cin  a[i].x >> a[i].y;
  	}
  	sort(a.begin(), a.end());
  	vectors(n + 1);
  	for(int i = 1; i 
  		s[i] = s[i - 1] + a[i].y;
  	}
  	int ans = m;
  	for(int i = n; i = 1; i --){
  		int dis = a[i].x - s[i];
  		if(dis > m){
  			continue;
  		}
  		ans = max(ans, m + s[i]);
  	}
  	cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	//t = 1;
  	cin  t;
  	while(t--)
  	solve();
  }
   
  H
   
  #include
  #define endl '\n'
  #define int long long
  #define deb(x) cout 
  	int n, m; cin  n  m;
  	vectorv(n), w(n);
  	for(int i = 0; i > v[i] >> w[i];
  	}
  	int ans = 0, pre = 0;
  	for(int i = 31; i >= 0; i --){
  		int x = pre;
  		if((m >> i) & 1){
  			x += (1 
  			if((x | w[j]) == x){
  				sum += v[j];
  			}
  		}
  		ans = max(ans, sum);
  	}
  	int sum = 0;
  	for(int j = 0; j > a[i];
  	}
  	auto check = [&](int dis)->bool{
  		// cout 
  			return false;
  		}
  		for(int i = 0; i  dis){
  				st.erase(*st.rbegin());
  			}
  			
  			if(!st.size()){
  				return false;
  			}
  			st.insert(a[i]);
  		}
  		return true;
  	};
  	int l = 0, r = 1e9;
  	while(l > 1;
  		if(check(mid)){
  			r = mid;
  		}else{
  			l = mid + 1;
  		}
  	}
  	cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	t = 1;
  	// cin  t;
  	while(t--)
  	solve();
  }
   
  K
   
  #include
  #define endl '\n'
  #define deb(x) cout 
  	if(x != p[x])
  		p[x] = find(p[x]);
  	return p[x];
  }
  void init(int x){
  	for(int i = 1; i 
  		p[i] = i;
  		root.insert(i);
  	}
  }
  void merge(int x, int y){
  	int px = find(x);
  	int py = find(y);
  	if(px != py){
  		if(in[px])
  		{
  			p[px] = py;
  			root.erase(px);
  		}
  		else
  		{
  			p[py] = px;
  			root.erase(py);
  		}
  	}
  }
  void dfs(int u, char answer){
  	if(st[nex[u]]){
  		if(answer == t[nex[u]]){
  			nums ++;
  		}
  		return;
  	}
  	
  	char nex_answer = choice[nex[u]][answer - 'A'];
  	t[nex[u]] = answer;
  	st[nex[u]] = true;
  	dfs(nex[u], nex_answer);	
  	st[nex[u]] = false;
  }
  void solve()
  {
  	int n; cin  n;
  	init(n);
  	for(int i = 1; i 
  		int x; string s;
  		cin  x  s;
  		choice[i] = s;
  		nex[i] = x;
  		in[x] ++;
  		merge(x, i);
  	}
  	int ans = 1;
  	for(auto x: root){
  		for(int i = 0; i  
  L
   
  #include
  #define endl '\n'
  #define deb(x) cout 
  	int c, d, h, w;
  	cin  c  d >> h >> w;
  	cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	//t = 1;
  	cin  t;
  	while(t--)
  	solve();
  }
   
  M
   
  #include
  #define endl '\n'
  #define deb(x) cout 
  	int n; cin  n;
  	if(n % 6)
  		cout 
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	int t;
  	//t = 1;
  	cin  t;
  	while(t--)
  	solve();
  }