CF1400:1561B. Charmed by the Game(思维)、1519C. Berland Regional(技巧)

wuchangjian2021-11-04 22:36:50编程学习

1561B. Charmed by the Game(思维)

题意:

最终题意转化为:
给定一串ab循环串(ababab...bababa...)。
问可以修改(a变为b或b变为a)多少次,使得a,b出现的次数分别为n,m?
输出所有答案。

思路:

找出出现次数的差值,然后需要这些a或者b能够补齐。
所以最小的修改次数便是这个差值。
后面的修改便是画蛇添足,为了使差值不变,就需要同时变两个(一个a变成b,一个b变成a),相互抵消。
所以要看还剩多少个完整的ab对能够修改。

奇偶分开讨论。

Code:

int main(){
	Ios;
	
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		if(n>m) swap(n,m);
		int sum=n+m;
		
		set<int> st;
		
		if(sum%2==0)
		{
			int x=sum/2-n;
			for(int i=0;i<=sum/2-x;i++) st.insert(x+2*i);
			cout<<st.size()<<endl;
			for(auto it:st) cout<<it<<" ";
			cout<<endl;
		}
		else
		{
			int x=sum/2,y=x+1;
			for(int i=0;i<=(sum/2-(x-n));i++) st.insert(x-n+2*i);
			for(int i=0;i<=(sum/2+1-(y-n));i++) st.insert(y-n+2*i);
			cout<<st.size()<<endl;
			for(auto it:st) cout<<it<<" ";
			cout<<endl;
		}
	}
	
	return 0;
}

1519C. Berland Regional(技巧)

题意:

一共n个班级,每个班级若干个人。一共n个人,每个人有一个权值。 (n ≤ 2e5)
现有一个活动,限定每组k人。每个班都会将权值最大的放到一组…
如果最后几人组不成一组,则舍弃。
输出 k = 1~n 时,所有班的所有组的权值之和。

思路:

因为班级一共n个,每个班最多n个人,所以如果开一个二维数组的话,空间太大。所以可以用 vector[N],每个班中的人数存到对应的 vector 中。

当每组 k 人时,每个班的最后%k剩余的人将不会有贡献。所以可以维护前缀和,直接用总贡献减去最后这些人的贡献便是这个班的贡献。

因为要遍历一遍k,还要遍历所有班级,所以复杂度就为 n 2 n^2 n2 ??
要想办法优化。

题目特殊的地方在于,一共 n 个班级,而所有人数加起来也一共有 n 个。所以有些班级的人很少,甚至没有。
而如果一个班级的总人数少于 k 的话,连一个组都组不成,不会对答案有贡献。所以遇到这样的班级就可以跳过。
所以可以将所有班级的人数从大到小排序再遍历,如果遍历到一个班级人数小于k了,就 break。
所有班级总人数为 n,最终的复杂度为 O(NlogN)。

Code:

const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
int ans[N];
vector<int> v[N];
PII f[N];

bool cmp(PII a,PII b){
	return a.first>b.first;
}

signed main(){
	Ios;
	
	cin>>T;
	while(T--)
	{
		cin>>n;
		int cnt=0;
		for(int i=1;i<=n;i++) cin>>a[i],v[i].clear();
		
		for(int i=1;i<=n;i++){
			int x;cin>>x;
			v[a[i]].push_back(x);
		}
		
		for(int i=1;i<=n;i++)
		{
			sort(v[i].begin(),v[i].end());
			for(int j=0;j<v[i].size();j++){
				if(j) v[i][j]+=v[i][j-1];
			}
			f[i].first=v[i].size();
			f[i].second=i;
		}
		
		sort(f+1,f+n+1,cmp);
		
		for(int k=1;k<=n;k++)
		{	
			int tt=0,sum=0;
			for(int i=1;i<=n;i++)
			{
				int j=f[i].second;
				if(f[i].first<k) break;
				
				int t=v[j].size()%k;
				sum+=v[j][v[j].size()-1];
				
				if(t==0) continue;
				else tt+=v[j][t-1];
			}
			cout<<sum-tt<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

很有技巧性的一道题。

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。