最开始有一克金
第 \(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} \]显然不会更优
#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=\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\) ,继续执行。
#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; }
有 \(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("%lld\n",ans); return 0; }
有 \(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.\) 每个时刻对于当前后缀没有 \(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_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\limits_{i=1}^n (f(i)-f(i-1))\cdot a_i \]因为取上整很多都会被抵消掉,所以可以用前缀和优化成 \(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("%lld\n",ans); return 0; }