Educational Codeforces Round 86 (Rated for Div. 2)(A,B,C,D题解)

迟到的补题。。。。

题意：
你可以用花费 $a$a元，使得 $x$x或者 $y$y不同时加 $1$1或者减 $1$1，你也可以花费 $b$b元使得 $x,y$x,y同时加 $1$1或者减 $1$1，问你最少花费多少钱使得 $x=y=0$x=y=0。
思路：
无论你是同时还是单一操作，你都要先使得 $x=y$x=y，然后再考虑使用同时加减还是单一加减更优。
代码：

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
	int t;cin>>t;
	while(t--){
		ll x,y,a,b;cin>>x>>y>>a>>b;
		cout<<(max(x,y)-min(x,y)) * a + min(min(x,y) * b,min(x,y) * 2 * a)<<endl;
	}	
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你一个 $01$01字符串 $t$t，要你生产一个字符串 $s$s，使得 $t$t是 $s$s的子串，并且 $s$s的循环周期最短并且 $s$s的长度 <=2t。
思路：
容易发现如果 $t$t本身只包含 $0或者1$0或者1字符串的时候，循环周期为 $1$1且最短，这个时候直接输出即可。当 $t$t包含 $01$01字符串的时候我们不可能生产出比周期 $1$1更短的字符串，但是周期 $2$2确实可以生产的，只需要保证 $s$s的长度是 $t$t的两倍，那么 $t$t一定是 $s$s的字串，并且把 $s$s生成 $\mathrm{01010101...01}$01010101...01这样的字符串即可，因为周期为 $2$2最短。
代码：

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
	int t;cin>>t;
	while(t--){
		string s;cin>>s;
		int f1 = 0,f0 = 0;
		for(int i = 0; i < s.size(); i++){
			if(s[i] == '1')f1 = 1;
			if(s[i] == '0')f0 = 1;
		}
		if(f1 && f0){
			for(int i = 0; i < s.size(); i++){
				cout<<"01";
			}
			cout<<endl;
		}else{
			cout<<s<<endl;
		}
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你两个十进制数字 $a,b$a,b，和 $q$q个询问，每个询问包含一个区间 $L,R$L,R,问你这个区间满足 $x$x% $a$a%b $!=$!= $x$x% $b$b% $a$a的数有多少个。
思路：
当 x<max(a,b)的时候一定不满足。
我们可以发现当 $x=lcm(a,b)$x=lcm(a,b)的时候 $x$x% $a$a%b $=$= $x$x% $b$b% $a$a，并且 $lcm+max(a,b)$lcm+max(a,b)这一段都不满足，进而可以推广 $klcm+max(a,b)$klcm+max(a,b)这些段不满足，换言之， $lcm-max(a,b)$lcm−max(a,b)是满足条件的。所以我们需要在 $L,R$L,R找有多少个 $lcm$lcm，可以 $R/lcm-L/lcm$R/lcm−L/lcm找出 $lcm$lcm个数，当然还要考虑边界情况，把R可以少加的 $R-max(a,b)+1$R−max(a,b)+1加上，把L可能少减的 $L-max(a,b)$L−max(a,b)减掉就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
void solved(){
	int t;cin>>t;
	while(t--){
		ll a,b,q;cin>>a>>b>>q;
		ll lcm = a / __gcd(a,b) * b;
		while(q--){
			ll l,r;cin>>l>>r;
			if(r < max(a,b)){
				cout<<"0"<<endl;
			}else{
				ll n = r / lcm - l / lcm;
				ll ans = n * (lcm - max(a,b));
				r %= lcm;
				if(r >= max(a,b))ans += r - max(a,b) + 1;
				l %= lcm;	
				if(l > max(a,b))ans -= l - max(a,b);
				cout<<ans<<" ";
			}
		}
		cout<<endl;
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你 $n$n个数，要你分组，每组需要满足 $>=1$>=1的个数不超过 $Ci$Ci，。。。 $>=k$>=k的个数不超过 $Ck$Ck。要你使得分组数最少，并且输出分组方案。
思路：
为了方便处理先把所有数升序，然后找满足大于等于 $ai$ai的数有多少个 $/$/ $ci$ci,向上取整然后去最大值，就是最小方案数了。你可以这样理解，最大值并且大于其他所有数，其他所有分组数都满足了，这个时候只需要满足最大的这个数了，就会满足所有情况。然后把每个数依次分组填入即可(即将最大峰值缩小)。
核心： $max\left(si/ci\right)$max(si/ci)向上取整
代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
const int maxn = 2e5 + 10;
int m[maxn],c[maxn];
vector<int>ve[maxn];
void solved(){
	int n,k;cin>>n>>k;
	for(int i = 1; i <= n; i++)cin>>m[i];
	for(int i = 1; i <= k; i++)cin>>c[i];
	sort(m + 1, m + 1 + n);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		ans = max(ans,((n - i + 1) - 1) / c[m[i]] + 1);
	}
	for(int i = 1; i <= n; i++){
		ve[(i - 1) % ans].push_back(m[i]);
	}
	cout<<ans<<endl;
	for(int i = 0; i < ans; i++){
		cout<<ve[i].size()<<" ";
		for(int j = 0; j < ve[i].size(); j++){
			cout<<ve[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
	solved();
	return 0;
}