小故事

发这份题解时。出题人已经在去ICPC西安的火车上了.jpg

网络很差，如果有哪里做的不好的地方，还望指出

赛后更新： 出了两个锅，一个是B题的n数组数据是换行的，样例却是同一行的，内测赛并没有测到py这里会寄；另一个是C题第三个样例5110不满足数据范围，但大部分同学会测完样例再交，所以基本没有影响到大家，所以赛时把第三个样例删了，在此谢罪。

并且E题题面有点差。非常抱歉影响到大家的参赛体验。不会有下次了。

出题背景：

这套题是从两个月前就出好了的，陆陆续续到现在才放出来题目。最开始投的是牛客练习赛，因为太简单了，审题人建议我直接去投小白月赛（悲。

那个时候的A题还是现在的C题。接着觉得A题还是有点点难度，不太小白，就临时加了个现在的A题，mex和gcd的乘积这个题在B题。

同时加强了一下E题期望，这题是出题人有点希望期望的普及但还是有点担心小白被期望卡住，这个期望尽可能的简单（有我参与的三场都有期望呜呜呜）觉得加强后不再只是硬核求期望了，美妙了很多。

题两个月前就出好了，到赛前只有两个星期造数据的时候，才发现mex和gcd的乘积这题我写的std代码是错的！我漏考虑了全部为0的情况！！！于是我就憋着笑造完了这个十分逆天抽象题的数据。心情感觉非常的升天，非常的期待大家的表现

结果内测的时候过于壮烈，普遍都被这题卡了一下下。wa率非常的高，没有一个人一发过。（更何况我在群里当时发的std代码/题解都是错的）。所以考虑到以人为本的宗旨，整场题目还是要友好一点，怕赛时太壮烈不能让大家光在自闭坐牢没做出什么题，所以这题变成了C题，加了一道我也比较喜欢的题。A题和B题都是看起来很简单的题，但A题可能有点会写成暴搜、状压啥的，B题可能会想成01背包，也有一些要思考的地方，对于赛场上的策略还是挺有价值、有趣的。这场特点就是整场前期的题目非常的思维，很div3，后面的两题代码量还是有点足的，代码量整场下来还不算太低。

本来还想加强一下最后一题魔法树的，但考虑到小白场不应该出两个期望，加矩阵之类的内容也感觉在折磨做题人，该考察的内容也都考察到了，所以虽然看起来有点白给，究极板子题也挺好的，非常的经典。同时上场小白的最后一题过于困难（沙场），这次来个反差。也考虑到防止被牛客周赛造题的小红喷，说好要出个友好的小白场，就没加强了。整场的难度还是在努力控制，没有超过2000分的题目，自己也ak打了几场div3，并不觉得比它们难。同时也尽可能让赛时的情况丰富一些，有题可开。

这场把我跨越两年的全部idea、tirck全部用完了，连一丢丢都不剩了/(ㄒoㄒ)/，希望能给大家带来收获~

A.数位dp？

tag：思维，模拟

难度：800

• 不难发现只需要个位是偶数即可满足条件，因为

• 一直删个位即可。一直除以10或者从右往左扫皆可，直至找到第一个偶数

参考代码

int main()
{
    int n;
    scanf("%d",&n);
    int res=0;
    while(n%2)
    {
        res++;
        n/=10;
    }
    printf("%d\n",res);
}

附：在这个数据范围下，暴力搜索或者状压等各种暴力方法皆可过

B.灵异背包

tag：贪心

难度：900

• 因为要总和最大，我们不妨先把所有的数都选进背包
• 如果当前总和为奇数，那我们就从背包里面拿出来最小的奇数即可。注意因为总和为奇数，所以背包里面一定存在一个奇数可以拿出来

const int N=100005;
int a[N];
int n;
int main()
{
    scanf("%d",&n);
    int res=0;
    int mi=1e9;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]&1)//等价于a[i]%2==1,ai为奇数
        {
            mi=min(mi,a[i]);
        }
        res+=a[i];
    }
    if(res&1) res-=mi;
    printf("%d\n",res);
}

bonus：如果有些数是负数怎么做？

附：分类讨论较麻烦，用01背包，表示前个数选若干个数后，当前总和是奇/偶的最大值是多少。这题还是直接求和更加简单

C.mex和gcd的乘积

tag：思维，有点抽象的分类讨论

难度：1200

• 当一个区间的时，因为一定出现在区间里面，所以区间的一定等于，我们不妨把整个数组当作一个区间更优，因为此时最大，且仍然为

• 当一个区间的时，值为0

• 当一个区间的时，说明当前区间只有和除以外的数，而随着选择的非数越多，只会越变越小。所以我们区间中只包含和一个非数时更优

• 尤其要注意数组全为的情况下，此时答案为

• 所以答案即为

参考代码

const int N=100005;
int a[N];
bool st[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]),st[a[i]]=true;
    }
    if(*max_element(a+1,a+n+1)==0)
    {
        puts("0");
        return 0;
    }
    int res=0;
    while(st[res]) res++;
    for(int i=1;i<=n;i++)
    {
        if(!a[i])
        {
            res=max(res,a[i-1]);
            res=max(res,a[i+1]);
        }
    }
    printf("%d\n",res);
}

D.2^20

tag：思维，贪心，最短路bfs

cf：1400

解法一：

• 子弹数非常多，并且丧尸数量一定能变成的倍数。不可能用完，所以不可能输出

• 转化一下，题意相当于给你一个数，你每次操作要么使，要么使，问最少需要操作多少次使得是的倍数

• 由于一直乘2至多操作20次就一定能变成的倍数，所以最终答案一定小于等于

• 考虑二进制意义下，满足是的倍数相当于末尾有个，加一操作只有进位才有效果，乘二相当于往二进制末尾添。所以先乘后加肯定不如先加后乘

• 因为最多操作20次，所以我们只需要枚举加了多少次，再算需要乘多少次，更新答案即可

• 时间复杂度为

解法二：

• 考虑在的模意义下，预处理数字到数字的需要射击的次数

• 因为数字可以变成或者，不妨向建边，向建边，边权为，最多建条边

• 模意义下值为的点到每一个点的距离，即为射击次数，设为，显然。利用bfs求最短路预处理出来数组即可

• 时间复杂度为

解法一参考代码

int m=(1<<20);
void solve()
{
    int n;
    scanf("%d",&n);
    n%=m;
    int res=20;
    for(int i=0;i<=20;i++)
    {
        int val=(n+i)%m;
        if(!val) res=min(res,i);
        else
        {
            int num=0;
            while(!(val&1)) val/=2,num++;
            res=min(res,(20-num)+i);
        }
    }
    printf("%d\n",res);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

解法二参考代码

const int N=1e6+1e5;
int m=(1<<20);
int dist[N];
vector<int> edg[N];
void solve()
{
    int n;
    scanf("%d",&n);
    n%=m;
    printf("%d\n",dist[n]);
}
int main()
{
    for(int i=0;i<m;i++)
    {
        edg[(i+i)%m].push_back(i);
        edg[(i+1)%m].push_back(i);
    }
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    dist[0]=0;
    q.push(0);
    while(!q.empty())
    {
        auto u=q.front();
        q.pop();
        for(auto v:edg[u])
        {
            if(dist[v]>dist[u]+1)
            {
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

附：实测时解法一比解法二快很多，解法二在容易被卡常的边缘

E.重生之我是QQ邮箱

tag：组合数学，期望，循环节

cf：1600

听说题面，题意和考察方向都很奇怪，出题人想了好久好久好久也没想到怎么更好的优化这个题面了……

但我觉得这题对于期望的普及和循环节的小tirck还挺妙？

先考虑如何算期望时间：

易知每次输入密码只和后面七位有关，和前面怎么输入没有任何关系，后面七位的排列一共有种

所以每输入每个密码是正确的概率是

所以期望需要输入 个密码

（类比于抛硬币，正反面概率都是二分之一，要出现正面则需要抛两次）

所以需要输入的时间就是 秒

直接计算的话答案要开long long。另外需要注意如果的话，则一定不可能解锁密码

因为答案我们只需要看个位数，我们模即可

手玩发现开方操作后，个位数呈现以下规律：

所以大于等于2时，答案为定值

事实上因为有，只会有偶数的情况，分类讨论的话也会更加简单

附：也可以通过欧拉降幂（扩展欧几里得）解决，但非常的大炮轰蚊子了

参考代码

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    
    if(n<7)
    {
        puts("-1");
        return 0;
    }

    ll res=1;
    for(int i=1;i<=7;i++)
    res*=6;

    res=res*n;
    res%=10;
    if(m==0) printf("%lld\n",res);
    else if(m==1) printf("%lld\n",res*res%10);
    else printf("%lld\n",res*res*res*res%10);
}

F.是牛牛还是狗勾

tag：鸽笼原理，dp（01背包）

难度：1900

题意：对于给定的个数字（每个数字只能是中的一个），选出一些数字（至少选一个）使它们的和为的倍数，使剩下的数字和模千得到的数字最大，问最大值是多少，并且输出方案

对于有解的情况，最大牌型就是唯一的结果，答案就是这些数字之和%1000。这个其实非常显然（玩过牛牛的肯定都知道）

接下来讨论什么情况下有解：

根据鸽笼原理（抽屉原理），一定能凑出的倍数，证明如下：

• 考虑对数组求模意义下的前缀和得到数组，

• 对于区间和，它的前缀和即为

• 对于位置的前缀和，一定有两个数的前缀和相等

• 设这两个前缀和相等的下标分别为，，且。有，即

• 所以此时的区间和模意义下是

对于，找到两个前缀和相等的下标，，此时方案即为区间

对于，考虑，设为前张牌里面选的牌之和模千余数为是否可行

转移方程为

类似01背包一样得到具体输出方案即可

参考代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ld eps=1e-8;
const int INF=0x3f3f3f3f,mod=998244353;

#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

const int N=1000006;
int a[N];
int s[N];
int n;
bool dp[1003][1003];
void solve()
{
    scanf("%d",&n);
    int res=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),res=(res+a[i])%1000;
    if(n>=1000)
    {
        for(int i=1;i<=n;i++) s[i]=(s[i-1]+a[i])%1000;
        for(int l=0;l<=1000;l++)
        {
            for(int r=l+1;r<=1000;r++)
            {
                if(s[l]==s[r])
                {
                    printf("%d\n",res);
                    printf("%d\n",r-l);
                    for(int i=l+1;i<=r;i++) printf("%d ",i);
                    puts("");
                    return ;
                }
            }
        }
    }
    for(int i=0;i<=n;i++) for(int j=0;j<1000;j++) dp[i][j]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i][a[i]%1000]=1;
        for(int j=0;j<1000;j++)
        {
            dp[i][j]|=dp[i-1][(j-a[i]+1000)%1000];
            dp[i][j]|=dp[i-1][j];
        }
    }
    if(!dp[n][0]) puts("-1");
    else
    {
        for(int i=0;i<=n;i++) dp[i][0]=1;
        int w=0;
        int cur=n;
        vector<int> path;
        while(cur)
        {
            int las=(w-a[cur]+1000)%1000;
            if(dp[cur-1][las])
            {
                w=las;
                path.push_back(cur);
            }
            cur--;
        }
        reverse(path.begin(),path.end());
        printf("%d\n",res);
        printf("%d ",path.size());
        for(auto x:path)
        {
            printf("%d ",x);
        }
        puts("");
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

附：虽然这个题未必比后面一题简单，但感观上应该还是会有不少人感知到只需要选比较少的数即可凑成。std做法也并不好写，虽然的输出方案很妙（），很多其他做法如bfs或者乱搞皆可过，甚至比std更好写、跑的比std快很多，出题人没有特意卡任何其他做法或者说在这个证明结论下根本不可能卡掉。赛时写需要一点勇气，因为代码量并不低，写的时候你觉得方向寄了那你就寄了，赛时应该能看到五花八门的做法。所以这题对于把玩做题策略还是挺有意义的（？）

G.魔法树

tag：树形dp

难度：2000

考虑树形dp，当前点的什么信息需要从儿子结点的信息转移过来。

不妨设当前点为，子结点为

比方说我砍掉了一些边，当前能对上面造成影响的，就只有黄色的这些点权。也就是说，我们只需要记录这些结点所在的连通块的奇偶信息，才会影响结点连通块的状态。

所以我们得出，只有结点所在的连通块，会对上面的结点造成影响，下面所有断开的连通块，不会再更改奇偶性

同时，由于最终还要考虑下面的所有点的连通块奇偶要一致。所以我们还要记录下面所有断开的连通块的奇偶性

所以我们可以设数组。

表示以为根节点，与结点断开的连通块奇偶性均为，结点所在的连通块奇偶性为的方案数。

比如，我们先不管断开的连通块。我们可以发现结点和结点之间有这样一种关系

我们会发现，这不就很类似于01背包吗？对于某个结点，我们看作是一个物品，可以选或不选的情况（不选也就是与所在连通块断开的情况），唯一不同的就是选的时候情况选所在连通性为奇、所在连通块为偶两种情况。

而断开的连通块，我们举个例子，我们会发现，我们由与断开的连通块奇偶性为奇，只能转移向与断开的连通块为奇的情况。所以我们断开的连通块只能由当前的奇偶性转移至依旧相同的奇偶性

我们可以枚举当前下的每一个，类似与背包，每来一个，我就更新一下当前的数组

我们不妨举个例子，如果为偶，我们初始值应该是，

当开始枚举，每当来了一个，对于 ，它等于——

如果选的话：

如果不选的话：

因此我们可以列出转移方程

注意等于号的右侧，都是上一轮还未更新的，否则的话会有问题。（和滚动数组优化要倒着枚举是同一个道理）

另外我们照着上面敲看起来太繁琐了，不够简洁优美，而且出问题了也不太好找，其实我们发现转移都是有类似结构的。我们其实可以用两层for循环，用一个递推式代替上面的四个递推式

式子含义加的三项分别就是——

int ans[2][2]; //预存答案，然后再给dp数组，避免提前更新dp数组造成的影响

//看子节点v造成的影响
for (int j = 0; j < 2; j++)
    for (int k = 0; k < 2; k++)
        ans[j][k] = dp[u][j][0] * dp[v][j][k] + dp[u][j][1] * dp[v][j][1 ^ k] + dp[u][j][k] * dp[v][j][j];

for (int j = 0; j < 2; j++)
    for (int k = 0; k < 2; k++)
        dp[u][j][k] = ans[j][k];

（ps：为方便参考，我去掉了取模操作）

通过dfs更新完数组，最终的答案就等于啦！ （dfs以号点为根结点的情况）

参考代码

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

const int mod = 998244353;
const int N = 100005, M = 2 * N;
int w[N];
int h[N], ne[M], e[M], idx;
int dp[N][2][2];
int n;
void add(int x, int y) //建立邻接表
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}
void dfs(int u, int fa)
{
    dp[u][0][w[u] & 1] = dp[u][1][w[u] & 1] = 1; //先加上当前点造成的影响
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa)
            continue;

        dfs(v, u);

        int ans[2][2]; //预存答案，然后再给dp数组，避免提前更新dp数组造成的影响

        //看子节点v造成的影响
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                ans[j][k] = (1ll * dp[u][j][0] * dp[v][j][k] % mod + 1ll * dp[u][j][1] * dp[v][j][1 ^ k] % mod + 1ll * dp[u][j][k] * dp[v][j][j] % mod) % mod;

        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                dp[u][j][k] = ans[j][k];
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        w[i] = (x & 1); //只需要记录点权的奇偶性即可
    }
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1, -1);
    int res = (dp[1][0][0] + dp[1][1][1]) % mod;
    printf("%d\n", res);
}

bonus：只计算联通块为偶数的情况下，有没有更简单的解法？（无需dp）

这也是本来的简单版本的题目，但有点和两年前的杭电多校撞了，就没出了

解法： 分离出一棵能量值为偶数的子树并不影响整体的奇偶性。

我们假设以1号点为根，设表示以为根的子树下所有点的能量值之和的奇偶性。（0表示为偶，1表示为奇）

对于每棵能量值之和为偶数的子树，我们可以选择砍或不砍和的父节点这条边

所以方案数为

参考代码

const int N=100005;
int a[N];
int n;
vector<int> edg[N];
int siz[N];
int res=1;
void dfs(int u)
{
    siz[u]^=a[u];
    for(auto v:edg[u])
    {
        dfs(v);
        siz[u]^=siz[v];
    }
    if(u!=1&&!siz[u]) res=res*2%mod;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]&=1;

    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edg[x].push_back(y);
    }
    dfs(1);
    if(siz[1]) puts("0");
    else printf("%d\n",res);
}