tea5.20-5.24

茶5.20-5.24

Mon

Ternary String 1354B

题目翻译：

输入T（T<=2⁴)，表示T组数据。所有数据的字符串长度之和<=2⁵。

每组数据输入一个长度<=2⁵的字符串，只包含数字’1’,’2’,’3’。

输出s中的最短子串的长度，该子串必须包含所有’1’’2’’3’三种字符。

如果没有这样的子串，输出0。

Sol：

用一个长为3的cnt数组维护子串内的1 2 3的个数。如果三个数的cnt都大于0，就更新答案的最小值，移动左端点。

Code：

void solve()
{
    string s;
    cin>>s;
    int length = s.size();
    vi cnt(3,0);
    int ans = INT_MAX;
    int left = 0,right = 0;
    for(right = 0; right < length; right++) {
        cnt[s[right]-'1']++;
        while(cnt[0]>0&&cnt[1]>0&&cnt[2]>0) {
            ans = min(ans,right-left+1);
            cnt[s[left]-'1']--;
            left++;
        }
    }
    if(ans==INT_MAX) {
        ans=0;
    }
    cout<<ans<<endl;
}

Feb

Frodo and pillows 760B

题目翻译：

输入n m k(1<=n<=m<=10⁹,1<=k<=n).

有一个长为n的数组a，已知其所有元素均为正整数，元素和等于m且|a[i]-a[i+1]|<=1.

问：a[k]最大能是多少？

Sol：

二分。设a[k]=mx,那么数组元素最佳是按照

… a[k-2] = mx-2,a[k-1] = mx - 1,a[k] = mx,a[k+1] = mx - 1,a[k+2] = mx - 2,…

这样元素和尽量小。按照上述规则，计算等差数列和cnt，通过比较cnt与m的大小来调整二分边界。

Code:

void solve()
{
    ll n,m,k;
    cin>>n>>m>>k;
    m -= n;
    long long lo = 0;
    long long hi = m;
    
    while (lo < hi) {
        long long mid = (lo + hi + 1) / 2;
        long long need = -mid;
        if (mid <= k) {
        need += mid * (mid + 1) / 2;
        } else {
        need += (mid + mid - k + 1) * k / 2;
        }
        if (mid <= n - k + 1) {
        need += mid * (mid + 1) / 2;
        } else {
        need += (mid + mid - n + k) * (n - k + 1) / 2;
        }
    
        if (need <= m) {
        lo = mid;
        } else {
        hi = mid - 1;
        }
    }
    
    cout << lo + 1 << "\n";
}

Wed

Infected Tree 1689C

题目描述：

输入 T(≤5000) 表示 T 组数据。所有数据的 n 之和 ≤3e5。 每组数据输入 n(2≤n≤3e5) 和一棵 n 个节点的二叉树的 n-1 条双向边。节点编号从 1 开始。 二叉树的根节点是 1。 一开始，根节点被感染。 然后执行如下过程 n 次：

首先，选择一个未被感染也未被删除的点，将其删除（相连的边也删除）；或者什么也不做。

然后，任何与被感染节点相邻的节点，都被感染。

输出最多可以让多少个点不被感染也不被删除。

拓展：

改成多叉树：传染病控制

Sol：

贪心 + 树形dp

当某颗子树的根节点被感染时，删除左儿子或右儿子，可以尽最大可能地减少感染。

那么应该删除左儿子还是右儿子，用dp判断最优解。

可以考虑感染和删除最少多少个点。

对于以v为根点子树而言，在v被感染的情况下：

1.如果v是叶子，返回1，表示v被感染。

2.如果v只有一个儿子，删除儿子，返回2，表示v被感染，v的儿子被删除。

3.如果v有两个儿子，枚举删除哪个儿子，递归另一颗子树w，返回dfs（w，v） + 2 的最小值，第二个参数是父节点。

答案为 n - dfs（1，0）。

Code：

int dfs(vector<vector<int>>& g, int v, int fa) {
    if (g[v].size() <= 2) {
        return g[v].size();
    }
    int mx = 1e9;
    for (int w : g[v]) {
        if (w != fa) {
            mx = min(mx, dfs(g, w, v) + 2);
        }
    }
    return mx;
}
void solve()
{
    int n;
    cin>>n;
    vector<vector<int>> g(n + 1);
    g[1] = {0};
    for(int i = 1; i < n; i++) {
        int v, w;
        cin>>v>>w;
        g[v].push_back(w);
        g[w].push_back(v);
    }
    cout << n - dfs(g, 1, 0) << endl;
}

Thu

Devu and Flowers 451E

输入 n(1≤n≤20) s(0≤s≤1e14) 和长为 n 的数组 a(0≤a[i]≤1e12)。

你有 n 个盒子，第 i 个盒子装有 a[i] 朵颜色一样的花（无法区分）。
此外，没有两个盒子中的花朵颜色相同。
从这些盒子中恰好选出 s 朵花的方案数是多少？

输入
2 3
1 3
输出 2

输入
2 4
2 2
输出 1

输入
3 5
1 3 2
输出 3

Sol：

容斥原理+组合数。

请先阅读 n=3 时的题解 看成是把 s 个无区别的小球，分给 n 个有区别的盒子，第 i 个盒子至多容纳 a[i] 个小球。

计算方法同上面的力扣题（n=3 的情况）。

枚举 a 的所有子集，子集中的盒子预先分配 a[i]+1 个小球。 剩余的小球 s2 按照 C(s2+n-1,n-1) 计算方案数。 组合数 C(n,k) 的计算可以分别计算分子和分母，最后用模运算除法解决。 关于模运算除法请看 模运算的世界：当加减乘除遇上取模 注意 n 很大，要先把 n 取模。 注意使用 64 位整数。 代码 优化：预处理 n-1 以内的阶乘的逆元

Code:

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20;

int n;
long long f[N];

const int MOD = 1000000007;

int inv(int a) {
	return a == 1 ? 1 : (long long)(MOD - MOD / a) * inv(MOD % a) % MOD;
}

long long choose(long long s, long long n) {
	long long ret = 1;
	for (int i = 0; i < n; ++i) {
		ret = (long long)ret * ((s - i) % MOD) % MOD * inv(i + 1) % MOD;
	}
	return ret;
}

long long go(int i, long long s) {
	if (s < 0) {
		return 0;
	}
	if (i == n) {
		return choose(s + n - 1, n - 1);
	}
	return (go(i + 1, s) - go(i + 1, s - f[i])) % MOD;
}

long long s;

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; ++i) {
		cin >> f[i];	
		++f[i];
	}
	cout << (go(0, s) + MOD) % MOD << endl;
	return 0;
}

Fri

状压 DP！

优美的排列

如果一个 1-n 的排列 p，对于每个 i=1,2,3,…n，都满足 i 和 p[i] 其中一个能整除另一个，则称 p 是好的。
输入 n(1≤n≤15)，输出有多少个 1-n 的排列是好的。

输入 2
输出 2
解释 [1,2] 和 [2,1]

输入 1
输出 1

额外加练：

Hossam and Range Minimum Query

题解(仙佬的）:https://www.cnblogs.com/Athanasy/p/18012165

Sol：（摘自灵神）

1.寻找子问题

将1-n的排列简记为p

假设n=5，先不考虑整除：

• 枚举p₁选哪个，它可以是1，2，3，4，5，假设p₁=2.
• 枚举p₂选哪个，它可以是1，3，4，5，假设p₂=4.
• 枚举p₃选哪个，它可以是1，3，5，假设p₃=5.
• 枚举p₄选哪个，它可以是1，3，假设p₄=3.
• 枚举p₅选哪个，它只可以是1，所以p₅=1.

在这个过程中，我们需要知道：哪些数不能选。可以用一个集合S存储选过的数。枚举p_i的值，然后加入集合S。注意剩下能选的数变少了，要解决的问题规模也小了。

所以我们可以考虑递归解决。但是注意上述过程中，会产生重复子问题,例如

• 目前生成的排列 p = [2,4,1,,], 现在递归到倒数第二个位置，那么 S = {1,2,4}.
• 目前生成的排列 p = [4,2,1,,], 现在递归到倒数第二个位置，那么 S = {1,2,4}.

前面的排列具体如何，我们并不关心，我们记录的是无序的集合，不是有序的列表。

2.状态定义和状态转移方程

按照上面的讨论，定义dfs(S)表示在之前选过的数的集合为S的情况下，剩余数字可以构造的优美排列的数量。

考虑p_i选什么：

• 枚举 j = 1,2,…,n,且j $\notin$ S 且 i 和 j 一个可以整除另一个
• 要解决的问题变成：在之前选过的数的集合为 S $\bigcup$ {j} 的情况下，剩余数字可以构造的优美排列的数量，即dfs(S $\bigcup$ {j}).

$$dfs(S) = \sum_jdfs(S \bigcup {j})$$

递归边界: dfs(U) = 1,其中全集 U = {1,2,…n}.如果能递归到S = U的状态，表示所有数都选完了，我们找到了一个合法排列。

递归入口:dfs($\emptyset$),也就是答案。其中$\emptyset$表示空集，因为一开始什么也没选。

3.递归搜索+保存递归返回值=记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆话搜索来优化：

• 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个memo数组中。
• 如果一个状态不是第一次遇到（memo中保存的结果不等于memo的初始值），那么可以返回memo中保存的结果。

Code:

class Solution {
public:
    int countArrangement(int n) {
        vector<int> memo(1 << n, -1);
        function<int(int)> dfs = [&](int s) -> int {
            if (s == (1 << n) - 1) {
                return 1;
            }
            int &res = memo[s];
            if (res != -1) {
                return res;
            }
            res = 0;
            int i = __builtin_popcount(s) + 1;
            for (int j = 1; j <= n; j++) {
                if ((s >> (j - 1) & 1) == 0 && (i % j == 0 || j % i == 0)) {
                    res += dfs(s | (1 << (j - 1)));
                }
            }
            return res;
        };
        return dfs(0);
    }
};