「杂题选讲」#2
菜死了啊。
都是些比较简单的题目，可惜我做不出来
ABC261D Flipping and Bonus
分析
称正面朝上为获胜，反面朝上为失败。
一开始认为，输掉一局相当于把计数器置 \(0\)，所以应该加入状态，设 \(f(i,j)\) 为前 \(i\) 局，输掉 \(j\) 局，所能得到的最大收益。这个状态最大的问题是信息缺失。你怎么知道你赢下第 \(i\) 局是几连胜？无法转移。
设 \(f(i,j)\) 为前 \(i\) 局，其中第 \(i\) 局为 \(j\) 连胜。特别地，当 \(j=0\) 时表示输掉第 \(i\) 局。相比于上一个状态，这个状态是能够进行转移的，且没有荣誉信息，是正确的状态。
转移就比较简单了 \[ f(i,j) = \begin{cases} f(i-1,j-1) + x_i + b_j & j > 0 \\ \max_{k \in [0,i-1]}{\{ f(i-1,k) \}} & j=0 \end{cases} \] 最终答案 \[ \max_{i \in [1,n]} {\{ f(n,i) \}} \] 最后一局输掉显然不划算啊。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5005;
int n, m, x[N], b[N], f[N][N];
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
signed main() {
n=read(), m=read();
for(int i=1;i<=n;++i) x[i]=read();
for(int i=1;i<=m;++i) {
int c=read(), y=read();
b[c]=y;
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=i;++j) f[i][j]=f[i-1][j-1]+x[i]+b[j];
f[i][0]=0;
for(int j=0;j<i;++j) f[i][0]=max(f[i][0],f[i-1][j]);
}
int ans=0;
for(int i=1;i<=n;++i) ans=max(ans,f[n][i]);
printf("%lld\n",ans);
}ABC261D Sorting Color Balls
分析
首先明确冒泡排序的交换次数就是逆序对的个数。
注意到相同颜色的球，交换它们是不耗费代价的。
很容易想到答案即为总的逆序对个数减去同种颜色的逆序对个数。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n, ans, a[N], c[N];
vector<int> p[N];
void modify(int x,int y) { for(;x<=3e5;x+=x&-x) c[x]+=y; }
int query(int x) {
int ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
signed main() {
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) {
int x=read();
p[0].push_back(x);
p[a[i]].push_back(x);
}
for(int i=0;i<=n;++i) {
int sz=p[i].size();
for(auto x:p[i]) {
int dlt=query(n)-query(x);
// 逆序对
if(!i) ans+=dlt; else ans-=dlt;
// i=0为原序列，否则为颜色i
modify(x,1);
}
for(auto x:p[i]) modify(x,-1);
// 删除
}
printf("%lld\n",ans);
}ABC262C Min Max Pair
分析
注意到当 \(a_i = i\) 与任何 \(a_j = j\)，其中 \(i < j\)，配对时都满足条件。设满足 \(a_i = i\) 的 \(i\) 的个数为 \(t\)，则答案一定含有 \(\frac{t(t+1)}{2}\)。
否则若 \(a_i = j\) 且 \(j > i\)，那么 \(a_j\) 必须为 \(i\) 才能满足条件。扫一遍即可。
CODE
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
int n, ans, t, a[N];
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
signed main() {
n=read();
for(int i=1;i<=n;++i) {
a[i]=read();
if(a[i]==i) ++t;
}
ans=t*(t-1)/2;
for(int i=1;i<=n;++i) {
if(a[i]>i&&a[a[i]]==i) ++ans;
}
printf("%lld\n",ans);
}
ABC262D I Hate Non-integer Number
分析
平均数是个整数，说明分子模分母为 \(0\)。既然是个计数问题，考虑 DP。
这类问题的一个技巧就是，将分子模分母的结果加入状态。这样要求的问题变为了 DP 求出的一个子问题，在面对某些有特殊条件限制问题时有奇效，这也是为什么很多时候都要“考虑问题的简化版”。一开始我根本无法理解这种做法，后来才慢慢明白，为了 DP 而去 DP，在很多时候时行不通的。
设 \(r\) 为选出 \(r\) 个数的阶段。当 \(r=1\) 时，贡献显然为 \(n\)。这东西加不加进状态都无所谓，反正就当个模数。
设 \(f(i,j,k)\) 为考虑前 \(i\) 个数，选出了 \(j\) 个数，这 \(j\) 个数之和模 \(r\) 为 \(k\) 的方案数。注意如果是模 \(j\) 为 \(k\) 的话，无后效性就没了。
由于存在取模，所以这类状态还是使用刷表法比较好。 \[ f(i-1,j-1,k) \rightarrow f(i,j,k+a_i \bmod r ) \] 答案为 \[ n + \sum_{r=2}^n f(n,r,0) \] 注意到对于每一个阶段 \(r\)，相当于一个 0/1 背包问题，优化掉 \(i\) 这一维即可。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105, mod=998244353;
int n, ans, a[N], f[N][N];
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
signed main() {
n=read();
for(int i=1;i<=n;++i) a[i]=read();
ans=n;
for(int r=2;r<=n;++r) {
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=1;i<=n;++i) {
for(int j=min(i,r);j;--j) for(int k=0;k<r;++k)
(f[j][(k+a[i])%r]+=f[j-1][k])%=mod;
}
(ans+=f[r][0])%=mod;
}
printf("%lld\n",ans);
}ABC262E Red and Blue Graph
分析
提神醒脑数学题。
要求是
- 恰好有 \(k\) 个红点。
- 连接不同颜色点的边的数量为偶数。
设这 \(k\) 个红点的度数和为 \(Deg_k\)，连接红点的边的数量为 \(Red\)，连接不同颜色点的数量为 \(RedBlue\)，那么由于每条连接红点的边在度数中被统计了两次，则 \[ Deg_k = 2 Red + RedBlue \] 注意到 \(Deg_k\) 和 \(RedBlue\) 同奇偶。
题目要求 \(RedBlue\) 为偶数，可知 \(Deg_k\) 是偶数。于是乎求出每个节点的度数 \(deg_x\)，数量为 \(odds\)。
从 \(odds\) 中选出偶数 \(t\) 个点作为红点，在其他点中任选 \(k-t\) 个点作为蓝点，组合数求方案就行了。由于红点是计数的基准，所以蓝点的选择对答案没有贡献。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5, mod=998244353;
int n, m, k, odd, ans, deg[N], fac[N], inv[N];
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
int fp(int x,int y) {
int z=1; x%=mod;
for(;y;x=x*x%mod,y>>=1) if(y&1) z=z*x%mod;
return z;
}
int C(int n,int m) { return fac[n]*inv[m]%mod*inv[n-m]%mod; }
signed main() {
n=read(), m=read(), k=read();
for(int i=1;i<=m;++i) {
int x=read(), y=read();
++deg[x], ++deg[y];
}
fac[0]=fac[1]=1;
for(int i=2;i<=n;++i) fac[i]=fac[i-1]*i%mod;
inv[n]=fp(fac[n],mod-2);
for(int i=n-1;~i;--i) inv[i]=inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;++i) if(deg[i]&1) ++odd;
for(int i=0;i<=k;i+=2) {
if(i<=odd&&k-i<=n-odd)
(ans+=C(odd,i)*C(n-odd,k-i)%mod)%=mod;
}
printf("%lld\n",ans);
}NowCoderT62C 莫娜与阿贝多
分析
注：你的最优策略是依赖于每一步的掉落结果的。
……
很好，和博弈论没有关系。
随机应变啊。
等等！这不就是 DP 中的最优子结构性质？
设 \(f(i,j,k)\) 为 \(i\) 级物品剩下 \(j\) 个，\(i+1\) 级物品剩下 \(k\) 个，能达到目标的概率。
边界是 \(f(m,i,0) = 1\)，其中 \(i \ge n\)。
当 \(j \in [0,2]\) 时，无法进行合成 \[ f(i,j,k) = f(i+1,k,a_{i+2}) \] 否则 \[ f(i,j,k) = \max \begin{cases} p \cdot f(i,j-2,k+1) + (1-p) \cdot f(i,j-3,k+1) \\ q \cdot f(i,j-3,k+2) + (1-p) \cdot f(i,j-3,k+1) \end{cases} \] 答案 \(f(1,a_1,a_2)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
int n, m, a[N];
double p, q, f[10][N][N];
int read() {
int a=0, f=1; char c=getchar();
while(!isdigit(c)) {
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) a=a*10+c-'0', c=getchar();
return a*f;
}
signed main() {
n=read(), m=read();
scanf("%lf%lf",&p,&q);
for(int i=1;i<=m;++i) a[i]=read();
for(int i=n;i<=1e3;++i) f[m][i][0]=1.0;
for(int i=m-1;i;--i) {
for(int j=0;j<=2;++j) for(int k=0;k<=1e3;++k) f[i][j][k]=f[i+1][k][a[i+2]];
for(int j=3;j<=1e3;++j) for(int k=0;k<=1e3;++k) {
double k1=p*f[i][j-2][k+1]+(1-p)*f[i][j-3][k+1];
double k2=q*f[i][j-3][k+2]+(1-q)*f[i][j-3][k+1];
f[i][j][k]=max(k1,k2);
}
}
printf("%.6lf\n",f[1][a[1]][a[2]]);
}