Znzryb's Blog
0%

Posted on Edited on

题目大意

给定一棵有 n 个顶点的有根树,根节点为 1。每个叶子节点上都有一个樱桃。

你需要通过"摇动"顶点来收集所有樱桃。摇动顶点 v 时,所有作为 v 后代的叶子节点上的樱桃都会掉落。每个叶子的樱桃只能掉落一次,否则树会损坏。

关键限制:摇动的顶点数量必须是 3 的倍数。

问题:是否可能在满足上述条件下收集所有樱桃?

输入格式:

  • 第一行:测试用例数 t (1 ≤ t ≤ 10⁴)

  • 每个测试用例:第一行为 n (2 ≤ n ≤ 2×10⁵),接下来 n-1 行描述树的边

**输出格式:**对每个测试用例输出 “YES” 或 “NO”

思路讲解

当你发现一个问题的子结构之间互相重叠覆盖，其中还涉及这个决策的时候，这个时候，你就要想，是不是 dp 了。

树上 dp，定义状态为 dpu,idp_{u,i}，指的是以 uu 为根的子树中，是否可以凑出来为这个 i (0,1,2)i\ (0,1,2) 的这个 3 的余数。

接着问题就来到了如何转移？我们不妨定义，toto 为转移过来的子节点，四个你可以理解为 bitset 的东西，长度为 3，bibi 为目前的状态，若 dpto,0dp_{to,0} 为 true，那么 bi1bi1 就是这个 bibi 向前循环移动的结果，否则 bi1bi1 为全 0。同理，我们可以定义出 bi0bi0，bi2bi2。最终经过这个 toto 节点的转移后，bi←bi0∨bi1∨bi2bi\gets bi0 \lor bi1 \lor bi2。（当然，第一个 toto 节点转移过来的话，为了初值确定，bi←dptobi\gets dp_{to}）

最后，令 bi1←truebi_1\gets \text{true}（因为我们始终可以选择子树根节点，来解决这个问题），接着 dpu←bidp_u\gets bi。

为什么要这么转移？我们会发现，就是说如果子树只有一个唯一的位移的话，是不是只是让这个状态进行一个位移？那么其实只有一个位移是没什么大用的，但是如果有两种位移？三种位移？这几种位移之间如何组合？那么答案就昭然若揭了。

AC代码

AC
https://codeforces.com/contest/2184/submission/357994744

心路历程（WA，TLE，MLE……）

image

Posted on Edited on

题目大意

给定一个长度为 n 的排列 p。定义一个数组为 k-exquisite 当且仅当：

  • 该数组至少包含两个元素

  • 任意两个相邻元素的差的绝对值至少为 k

对于每个 k（从 1 到 n-1），需要求出排列 p 中有多少个子数组是 k-exquisite 的。

输入格式：

  • 第一行：测试用例数 t（1 ≤ t ≤ 25000）

  • 每个测试用例：

    • 第一行：整数 n，排列的长度（2 ≤ n ≤ 10⁵）
    • 第二行：n 个整数 p₁, p₂, …, pₙ，表示排列（1 ≤ pᵢ ≤ n，且各不相同）

输出格式：

对于每个测试用例，输出 n-1 个整数，第 i 个整数表示 i-exquisite 子数组的个数。

数据范围：

  • 时间限制：2 秒

  • 内存限制：256 MB

  • 所有测试用例的 n 之和不超过 2×10⁵

思路讲解

感觉比 D，B 简单。

如果只需要求这个 k-exquisite 子数组的个数，那就直接双指针，不过这波是要求这个 i-exquisite 子数组的个数。

我们想到，其实这个无非就是把整个数组切成了几段，我们可以采用做减法的方式，去解决这个问题。具体来讲，设我们所求的这个子数组参数为 kk，一个差值 Δ\Delta，k≤Δk≤\Delta 可以直接跨过去，k>Δk>\Delta 就不可以。

image

不难想到，我们可以对这个差值进行排序，或者一种更方便的实现是使用这个 map，并在 set 中存放分隔点，初始设置为这个 0，N（其实这里是一个坑点，不要选成 0，N+1 了，因为我们的分隔点采用前向点，最大为 N-1，因此哨兵应该选 N）。不难发现，设我们的新分隔点为 pospos，set 数组中第一个比我们小的数字是 lowlow，第一个比我们大的数字是 highhigh，我们所需要减去的值就是 (pos−low)×(high−pos)(pos-low)\times(high-pos)，即 low 区有 (pos−low)(pos-low) 种选择，high 区是 (high−pos)(high-pos) 种选择，使用乘法原理乘起来即可。

1
2
3
4
5
6
7
8
9
10
11
set<ll> st={0,N};
for (int i=1;i<=N-1;++i) {
    cout<<ans<<" ";
    for (auto pos:mp_diff_pos[i]) {
        ll low=get_lower(pos);
        ll high=*st.lower_bound(pos);
        ll minus=(pos-low)*(high-pos);
        ans-=minus;
        st.insert(pos);
    }
}

AC代码

AC
https://codeforces.com/contest/2184/submission/357897043

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

Bob 想了一个 1 到 n 之间的数字（n = 2^d）。Alice 初始知道这个数字是奇数还是偶数。

Alice 每回合可以选择：

  • 将当前数字除以 2（仅当数字为偶数时）

  • 将当前数字减 1

每次操作后，Bob 会告诉 Alice 一个非负整数 x，表示当前数字 a 能被 2^x 整除，但不能被 2^(x+1) 整除。如果数字变为 0，Alice 获胜。

游戏最多进行 k 回合。求有多少个初始数字（1 到 n）使得 Alice 在最优策略下无法在 k 回合内获胜。

ABC-387-C - Snake Numbers 

HDU - 2089- 不要62

思路讲解

在题目要求下，一个数字要删多少次有规律吗？其实就是 popcount(x)+⌊log⁡2(x)⌋\text{popcount}(x)+\lfloor\log_{2}(x)\rfloor

然后问题就来到了这个怎么样快速统计了，这个是这道题目的难点。当然，显然我们应该使用这个数位 dp。

那么我们一般数位 dp 采用的是这个记忆化搜索，我们定义搜索递归函数为 dfs(len,limit)dfs(len,limit) ，dplen,limit,valdp_{len,limit,val} 表示在 $len $ 长度下，limitlimit 受或不受 nn 高位限制的情况下，数字所需消耗次数为 valval 的数有几个。

然后我们来想一想，就是这个普通搜索，我们要知道 dfs(len,limit)dfs(len,limit) 的结果，进入到 dfs(len,limit)dfs(len,limit) 之后，我们需要搜什么？显然，我们需要搜索 dfs(len−1,?)⋯dfs(l,?)⋯dfs(0,?)dfs(len-1,?)\cdots dfs(l,?)\cdots dfs(0,?)，因为我们要搜索所有可能会转移到这个状态的状态。

从状态 l→lenl\to len，那么会增加多少消耗次数呢？Δ←len−l+1\Delta \gets len-l+1（长度增加 len−llen-l，还增加了一个 1）。

⚠️ 注意：从 0 转移过来的特殊情况，Δ←len−l\Delta \gets len-l，如果你像我一样认为 0 的二进制长度为 1 的话（这个是因为，我们虽然认为 0 的二进制长度为 0，但是实际上我们的 lenlen 并没有增加 lenlen 的长度，只增加了 len−1len-1 的长度）。

那么前面讲的有点抽象，举个例子就是，(1011)2(1011)_{2} 就是从 (11)2(11)_{2} 转移过来的，因为我们的状态设计是不包含前导 0 的。当然，如果 (1011)2(1011)_{2} 就是题目中的 n 的话（即表示二进制长度为 4 的上限限制），除了 (11)2(11)_{2}，还可以从 (1)2(1)_2，(0)2(0)_2 转移过来，但是显然不能从 (100)2(100)_2 等二进制长度为 3 的状态转移过来。

最后统计答案的时候，需要将这个 dfs(len,1),dfs(len−1,0),⋯ ,dfs(0,0)dfs(len,1),dfs(len-1,0),\cdots,dfs(0,0) 的状态结果累和得到答案。

AC代码

AC
https://codeforces.com/contest/2184/submission/357806886

心路历程（WA，TLE，MLE……）

向左短路 RE 了。

image

首先，不难发现，在题目要求下，我们只能够在二进制第一个 1 出现位置进行操作，把这个 1 后面出现的所有 0 全部消除。所以说，一个数字要删多少次有规律吗？

首先，不妨定义状态，dpidp_i 指的是

当然，虽然知道了要使用数位 dp，如何实现也至少是需要想一想的。虽然说数位 dp 一般采用这个自顶向下的记忆化搜索设计方法，但是这道题目没什么限制条件，以计数为主，直接采用这个递推法即可。

dplen,idp_{len,i} 表示在该（二进制）长度下，val=ival=i 的这个数字的数量。

dplen,i←∑l=0len−1dpl,i+1+len−ldp_{len,i}\gets \sum_{l=0}^{len-1}dp_{l,i+1+len-l}

那么我们一般数位 dp 采用的是这个记忆化搜索，我们就先想搜索吧，搜索 [0,n][0,n] 有几个数字的 val>kval>k。当然这个有点奇怪，我们不妨假设我们是求的这个 [0,n][0,n] 下，val=ival=i 的这个数字的数量，即 dpidp_i。

那我们要搜索这个东西，需要什么呢？dfs(len,ismax)dfs(len,ismax) 可以吗？我们先试试，我们首先发现，只有 dpidp_{i} 无法满足这个我们的要求，设置为 dplen,idp_{len,i} 更为合适。

Posted on Edited on

这道题目没开出来，这把实在打的太唐了。

总结而言，有三点问题：

第一是这个没看榜，还是要经常看榜，观察这个题目的出题速度，人数变化情况，一旦这个人数超过 5000 以上，或者在比赛未过半的时候达到 3000，那么就说明这道题目就是非常简单，还是能比较简单的可以看出来/猜出来的（就比如说这道题目，这个神秘小性质还是很简单的）。

其实也没有其他问题，div3 的经验我确实比较少，最近打的比较少。

题目大意

给定一个包含 N 个苹果的堆，每次可以将一个堆分成两个堆，如果原堆有 x 个苹果，则分成 ⌊x/2⌋ 和 ⌈x/2⌉ 两个堆，每次分堆需要 1 分钟。

问能否通过若干次分堆操作得到一个恰好包含 K 个苹果的堆？如果可以，求最少需要多少分钟。

输入：

  • 第一行一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例数量

  • 每个测试用例一行两个整数 n 和 k (1 ≤ n, k ≤ 10⁹)，分别表示初始苹果数和目标苹果数

输出：

对于每个测试用例，如果无法得到恰好 K 个苹果的堆，输出 -1；否则输出最少需要的分钟数。

思路讲解

其实这道题目只需要一个关键结论，就是第 kk 步只可能产生 ⌊N2k⌋\lfloor\frac{N}{2^k}\rfloor 或者 ⌈N2k⌉\lceil\frac{N}{2^k}\rceil（当然这两个可能相等）。因此就猜一下就可以了。

当然，利用这个结论，也可以写一个记忆化 bfs，详细地来说，用一个 set 存一下，搜过的数字就不继续搜了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (!q.empty()) {
    auto [x,step]=q.front();
    q.pop();
    if (x==K) {
        cout<<step<<"\n";
        return;
    }
    if (x<K) {
        continue;
    }
    auto res=st.emplace(x/2,step+1);
    bool con=!res.second;
    if (!con) {
        q.emplace(x/2,step+1);
    }
    res=st.emplace((x+1)/2,step+1);
    con=!res.second;
    if (!con){
        q.emplace((x+1)/2,step+1);
    }
}
cout<<-1<<"\n";

AC代码

AC
https://codeforces.com/contest/2184/submission/357642090

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

AC代码

https://www.codechef.com/viewsolution/1209777968

心路历程（WA，TLE，MLE……）