华东交通大学2020年ACM“双基”程序设计竞赛

C、欧涛的生日聚会

思路：
画个图就比较清楚要求什么了（补题的时候比较懒，没画完图就在写了，没考虑全）
1.当给的关系图没有环时，显然最大可能的服装类就是每个连通块的最长链之和，最小值就是3（如果最大值小于3的话，最小值和最大值都是-1）
2.当给的关系图有一个环时，显然最大值就是环的长度，最小值就是最大值大于等于3的最小约数（反之同上）
3.（懒得想有多个环的情况，但其实是会出现有多个环的情况）
4.当多个连通块都有环或者一个连通块有多个环，这些环的长度的最大公约数就是最大值，最小值就是最大值大于等于3的最小约数（反之同上）

这题需要建一个边权取反的反向图，最大值取的是每个连通块的最长链之和，连通块是一堆有关系的点的集合，从某个点跑一遍不一定能跑完整个连通块（我当时以为用并查集维护每个连通块然后从祖先开始跑图就能跑完整个连通块，但是不行，太天真），为了防止多加，需要保证每次都要把一个连通块跑完。

并查集维护的有向图可以看成一颗树（有环就先不管，不影响分析），而连通块可以是两颗树连成的森林，不管从那边的根节点开始走，都走不到另外一棵树的其它节点上。所以必须建边权为负的反向图。
案例如下：

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,maxm=2e5+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int head[maxn],to[maxm],Next[maxm],val[maxm],tot;
int boom[maxn],gcd;
void add(int x,int y,int c) {
    to[++tot]=y;
    val[tot]=c;
    Next[tot]=head[x];
    head[x]=tot;
}
bool vis[maxn],bone[maxn];
int maxx,minn;
void dfs(int id,int f,int dep) {
    boom[id]=dep;//统计编号 
    bone[id]=true;//标记是否来过 
    maxx=max(maxx,dep);
    minn=min(minn,dep);
    for(int i=head[id],v; i; i=Next[i]) {
        v=to[i];
        if(v==f&&dep+val[i]==boom[v])
            continue;//防止走回退边
        if(vis[v]) {
            gcd=__gcd(gcd,abs(dep-boom[v])+1);
            return;
        }
        vis[v]=true; 
        dfs(v,id,dep+val[i]);
        vis[v]=false;//防止将重复边误判为环 
    }
}
int main() {
    int n=read(),m=read(),res=0;
    for(int i=1,u,v; i<=m; ++i) {
        u=read(),v=read();
        add(u,v,1);
        add(v,u,-1);
    }
    for(int i=1; i<=n; ++i) {
        if(!bone[i]) {
            maxx=-1e5,minn=1e5;
            vis[i]=true;
            dfs(i,0,1);
            res+=maxx-minn+1;
        }
    }
    if(gcd) {
        if(gcd>=3) {
            for(int i=3; i<=gcd; ++i) {
                if(gcd%i==0) {
                    printf("%d %d\n",gcd,i);
                    break;
                }
            }
        } else printf("-1 -1\n");
    }
    else {
        if(res>=3) 
            printf("%d 3\n",res);
        else printf("-1 -1\n");
    }
    return 0;
}

F、糖果店

思路：

$Jerry$ 购买方式的数目是最好算的，最小值的个数为 $x$ ，最大值的个数为 $y$ ，那么只要枚举取每个最小值的糖果取还是不取（不能一个都不取），每个最大值的糖果取还是不取（不能不取），以及每个既不是最小值也不是最大值的糖果取还是不取，方案数就是： $(2^x-1)*(2^y-1)*2^{n-x-y}$ 。

$Bob$ 购买方式的数目:

$Bob$ 每次购买就是选一个区间，显然的，某个最小值和某个最大值的区间就是一个，但是这个区间的左区间和右区间是可以向两边扩展形成一个新的合法区间的，所以我们需要知道某个最小值和某个最大值的区间最多能向两边扩展到多远（因为要保证不会算重）。

假设 $a$ 表示最小值， $b$ 表示最大值，则有如下数组：

$.b0..a1...b1...a2...b2...a0$

$[b1,a2]$ 的区间最多可以扩展到 $b0$ 后面 $b2$ 前面，或者 $a1$ 后面 $a0$ 前面。
即最大值（最小值）和最小值（最大值）组成的区间扩展的策略是，不能超过取到左边第一个最值，不能取到右边第一个最小值（最大值）：或者不能超过取到右边第一个最值，不能取到左边第一个最大值（最小值）。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod=1e9+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[maxn],b[maxn];
ll qpow(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main() {
    int t=read(),maxx,minn,n,top;
    ll ans,x,y;
    while(t--) {
        n=read();
        maxx=-1,minn=100000;
        ans=top=x=y=0;
        for(int i=1;i<=n;++i) {
            a[i]=read();
            if(maxx<a[i]) maxx=a[i];
            if(minn>a[i]) minn=a[i];
        }
        for(int i=1;i<=n;++i) {
            if(a[i]==maxx) {
                b[++top]=i;
                y+=1;
            }
            if(a[i]==minn) {
                b[++top]=i;
                x+=1;
            }
        }
        for(int i=1,l,r=-1;i<top;++i) {
            l=b[i]-b[i-1];
            if(a[b[i]]==maxx) {
                for(int j=i+1;j<=top;++j) if(a[b[j]]==minn) {
                    for(int k=j+1;k<=top;++k) {
                        if(a[b[k]]==a[b[j]]) {
                            r=b[k]-b[j];
                            break;
                        }
                    }
                    if(r==-1) r=n-b[j]+1;
                    ans+=r*l;
                    ans%=mod;
                    r=-1;
                }
            }
            else {
                for(int j=i+1;j<=top;++j) if(a[b[j]]==maxx) {
                    for(int k=j+1;k<=top;++k) {
                        if(a[b[k]]==a[b[j]]) {
                            r=b[k]-b[j];
                            break;
                        }
                    }
                    if(r==-1) r=n-b[j]+1;
                    ans+=r*l;
                    ans%=mod;
                    r=-1;
                }
            }
        }
        printf("%lld %lld\n",ans,(qpow(2,x)-1)*(qpow(2,y)-1)%mod*qpow(2,n-x-y)%mod);
    }
    return 0;
}

G、钥匙

思路：
有了思路就差实现了，记忆化搜索。

$dp[len][h][pos]$ ,当前是第 $len$ 个卡槽，第 $len+1$ 个卡槽深度为 $h$ ， $pos$ 的二进制位 $1$ 的个数表示有多少种卡槽。

还有一种方法就是用总的方案数（不管有多少种卡槽）减去只有一种和只有两种卡槽的方案数：Code

code；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod=1e9+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
ll dp[30][7][1<<7];
ll dfs(int len,int h,int pos) {
    if(!len) {
        int cnt=0;
        for(int i=0;i<6;++i) if((1<<i)&pos) cnt+=1;
        return cnt>=3;
    }
    if(dp[len][h][pos]!=-1) return dp[len][h][pos];
    ll ans=0;
    for(int i=0;i<6;++i) if(abs(h-i)<5) {
        ans+=dfs(len-1,i,pos|(1<<i));
    }
    dp[len][h][pos]=ans;
    return ans;
}
int main() {
    int n;
    ll ans=0;
    memset(dp,-1,sizeof dp);
    while(~scanf("%d",&n)) {
        printf("%lld\n",dfs(n,2,0));
    }
    return 0;
}

赛后补提文章被收录于专栏

不能不补，不能偷懒