[Nowcoder]周周练14
本文最后更新于 200 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/nowcoderweekly14/

前言

说是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$满足以下条件:

  1. 它是$s$的前缀
  2. 它是$s$的后缀
  3. 除前缀和后缀外,它还在$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;
}
本文标题:[Nowcoder]周周练14
本文作者:Clouder
本文链接: https://www.codein.icu/nowcoderweekly14/
转载请标明。

评论

  1. 7月前
    2020-7-08 9:44:47

    A代码能解释一下吗

    • Clouder 博主
      7月前
      2020-7-10 7:21:12

      每个人开一棵线段树,维护根节点编号。用动态开点线段树来节省空间。维护最大消息数、最大消息数的坐标、最大消息数的时间,上推时以消息数为第一关键字,时间为第二关键字比较。
      在每次对线段树进行修改时,比较修改前与修改后的最大消息坐标,进行答案更新。

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇