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

1、排序 2、贪心 3、字符Hash

1、第k天，从可以使用的题单里面找到题目数量>=k的题单，从里面挑题目少量最少的即可。因此，
可以先对题单按题目数量排序，对于第k天贪心使用最少题目数量>=k的题单。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N];
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int cnt = 1;
    for(int i = 1; i <= n; i++){
        if(a[i] < cnt) continue;
        else cnt++;
    }
    cout << --cnt;
    return 0;
}
2、先找出所有的数字，然后使用贪心算法把大的数字排在前面。
注意：除了0以外，第一位数不会0；如果没有数字，结果为0。
#include<bits/stdc++.h>
using namespace std;
string s,ans;
int a[10];
int main(){
	cin>>s;
	for(int i=0;i<s.size();++i) if (s[i]>='0' && s[i]<='9')
		++a[s[i]-'0'];
	for(int i=9;i>=0;--i){
		while(a[i]>0){
			ans.push_back('0'+i);
			--a[i];
		}
	}
	while(ans.size()>1 && ans[0]=='0') ans.erase(0,1);
	if (ans.size()==0) ans.push_back('0');
	cout<<ans<<endl; 
	return 0;
}


3、最多挑选(n+1)/2个数，是的这些数的总和最大。所以可以贪心挑选的数越大越好，且不挑负数。
#include<bits/stdc++.h>
using namespace std;
long long n,ans=0,t;
long long a[200005];
int main(){
	cin>>n;
	t=(n+1)/2;
	for(int i=0;i<n;++i) cin>>a[i];
	sort(a,a+n);
	for(int i=1;i<=t;++i) {
		if (a[n-i]>0) ans+=a[n-i];
	}
	cout<<ans<<endl; 
	return 0;
}
4、总体思路：
a.每个成员都选最满意的部门，求个总和。
b.如果任何一个部门都没有超过半数的成员加入，直接输出答案。
c.如某个部门超员了，把代价最低的成员移动到他比较满意的部门。
d.总和扣减掉损失的代价。
这个贪心过程，我们通常称为反悔贪心。需要反悔的时候，就让反悔的惩罚或者损耗最小化。同时每个人要么选择价值最大的部门，要么选择价值第二大的部门（思考一下为什么？）。
#include<bits/stdc++.h>
using namespace std;
int n,t;
long long a[100005][3];
void sovle(){
	long long ans =0,k=-1;
	scanf("%d",&n);
	vector<long long> vc[3];
	for(int i=0;i<n;++i){
		scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
		//每个人都选价值最大的社团，并记录到该社团下，同时记录其他两个社团的最大值 
		if (a[i][0]>=a[i][1] && a[i][0]>=a[i][2]){
			ans+=a[i][0];
			vc[0].push_back(a[i][0]-max(a[i][1],a[i][2]));
		}else if (a[i][1]>=a[i][0] && a[i][1]>=a[i][2]){
			ans+=a[i][1];
			vc[1].push_back(a[i][1]-max(a[i][0],a[i][2]));
		}else if (a[i][2]>=a[i][1] && a[i][2]>=a[i][0]){
			ans+=a[i][2];
			vc[2].push_back(a[i][2]-max(a[i][1],a[i][0]));
		}
	}
	n=n/2;
	//是否有社团的人数超过一半 
	for(int i=0;i<3;++i) if (vc[i].size()>n) k=i;
	// 超过人数的社团减员
	// 挑该加入其他社团后价值减少最少的来进行减员 
	if (k!=-1){
		sort(vc[k].begin(), vc[k].end()); 
		int m=vc[k].size()-n;
		for(int i=0;i<m;++i) ans-=vc[k][i];
	}
	cout<<ans<<endl;
}
int main(){
	scanf("%d",&t);
	while(t-->0){
		sovle(); 
	}
	return 0;
} 

5、n为a字符串的长度，m为b字符串的长度。在a字符串中枚举每一个长度为m的子字符串，是否等于b。n,m<=10^6，所以通过字符串判断的方式会超时。这时候引入字符串hash的方式。
字符串哈希，使用基数转换法求一个字符串的哈希值：
	给出一个固定进制，将一个字符串上的每个字符看做一个进制位上的数字，所以这个字符串就可以看做一个进制的数，可以配合除留余数法，将这个数的数值再对一个模数取模，就可以得到这个字符串的哈希值。
	选取两个互质的常数进制P和模数MOD（P<MOD），假设有字符串s，长度为n，ci是字符si对应的数字，那么我们定义哈希函数：

注意：
a.新的基数一般大于字符串对应的数字串的基数。
b.基数与模数互质，一般选择质数。
c.字符转为对应的数字选择：一般不转为数字。
#include<bits/stdc++.h>
using namespace std;
long long pr[1000005],hashi[1000005];
long long P=6151,MOD = 1e9+7,bhash =0, ahash;
int main(){
	int n,m,ans = 0;
	string a,b;
	cin>>a;
	cin>>b;
	n=a.size();m=b.size();
	pr[0] = 1; hashi[0] = 0;
	//初始化a字符串各个前缀的hash值
	//同步技术P^i的值 
	for(int i=0;i<n;++i){
		pr[i+1] = (pr[i]*P)%MOD;
		hashi[i+1] = (hashi[i]*P+a[i]-'a')%MOD;
	}
	//计算b字符串的hash值 
	for(int i=0;i<m;++i){
		bhash = (bhash*P+b[i]-'a')%MOD;
	}
	//枚举a每一个m长度的子字符串，并计算hash值 
	for(int i=m-1;i<n;++i){
		ahash = (hashi[i+1] - hashi[i+1-m]*pr[m] % MOD+MOD) %MOD;
		if (ahash == bhash) ans++;
	} 
	cout<<ans<<endl;
	return 0;
} 
6、题目要求判断子串s[0~i] ==s[n-1-i~n-1]，如果快速的判断前缀子符串和后缀子字符串相等问题：字符串哈希！
#include<bits/stdc++.h>
using namespace std;
long long pr[400005],hashi[400005];
long long P=6151,MOD=1e9+7,ahash,bhash;
int main(){
	string s;
	int n;
	pr[0] = 1; hashi[0] = 0;
	for(int i=0;i<400000;++i) pr[i+1] = (pr[i]*P)% MOD;
	while(cin>>s){
		n=s.size();
		for(int i=0;i<n;++i) hashi[i+1] = (hashi[i]*P+s[i]-'a') %MOD;
		for(int i=1;i<=n;++i){
			ahash = hashi[i];//前缀子串hash值 
			//后缀子串hash值 
			bhash = (hashi[n] - hashi[n-i]*pr[i] % MOD+MOD)%MOD;
			if (ahash == bhash) cout<<i<<" "; 
		}
		cout<<endl;
	}
	return 0;
}