ARC128题解

2024-03-09 08:38:59

A

题意

最开始有一克金
第 \(i\) 天若有金 \(x\) 克，可以把所有金换成 \(A_i\cdot x\) 克银
若有银 \(x\) 克，可以把所有银换成 \(\frac{x}{A_i}\) 克金
问最后有多少克金

题解

金变银、银变金一定是成对的，设一对变换的下标分别是 \(x\) 和 \(y\) ，发现 \(x\) 和 \(y\) 一定是一段下降序列的两端。因为若中间 \(a\) 变金 \(b\) 变银，那么贡献由

\[\frac{A_x}{A_y} 变为 \frac{A_x}{A_a}\cdot\frac{A_b}{A_y}=\frac{A_x}{A_y}\cdot\frac{A_b}{A_a} \]

显然不会更优

Code

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn],ans[maxn],n;
int main(){
	cin>>n;
	for(ri i = 1;i <= n;++i) cin>>a[i];
	for(ri i = 1;i < n;++i){
		int j = i + 1;
		if(a[j] >= a[i]) continue;
		ans[i] = 1;
		while(a[j+1] < a[j] && j < n) ++j;
		ans[j] = 1; i = j;
	}
	for(ri i = 1;i <= n;++i) cout<<ans[i]<<' ';
	putchar('\n');
	return 0;
}

B

简要题意

有三种颜色的球各若干个，每次操作可以把两个异色的球变成与它们都不同的颜色，找到最少操作次数使所有球颜色一样或判无解

题解

设三种颜色的球分别有 \(R,G,B\) 个，最后 \(R'=0,G'=0,B'=R+G+B\)
首先想到若 \(R=G\) ，那么每次把一个 \(R和G\) 变成 \(B\) 即可
考虑三种颜色两两不同，设 \(R<G\)，需要把 \(R,G\) 变成相同再变成 \(B\)。发现无论怎么操作 \(R-G\) 模3意义下不变，用这个可判无解。
每次 \(R+2,G-1,B-1\) ，再 \(R-1,G-1,B-1\) ，就可以一直操作到 \(R=G\)，前提是 \(B!=0\) 。

Code

    #include<bits/stdc++.h>
    #define ri register int
    #define ll long long
     
    using namespace std;
    ll a[4],r,g,b,l;
    const ll inf = 0x7f7f7f7f7f7f7f7f;
    int n;
    int main(){
    	cin>>n;
    	for(ri i = 1;i <= n;++i){
    		for(ri j = 1;j <= 3;++j) cin>>a[j];
    		r = a[1],g = a[2],b = a[3];
    		ll ans = inf;
    		if(abs(r-g) % 3 == 0){
    			if(b){
    				l = abs(r-g)/3;
    				ans = min(ans,abs(r-g) / 3 + min(r,g) + 2*l);
    			}
    		}
    		r = a[2],g = a[3],b = a[1];
    		if(abs(r-g) % 3 == 0){
    			if(b){
    				l = abs(r-g)/3;
    				ans = min(ans,abs(r-g) / 3 + min(r,g) + 2*l);
    			}
    		}
    		r = a[3],g = a[1],b = a[2];
    		if(abs(r-g) % 3 == 0){
    			if(b){
    				l = abs(r-g)/3;
    				ans = min(ans,abs(r-g) / 3 + min(r,g) + 2*l);
    			}
    		}
    		if(ans == inf) cout<<-1<<endl;
    		else cout<<ans<<endl;
    	}
    	return 0;
    }

C

简要题意

给你 \(n,m,s\) 以及大小为 \(n\) 的序列 \(a\) ，求实数序列 \(x\) 满足

\(x\) 单调不降，且 \(x_i \in [0,m]\)
\(\sum\limits_{i=1}^n x_i = s\)
\(\sum\limits_{i=1}^n a_i\times x_i\)最大
找到最大值

题解

发现序列要单调不降，转差分， \(d_i=x_i-x_{i-1}\),\(v_i=\sum\limits_{j=i}^n a_j\),\(c_i=n-i+1\)

\(d_i\ge 0\)
\(\sum\limits_{1\le j\le i\le n} d_j \le m\)
\(\sum\limits_{i=1}^n d_i\times c_i = s\)

求\(\sum\limits_{i=1}^n d_i\times v_i\)最大值

问题转化为：有 \(n\) 种物品，总共最多选 \(m\) 个单位，一个单位 \(i\) 物品代价为 \(c_i\) ，价值为 \(v_i\)，总共代价为 \(s\) ，要总价值最大。

若没有 \(m\) 的限制直接按 \(\frac{v_i}{c_i}\)贪心选最大的。因为有限制，所以首先把最大的选满。因为代价可能小于 \(s\) ，所以要替换，把其他所有物品的价值改为与当前选的差值，然后再贪心，把最大的选满....直到选满时代价大于等于 \(s\) 。发现改为差值后，后面的物品一定没用了(价值为负)，每次从后往前扫找到 \(\frac{v_i}{c_i}\) 最大的 \(i\) 中最靠前的，然后尽量选满，选满后代价仍不足，就把前面的 \(v_j\) 减去 \(v_i\) ，继续执行。

Code

    #include<bits/stdc++.h>
    #define ri register int
    #define ll long long
    using namespace std;
    const int maxn = 5e3 + 10;
    int n;
    double m,s;
    ll a[maxn];
    inline int rd(){
    	int res = 0,f = 0; char ch = getchar();
    	for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = 1;
    	for(;isdigit(ch);ch = getchar()) res = (res<<3) + (res<<1) + ch - 48;
    	return f ? -res : res;
    }
    int main(){
    	n = rd();cin>>m>>s;
    	for(ri i = 1;i <= n;++i) a[i] = rd();
    	for(ri i = n;i >= 1;--i) a[i] += a[i+1];
    	double mx = 0,del,ans = 0;
    	int pos = 0;
    	for(ri r = n;r >= 1;--r){
    		mx = 0;
    		for(ri l = r;l >= 1;--l)
    			if(mx < 1.0*(a[l]-a[r+1])/(r-l+1))
    				mx = 1.0*(a[l]-a[r+1])/(r-l+1),pos = l;
    		del = s/(r-pos+1);
    		if(del <= m){
    			ans += del * (a[pos]-a[r+1]);
    			break;
    		}
    		ans += m * (a[pos]-a[r+1]);
    		s -= (r-pos+1)*m;
    		r = pos;
    	}
    	printf("%.7lf\n",ans);
    	return 0;
    }

D

简要题意

有 \(n\) 个球，上面有颜色，每次操作可以选择三个相邻的球，要求中间的球与两边的球颜色都不同，可以选择删去中间的球，两边的球就会相邻。问最终剩下的球有多少种可能情况。相同颜色但初始位置不同视为不同的球。

题解

发现剩下的球两两之间的球都被删空了，可以线性 \(DP\) 求出答案，但需要区间 \(DP\) 求两个球之间的球能否全部删掉。线性 \(DP\) 可以考虑前缀和之类的优化成 \(O(n)\) ，瓶颈在区间 \(DP\) 。然后把原序列分成若干"最长的、连续的、相邻球颜色不同的段"，因为段之间的贡献独立。
结论：

若段大小\(\leq 3\)，则一定可以把中间的删空。
若大小 \(> 3\) ，颜色个数 \(\ge 3\) 则可以删空，否则不能。

(2):若颜色个数 \(=2\) ，则为\(xyx...xy\) 这类，中间的一定删不空。否则一定存在一段为 \(...xyz..\) ，若删去 \(y\) 后仍有三种颜色就删去 \(y\) 然后递归，否则删去 \(z\) 然后递归，直至大小为 \(3\)。

把每一段扣除来，因为符合条件的转移点一定是一个前缀，用一个指针往后扫找到最大的转移点，然后加上前缀和。最后的答案就是每一段的答案乘起来。

Code

    #include<bits/stdc++.h>
    #define ri register int
    #define ll long long
    using namespace std;
    const int maxn = 2e5 + 10,mod = 998244353;
    int a[maxn],*p,n,cnt[maxn],tot,len;
    ll f[maxn],sum[maxn];
     
    inline void add(int x){
    	if(!cnt[p[x]]) ++tot;
    	cnt[p[x]]++;
    }
    inline void del(int x){
    	cnt[p[x]]--;
    	if(!cnt[p[x]]) --tot;
    }
    inline ll solve(){
    	sum[1] = f[1] = 1; add(1);
    	int hd = 1;
    	for(ri i = 2;i <= len;++i){
    		f[i] = (f[i-1] + f[i-2]) % mod; add(i);
    		int hhd = hd;
    		while(tot >= 3 && hd < i - 2)
    			del(hd),hd++;
    		if(hd > hhd) --hd,add(hd);
    		if(tot >= 3 && hd < i-2)
    			(f[i] += sum[hd]) %= mod;
    		sum[i] = (sum[i-1] + f[i]) % mod;
    	}
    	while(hd <= len) del(hd),hd++;
    	return f[len];
    }
    int main(){
    	cin>>n;
    	for(ri i = 1;i <= n;++i) cin >> a[i];
    	ll ans = 1;
    	for(ri st = 1,en;st <= n;){
    		while(st < n && a[st] == a[st+1]) ++st;
    		en = st;
    		while(en < n && a[en] != a[en+1]) ++en;
    		p = a + st - 1; len = en - st + 1;
    		ans = ans * solve() % mod;
    		st = en + 1;
    	}
    	printf("%lld\n",ans);
    	return 0;
    }

E

简要题意

有 \(A_i\) 个 \(i\) ，要求把所有数都丢进一个序列，相邻两个相同的数距离至少为 \(k\) ，求最小字典序的方案或判无解。\(\sum A_i \leq 200000,n \leq 500\)

题解

有一个显然的合法构造：把序列分成 \(kkk..kq\) ，\(1\leq q \leq k\)，共 \(p\) 个块。若 \(A_i>p\) ，直接无解；若 \(A_i=p\) ，将其放在每个块的相同位置；若 \(A_i<p\) 将其在剩下的空中从第一个空开始填，两个 \(i\) 距离超过 \(p\) 且尽量靠近。若没有 \(A_i > p\) 且 \(cnt[A_i=p] \leq q\)，这样一定可以构造出合法解。
因为要字典序最小，从第一位开始一位一位填。每次判当前后缀是否 \(cnt[A_i=p]=q\) 。

若是，找出 \(A_i=p\) 的 \(i\) 中最小的可以填的，填上
若不是，找出最小的可以填上的数，填上

可以证明这样能找出最优解且若最开始有解，最终一定有解。
为此只需要证明
\(a.\) 每个时刻对于当前后缀没有 \(A_i > p\) 且 \(cnt[A_i=p] \leq q\)。(只考虑后面)
\(b.\) 每个时刻都有可以填的数，即距离至少为 \(k\) 的。(考虑前面对现在的影响)
\(a\)很好证，因为每次 \(A_i=p\) 的个数堆满了我们就减掉了。
\(b\):设当前在位置 \(i\) ，若没有数可填发生在情况1，则前 \(k-1\) 个数包含了 \(q\) 个 \(A_j=p\)的 \(j\) ，而在 \(i-k+1\) 的位置，此时的后缀中 \(A_j=p+1\) 的也有 \(q\) 个，然而此时的 \(q'=q-1\) ，与 \(a\) 矛盾。情况2类似可以反证。
因此最开始的时候判一下无解，然后构造即可

Code

    #include<bits/stdc++.h>
    #define ri register int
    #define ll long long
    using namespace std;
    const int maxn = 2e5 + 10,N = 510;
    int a[N],ans[maxn],last[N],n,k,s;
    int main(){
    	scanf("%d%d",&n,&k);
    	for(ri i = 1;i <= n;++i) scanf("%d",&a[i]),s += a[i],last[i] = -k;
    	int cnt = 0;
    	for(ri i = 1;i <= n;++i){
    		if(a[i] > (s-1)/k+1){puts("-1");return 0;}
    		if(a[i] == (s-1)/k+1) ++cnt;
    	}
    	if(cnt > (s-1) % k + 1){
    		puts("-1"); return 0;
    	}
    	for(ri i = 1;i <= s;++i){
    		cnt = 0;
    		int x=0,y=0;
    		for(ri j = n;j >= 1;--j)
    			if(a[j]){
    				if(a[j] == (s-i)/k+1) ++cnt;
    				if(last[j]+k > i) continue;
    				if(a[j] == (s-i)/k+1) x = j;
    				y = j;
    			}
    		if(cnt == (s-i) % k + 1)
    			ans[i] = x,a[x]--,last[x] = i;
    		else ans[i] = y,a[y]--,last[y] = i;
    	}
    	for(ri i = 1;i <= s;++i) printf("%d ",ans[i]);
    	putchar('\n');
    	return 0;
    }

F

简要题意

\(n\) 个卡片，有两种属性 \(P,A\) ，每次玩家选一个卡片删掉并得到它的 \(A\) 累加进分数，机器人再找到剩下的 \(P\) 最大的卡删掉。\(P\) 为 \(1-n\) 的所有排列情况下，每个情况采取最优策略可以获得的最大分数总和。 \(n\) 是偶数。

题解

假设 \(A\) 降序。
考虑静态问题， \(P\) 确定，将卡片按 \(P\) 升序排列，每个偶数长的后缀最多选 \(\frac{len}{2}\) 个数，从前往后往堆里加入连续两个数，取出堆里最大的。

考虑 \(p\) 不确定，枚举 \(k\)，算\(A_k\) 及比其大的 \(A\) 总共统计了多少次。设 \(x_i\) 为 “\(P\) 是 \(i\) 的卡片的编号"，构造新的序列 \(y\)，所有 \(x_i\leq k\) 的位置 \(y_i=1\)，否则为 \(-1\)。当前贡献是 \(k!(n-k)!\)。然后对于一个确定的 \(y\) ，它的贡献是 \(k-max_{i=0,2...n} cnt_1(i)-i/2\) ， \(i\) 是从后往前 \(i\) 个元素。因为\(cnt_1(i)-\frac{i}{2}=\frac{cnt_1(i)-cnt_{-1}(i)}{2}\)，设 \(suf(i)\) 为 \(y\) 后 \(i\) 个元素的和，令 \(h=max_{i=0}^n \frac{suf(i)}{2}\) ，贡献变为 \(\lceil \frac{k+k-h}{2} \rceil\) ，然后枚举 \(h\) 。把最小的 \(i\) 且 \(suf(i)=h\) 的 \(i\) 记为 \(m\) ，把后 \(m\) 个元素翻转，并都乘上 \(-1\) ，则会得到新序列 \(z\) ，并且发现有趣的性质。

\(\sum z_i=2\cdot k-2\cdot h - n\)
\(\forall i,pre(i)\ge 2\cdot k-2\cdot h - n\)
第一个显然，第二个因为 \(y\)的后 \(m\) 个元素由一段最终到 \(h\) 的和一些先降后升总和为 \(0\) 的构成， \(z\) 的后 \(m\) 个元素任何后缀和都小于等于 \(0\) ，故成立。
发现符合这两个性质的 \(z\) 就可以对应一个 \(y\) ，所以对合法的 \(z\) 计数。发现把性质转到网格图上就可以类似卡特兰数那样，贡献就是 \(\binom{n}{k-h}-\binom{n}{k-h-1}\)
设大于等于 \(A_k\) 的数贡献了 \(f(x)\) 次，

\[f(k)=(n-k)!k!\sum\limits_{h=max(2k-n,0)}^k (\binom{n}{k-h}-\binom{n}{k-h-1})\cdot \lceil \frac{k+k-h}{2} \rceil \]

答案就是

\[\sum\limits_{i=1}^n (f(i)-f(i-1))\cdot a_i \]

因为取上整很多都会被抵消掉，所以可以用前缀和优化成 \(O(n)\) ，至于细节还需要分类讨论，手算一下即可

Code

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn = 1e6 + 10,mod = 998244353;
ll fac[maxn],inv[maxn],c[maxn],sum[maxn],f[maxn];
int a[maxn],n;
inline ll qp(ll x,int k){
	ll res = 1;
	while(k){
		if(k & 1) res = res * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return res;
}
inline ll C(int x,int y){
	return fac[x] * inv[y] % mod * inv[x-y] % mod;
}
inline ll calc(int k){
	ll res = 0;
	if(k <= n / 2){
		res = c[k] * k % mod;
		if(k >= 2) res = (res - sum[k-2] + mod) % mod;
	}
	else{
		res = c[n-k] * (n/2) % mod;
		if(n-k >= 2) res = (res - sum[n-k-2] + mod) % mod;
	}
	res = res * fac[k] % mod * fac[n-k] % mod;
	return res;
}
int main(){
	scanf("%d",&n);
	for(ri i = 1;i <= n;++i) scanf("%d",&a[i]);
	fac[0] = 1;
	for(ri i = 1;i <= n;++i) fac[i] = fac[i-1] * i % mod;
	inv[n] = qp(fac[n],mod - 2);
	for(ri i = n - 1;i >= 0;--i) inv[i] = inv[i+1] * (i+1) % mod;
	sort(a + 1,a + n + 1); reverse(a + 1,a + n + 1);
	c[0] = C(n,0); sum[0] = c[0];
	for(ri i = 1;i <= n;++i){
		c[i] = C(n,i); sum[i] = c[i];
		if(i >= 2) sum[i] = (sum[i] + sum[i-2]) % mod;
	}
	for(ri i = 1;i <= n;++i) f[i] = calc(i);
	ll ans = 0;
	for(ri i = 1;i <= n;++i) ans = (ans + (f[i]-f[i-1]+mod) * a[i] % mod) % mod;
	printf("%lld\n",ans);
	return 0;
}

码农公寓

A

题意

题解

Code

B

简要题意

题解

Code

C

简要题意

题解

Code

D

简要题意

题解

Code

E

简要题意

题解

Code

F

简要题意

题解

Code

相关文章