牛客网周周练14

前言

~~欢迎来蒟蒻博客看看~~
说是Div2 A-C的难度，怎么感觉不太靠谱……
按照难度来写题解吧。代码丑压行狠，建议拷到IDE里再看……

D 绝地求生(pubg)

显然求 $\operatorname{lcm}(x,y)$ ，即 $x \times y \div \operatorname{gcd}(x,y)$ 。

由于相乘可能溢出，先除再乘即可，答案保证在 long long 范围内。

#include <cstdio>
#include <algorithm>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int T;
long long x,y;
inline long long gcd(long long a,long long b)
{
    return b == 0 ? a : gcd(b,a % b);
}
int main()
{
    read(T);
    for(int i = 1;i<=T;++i)
    {
        read(x),read(y);
        if(x < y) std::swap(x,y);
        printf("Case %d: %lld\n",i,x / gcd(x,y) * y);
    }
}

B Circle

现在我们要把 $1\ldots n$ 这 $n$ 个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。

直接按顺序排列便是最多情况， $1$ 与任何数互质。

#include <cstdio>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int n;
int main()
{
    read(n);
    printf("%d\n",n);
    return 0;
}

E 悠悠碧波

帕秋莉掌握了一种水属性魔法，

这种魔法可以净化黑暗。

帕秋莉发现对于一个黑暗的咒语 $s$ ，可以使用这个水元素魔法净化它，净化的咒语是一个最长的字符串 $t$ ， $t$ 满足以下条件：

它是 $s$ 的前缀
它是 $s$ 的后缀
除前缀和后缀外，它还在 $s$ 中出现过至少一次

既然你都学会了，那么净化的工作就交给你了！

求字符串 $t$ 为 $s$ 的前缀、后缀，且在中间出现过至少一次。

一道原题：洛谷题解直达

C Tree

求一棵树每个点的包含其的连通子集数量。

一开始还以为跟链有什么关系……后来发现想错了，考虑用树形dp解决。

假定目前遍历节点 $u$ ，某相连非父亲节点 $v$ 。

设 $f(i)$ 为以 $i$ 为根的子树的、包含 $i$ 的连通子集数量。

此时对于 $u,v$ 两个子集集合，分别任选一个，用一条边联通。

根据乘法原理得新数量为 $f(u) \times f(v)$ ，其中 $f(u)$ 为之前的数量。

累加上去即可，可以化简为 $f(u) = f(u) \times (f(v) + 1)$ ，方便后续计算。记得边算边取模。

然而这样计算，只能算出根节点的正确的子集数量，考虑如何解决子节点的数量。

设当前点为 $u$ ，父亲节点为 $fa$ ：

将 $u$ 当做根时， $u$ 比原先多了与 $fa$ 相连的一棵子树。

将这棵子树拿来更新 $f(u)$ ，便可得到 $u$ 为根的答案，记为 $ans(u )$ 。

这棵子树的子集数量如何计算呢？可以通过 $ans(fa)$ 得到：

$ans(fa) = (f(son_1) + 1) \times (f(son_2) + 1) \ldots \times (f(u) + 1)$ ，所求即除去 $f(u) + 1$ 的 $ans (fa)$ 。

记为 $g(u) = \dfrac{ans(fa)}{f(u) + 1}$ 。

$g(u)$ 即除去 $u$ 的子树中的点，加上 $u$ 这个点的树的包含 $u$ 的子集个数。或者说，就是它与父亲子树组成的树的子集数量。

$ans(u) = (g(u) + 1)\times f(u)$

由于是取模除法，需要计算逆元。

然而有一个奇怪的坑点，就是 $f(u) + 1$ 在 $\mod p$ 意义下可能为 $0$ ，那么求逆元就会出锅……

对于这种情况，返回父亲去暴力遍历一遍，跳过当前子树再求一遍 $g(u)$ 好了。

$g(u) = (g(fa) + 1) \times (g(son) + 1) (son \ne u,fa)$

代码实现中，用费马小定理求逆元，为了避免溢出用了#define int long long 。

#include <cstdio>
#define int long long
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 1e6 + 100;
struct node
{
    int to,next;
}E[maxn<<1];
int head[maxn];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],head[x] = tot,E[tot].to = y;
}
const long long mod = 1e9 + 7;
int n;
long long f[maxn],ans[maxn],g[maxn];
int fa[maxn];
void dfs1(int u)
{
    f[u] = 1;
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        fa[v] = u,dfs1(v);
        f[u] = f[u] * (f[v] + 1) % mod;
    }
}
inline long long fastpow(long long x,int k)
{
    long long res = 1,t = x;
    while(k) 
    {
        if(k & 1) res  = res * t % mod;
        t = t * t % mod;
        k >>= 1;
    }
    return res;
}
inline long long inv(long long x){return fastpow(x,mod - 2);}
void dfs2(int u)
{
    if(fa[u])
    {
        long long gu;
        if((f[u] + 1) % mod == 0)
        {
            gu = g[fa[u]] + 1;
            for(int p = head[fa[u]];p;p=E[p].next)
            {
                int v = E[p].to;
                if(v == u || v == fa[fa[u]]) continue;
                gu = gu * (f[v] + 1) % mod;
            }
        }
        else gu = ans[fa[u]] * inv(f[u] + 1) % mod;
        g[u] = gu, ans[u] = (gu + 1) * f[u] % mod;
    }
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        dfs2(v);
    }
}
signed main()
{
    read(n);
    for(int i = 1;i<n;++i)
    {
        int x,y;
        read(x),read(y);
        add(x,y),add(y,x);
    }
    dfs1(1), ans[1] = f[1], dfs2(1);
    for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
    return 0;
}

A 友谊巨轮

栗子米从来不知道，友谊的巨轮是单向的，直到有一天他和她在了一起。

这个地球上一共有n个人，他们之间会互相发消息。在每个时刻，a与b之间互相发了c条消息。对于每个人，它友谊的巨轮为最近m个时刻里与它发消息最多的人，如果有多个发消息最多的人，那么巨轮为这里面最近发的人。如果这个人在最近m个时刻里面没有与任何人发过消息，那么它没有友谊的巨轮。
在这个题目里面，我们设定一个时刻只有某两个人之间互相发了c条消息。
栗子米获得了上帝视角，她知道了每个时刻哪两个人发了消息。她经常会发现Alice和Bob发完晚安之后，又和Charlie聊一整晚。Bob的巨轮是Alice，但是Alice的巨轮却是Charlie。栗子米想知道，每个时刻发完消息之后，有多少的人的巨轮是单向的，即它的巨轮的巨轮不是它。

还是去官网看题面会比较舒服……数据范围 $10^5$ ，提示是 $\log$ 做法。

可以对每个人建立一棵线段树：

下标代表人的编号，值代表消息数量。

那么就可以维护值最大的下标了。

由于空间不够，使用动态开点线段树，将空间压缩到 $O(n \log n)$ 级别。

遍历时刻，将离现在超过 $m$ 时间的操作，做反操作撤销即可。

相同权值取时刻最大者，额外记录一个最后修改时间，在 pushup 的时候操作一下。

答案是求多少人的巨轮单向，在每次修改的时候判断，具体看代码吧。

十年OI一场空，不开long long见祖宗！

~~连WA8次的惨痛教训！！！~~

#include <cstdio>
#include <cstring>
#include <queue>
template<typename T>
inline T max(const T &a,const T &b){return a>b?a:b;}
const int bufSize = 1e6;
inline char nc()
{
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=nc();c>'9'||c<'0';c=nc());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=nc());
}
const int maxn = 2e5 + 100;
namespace Seg
{
    long long maxx[maxn<<5];
    int maxpos[maxn<<5],tim[maxn<<5],root[maxn],L[maxn<<5],R[maxn<<5],tot;
    inline void pushup(int p)
    {
        if (maxx[L[p]] > maxx[R[p]] || (maxx[L[p]] == maxx[R[p]] && tim[L[p]] > tim[R[p]])) tim[p] = tim[L[p]], maxx[p] = maxx[L[p]], maxpos[p] = maxpos[L[p]];
        else tim[p] = tim[R[p]], maxx[p] = maxx[R[p]], maxpos[p] = maxpos[R[p]];            
    }
    void modify(const int &l,const int &r,int &p,const int &pos,const long long &k,const int &t)
    {
        if(!p) p = ++tot,maxpos[p] = maxx[p] = L[p] = R[p] = tim[p] = 0;
        if (l == r) return (void)(maxpos[p] = pos, tim[p] = max(tim[p],t), maxx[p] += k);
        int mid = l + r >> 1;
        if(pos <= mid) modify(l,mid,L[p],pos,k,t);
        else modify(mid + 1,r,R[p],pos,k,t);
        pushup(p);
    }
}
int T,n,m,k;
int A[maxn],B[maxn],C[maxn],ans;
inline void update(int a,int b,int c,int t)
{
    int f = Seg::maxpos[Seg::root[a]];
    Seg::modify(1,n,Seg::root[a],b,c,t);
    int now = Seg::maxpos[Seg::root[a]];
    if(f == now) return;
    if(f) ans += (Seg::maxpos[Seg::root[f]] == a ? 1 : -1);
    if(now) ans += (Seg::maxpos[Seg::root[now]] == a ? -1 : 1);
}
inline void init()
{
    ans = Seg::tot = 0, Seg::tim[0] = 1 << 30;
    for(int i = 1;i<=m;++i) Seg::root[i] = 0;
}
signed main()
{
    read(T);
    while(T--)
    {
        init(),read(n),read(m),read(k);
        for (int i = 1; i <= m; ++i)
        {
            read(A[i]), read(B[i]), read(C[i]);
            update(A[i],B[i],C[i],i),update(B[i],A[i],C[i],i);
            if(i > k) update(A[i - k], B[i - k], -C[i - k], i - k),update(B[i - k], A[i - k], -C[i - k], i - k);
            printf("%d\n", ans);
        }
    }
    return 0;
}