2026牛客寒假算法基础集训营2
锐评
总共10个题，赛时AC了5道题，进了前1000名
赛时AC顺序A > B > I > F > H
赛后AC顺序E 、J
难度：J > H > E > F > I > B > A
A
题目链接：https://ac.nowcoder.com/acm/contest/120562/A
思路：最大场次不能比最小场次超过1
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int a, b, c, d;
std::cin >> a >> b >> c;
d = min({a, b, c});
a -= d;
b -= d;
c -= d;
if(a > 1 || b > 1 || c > 1){
std::cout << "NO\n";
}else{
std::cout << "YES\n";
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
B
题目链接：https://ac.nowcoder.com/acm/contest/120562/B
思路：
对于每一个数我们想要留下他到最后，就把其他数与最大值比较消除，最后最大值与最大值共同竞争就会一起消掉，最大值为奇数说明最大值一定不会消完，那最大值就输出1，其他值只能为0，如果最大值是偶数个，说明最大值的数最后一定会两两消除，输出0，其他值可以通过最大值来消掉最后输出1.
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n;
std::cin >> n;
std::vector<int> a(n);
for(auto &x : a) std::cin >> x;
int mx = *max_element(a.begin(), a.end());
int ans = 0;
for(int i = 0;i < n; i++) if(a[i] == mx) ans ++;
for(int i = 0;i < n; i++){
if(a[i] < mx){
if(ans & 1)
std::cout << 0;
else
std::cout << 1;
}else{
if(ans & 1){
std::cout << 1;
}else{
std::cout << 0;
}
}
}
std::cout << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
I
题目链接：https://ac.nowcoder.com/acm/contest/120562/I
思路：
1000...0001都是回文串
01111...11110也是回文串
所以我只需要看1的个数和0的个数只要大于1就一定能组成回文串
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
int n, m;
std::cin >> n >> m;
std::vector<string> s(n);
for(int i = 0;i < n; i++) std::cin >> s[i];
int ans = 0, cnt = 0;
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
if(s[i][j] == '1') ans ++;
else cnt ++;
}
}
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
if(s[i][j] == '0' && cnt == 1){
std::cout << 'N';
}else if(s[i][j] == '1' && ans == 1){
std::cout << 'N';
}else{
std::cout << 'Y';
}
}
std::cout << "\n";
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
F
题目链接：https://ac.nowcoder.com/acm/contest/120562/F
思路：
要使x^y最小，x,y都是a的倍数，假设x = az, y = bz;x^y=(az)^(bz) = z*(a^b)>=z
因此我们找到异或值为z的就行，看z的二进制，x就在z的二进制后面拉等长位的0,eg:z:10001,x:1000100000
y就在x上加个z，y:1000110001,这两异或一定为z。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
i64 n;
std::cin >> n;
i64 x = n;
std::vector<int> a;
while(x){
a.insert(a.begin(), x % 2);
x /= 2;
}
i64 ans = n, cnt = 0;
int len = a.size();
for(int i = 0;i < len; i++){
ans = ans * 2;
}
cnt = ans + n;
std::cout << ans << " " << cnt << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
H
题目链接：https://ac.nowcoder.com/acm/contest/120562/H
思路：
这里的权值指的是在给定区间[l, r]每次从[l,i]不同元素的个数的累加和。
我们用dp来转移，dp[0]先记录[1,n]的这个区间的权值，然后划分子区间子问题，删除从[1,n]逐个往前删，先删除1然后删除2在删除第三个数，然后我们先记录当前位置i所在的值x他后面有没有和他一样的数记录他的位置。有的话就等差递增（i, y）, (y, n)就平级递增，没有的话全部等差递增，在前一个状态下减去，这里的dp指的是删除到第几个元素所产生的总数。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
i64 n;
std::cin >> n;
std::vector<i64> a(n+1);
for(int i = 1;i <= n; i++) std::cin >> a[i];
std::vector<i64> dp(n+10), pre(n+10);
i64 ans = 0, sum = 0;
std::unordered_map<i64, i64> mp;
for(int i = 1;i <= n; i++){
if(!mp[a[i]]){
ans ++;
}
mp[a[i]] = i;
sum += ans;
dp[0] += sum;
}
mp.clear();
for(int i = n; i > 0; i--){
pre[i] = mp[a[i]];
mp[a[i]] = i;
}
for(int i = 1;i < n; i++){
if(pre[i] == 0){
i64 k = n - i + 1;
dp[i] = dp[i-1] - k * (k + 1) / 2;
}else{
i64 k = pre[i] - 1 - i + 1;
i64 s = n - pre[i] + 1;
dp[i] = dp[i-1] - k * (k + 1) / 2 - s * k;
}
}
i64 cost = 0;
for(int i = 0;i < n; i++) cost += dp[i];
std::cout << cost << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve<int>();
return 0;
}
E
题目链接：https://ac.nowcoder.com/acm/contest/120562/E
思路：构造场
n = 1
0
n = 2
10
00
n = 3
010
110
000
n = 4
1010
0010
1110
0000
n = 5
01010
11010
00010
11110
00000
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve(){
/*
n = 1
0
n = 2
10
00
n = 3
010
110
000
n = 4
1010
0010
1110
0000
n = 5
01010
11010
00010
11110
00000
n = 6
101010
001010
111010
000010
111110
000000
*/
int n;
std::cin >> n;
std::vector<string> s(n);
if(n & 1){
for(int i = 0;i < n; i++){
if(i & 1) s[0] += '1';
else s[0] += '0';
}
}else{
for(int i = 0;i < n; i++){
if(i & 1) s[0] += '0';
else s[0] += '1';
}
}
for(int i = 1;i < n; i++){
for(int j = 0;j <= i; j++){
s[i] += s[0][i];
}
for(int j = i+1;j < n; j++){
s[i] += s[0][j];
}
}
for(int i = 0;i < n; i++){
std::cout << s[i] << "\n";
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve<int>();
return 0;
}
J
题目链接：https://ac.nowcoder.com/acm/contest/120562/J
思路：
最短路问题：已知每个点相连的边数，我们就从最大开始遍历同时搜，对每个较低的点进行取最小值就可以了。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
//输入报错可能是数组边界问题，看下循环条件关于索引的位置有没有放反
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
struct point{
int v;
int step;
};
template<class T>
void solve(){
int n, m;
std::cin >> n >> m;
std::vector<vector<int>> G(n+1);
for(int i = 0;i < m; i++){
int u, v;
std::cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
std::unordered_map<int, vector<int>> mp;
for(int i = 1;i <= n; i++){
int len = G[i].size();
mp[len].push_back(i);
}
queue<point> q;
std::vector<bool> vis(n+1);
std::vector<int> ans(n+1, N);
for(auto &[x, c] : mp){
for(auto &u : c){
q.push({u, 0});
vis[u] = true;
}
while(!q.empty()){
auto [a, b] = q.front();
q.pop();
for(auto &u : G[a]){
if(vis[u]) continue;
vis[u] = true;
q.push({u, b + 1});
int len = G[u].size();
if(len < x) ans[u] = min(ans[u], b + 1);
}
}
for(int i = 1;i <= n; i++) vis[i] = false;
}
for(int i = 1;i <= n; i++){
std::cout << (ans[i] == N ? -1 : ans[i]) << " ";
}
std::cout << "\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--)
solve<int>();
return 0;
}
