前面的碎碎念：
自考研复试之后，一年来没打过这种限时比赛了。这次疫情呆在家没事干，便想着报名来玩一玩。虽然心里已经做好准备，知道自己太久不打比赛可能会有所拉跨，不过结束后发现有几道题目其实在自己能力范围，属于应该要做出来的，这样还是比较令人难受的。
小白月赛时间是7点-10点，由于7-8点这段时间吃饭+有事，实际上我8点才开始做题，不过感觉时间就算再多，该卡住的题目还是很难能花时间想通的。题目整体难度官方解释是DIV2 A-C，大部分题目不是很难，个人觉得比赛时应该要做出7题，最终只做出了5题，还是太菜。

题解部分：

A-膜法记录
比赛时先看的第一题，脑子里冒出来的第一个想法就是枚举攻击哪些行，然后统计还有多少列需要攻击，需要攻击的列数能小于等于b就行了，但是这样做的时间复杂度是O(m图片说明2^n)，肯定会超时。赛后发现，其实很多人都是写的这种做法然后莽过去了，出题人造数据不严谨啊...
咨询了大佬之后了解了正确做法:先进行预处理，把每一列变成一个01序列，其二进制形式对应着一个数字，用一个数组num[]统计这些数字个数，这部分时间复杂度为O(n图片说明m)。之后开始枚举每行，对于每行，枚举0-2^n-1的01序列，对每个01序列表示的集合，其个数要向其增集转移，这样就直接统计出了0-2^n-1种行攻击方式下，对应会消灭多少列。这部分有点类似于状压DP，时间复杂度为O(n图片说明2^n)。
之后再枚举0-2^n-1种行攻击方式，若满足行攻击次数小于等于a且m-对应会消灭多少列小于等于b，那么就可以全歼，否则不能全歼。
整体时间复杂度O(n图片说明m+n图片说明2^n)。
A题代码：

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

int num[2000005];
char R[25][100005];
int main()
{
    int i,j,k,n,m,a,b,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&a,&b);
        for(i=0;i<(1<<n);i++)num[i]=0;
        for(i=0;i<n;i++)scanf("%s",R[i]);
        for(j=0;j<m;j++)
        {
            for(k=i=0;i<n;i++)if(R[i][j]=='*')k|=(1<<i);
            num[k]++;
        }
        for(i=0;i<n;i++)
            for(j=0;j<(1<<n);j++)if((j&(1<<i))==0)num[j|(1<<i)]+=num[j];
        for(i=0;i<(1<<n);i++)if(__builtin_popcount(i)<=a&&m-num[i]<=b)break;
        if(i<(1<<n))printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

B-阶乘
对于一个数P，我们可以把他分成若干个质数之积，也就是这种形式：P=p1^k1 x p2^k2 x ...x pn^kn，其中p1,p2,...,pn为互不相同的质数。那么我们对每个质数pi，找到能凑到指数ki的最小数字，比如pi=2,ki=2，那么2含有1个2因子，4含有2个2因子，加起来为3>=2，所以凑成2^2至少要4！。我们对每个质数都进行这样的一次寻找，ans保存最大的那个就行了。
比赛期间我一时没想清暴力寻找的复杂度其实最多也就log(P)，想二分快速找到各质数对应需要的最小数字，但是一直没想出如何O(1)计算n!含有多少个质因子pi的方法，所以被这题坑了大概40多分钟。以后还是不能太谨慎，大力出奇迹...
时间复杂度O(T图片说明图片说明图片说明log(P))
B题代码：

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

unordered_map<int,int>V;
int main()
{
    long long i,j,k,s,ans,T,p;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&p),j=p,ans=0;
        for(i=2;i*i<=p;i++)
        {
            if(p%i)continue;
            for(s=0;p!=1&&p%i==0;p/=i)s++;
            V.clear();
            for(j=1,k=0;k<s;j++)V[j*i]=V[j]+1,k+=V[j*i];
            ans=max(ans,(j-1)*i);
        }
        ans=max(ans,p);
        printf("%lld\n",ans);
    }
    return 0;
}

C-完全图
首先，一个完全图本身就是一个联通分量。若我们把他变成两个连通分量，最少要把某点和其他点的所有边都去除掉，也就是要去掉n-1条边。若我们把他变成三个连通分量，在剩下n-1个结点的连通分量上，最少要把某点和其他点的所有边都去除掉，也就是要去掉n-2条边，以此类推...
我们发现规律后就很简单了，显然m越大，最后的答案也会越大，其具有单调性可以二分。我们设答案-1为ans，那么ans肯定要满足(n-1)+(n-2)+...+(n-ans)<=m，左边可以直接高斯求和，那么二分找到最大的ans即可。注意求和时可能炸long long，因此我们要使用__int128，比赛中此题通过人数不是很多，估计就是被高精度坑了。
时间复杂度O(log(n))
C题代码:

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

int main()
{
    long long ans,T,n,m;
    __int128 l,r,mid,t;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        for(l=0,r=n-1;l<=r;)
        {
            mid=(l+r)>>1,t=(n-1+n-mid)*mid/2;
            if(t<=m)ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n",ans+1);
    }
    return 0;
}

D-病毒传染
QAQ太菜了不会。

E-A+B问题
签到题，答案恒等于4294967296，也就是2^32，即int位数。
时间复杂度O(1)。
E题代码：

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

int main()
{
    int x;
    scanf("%d",&x);
    printf("4294967296\n");
    return 0;
}

F-美丽的序列I
比赛时看了一眼题没啥思路，遂放弃，以后有时间补上。

G-树上求和
最后10分钟看的题，一时没想出来，着实思想江化。
此题需要从算贡献的角度思考，对于每条边对答案的贡献，等于其左边子树结点个数 x 右边子树结点个数 x 边长。因此我们先随便从一点DFS，预处理出每个子树的结点个数。再遍历所有的边，把左边子树结点个数 x 右边子树结点个数的积保存下来，从大到小排序，然后从前往后遍历一遍分别乘上1/2/3/.../n-1，加起来即可。
时间复杂度O(n x log(n))。
G题代码:

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

struct node
{
    int x,y;
}E[100005];
bool cmp(long long a,long long b)
{
    return a>b;
}
int n,S[100005]={0};
long long a,b,ans=0,B[100005];
vector<int>R[100005];
void DFS(int x,int fa)
{
    int i,j;
    S[x]=1;
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(j!=fa)DFS(j,x),S[x]+=S[j];
    }
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n-1;i++)
    {
        scanf("%d%d",&E[i].x,&E[i].y);
        R[E[i].x].push_back(E[i].y),R[E[i].y].push_back(E[i].x);
    }
    DFS(1,0);
    for(i=0;i<n-1;i++)a=min(S[E[i].x],S[E[i].y]),b=n-a,B[i]=a*b;
    sort(B,B+n-1,cmp);
    for(i=0;i<n-1;i++)ans+=(i+1)*B[i];
    printf("%lld\n",ans);
    return 0;
}

H-奇怪的背包问题增加了
首先我们要知道2^i+2^i=2^(i+1)，想到了这点，那么本题基本上就能A掉了。
我们用V1和V2数组保存n个ki中，0-29分别有多少个。那么先从0遍历到29，每次把V1[i]/2加到V[i+1]上，因为根据上面的公式，两个V1[i]可以变成一个V1[i+1]。遍历完后检查V1[30]是否大于等于1，若是表示有解，否则无解。
若有解，我们反着利用V2数组从29遍历到0，用一个变量j表示当前数字期望需要多少个，一个need数组保存每个数字实际需要用到多少个。若期望个数大于实际能提供的个数，令j减去实际个数，j扩大两倍后继续遍历重复此过程，直到期望个数小于等于实际能提供的个数。最后我们根据need数组，遍历一遍k即可。
时间复杂度O(T x m)。
H题代码:

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

int a[100005],V1[35],V2[35],need[35];
int main()
{
    int T,i,j,n,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(V1,0,sizeof(V1)),memset(V2,0,sizeof(V2)),memset(need,0,sizeof(need));
        for(i=1;i<=n;i++)scanf("%d",&a[i]),V1[a[i]]++,V2[a[i]]++;
        for(i=0;i<30;i++)V1[i+1]+=V1[i]/2;
        if(!V1[30]){printf("impossible\n");continue;}
        for(j=2,i=29;i>=0;i--,j<<=1)
        {
            if(V2[i]>=j)
            {
                need[i]=j;
                break;
            }
            else need[i]=V2[i],j-=V2[i];
        }
        for(i=1;i<=n;i++)
        {
            if(need[a[i]])need[a[i]]--,printf("1");
            else printf("0");
        }
        printf("\n");
    }
    return 0;
}

I-寻找子串
比赛时没看数据范围直接写了个O(n^3)算法居然过了，后面补上了正确做法2333
字典序最大的子串，一定是原串的后缀，所以我们枚举所有后缀串即可。
时间复杂度O(n^2)。
I题代码：

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

int main()
{
    int i,j,L;
    char R[1005],T[1005],ans[1005];
    scanf("%s",R);
    ans[0]='a',ans[1]='\0';
    for(i=0;R[i]!='\0';i++)
    {
        for(L=0,j=i;R[j]!='\0';j++)T[L++]=R[j];
        T[L]='\0';
        if(strcmp(T,ans)>0)strcpy(ans,T);
    }
    printf("%s\n",ans);
    return 0;
}

J-最大的差
签到题，序列中的最大值-最小值就行了。
时间复杂度O(n)。
J题代码：

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

int main()
{
    int n,x,Max=-1e9,Min=1e9;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        Max=max(Max,x);
        Min=min(Min,x);
    }
    printf("%d\n",Max-Min);
    return 0;
}

本人第一次写博客，写的比较啰嗦，大佬们轻喷啊，完结撒花~