第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）：签到题CDGM

序

• 签到题CDGM，罚时少有铜
• 银牌题AJ，做出来就有银
• 签到题按照考场的开题顺序补的题解。

M Cook Pancakes!

题意： 煎n个煎饼，每个饼有2两个面，每次能煎k个面，求最少煎几次。（n,k<100）
题解： 如果n是k的倍数，直接煎答案就是2*n/k。否则把前面[n/k]-1个饼先单独直接煎，剩下的k个加上余数个分类讨论，根据和k的关系分为煎3次或者4次。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
	LL n, k;  
	cin>>n>>k;
	LL ans=0;
	if(n<=k){
		cout<<2<<"\n";
		return 0;
	}
	
	if(n%k==0)ans = n*2/k;
	else{
		ans += 2*((n/k)-1);
		LL t = n-(n/k)*k;
		if(2*t<=k)ans+=3;
		else ans += 4;
	}
	cout<<ans<<"\n";
	return 0;
}

G Xor Transformation

题意： 给出两个数X和Y（X，Y<1e18），X需要通过小于5次异或一个小于X的数A（A的范围随着X的减少而减小），变得和Y相等，求一种可行的方案（SPJ）。
思路： 比较二进制下X和Y的每一位，如果相同那么不需要异或A来修改，如果不同就需要异或一个1来变成另一个不同的数。按位比较X和Y，维护一个变量sum，每次遇到不同就更新sum那一位的值为1，如果sum>X了就重新累加。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
	LL x,y;
	cin>>x>>y;
	LL xx = x, yy = y;
	vector<LL>ans;
	
	LL cnt = 1, sum = 0;
	while(x>0){
		if(x%2==y%2){
			cnt *= 2;
			x>>=1; y>>=1;
			continue;
		}else{
			//cout<<sum<<" "<<xx<<"\n";
			//sum += cnt;
			if(sum+cnt > xx){
				ans.push_back(sum);
				sum = cnt;
			}else{
				sum += cnt;
			}
		}
		cnt *= 2;
		x >>= 1;
		y >>= 1;
	}
	if(sum>0)ans.push_back(sum);
	cout<<ans.size()<<"\n";
	for(int i = 0; i < ans.size(); i++){
		if(i!=0)cout<<" ";
		cout<<ans[i];
	}
		
	return 0;
}

C Stone Game

题意： 给出n堆石头，含有一块石头的a堆，两块的b堆，三块石头的c堆。合并两堆石头x,y的代价为x*y%3，求合并的最小代价。
思路： 考虑与大小为3的倍数的石头堆合并时代价为零，所以c堆与答案无关，同时贪心的让a和b尽可能多的合并成3的倍数。首先把a和b等数量的合并（1+2==3，代价只有2），剩余的分两类合并（1+1+1==3，代价3）（2+2+2==6，代价6），最后如果有剩余落单的1就加上合并代价1，落单的2就加4。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
	LL a, b, c;
	cin>>a>>b>>c;
	
	LL ans = 0;
	if(a==b){
		ans = a*2;
	}else if(a>b){
		ans += b*2;
		LL t = a-b;
		if(t%3==0){
			ans += (t/3)*3;
		}else{
			ans += (t/3)*3;
			if(t%3==2)
				ans += 1;
		}
	}else{
		ans += a*2;
		LL t = b-a;
		ans += (t/3)*6;
		if(t%3==2){
			ans += 4;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

D Fight against involution

题意： 给出n个人写的文章的下限字数和上限字数，成绩为小于等于他字数的总人数（含自己），初始成绩根据上限字数来计算。现在求在满足每个人成绩不小于初始成绩的情况下（可以等于），修改每个人的字数并让总字数最小，求最小总字数。
思路： 可以发现，对于上限字数相同的文章，因为初始成绩相同，所以修改后的字数也必须相同（否则成绩就会不同），所以只能修改成一样的（即最大下限字数），所以维护对于相同上限字数的文章的最大下限字数和对应的文章数量，则修改后的字数就是最大下限字数乘以文章篇数。最后枚举的时候再考虑到如果上一篇文章的最大下限字数或者最后选择的字数要大于当前文章的最大下限，那么当前文章的字数必须取最大（可以和上一篇相等，因为成绩只要不小于就行）。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 1e10;
map<LL,LL>mm,ma,mi;
set<LL>se;
int main(){
	ios::sync_with_stdio(false);  cin.tie(0);
	LL n;  cin>>n;
	for(int i = 1; i <= n; i++){
		LL ai, bi;  cin>>ai>>bi;
		se.insert(bi);
		mm[bi]++;
		if(!ma.count(bi)){ ma[bi] = 0;}
		ma[bi] = max(ma[bi],ai);
		//if(!mi.count(bi)){ mi[bi] = inf;}
		//mi[bi] = min(mi[bi],ai);
	}
	LL ans = 0, last=0;
	for(LL i : se){
		//ans += max(ma[i],ma[i-1]+1)*mm[i];
		LL t = max(ma[i],max(ma[i-1],last) );
		ans += t*mm[i];
		last = t;
	}
	cout<<ans<<"\n";
	return 0;
}