Codeforces Round #643 (Div. 2)(A-E)题解

题目大意：
给你一个 $a1$a1，要你求 $ak$ak，其中 $ai=ai-1+maxdigit(ai-1)\ast mindigit(ai-1)$ai=ai−1+maxdigit(ai−1)∗mindigit(ai−1)， $maxgigit\left(123\right)=max(1,2.3)=3$maxgigit(123)=max(1,2.3)=3。
思路：
这题一开始我项会不会有循环节，因为样例 $a2和a7的maxdigit\left(\right)与mindigit\left(\right)$a2和a7的maxdigit()与mindigit()相同。然后写了后面几项发现并不是。不难发现如果出现 $0$0就可以直接不用算了，但是如果一直不出现 $0$0就很尴尬，但是没不到其他思路了就按照找 $0$0写了一发，就 $AC$AC了，证明不太会。。。。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
void solved(){
	int t;cin>>t;
	while(t--){
		ll a1,k;cin>>a1>>k;
		set<int>st;
		ll temp = a1;
		int maxx = 0,minn = 10;
		while(a1 > 0){
			maxx = max(maxx,(int)(a1 % 10));
			minn = min(minn,(int)(a1 % 10));
			st.insert(a1 % 10);
			a1 /= 10;
		}
		ll tot = 1;
		while(tot < k && st.find(0)==st.end()){
			tot++;
			temp = temp + maxx * minn;
			ll t = temp;
			int minnn = 10,maxxx = 0;
			while(t > 0){
				maxxx = max(maxxx,(int)(t % 10));
				minnn = min(minnn,(int)(t % 10));
				st.insert(t % 10);
				t /= 10;
			}
			maxx = maxxx;minn = minnn;
		}
		cout<<temp<<endl;
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你一个长度为 $n$n的序列， $ai$ai表示第 $i$i个人的经验值，现在你要对他们进行分组，当每组人数 <=ai，ai就可以加入这组，现在要你求最多能分多少组？
思路：
这个题好像很显然，看题+写代码不到 $10$10分钟就 $a$a了。就统计一下 $ai$ai的人数，然后 $ai/i$ai/i这样分配肯定是最优的， $ai$ai % $i$i可能不为0，所以再用一个变量表示剩余人数就行，剩余人可以加到别的组。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
int cnt[maxn];
void solved(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		for(int i = 1; i <= n; i++)cnt[i] = 0;
		for(int i = 1; i <= n; i++){
			int a;cin>>a;cnt[a]++; 
		} 
		int ans = 0,rest = 0;
		for(int i = 1; i <= n; i++){
			ans += (cnt[i] + rest) / i;
			rest = (cnt[i] + rest) % i;
		}
		cout<<ans<<endl;
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你四个数： $a,b,c,d$a,b,c,d，然后要你找三条边 a<=x<=b,b<=y<=c,c<=z<=d，满足他们是一个非退化三角形，求非退化三角形的个数。
思路：
这个题也很简单，非退化三角形指的是面积为0不共线的三角形，通俗的讲就是 $a+b!=c$a+b!=c。先枚举 $a+b$a+b的个数，然后在 $[c,d]$[c,d]找有多少个数满足 x<a+b就行了。统计个数要区间 $+1$+1用个差分就行了。注意要开LL.
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 5e5 + 10;
ll cnt[maxn << 1 | 1];
void solved(){
	ll a,b,c,d;cin>>a>>b>>c>>d;
	for(ll i = a; i <= b; i++){
		cnt[i + b]++;cnt[i + c + 1]--;
	}
	for(ll i = 1; i <= maxn << 1; i ++)cnt[i] += cnt[i - 1];
	ll ans = 0;
	for(ll i = 1; i <= maxn << 1; i++){
		ans += cnt[i] * max(0LL,(min(d,i - 1) - c + 1));
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
} 

题目大意：
要你构造一个长度为 $n$n的序列使得他们的和为 $s$s。现在你指定一个数 $k$k，问选择一段连续的区间的和能不能得到 $k$k，如果能,输出“NO”，非则输出"YES",并且输出你构造的数组以及 $k$k。
思路：
构造一个 $[1,1,1,1,...,s-n-1]$[1,1,1,1,...,s−n−1]数组选 $k=n$k=n。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int cnt[maxn];
void solved(){
	int n,s;cin>>n>>s;
	int l1 = 1,r1 = n - 1;
	int l2 = s - (n - 1),r2 = s;
	for(int i = l1 ; i <= r1; i++)cnt[i]=1;
	for(int i = l2 ; i <= r2; i++)cnt[i]=1;
	int ans = -1;
	for(int i = 1; i <= n; i++){
		if(cnt[i] == 0){
			ans = i;break;
		}
	}
	if(ans != -1){
		cout<<"YES"<<endl;
		for(int i = 1; i <= n - 1; i++){
			cout<<"1"<<" ";
		}
		cout<<s - (n - 1)<<endl;
		cout<<ans<<endl;
	}else{
		cout<<"NO"<<endl;
	}
}
int main(){
	solved();
	return 0;
}

题目大意：
给你一个长度为 $n$n的序列，现在要使得序列的所有元素相等，你可以花费 $a$a使得 $ai+1$ai+1或者花费 $r$r使得 $ai-1$ai−1，或者花费 $m$m使得 $ai-1,aj+1$ai−1,aj+1。问最小花费。
思路：
存在最小花费说明在函数 $f\left(x\right)$f(x)是一个开口向上的的函数。
大概长这样。

所以我们考虑用三分去找到这个点。那么 $check$check怎么写？
注意到当 a+r<=m说明我们可以完全用 $+1,-1$+1,−1的花费 $a+r$a+r代替掉 $m$m，贪心的选，算一下对于答案高度 $x$x，高于它的和低于它的值分别是多少？然后 $\ast a或者r$∗a或者r即可。
当 $a+r>m$a+r>m同样计算一下高出多少低出多少，然后先用 $k次+1,-1$k次+1,−1花费 km<k(a+r)，剩余的再乘上 $a或者b$a或者b即可。
总结：第一次写三分。三分不同于二分的只是函数不同，方法是一样的。三分学习参考https://blog.csdn.net/JiangHxin/article/details/106167659#comments_12243449
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
typedef long long int ll;
ll h[maxn];
ll n,a,r,m;
ll f(ll x){
	ll ans = 0;
	if(a + r <= m){
		for(int i = 1; i <= n; i++){
			if(h[i] > x)ans += (h[i] - x) * r;
			if(h[i] < x)ans += (x - h[i]) * a;
		}
	}else{
		ll s1 = 0,s2 = 0;
		for(int i = 1; i <= n; i++){
			if(h[i] > x)s1 += (h[i] - x);
			if(h[i] < x)s2 += (x - h[i]);
		}
		ll mi = min(s1,s2);
		ans += mi * m;
		ans += (s1 - mi) * r;
		ans += (s2 - mi) * a;
	}
	return ans;
}
void solved(){
	cin>>n>>a>>r>>m;
	for(int i = 1; i <= n; i++)cin>>h[i];
	sort(h + 1,h + 1 + n);
	ll l = 0,r = 1e9 + 10;
	ll ans = 1e18;
	while(l <= r){
		ll lL = l + (r - l) / 3;
		ll rR = r - (r - l) / 3;
		ll w1 = f(lL),w2 = f(rR);
		ans = min(min(w1,w2),ans);
		if(f(lL) <= f(rR)){
			r = rR - 1;
		}else{
			l = lL + 1;
		}
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
}