2022蓝桥杯省赛复盘+部分题解（C++ A组）_C

与其说写题解，不如说是自己场上心里完全没数，下来想一遍发现T1（没加周围4刀）,T2（把放满的状态当成了先手败，惯性思维了属于是）,T4,T6（漏写更新条件）都挂了，心态爆炸. OI赛制恐怖如斯，估计只有60分了，连国赛都去不了了。

该好好反省下自己做题浮躁的习惯了，上次CSP就两眼出思路的T4也是卡了两小时，导致没时间做T3。

更远的追溯到南京，2h12min第一发交H的树形dp，思路没错，因为写错变量名卡到4h24min（就是这么离谱），下来看了看1h内解决掉I,也算痛失银牌。

。

虽说acm不像OI,但也要少吃罚时少卡题。

另外第一次学对拍，附上对拍代码：

int main(){
    while(1){
        system("gen.exe > in.txt");
        system("E.exe < in.txt > out1.txt ");
        system("baoli.exe < in.txt > out2.txt ");   //baoli中间不能有空格，不然命令行识别不了
        if(system("fc out1.txt out2.txt")) break;
    }
}

法一：dp，记dp(r,c)表示切割一块r行c列的最少次数（没算外围的四刀），转移方程:

dp(r,c)=min(1+dp(r-i,c)+dp(i,c)), 1<=i<=r-1;

dp(r,c)=min(1+dp(r,c-j)+dp(r,j)), 1<=j<=c-1;

最后答案:dp(20,22)+4;
法二：考虑每条要切割的边(如图中红线，长度为1)，如果一次只能切割一条边，答案就是边数=21 * 20+19 * 22；
不过显然可以一次切多条边。

考虑每个交点对节省切割次数的贡献，对于每个交点，最优的方法是要么横着，要么竖着切，只能选一种，1次切了2条，使次数-1。

那么答案 - = 交点数（19 * 21）。

B
博弈论+状压dp.
用8位2进制数记录8个格子的状态，每位上为1代表对应方格被选，0代表没被选。

dp[i]=1时代表i为先手必胜态。

博弈论基础可知，先手必败态可转移到若干先手必胜态，而转移过后的状态标号一定小于原标号，故倒序做一遍即可。

Code:

#include
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define IOS {cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);}
#define ll long long
#define P pair<int,int>
int t[]={1,2,4,8,16,32,64,128,3,6,12,48,96,192};
int dp[256];//当前情况下先手是否必胜
int main(){
    dp[255]=1;  //场上读假题了,惯性思维以为谁放不了谁输..
    per(i,255,0){
        if(!dp[i]){
            rep(j,0,13){
                if((i|t[j])==i )dp[i^t[j]]=1;
            }
        }
    }
    cout<<dp[1]<<dp[3]<<dp[2]<<dp[6]; //实际上此时小蓝是后手
}

C
全场最简单的送分题感觉。

记sum为n个数之和。

对于特定i, ∑ j = 1 n a i ∗ a j \sum_{j=1}^na_i*a_j ∑j=1nai∗aj = a i a_i ai * (sum- a i a_i ai);
考虑每对积算两次，则2 * ans= ∑ i = 1 n a i \sum_{i=1}^na_i ∑i=1nai*(sum- a i a_i ai).
或者想不到算两次的话，遍历的过程中维护sum即可。

D
从D题开始怎么难度就上来了啊。

。

（第一次参赛，天真的我还以为真的是暴力杯，题目会很水（bushi））
题面：

大致想法是对 a l a_l al^ a r a_r ar=x 的一对(l,r)更新区间，即左端点位于[1,l],右端点位于[r,n]的询问是yes,比较常见的离线套路。

做法：离线询问，并按右端点从左到右对询问排序。

从左向右遍历，遍历到i时，将i视为 a l a_l al^ a r a_r ar=x 的(l,r)中的r。

对于前面所有的 a l a_l al^x= a r a_r ar,只考虑最靠右的 a l a_l al即可，这个由于数据范围小可以用一个数组实现。

那么右端点>=i的所有询问，如果左端点<=l即为yes。

由于询问是按右端点排序的，统计询问答案也是随着遍历有序的。

E
期望dp+逆元
记 d p i dp_ i dpi为爬到高度i时的期望时间，直接上式子：
d p i − 1 dp_ {i-1} dpi−1=（1- p i p_i pi）* d p i dp_i dpi + p i p_i pi * d p 0 dp_0 dp0 + 1;
显然 d p n dp_n dpn=0,那么我们可以得到n个关于 d p 0 dp_0 dp0— d p n − 1 dp_{n-1} dpn−1的式子，解出 d p 0 dp_0 dp0即可。

发现 d p n − 1 dp_ {n-1} dpn−1式子右边只与 d p 0 dp_ 0 dp0有关，把 d p n − 1 dp_ {n-1} dpn−1带入 d p n − 2 dp_ {n-2} dpn−2，再把 d p n − 2 dp_ {n-2} dpn−2带入 d p n − 3 dp_ {n-3} dpn−3 … 每一项都是 d p i dp_ i dpi= 系数* d p 0 dp_ 0 dp0+ 常数。

最终 d p 0 dp_ 0 dp0=系数* d p 0 dp_ 0 dp0+ 常数。

F

首先，要求的是最低跳跃能力，一眼二分。

然后注意到，从左向右和从右向左跳是等效的。

于是转化为从0跳到n，可跳>=2*x 次。

又想到，对于当前所在的点和给定的跳跃能力，贪心地尽可能跳到最右的一定最优。

做法：check(跳跃能力k)即可：
设 d p i dp_i dpi 为从i往后跳能上岸的最多次数。

首先 d p i dp_i dpi<= H i H_i Hi; 然后 d p i dp_i dpi 先找最右边能到的 d p i + k dp_{i+k} dpi+k, 如果 d p i + k dp_{i+k} dpi+k不能满足则把 d p i + k dp_{i+k} dpi+k 的次数全给 d p i dp_i dpi，再往左找下一个[i,i+k]范围内最大的。