育华周赛 第十六期 接受dp的审判

T1

$x / 0.75$为整数等价于$x * 4 / 3$为整数，显然$x$是 3 的倍数即可。

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

int main() {
    long long x;
    cin >> x;
    // 判断 x 是否是 0.75 的整数倍
    // 等价于判断 4 * x 是否是 3 的整数倍
    if ((4 * x) % 3 == 0) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    return 0;
}

T2

类似于最长上升子序列,约束条件是$|a_i - a_j| \leq k$。由于$n \leq 1000$ 使用双重循环遍历即可。

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

const int N = 1010;
int a[N], dp[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            // 如果 a[i] 与 a[j] 的差的绝对值不超过 k
            if (abs(a[i] - a[j]) <= k) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

T3

根据排序不等式(请自行问 ai)，调整后$b_i$的排序序号和$a_i*i$的排序序号是对应的即可。

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

const int N = 2e5 + 5;
typedef long long ll;

int n;
ll a[N], b[N], ai[N], idx[N];

// 不用struct,可以这样解决
bool cmp(const int &i, const int &j) {
    return ai[i] > ai[j];
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ai[i] = a[i] * i;
        idx[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }

    // 对 a[i] * i 的索引进行降序排序
    sort(idx+1, idx + n+1, cmp);

    // 对 b 进行降序排序
    sort(b+1, b + n+1, greater<ll>());

    // 重新排列 b
    ll res[N];
    for (int i = 1; i <= n; ++i) {
        res[idx[i]] = b[i];
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}

T4

普通递推问题,总共有 5 种需要更新的状态,分别是 Y,YU,YUH,YUHU,YUHUA 的数量。

#include<bits/stdc++.h>
using namespace std;
string a;
int dp[100005][5];
long long mod=1e9+7;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a;
	for(int i=1;i<=a.size();i++){
		dp[i][0]=dp[i-1][0];
		dp[i][1]=dp[i-1][1];
		dp[i][2]=dp[i-1][2];
		dp[i][3]=dp[i-1][3];
		dp[i][4]=dp[i-1][4];
		if(a[i-1]=='Y'){
			dp[i][0]=(dp[i-1][0]+1)%mod;
		}
		else if(a[i-1]=='U'){
			dp[i][1]=(dp[i-1][1]+dp[i-1][0])%mod;
			dp[i][3]=(dp[i-1][3]+dp[i-1][2])%mod;
		}
		else if(a[i-1]=='H'){
			dp[i][2]=(dp[i-1][2]+dp[i-1][1])%mod;
		}
		else if(a[i-1]=='A'){
			dp[i][4]=(dp[i-1][4]+dp[i-1][3])%mod;
		}
	}
	cout<<(dp[a.size()][4])%mod;
	return 0;
}

T5

符号定义

• $sum[i]$：表示 $c[i]$ 的前缀和，即 $sum[i]=\sum_{j = 1}^{i}c[j]$ 。
• $C[i][j]$：表示组合数 $C_{i}^j$ 。

动态规划状态定义

设 $f[i][j]$ 表示使用了前 $i$ 种颜色涂了 $sum[i]$ 个板块，其中有 $j$ 对相邻同色块的方案数。

状态转移分析

考虑从 $f[i][j]$ 转移到 $f[i + 1][j - b + c[i + 1] - a]$ ：

• 把 $c[i + 1]$ 个板块分成 $a$ 组插入到已涂好的板块中。
• 其中 $b$ 组插入到之前同色板块之间，这会减少 $b$ 对相邻同色块；$a - b$ 组采用插空方式放置，使其不相邻，这会增加 $c[i + 1] - a$ 个新的板块，从而影响相邻同色块的数量。
• 转移的方案数为 $f[i][j] * C[c[i + 1] - 1][a - 1] * C[j][b] * C[sum[i] + 1 - j][a - b]$ ，其中：
  • $C[c[i + 1] - 1][a - 1]$ ：将 $c[i + 1]$ 个板块分成 $a$ 组的方案数（这里是无序分组 ）。
  • $C[j][b]$ ：将 $b$ 组插入到之前 $j$ 对相邻同色板块之间的方案数（考虑插入位置不同 ）。
  • $C[sum[i] + 1 - j][a - b]$ ：前面已有 $sum[i] + 1$ 个位置（包含间隔 ），由于 $j$ 个相邻同色块占据了一些位置不能放置，将 $a - b$ 组插入剩余位置的方案数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -f : f, ch = getchar();
    while (isdigit(ch)) ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

const int P = 1e9 + 7, N = 1000;
int n, col[N], sum[N], f[N][N], c[N][N];

signed main() {
    n = read();
    for (int i = 1; i <= n; ++i) col[i] = read(), sum[i] = sum[i - 1] + col[i];

    c[0][0] = 1;
    for (int i = 1; i <= 100; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= 100; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }

    f[1][col[1] - 1] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = 0; j <= sum[i] - 1; ++j)
            for (int a = 1; a <= min(sum[i] + 1, col[i + 1]); ++a)
                for (int b = 0; b <= min(j, a); ++b)
                    f[i + 1][j + col[i + 1] - a - b] +=
                        f[i][j] * c[sum[i] + 1 - j][a - b] % P * c[j][b] % P *
                        c[col[i + 1] - 1][a - 1] % P,
                        f[i + 1][j + col[i + 1] - a - b] %= P;

    printf("%lld\n", f[n][0]);
    return 0;
}

T6

知识点

涉及树形动态规划（树形DP）和深度优先搜索（DFS） 。

题意分析

1. 根节点选择：可随意选择一个非叶节点作为根节点，对最终答案无影响。因为着色方案要求根结点到每个叶子的简单路径上至少有一个有色结点，而叶节点的着色方案只与其上方第一个有色节点有关。
2. 状态定义：设 $f[i][j]$ 表示第 $i$ 个节点染成 $j$ 颜色所需的代价。
3. 代价分析：若某节点需染成 $x$ 色，且其父节点已染成 $x$ 色，该节点可继承父节点颜色，无需额外染色代价；否则，该节点被染成 $x$ 色的代价有两种情况：一是继承父亲染成 $x$ 色的代价；二是保持父亲为非 $x$ 色，单独将此节点染成 $x$ 色 。
4. 状态转移方程：
   • $f[u][0]+=\min(f[v][0] - 1, f[v][1])$
   • $f[u][1]+=\min(f[v][1] - 1, f[v][0])$
   • 这里 $u$ 是 $v$ 的父亲节点，方程表示将一个节点染成颜色 $j$ 的代价，是其所有子节点染成颜色 $j$ 代价的和 。

算法实现

1. 初始化：
   • 对于所有节点 $i$，令 $f[i][1] = 1$，$f[i][0] = 1$，表示将每个点染成某种颜色的代价均为 $1$ 。
   • 对于叶节点 $i$，若叶节点应变成的颜色为 $c[i]$，则令 $f[i][1 - c[i]] = INF$（$INF$ 为极大值 ），确保叶节点不会被染成其他颜色，不会用于更新其他节点 。
2. DFS过程：
   • 选择一个非叶节点作为树根开始DFS。
   • 到达叶节点时，直接返回，因为叶节点代价无需更新。
   • 对于非叶节点，循环枚举所有非父节点，先更新它们的值。
   • 递归回到某节点时，用已更新的子节点值来更新该节点的值。
3. 结果获取：DFS完成后，得到所有 $f$ 的值。由于根节点有染成 $0$ 色和 $1$ 色两种情况，在 $f[root][0]$ 与 $f[root][1]$ 中取最小值，即为所求答案。

#include<bits/stdc++.h>
#define min(a,b) a<b?a:b
//======================================================
const long long MARX = 1e4+10;
const long long INF = 2147483647;//极大值
struct edge
{
    long long u,v,ne;
}e[2*MARX];
long long m,n,c[MARX];//输入数据
long long root,num,head[MARX]; //建树
long long f[MARX][2]; // f[i][j]表示,第i个点,将其染成j颜色,所需要的代价
//======================================================
inline long long read()
{
    long long fl=1,w=0;char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    if(ch=='-') fl=-1;
    while(isdigit(ch)){w=w*10+ch-'0',ch=getchar();}
    return fl*w;
}
inline void add(long long u,long long v)
{
    e[++num].u=u,e[num].v=v;
    e[num].ne=head[u],head[u]=num;
}
void dfs(long long u,long long fa)
{
    if(u<=n) return ;//叶节点,直接return ;
    for(int i=head[u],v=e[i].v;i;i=e[i].ne,v=e[i].v)//枚举所有非父节点
        if(v!=fa)
        {
            dfs(v,u);
            f[u][0]+=min(f[v][0]-1,f[v][1]);//用子节点,更新当前点的各值
            f[u][1]+=min(f[v][1]-1,f[v][0]);
        }
}
//======================================================
int main()
{
    m=read(),n=read();
    root=n+1;//随意选择一个不为叶节点的节点
    for(int i=1;i<=n;i++) c[i]=read();
    for(int i=1;i<=m-1;i++)
    {
        long long u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)//初始化
    {
        f[i][0]=f[i][1]=1;
        if(i<=n) f[i][(!c[i])]=INF;//叶节点特殊初始化
    }
    dfs(root,root);
    printf("%lld",min(f[root][0],f[root][1]));//取较小的值
    return 0;
}