2026年编程兔冬令营集训第四场作业

1、位运算

2、二分

1、计算10进制数转换成2进制数后1的个数。
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,ans =0;
	cin>>n;
	while(n>0){
		ans+=n%2;
		n=n/2;
	}
	cout<<ans<<endl;
	//cout<<__builtin_popcount(int n)<<endl;
	return 0;
} 

2、枚举进阶：全排列问题。问题：枚举 n 个不同元素的所有全排列（每个元素出现且仅出现一次的排列）。n 个元素的全排列共有 n! 种，时间复杂度为 O (n!)。该方法适用于 n≤10 的场景（10!≈360 万，可接受）。
思路：
• 递归枚举：固定第 k 个位置的元素，递归枚举剩余位置的元素。
• 去重处理：通过交换元素避免重复（确保每个位置的元素唯一）。
#include<bits/stdc++.h>
using namespace std;
int a[20],n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) a[i] = i;
	do{
		for(int i = 1;i <= n;i++) cout << a[i] << ' ';
		cout << "\n";
	}while(next_permutation(a + 1,a + n + 1));
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[11],b[11],n;
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<=n;i++)cout<<a[i]<<" ";
		cout<<endl;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0)
		{
			a[x]=i;
			b[i]=1;
			dfs2(x+1);
			b[i]=0;
		}
	}
}
int main()
{
	cin>>n;
	dfs(1);
	return 0;
}


3、题意：给 n 个动物和一个条件列表：如果存在一个动物第 i 位为 1，则购买第 i 位的饲料，否则不购买第 i 位饲料。根据当前的动物，确定了饲料集合。问在不改变饲料集合的前提下，还能加入多少个动物。重点就是二进制位数对应饲料。本题数据会超过64位，可以使用__int128类型。
a.如果某一位二进制没有出现过对应的饲料，则这一位二进制可0可1，不会增加新饲料；
b.如果某一位二进制出现过饲料，并且这一位二进制在动物中出现过，饲料必买，则这一位二进制可0可1，不会增加新饲料。
#include<bits/stdc++.h>
using namespace std;
int b[65];
void show(__int128 ans){
	string s;
	if (ans ==0) {
		cout<<0<<endl;return;
	}
	while(ans>0){
		s.push_back('0'+ans%10);
		ans/=10;
	}
	reverse(s.begin(), s.end());
	cout<<s<<endl;
	return;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	unsigned long long n,m,c,k,p,q, tn=0, ai,one=1;
	__int128 ans=1; //总方案会超过64位 
	cin>>n>>m>>c>>k;
	//统计动物对应的位数为1
	for(int i=0;i<n;++i) {
		cin>>ai;
		tn=tn|ai;
	}
	//统计饲料对应的位数为1 
	for(int i=0;i<m;++i){
		cin>>p>>q;
		b[p] = 1;
	}
	//枚举位数，计算总方案 
	for(int i=0;i<k;++i){
		if (b[i]==0){//没有对应的饲料出现，可0可1，方案为2 
			ans = ans*2;
		}else{
			// 有对应的饲料，且已经购买，可0可1，方案为2 
			if ((tn & (one<<i)) !=0 ) ans = ans *2;
		}
	}
	// 总方案-已经出现的=剩余的 
	ans = ans -n;
	show(ans);
	return 0;
}
4、二分查找，它仅适用于有序的顺序表。
折半查找的基本思想：① 首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；② 若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若 key 大于中间元素，则所查找的元素只可能在后半部分），然后在缩小的范围内继续进行同样的查找。重复上述步骤，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
bool query(int x){
	int l=0,r=n-1,mid;
	while(l<=r){
		mid = (l+r+1)/2;
		if (a[mid] == x) return x;
		if (a[mid]<x) l=mid+1;
		else r=mid-1;
	}
	
	return false;
}
int main(){
	cin>>n>>q;
	for(int i=0;i<n;++i) cin>>a[i];
	//排序，确保有序 
	sort(a,a+n);
	int x;
	while(q-->0){
		cin>>x;
		cout<<(query(x)?"Yes":"No")<<endl;
	}
	return 0;
}
使用lower_bound函数
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
bool query(int x){
	int mid = lower_bound(a,a+n,x)-a; 
	if (mid<n && a[mid]==x) return true;
	
	return false;
}
int main(){
	cin>>n>>q;
	for(int i=0;i<n;++i) cin>>a[i];
	//排序，确保有序 
	sort(a,a+n);
	int x;
	while(q-->0){
		cin>>x;
		cout<<(query(x)?"Yes":"No")<<endl;
	}
	return 0;
}

5、题目要求将数列划分成  段，求“每段和的最大值”的最小值。每当我们看到 “最大值最小” 或 “最小值最大” 这类字眼时，首先应该想到的就是 二分答案。
a.二分枚举“每段和的最大值”这一可能得答案（设为 x）。 
b.然后检查：如果每段和最大不超过 x，最少需要分成几段？
#include<bits/stdc++.h>
using namespace std;
// 使用 long long (ll) 是为了防止和溢出。
// 虽然 N <= 10^5, A_i <= 10^8，但总和可能达到 10^13，超过 int (2*10^9) 范围。
typedef long long ll;
const int MAXN = 100005;
ll a[MAXN];
/**
 * 检查函数 check(limit)
 * 功能：判断当每段和的最大值不超过 limit 时，最少需要分多少段。
 *
 * 贪心策略：
 * 尽可能把更多的数字塞进当前这一段，直到塞不下（和超过 limit）为止，
 * 然后开启新的一段。这样得到的段数是最少的。
 */
bool check(int n, int m, ll limit) {
    int seg = 1;     // 当前是第几段（初始为第1段）
    ll cur_sum = 0;  // 当前这一段的累加和
    for (int i = 1; i <= n; i++) {
        // 如果加上当前数字 a[i] 会超过限制 limit
        if (cur_sum + a[i] > limit) {
            seg++;           // 必须开启新的一段
            cur_sum = a[i];  // 新的一段从 a[i] 开始
        } else {
            cur_sum += a[i];  // 否则加到当前段里
        }
    }
    // 如果最少需要的段数 seg <= m，说明 limit 是可行的（甚至可能偏大），返回
    // true
    return seg <= m;
}
int main() {
    int N, M;
    cin >> N >> M;
    ll sum = 0;
    ll l = 0;  // 二分下界：答案至少是数列中的最大值（因为一段至少包含一个数）
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        sum += a[i];
        l = max(l, a[i]);
    }
    // 二分上界：答案至多是所有数的和（即只分成 1 段）
    ll r = sum;
    // 二分查找
    while (l <= r) {
        ll mid = l + (r - l) / 2;
        if (check(N, M, mid)) {
            // 如果 limit = mid 可行（分的段数 <= M），说明答案可能是 mid
            // 或者更小
            r = mid - 1;
        } else {
            // 如果不可行（分的段数 > M），说明 limit 太小了，需要增大
            l = mid + 1;
        }
    }
    // 最终 l 指向的就是满足条件的最小值
    cout << l << endl;
    return 0;
}

6、思路：二分答案 + 差分数组
a.二分订单数k，判断前k个订单是否导致某天教室不足。
b.用差分数组快速计算每天教室使用量，复杂度O(n + m log m)。
#include<bits/stdc++.h>
using namespace std;

// 检查函数，用于判断在给定的订单索引mid之前，是否所有订单都能被满足
bool check(const vector<long long>& rooms, const vector<vector<int>>& orders, int mid) {
    vector<long long> diff(rooms.size() + 1, 0); // 初始化差分数组
    for (int i = 0; i <= mid; ++i) { // 遍历到mid的订单
        diff[orders[i][1]] += orders[i][0]; // 在订单开始日增加需求
        diff[orders[i][2] + 1] -= orders[i][0]; // 在订单结束日的下一天减少需求
    }
    long long current = 0; // 当前已分配的教室数量
    for (int i = 1; i < rooms.size(); ++i) { // 遍历每一天
        current += diff[i]; // 更新当前已分配的教室数量
        if (current > rooms[i]) { // 如果当前需求超过可用教室
            return false; // 返回false，表示无法满足
        }
    }
    return true; // 如果所有天都能满足，返回true
}

int main() {
    int n, m;
    cin >> n >> m; // 读取天数n和订单数量m
    vector<long long> rooms(n + 1, 0); // 初始化教室数组，0号位置不用
    for (int i = 1; i <= n; ++i) {
        cin >> rooms[i]; // 读取每天的教室数量
    }
    vector<vector<int>> orders(m, vector<int>(3)); // 初始化订单数组
    for (int i = 0; i < m; ++i) {
        cin >> orders[i][0] >> orders[i][1] >> orders[i][2]; // 读取每个订单的需求、开始和结束日期
    }

    // 二分查找第一个无法满足的订单
    int left = 0, right = m - 1; // 初始化二分查找的左右边界
    while (left <= right) {
        int mid = left + (right - left) / 2; // 计算中间索引
        if (check(rooms, orders, mid)) { // 如果mid之前的订单都能满足
            left = mid + 1; // 向右移动左边界
        } else {
            right = mid - 1; // 否则向左移动右边界
        }
    }

    if (left == m) {
        cout << 0 << endl; // 如果left等于m，表示所有订单都能满足
    } else {
        cout << -1 << endl; // 否则输出-1
        cout << left + 1 << endl; // 输出第一个无法满足的订单的编号（编号从1开始）
    }

    return 0;
}