2019华工校赛 - B, F, H, K题题解

本场比赛四道中等题,其中三道题数据范围故意放水降低难度。
然后。。没放水那题。。好像。。没人过啊。。?

B - 修仙时在做什么?有没有空?可以来炼丹吗?

题目链接

M姓出题人:这么老的idea怎么还没人做XD

考虑到本题的idea非常古老,所以在预估难度时设为中等题,然而现场没人过。题意本质上就是给出一个含$2^{18}$个结点的无向连通图,再指定其中$n$个点,求这$n$个指定点的两两之间的最短路的最小值。

接下来的讨论假定$n$个指定点的编号两两不同(如果出现相同编号的话答案就是$0$)。我们不妨考虑二进制分组。枚举二进制位$0 \sim 17$,对每个枚举出的二进制位$2^k$,我们将这$n$个点按照编号对应的二进制位$2^k$为$0$还是$1$分成两组,从一组往另一组跑多起点最短路,然后取个最小值就没了,总复杂度$O(18n \log n)$。

为什么这样做是正确的呢?考虑答案一定是某个编号为$u$的结点到某个编号为$v$的结点的最短路,而$u \neq v$,则他们一定在某个二进制位上是不相同的。当我们按照前述操作枚举到这个不相同的二进制位时,$u$和$v$一定会分到不同组中,因此跑完多起点最短路后一定会计算出全局最小值,于是这题就做完了。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 2e5;
const int maxm = 18;
const int maxV = 1<<maxm;
const int INF = 0x3f3f3f3f;
const int P = 19260817;
int cost[maxV][maxm];
int start[maxn], mark[maxV], ans = INF, cc = INF, n;

inline LL PowMod(LL a, LL b) { LL r=1; while(b) { if(b&1) r=r*a%P; a=a*a%P, b>>=1; } return r; }

void init()
{
    for (int s = 0; s < maxV; ++s) {
        for(int i = 0; i < maxm; ++i)
        {
            cost[s][i] = PowMod( max(s,s^(1<<i))%P, 1<<i ) % P + 1;
        }
    }
}
struct node
{
    int u,dis;
    node(int _u=0, int _dis = 0): u(_u), dis(_dis){}
    bool operator <(const node& nn) const
    {
        return dis > nn.dis;
    }
};
priority_queue<node>que;
int dis[maxV];
void solve(int mask)
{
    while(!que.empty()) que.pop();
    for (int i = 0; i < maxV; ++i) dis[i] = INF;
    for (int i = 0; i < n; ++i)
        if(start[i] >> mask & 1) 
        {
            dis[start[i]] = 0;
            que.push(node(start[i], 0));
        }
    while(!que.empty())
    {
        node tmp = que.top(); que.pop();
        int u = tmp.u, d = tmp.dis;
        if(d >= ans) return;
        if(d != dis[u]) continue;
        if(d && mark[u])
        {
            ans = d;
            return;
        }
        for(int i = 0; i < maxm; ++i)
            if(dis[u^(1<<i)] > d + cost[u][i])
            {
                dis[u^(1<<i)] = d + cost[u][i];
                que.push(node(u^(1<<i), dis[u^(1<<i)]));
            }
    }
}
int main()
{
    init();
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
    {
        scanf("%d", &start[i]);
        if(mark[start[i]]==1) exit( puts("0")*0 );
        mark[start[i]] = 1;
    }
    for (int i = 0; i < maxm; ++i) solve(i);
    printf("%d\n",ans);
    return 0;
}

F - 翻牌游戏

题目链接

这是一道打表找规律概率DP题。其实这题的数据范围可以出很大,但在某C姓出题人的极力阻止下改成了现在这个范围,也就是说允许直接交概率DP (说到底还是因为CC handsome!)

设$f[i][k]$表示当前有$i$对对子完全没有翻开过、$k$个对子已经翻开过恰好一张时,在最佳策略下翻完所有牌所需操作数的期望值。那么我们对每个状态有以下两种操作:

  • 选两张都没有翻过的牌翻开;
  • 选一张翻过的牌和一张没翻过的牌翻开。

仔细讨论每种操作下的转移即可,时间复杂度$O(n^2)$,然后你就会发现$ANS = 2n-1$。此外你还会发现,第二个操作只有在恰好剩两张牌翻过两张牌没翻过时才会进行。

其实这题可以出更难,因为通过打表可以发现$f[n][m] = 2n-1+\frac{3}{2}m+\frac{m}{2(2n+m)}$。。。不过为了提升参赛体验,就不出这么自闭了。

// CC!
#include<bits/stdc++.h>

using namespace std;

typedef double DB;

const int maxn = 5000;

DB f[maxn+5][maxn+5];
bool vi[maxn+5][maxn+5];

DB dfs(int n, int m) {
    if(vi[n][m]) return f[n][m];
    vi[n][m] = 1;
    if(n==0 && m==0) return f[n][m] = 0;

    f[n][m] = 1e9;
    int hd = n*2+m;

    // nn策略
    if(hd>=2) {
        DB tmp = 0;
        if(n>=1) tmp += DB(n*2.0) / (hd*(hd-1.0)) * (dfs(n-1,m)+1); // 2张未知且相同
        if(n>=2) tmp += (2.0*n*(2.0*n-2.0)) / DB(hd*(hd-1.0)) * (dfs(n-2,m+2)+1); // 2张未知但不同
        if(m>=2) tmp += DB(m*(m-1.0)) / DB(hd*(hd-1.0)) * (dfs(n,m-2)+3); // 2张已知
        if(n>=1 && m>=1) tmp += DB(4.0*n*m) / DB(hd*(hd-1.0)) * (dfs(n-1,m)+2); // 1张已知1张未知
        f[n][m] = min(f[n][m], tmp);
    }

    // nm策略
    if(m>0) {
        DB tmp = 0;
        tmp += 1.0 / DB(hd) * (dfs(n,m-1)+1); // 2张已知且相同
        if(m>=2) tmp += (m-1.0) / DB(hd) * (dfs(n,m-1)+2); // 2张已知但不同
        if(n>=1) tmp += (2.0*n) / DB(hd) * (dfs(n-1,m+1)+1); // 1张未知1张已知
        f[n][m] = min(f[n][m], tmp);
    }

    return f[n][m];
}

int main() {
    int _; scanf("%d", &_);
    while(_--) {
        int n; scanf("%d", &n);
        printf("%.2f\n", dfs(n,0) );
    }
    return 0;
}

H - Parco_Love_GCD

题目链接

这题原本的时间限制要更小,主要是为了卡掉RMQ的做法。但考虑到大家的参赛体验,就还是给多了时间让RMQ过了(现在来看或许不应该放水)。

两种做法。第一种做法是RMQ进行$O(n \log n \log 10^9)$的预处理搞出区间GCD值,然后每次就可以$O(\ log 10^9)$回答任意区间的GCD值。之后为了计算所有区间的GCD值之和,我们考虑$O(n)$枚举区间左端点,然后每次右端点从左往右二分+RMQ找到第一个会让区间GCD变化的位置,并累加答案。注意到右端点从左往右扫的过程中,GCD至多只会变化$O(\log 10^9)$次,所以这样做总复杂度就变成了$O(n \log n \log^2 10^9)$。

第二种做法是CDQ分治,也就是原本的正解。我们用函数$Solve(l,r)$来计算$[l,r]$的所有子区间的GCD之和。在每一层$Solve(l,r)$中,令$mid = \lfloor \frac{l+r}{2} \rfloor$,然后让左端点从$mid$往$l$扫,记录算出的GCD值及对应出现次数并扔到一个map里,同理让右端点从$mid+1$往$r$扫,将计算出的GCD值出现次数信息扔到另一个map里。现在我们有了两个map,他们的大小均不超过$O(\log 10^9)$,于是就可以$O(\log^2 10^9)$枚举两个map里的东西,同时$O(\log 10^9)$算一下GCD统计答案。

算一下第二种做法的复杂度。端点左右扫加上GCD以及map的复杂度后,所需的总复杂度为$O(n \log n \log 10^9)$。枚举map里的东西时,因为$Solve(1,n)$所涉及到的所有区间个数是$O(n)$级别的,所以这部分总复杂度为$O(n \log^3 10^9)$。综上CDQ分治的复杂度为$O(n (\log n \log 10^9 + \log ^3 10^9))$。

这里只贴CDQ分治的代码:

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxn = 5e5;
const int maxV = 1e9;
const int P = 1e9+7;

LL Gcd(LL a, LL b) { return b ? Gcd(b,a%b) : a; }

map<int,int> s1, s2;
int n, ai[maxn+5];
LL ans = 0;

inline void Add(LL &a, LL b) { a+=b; if(a>=P) a-=P; }

void Solve(int l, int r) {
    if(l==r) { Add(ans, ai[l]); return; }
    int mid = (l+r)>>1;
    s1.clear();
    s2.clear();

    int now = 0;
    for(int i = mid; i >= l; --i) {
        now = Gcd(now, ai[i]);
        ++s1[now];
    }

    now = 0;
    for(int i = mid+1; i <= r; ++i) {
        now = Gcd(now, ai[i]);
        ++s2[now];
    }

    for(auto pp : s1) {
        for(auto qq : s2) {
            Add(ans, Gcd(pp.fi, qq.fi) * pp.se % P * qq.se % P);
        }
    }

    Solve(l, mid);
    Solve(mid+1, r);
}

int main() {
    scanf("%d", &n);
    assert(1<=n && n<=maxn);
    REP(i,1,n) scanf("%d", ai+i);
    Solve(1,n);
    printf("%lld\n", ans);
    return 0;
}

K - Parco_Love_String

题目链接

本题时间限制及数据范围继续放水,出题人现在就是很后悔_(:3」∠)_

第一种做法是Hash后STL乱搞,没什么好说的,唯一要注意的是现场专门卡掉了map,需要unordered_map或者pb_ds才能通过,但牛客上是没有卡map的。

第二种做法是SAM(后缀自动机)乱搞。问题的核心就是给出$A, B$两个串,如何快速$B$的每个子串在$A$中的出现次数之和。我们考虑对$A$建SAM,通过经典的Fail树结点基数排序后就可以算出SAM中每个结点对应的那个(那些)串在整个$A$串中的出现次数(代码中记为occ。此外,对于每个SAM上每个结点的$len$成员(在标程代码中是val),预处理出它在SAM中对应的那个长度为$len$的串的所有子串在整个$A$串的出现次数之和(代码中记为sum。然后拿$B$串在SAM上跑一遍顺便计个数就可以算出答案了,具体计数方法参考代码。总时间复杂度$O(n^2)$,比Hash不知道高到哪里去

现场还有人用KMP也过了,大家可以自行思考,这里只贴SAM代码。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxn = 1000, c_size = 26;

struct State {
    int val;
    LL sum, occ;
    int par, go[c_size];
    void init() { val = 0, sum = 0, occ = 0, par = -1, mem(go,-1); }
}que[maxn*2+5];
int root, last;
int tot;

void Extend(int w) {
    int p = last, np = tot++;
    que[np].init();
    que[np].val = que[p].val+1;
    que[np].occ = 1;
    while(p!=-1 && que[p].go[w]==-1)
        que[p].go[w] = np, p = que[p].par;
    if(p == -1) que[np].par = root;
    else {
        int q = que[p].go[w];
        if(que[p].val+1 == que[q].val) que[np].par = q;
        else {
            int nq = tot++;
            que[nq] = que[q];
            que[nq].val = que[p].val+1;
            que[nq].occ = 0;
            que[np].par = que[q].par = nq;
            while(p!=-1 && que[p].go[w]==q)
                que[p].go[w] = nq, p = que[p].par;
        }
    }
    last = np;
}


char str[maxn+5];
LL f[maxn+5];
int cont[maxn+5], S[maxn*2+5];

int main() {
    scanf("%s", str+1);
    int n = strlen(str+1);
    for(int kk = 1; kk < n; ++kk) {
        root = last = 0;
        tot = 1, que[0].init();
        for(int i = 1; i <= kk; ++i) Extend(str[i]-'a');
        for(int i=0; i<=kk; ++i) cont[i] = 0;
        for(int i=0; i<tot; ++i) ++cont[que[i].val];
        for(int i=1; i<=kk; ++i) cont[i] += cont[i-1];
        for(int i=tot-1; i>=1; --i) S[--cont[que[i].val]] = i;
        for(int i = tot-1; i >= 1; --i) {
            int x = S[i];
            que[que[x].par].occ += que[x].occ;
        }
        for(int i = 1; i < tot; ++i) {
            int x = S[i];
            que[x].sum = que[que[x].par].sum;
            que[x].sum += LL(que[x].val-que[que[x].par].val) * que[x].occ;
        }
        int p = root;
        int now = 0;
        f[kk] = 0;
        for(int i = kk+1; i <= n; ++i) {
            int w = str[i]-'a';
            if(que[p].go[w] != -1) {
                p = que[p].go[w];
                ++now;
            }
            else {
                while(p!=-1 && que[p].go[w]==-1) p = que[p].par;
                if(p == -1) p = root, now = 0;
                else {
                    now = que[p].val+1;
                    p = que[p].go[w];
                }
            }
            if(now>0) {
                f[kk] += que[que[p].par].sum;
                f[kk] += LL(now - que[que[p].par].val) * que[p].occ;
            }
        }
    }
    int _; scanf("%d", &_);
    while(_--) {
        int kk; scanf("%d", &kk);
        printf("%lld\n", f[kk]);
    }
    return 0;
}