脚本宝典收集整理的这篇文章主要介绍了ARC128题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
最开始有一克金 第 (i) 天若有金 (x) 克，可以把所有金换成 (A_icdot x) 克银 若有银 (x) 克，可以把所有银换成 (frac{x}{A_i}) 克金 问最后有多少克金
金变银、银变金一定是成对的，设一对变换的下标分别是 (x) 和 (y) ，发现 (x) 和 (y) 一定是一段下降序列的两端。因为若中间 (a) 变金 (b) 变银，那么贡献由
显然不会更优
#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;
}
有三种颜色的球各若干个，每次操作可以把两个异色的球变成与它们都不同的颜色，找到最少操作次数使所有球颜色一样或判无解
设三种颜色的球分别有 (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) 。
#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;
}
给你 (n,m,s) 以及大小为 (n) 的序列 (a) ，求实数序列 (x) 满足
发现序列要单调不降，转差分， (d_i=x_i-x_{i-1}),(v_i=sumlimits_{j=i}^n a_j),(c_i=n-i+1)
(d_ige 0)
(sumlimits_{1le jle ile n} d_j le m)
(sumlimits_{i=1}^n d_itimes c_i = s)
求(sumlimits_{i=1}^n d_itimes 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) ，继续执行。
#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("%.7lfn",ans);
return 0;
}
有 (n) 个球，上面有颜色，每次操作可以选择三个相邻的球，要求中间的球与两边的球颜色都不同，可以选择删去中间的球，两边的球就会相邻。问最终剩下的球有多少种可能情况。相同颜色但初始位置不同视为不同的球。
发现剩下的球两两之间的球都被删空了，可以线性 (DP) 求出答案，但需要区间 (DP) 求两个球之间的球能否全部删掉。线性 (DP) 可以考虑前缀和之类的优化成 (O(n)) ，瓶颈在区间 (DP) 。然后把原序列分成若干"最长的、连续的、相邻球颜色不同的段"，因为段之间的贡献独立。 结论：
(2):若颜色个数 (=2) ，则为(xyx...xy) 这类，中间的一定删不空。否则一定存在一段为 (...xyz..) ，若删去 (y) 后仍有三种颜色就删去 (y) 然后递归，否则删去 (z) 然后递归，直至大小为 (3)。
把每一段扣除来，因为符合条件的转移点一定是一个前缀，用一个指针往后扫找到最大的转移点，然后加上前缀和。最后的答案就是每一段的答案乘起来。
#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("%lldn",ans);
return 0;
}
有 (A_i) 个 (i) ，要求把所有数都丢进一个序列，相邻两个相同的数距离至少为 (k) ，求最小字典序的方案或判无解。(sum A_i leq 200000,n leq 500)
有一个显然的合法构造：把序列分成 (kkk..kq) ，(1leq 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.) 每个时刻对于当前后缀没有 (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类似可以反证。 因此最开始的时候判一下无解，然后构造即可
#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;
}
(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_ileq 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) ，并且发现有趣的性质。
答案就是
因为取上整很多都会被抵消掉，所以可以用前缀和优化成 (O(n)) ，至于细节还需要分类讨论，手算一下即可
#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("%lldn",ans);
return 0;
}以上是脚本宝典为你收集整理的ARC128题解全部内容，希望文章能够帮你解决ARC128题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。