2026牛客寒假算法基础集训营2（A B I F E H）

2026牛客寒假算法基础集训营2（A B I F E H）

Lionlnuc
Lionlnuc Lv4
  2026-02-08 2026-02-08 创建   2026-02-08 2026-02-08 更新      

这场打的非常差……

A 比赛安排

思路：
题目还是很简洁的，三种比赛进行分配，任意连续的 3 场比赛的类型互不相同，，最后只能其中一种比赛类型或者两种比赛类型多一场，所以最多比赛场次和最少比赛场次的差值不能超过1。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
void solve()
{
    int a,b,c;
    cin>>a>>b>>c;
    int ma=max(a,max(b,c));
    int mi=min(a,min(b,c));
    if(ma-mi<=1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

B NCPC

思路：
给定n个整数，每次可以选定两个整数，若两个数字不等，留下较大值，否则全部删除，问对于每个整数能否是最后剩下的数字。如果最大的数是奇数个的话，那么其余所有的数都不可能剩下，相反的，如果最大的数个数是偶数个的话，其余所有的数都有可能留下。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define x first
#define y second
#define endl "\n"
const int N=2e5+5;
int a[N];
void solve()
{
    int n;
    cin>>n;
    int ma=0;
    map<int,int> cnt;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ma=max(a[i],ma);
        cnt[a[i]]++;
    }
    bool flag;
    if(cnt[ma]%2)flag=true;
    else flag=false;
    for(int i=1;i<=n;i++)
    {
        if(flag)
        {
            if(a[i]==ma)cout<<"1";
            else cout<<"0";
        }else{
            if(a[i]==ma)cout<<"0";
            else cout<<"1";
        }
    }
    cout<<endl;
}
signed main(){
	IOS
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}

I 01 回文

思路：
这个题的话统计 0/1 个数，只要大于等于 2 就是有可能的，注意下超时问题。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n"
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<char>> ch(n,vector<char>(m));
    int cnt0=0,cnt1=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>ch[i][j];
            if(ch[i][j]=='0')cnt0++;
            else cnt1++;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(ch[i][j]=='1')
            {
                if(cnt1>1)cout<<"Y";
                else cout<<"N";
            }else{
                if(cnt0>1)cout<<"Y";
                else cout<<"N";
            }
        }
        cout<<endl;
    }
}
signed main(){
	IOS;
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}

F x?y?n!

题意：
在 gcd⁡(x,y)=n 条件下最小化 。
思路：
根据 ，gcd⁡(x,y)=n，可知 至少是 n 的一倍，所以 。
$x=an，y=bn$，所以 gcd(a,b)=1。
XOR 最小意味着两个数的二进制表示越相同。n 是理论最小下界。让 x,y 在所有高位完全相同，只在最低若干位制造差异，且差异值正好是 n。
我们令 此时 gcd(a,b)=1。此时的 $x=n2^k=n<<k二进制知识点这里一个数字乘一个就相当于把二进制表示中每位的位权加一，也就是相当于在二进制表示后面补了个所以等同于将的所有二进制位向左移动个位置，右边空出的位补。此时x⊕y=(n≪k)⊕((n≪k)+n)，可以看成A⊕(A+B)=B。两边同时异或可以得到A⊕(A+B)⊕B=0即(A⊕B)⊕(A+B)=0，可得(A⊕B)=(A+B)。二进制加法和异或的关系A+B=(A⊕B)+2(A\And B)Misplaced & 在二进制下，异或是不进位的加法，A&B 是产生进位的位。 当 A \And  B=0时，没有进位。此时A+B=(A⊕B)。所以(n≪k)\And n=0。接下来我们去找满足(n≪k)\And n=0$ 的 k。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define x first
#define y second
#define endl "\n"
void solve()
{
    int n;
    cin>>n;
    int a=0,b=0,k=n;
    for(int i=1;i<=31;i++)
    {
        k<<=1;
        if((k&n)==0)
        {
            a=k,b=k+n;
            break;
        }
    }
    cout<<a<<" "<<b<<endl;
}
signed main(){
	IOS
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}

E 01矩阵

思路：
只能说很玄幻。😇可以根据 2 的构造往后推一下。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#define endl '\n'
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<min(i,j)%2;
        }
        cout<<endl;
    }
}
signed main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
}

H 权值计算

思路：
读懂题是第一步，伪代码是在计算一个数组中每个前缀中不同元素个数的和。，然后我们需要计算一个数组的每个子数组的权值之和。
我们用第二个样例来找找规律。数组为{1,1,4,5,1,4}，我们来计算每个子数组的贡献。
l 的范围是[1 ,n]，r 的范围是[l, n]。

l\r 1 2 3 4 5 6
1 1 1 2 3 3 3
2 1 2 3 3 3
3 1 2 3 3
4 1 2 3
5 1 2
6 1
列和 1 2 5 9 12 15
可以发现如果 a[i]之前没有出现过，相较于上一列会增加 i 的贡献，否则增加 的贡献（pos 为上次出现的位置）。
所以对于一个位置 i，它对答案的贡献为 。
g(l, i) 表示从 l 到 i 这段区间中不同元素的个数。
所以 $ans=\sum^{n}{i=1}[\sum^{i}{l=1}g(l,i)]*(n-i+1)$。
令
代码： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define x first
#define y second
#define endl "\n"
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    map<int,int>m;//记录每个值最近一次出现的位置
    int ans=0;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int last=0;
        last=m[a[i]];
        m[a[i]]=i;
        sum+=i-last;
        ans+=sum*(n-i+1);
    }
    cout<<ans<<endl;
}
signed main(){
	IOS
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}
  • 标题: 2026牛客寒假算法基础集训营2（A B I F E H）
  • 作者: Lionlnuc
  • 创建于 : 2026-02-08 00:00:00
  • 更新于 : 2026-02-08 00:00:00
  • 链接: https://lionlnuc.github.io/2026/02/08/2026牛客寒假算法基础集训营2（A B I F E H）/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
2026牛客寒假算法基础集训营2（A B I F E H）
  1. A 比赛安排
  2. B NCPC
  3. I 01 回文
  4. F x?y?n!
  5. E 01矩阵
  6. H 权值计算