A.骰⼦的游戏

水题，直接暴力枚举六个面再比较大小，完结散花。

时间复杂度O(6*6)

#include<bits/stdc++.h>
using namespace std;
int T,x,y,a[7],b[7];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        x=0;y=0;
        for(int i=1;i<=6;i++)scanf("%d",&a[i]);
        for(int i=1;i<=6;i++)scanf("%d",&b[i]);
        for(int i=1;i<=6;i++)
            for(int j=1;j<=6;j++)
                if(a[i]>b[j])x++;
                else if(a[i]<b[j])y++;
        if(x>y)puts("Alice");
        if(x<y)puts("Bob");
        if(x==y)puts("Tie");
    }
    return 0;
}

B.购物

dp题，中等偏下难度（我不知道为什么我的记忆化搜索萎了）

表示前i天，买j个糖果的最小代价。

时间复杂度O(n^3)

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,m,sum[N][N],f[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            scanf("%d",&sum[i][j]);
        sort(sum[i]+1,sum[i]+m+1);
        for(int j=2;j<=m;j++)
            sum[i][j]+=sum[i][j-1];
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int k=i-1;k<=j;k++)
                if(j-k<=m)
                f[i][j]=min(f[i][j],f[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
    cout<<f[n][n];
    return 0;
}

C.随机树

这题较难，思维上要用唯一分解定理，代码实现上要用树链剖分（或dfs序）。

唯一分解定理：任何一个数都能被分解成若干质数的若干次数的乘积,也就是分解质因数（）

因数个数为每一个质数加1的乘积,比如12，因数个数为（2+1）*（1+1））

时间复杂度O(nlog(n))

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define int long long
const int mod=1e9+7;
const int xu[6]={2,3,5,7,11,13};
const int N=100005;
int n,m,x,y,top,a[N],ans[10],head[N],seg[N],rev[N],size[N];
char s[N];
struct node{
    int too,next;
}edge[N*2];
struct node2{
    int jia[10];
}tree[N*4];
int kuai(int a,int b)
{
    if(b==0)return 1;
    if(b==1)return a;
    int x=kuai(a,b/2);
    if(b%2==0)return x*x%mod;
    return x*x%mod*a%mod;
}
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa)
{
    seg[u]=++seg[0];
    rev[seg[0]]=u;
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fa)continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}
void pushup(int nod)
{
    for(int i=0;i<6;i++)
        tree[nod].jia[i]=(tree[nod*2].jia[i]+tree[nod*2+1].jia[i])%mod;
}
void build(int nod,int l,int r)
{
    if(l==r)
    {
        for(int i=0;i<6;i++)
        {
            while(a[rev[l]]%xu[i]==0)
            {
                tree[nod].jia[i]++;
                tree[nod].jia[i]%=mod;
                a[rev[l]]/=xu[i];
            }
        }
        return;
    }
    build(nod*2,l,mid);build(nod*2+1,mid+1,r);
    pushup(nod);
}
void change(int nod,int l,int r,int x,int val)
{
    if(l==r)
    {
        for(int i=0;i<6;i++)
        {
            while(val%xu[i]==0)
            {
                tree[nod].jia[i]++;
                tree[nod].jia[i]%=mod;
                val/=xu[i];
            }
        }
        return;
    }
    if(x<=mid)change(nod*2,l,mid,x,val);
    else change(nod*2+1,mid+1,r,x,val);
    pushup(nod);
}
void find(int nod,int l,int r,int L,int R)
{
    if(l==L&&r==R)
    {
        for(int i=0;i<6;i++)ans[i]=(ans[i]+tree[nod].jia[i])%mod;
        return;
    }
    if(R<=mid)find(nod*2,l,mid,L,R);
    else if(L>mid)find(nod*2+1,mid+1,r,L,R);
    else{
        find(nod*2,l,mid,L,mid);
        find(nod*2+1,mid+1,r,mid+1,R);
    }
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        x++;y++;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    dfs(1,0);
    build(1,1,n);
    scanf("%lld",&m);
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='R')
        {
            int res=1,sum=1;
            scanf("%d",&x);
            x++;
            for(int i=0;i<6;i++)ans[i]=0;
            find(1,1,n,seg[x],seg[x]+size[x]-1);
            for(int i=0;i<6;i++)
            {
                res=(long long)res*kuai(xu[i],ans[i])%mod;
                sum=(long long)sum*(ans[i]+1)%mod;
            }
            printf("%lld %lld\n",res,sum);
        }
        else{
            scanf("%lld%lld",&x,&y);
            x++;
            change(1,1,n,seg[x],y);
        }
    }
    return 0;
}

D.珂朵莉的无向图

简单题，直接宽搜。

把一开始的t个点都加入队列，宽搜求出每个点的最短路径。最后记录答案，输出。

时间复杂度O(qn)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,Q,x,y,t,s,top,ans,head[N],dis[N];
queueq;
bool vis[N];
struct node{
    int too,next;
}edge[N];
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
int main()
{
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    while(Q--)
    {
        while(!q.empty())q.pop();
        scanf("%d%d",&t,&s);
        ans=0;
        for(int i=1;i<=n;i++)
        {
            vis[i]=false;
            dis[i]=1e9;
        }
        for(int i=1;i<=t;i++)
        {
            scanf("%d",&x);
            q.push(x);
            dis[x]=0;
            vis[x]=true;
            //ans++;
        }
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=edge[i].next)
            {
                int v=edge[i].too;
                if(!vis[v])
                {
                    dis[v]=dis[u]+1;
                    vis[v]=true;
                    q.push(v);
                    //if(dis[v]<=s)ans++;
                }
            }
        }
        for(int i=1;i<=n;i++)
            if(dis[i]<=s)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

E.珂朵莉的数列

难度中等偏高，思维难度较高，代码实现中等。

我们考虑每个数对答案的贡献，比如总共有8个数，考虑第5个数，如果第3个数和第5个数符合条件，对答案的贡献就是(3-1+1) * (8-5+1)

查找符合条件的数可以用树状数组实现，代码和求逆序对差不多，就是原来是加一，现在是加自己的位置。

注意：要高精度，可以使用两个int，分开来存。

时间复杂度O(nlog(n))

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000005;
int n,ans1,ans2,a[N],b[N],c[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    for(int i=1;i<=n;i++)
    {
        int t=(query(n)-query(a[i]))*(n-i+1);
        add(a[i],i);
        ans2+=t;
        ans1+=ans2/10000000000000000ll;
        ans2%=10000000000000000ll;
    }
    if(ans1)printf("%lld%016lld",ans1,ans2);
    else printf("%lld\n",ans2);
    return 0;
}