前言

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

D 绝地求生(pubg)

显然求 ,即

由于相乘可能溢出,先除再乘即可,答案保证在 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

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

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

#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 悠悠碧波

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

这种魔法可以净化黑暗。

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

  1. 它是的前缀

  2. 它是的后缀

  3. 除前缀和后缀外,它还在中出现过至少一次

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

求字符串 的前缀、后缀,且在中间出现过至少一次。

一道原题:洛谷题解直达

C Tree

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

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

假定目前遍历节点 ,某相连非父亲节点

为以 为根的子树的、包含 的连通子集数量。

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

根据乘法原理得新数量为 ,其中 为之前的数量。

累加上去即可,可以化简为 ,方便后续计算。记得边算边取模。

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

设当前点为 ,父亲节点为

当做根时, 比原先多了与 相连的一棵子树。

将这棵子树拿来更新 ,便可得到 为根的答案,记为

这棵子树的子集数量如何计算呢?可以通过 得到:

,所求即除去

记为

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

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

然而有一个奇怪的坑点,就是 意义下可能为 ,那么求逆元就会出锅……

对于这种情况,返回父亲去暴力遍历一遍,跳过当前子树再求一遍 好了。

代码实现中,用费马小定理求逆元,为了避免溢出用了#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。栗子米想知道,每个时刻发完消息之后,有多少的人的巨轮是单向的,即它的巨轮的巨轮不是它。

还是去官网看题面会比较舒服……数据范围 ,提示是 做法。

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

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

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

由于空间不够,使用动态开点线段树,将空间压缩到 级别。

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

相同权值取时刻最大者,额外记录一个最后修改时间,在 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;
}