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

Before the Beginning

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

前言

A:乱搞

B:贪心

C:神仙题,贪心+图论?

D:数据结构

E:数论

A 数列下标

看到范围,随便打个 $O(n^2)$ 水过去,理论上卡满可能会TLE,但就是过了……

#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    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>
inline T read(T &r)
{
    static char c;
    r=0;
    for(c = nc();!isdigit(c);) c = nc();
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 1e4 + 100;
int n;
int a[maxn];
int b[maxn];
int main()
{
    read(n);
    for(int i = 1;i<=n;++i) read(a[i]);
    for(int i = 1;i<=n;++i)
    {
        for(int j = i + 1;j<=n;++j)
            if (a[j] > a[i])
            {
                b[i] = j;
                break;
            }
    }
    for(int i = 1;i<=n;++i) printf("%d ",b[i]);
    return 0;
}

B 可持久化动态图上树状数组维护01背包

说实话我都不知道可持久化动态图是个啥东西……

题目其实是贪心:显然每次删除第一个元素,可以让整体代价最小。

但 $a_i < 0$ 时,代价是负数,要求最大,那么对于 $a_i$ 而言最大的下标就是原始下标。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define int long long
#define DEBUG
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    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>
inline T read(T &r)
{
    static char c;
    static int flag;
    r=0;
    flag = 1;
    for(c = nc();!isdigit(c);c = nc()) if(c == '-') flag = -1;
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r * flag;
}
const int maxn = 1e6 + 100;
int n;
int a[maxn];
signed main()
{
    scanf("%lld",&n);
    for(int i = 1;i<=n;++i) scanf("%lld",a + i);
    long long sum = 0;
    for(int i = 1;i<=n;++i) if(a[i] < 0) sum += i * a[i]; else sum += a[i];
    printf("%lld\n",sum);
    return 0;
}

D 树上求和

其实这是我打的第二道题……一眼可以用树剖做,于是就是树链剖分的板子题。

但其实似乎只求子树用dfs序就可以……?是我蠢了。

线段树维护平方和也是老套路了:

$\sum (a_i + k)^2 = \sum a_i^2 + \sum a_i \times k \times 2 + len \times k^2$

#include <cstdio>
#include <ctype.h>
#define DEBUG
#define int long long
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    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>
inline T read(T &r)
{
    static char c;
    r=0;
    for(c = nc();!isdigit(c);) c = nc();
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 1e5 + 100,maxm = 2e5 + 100;
int n,m;
struct node
{
    int to,next;
}E[maxm];
int head[maxn];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int w[maxn];
int size[maxn],fa[maxn],son[maxn],dfn[maxn],id[maxn],cnt;
long long sum[maxn<<2],tsum[maxn<<2],tag[maxn<<2];
const int mod = 23333;
#define ls p<<1
#define rs p<<1|1
inline void pushup(const int &p){sum[p] = sum[ls] + sum[rs];tsum[p] = tsum[ls] + tsum[rs];sum[p] %= mod,tsum[p] %= mod;}
inline void pushdown(const int &l,const int &r,const int &p)
{
    if(!tag[p]) return;
    int mid = l + r >> 1;
    tsum[ls] += (mid - l + 1) * tag[p] * tag[p] + 2 * sum[ls] * tag[p];
    tsum[rs] += (r - mid) * tag[p] * tag[p] + 2 * sum[rs] * tag[p];
    sum[ls] += (mid - l + 1) * tag[p];
    sum[rs] += (r - mid) * tag[p];
    tag[ls] += tag[p],tag[rs] += tag[p];
    tsum[ls] %= mod,tsum[rs] %= mod,sum[ls] %= mod,sum[rs] %= mod,tag[ls] %= mod,tag[rs] %= mod;
    tag[p] = 0;
}
void build(int l,int r,int p)
{
    if(l == r) return (void)(sum[p] = w[id[l]] % mod,tsum[p] = (w[id[l]] * w[id[l]]) % mod);
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
    pushup(p);
}
void modify(int l,int r,int p,int ll,int rr,long long k)
{
    if(l >= ll && r <= rr)
    {
        tsum[p] += (r - l + 1) * k * k + 2 * sum[p] * k;
        sum[p] += (r - l + 1) * k;
        tag[p] += k;
        tsum[p] %= mod,sum[p] %= mod,tag[p] %= mod;
        return;
    }
    int mid = l + r >> 1;
    pushdown(l,r,p);
    if(ll <= mid) modify(l,mid,ls,ll,rr,k);
    if(rr > mid) modify(mid + 1,r,rs,ll,rr,k);
    pushup(p);
}
long long ask(int l,int r,int p,int ll,int rr)
{
    if(l >= ll && r <= rr) return tsum[p];
    int mid = l + r >> 1,ans = 0;
    pushdown(l,r,p);
    if(ll <= mid) ans = ask(l,mid,ls,ll,rr) % mod;
    if(rr > mid) ans = (ans + ask(mid + 1,r,rs,ll,rr)) % mod;
    return ans;
}
void dfs1(int u)
{
    size[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),size[u] += size[v];
        if(size[son[u]] < size[v]) son[u] = v;
    }
}
void dfs2(int u)
{
    dfn[u] = ++cnt;
    id[cnt] = u;
    if(!son[u]) return;
    dfs2(son[u]);
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v);
    }
}
signed main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) read(w[i]);
    for(int i = 1;i<n;++i)
    {
        int a,b;
        read(a),read(b);
        add(a,b),add(b,a);
    }
    dfs1(1),dfs2(1);
    build(1,n,1);
    while(m--)
    {
        int opt,x,y;
        read(opt),read(x);
        if(opt == 1) read(y),modify(1,n,1,dfn[x],dfn[x] + size[x] - 1,y);
        else printf("%lld\n",ask(1,n,1,dfn[x],dfn[x] + size[x] - 1) % mod);
    }
    return 0;
}

E 算式子

数论题。

显然左半边右半边可以分开计算。

不知道为啥用整除分块会TLE自闭到怀疑人生

定义:

$\operatorname{cnt}(i)$ 为值 $\leq i$ 的元素的数量。

$\operatorname{ans}(i)$ 为 $x = i$ 时,$\sum \lfloor \dfrac{a_i}{x} \rfloor$ 的值。

我们可以枚举 $x$:

对于一个 $x$,可以枚举右半边的商 $k$,即:

$\lfloor \dfrac{x}{a_i} \rfloor = k$

那么符合条件的 $a_i$ 显然在一个连续的值域范围内,即:

$l = k \times x, r = (k + 1) \times x – 1$

对于这个范围内的 $a_i$,对答案的贡献都为 $k$,这一段内的贡献就是 $k \times num$。

可以使用 $cnt$ 数组计算 $num$

此时计算完右半边式子的答案了,考虑如何计算左半边式子。

左半边式子乍一看不好处理,但可以发现对于每个 $a_i$,有一段连续的 $x$ 的答案是相同的,启示我们用类似的方法。

枚举 $a_i$ 的值域 $i$ 与商 $k$,同理可以得到:

$l = k \times i, r = (k + 1) \times i – 1$

那么对于 $[l,r]$ 中的 $x$,这个 $i$ 值对左半边的贡献为 $num \times k$,即 $i$ 值出现的次数乘上商。

对于这个区间修改,可以用差分处理,在 $l$ 点加上贡献,在 $r + 1$ 点减去贡献,最后做前缀和即可。

那么就可以预处理出 $ans$ 数组了。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
#define int long long
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    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>
inline T read(T &r)
{
    static char c;
    r=0;
    for(c = nc();!isdigit(c);) c = nc();
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 2e6 + 100;
int n,m;
int a[maxn];
int cnt[maxn<<1],ans[maxn<<1];
signed main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) read(a[i]),cnt[a[i]]++;

    for(int i = 1;i <= m; i++) if(cnt[i])
        for (int k = 1; i * k <= m; ++k)
        {
            int l = k * i, r = (k + 1) * i - 1;
            ans[l] += cnt[i] * k, ans[r + 1] -= cnt[i] * k;
        }
    for (int i = 1; i <= 2 * m; ++i) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= 2 * m; ++i) ans[i] += ans[i - 1];
    long long last = 0;
    for(int i = 1;i<=m;++i)
    {
        long long sum = 0;
        /* 
        for (int l = 1, r, k; l <= i; l = r + 1)
        {
            k = i / l, r = i / k;
            sum += k * (cnt[r] - cnt[l - 1]);
        }
        */
        sum += ans[i];
        for (int k = 1; i * k <= m; ++k)
        {
            int l = k * i, r = (k + 1) * i - 1;
            sum += k * (cnt[r] - cnt[l - 1]);
        }
        
        last ^= sum;
    }
    printf("%lld\n",last);
    return 0;
}

C 璀璨光滑

首先推几个结论:

  1. 原编号为 $1$ 的点新编号为 $0$ ,可使字典序最小。
  2. 距离新编号为 $0$ 的点,最短距离为 $x$ 的点,新编号中有 $x$ 个 $1$。考虑从 $0$ 号点开始走,每次增加一个 $1$,最少 $x$ 步后才能走出 $x$ 个 $1$,且该距离为最小距离,若不如此走,分两种情况:将新编号中 $1$ 位走成 $0$ 或将新编号中 $0$ 位走成 $1$,则都需要走回头路,因此距离更长。
  3. 新编号含有 $x$ 个 $1$ 的点,仅与若干个含有 $x + 1$ 个 $1$ 的点与含有 $x – 1$ 个 $1$ 的点联通,且若干个含有 $x – 1$ 个 $1$ 的点新编号的或和即为该点新编号。考虑含有 $x – 1$ 个 $1$ 的点,根据第二条结论发现它们离 $0$ 的距离为 $x – 1$,则其直接与含有 $x$ 个 $1$ 的点联通的路径即为其最短路。因此可以推出,这些点与含有 $x$ 个 $1$ 的点仅相差一个包含在 $x$ 个 $1$ 中的 $1$,且每个点相差的 $1$ 位置都不同。这些点或起来,即可得到含有 $x$ 个 $1$ 的点的新编号。
  4. 交换二进制位列,对图性质无影响。例如有点:101 001 010,将第一列交换至第三列,第二列交换至第一列,第三列交换至第二列,新编号为:011 010 100,而原先的图关系不变。
  5. 将所有点的二进制编号看做矩阵,行为点原编号,列为二进制位,值为对应的 $0$ 或 $1$,那么交换任意两列,图的性质不变。由于字典序,应当让原编号小的对应的 $1$ 的列排在低位。

可以看到,推出的前三个结论与距离密切相关。

整个图可以看做一圈一圈的、距离依次加一的几层,而用该层编号即可推出下层编号,因此可以对原图做一遍宽度优先搜索。

将与原 $1$ 号点相连的点随意分配初始编号,进行一次宽度优先搜索,即可找出一组可行解。

再根据后两个结论,将列进行排序,即可找出最优解。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    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>
inline T read(T &r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c);)
        c = nc();
    for (; isdigit(c); c = nc())
        r = r * 10 + c - 48;
    return r;
}
const int maxn = 2e6 + 100, maxm = 5e6 + 100;
int T, n, m;
struct node
{
    int to, next;
} E[maxm];
int head[maxn], tot;
inline void add(const int &x, const int &y)
{
    E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
int q[maxn], qt, qh;
int f[maxn], vis[maxn], inq[maxn];
struct A
{
    bool s[maxn];
    int id;
} P[22];
bool cmp(const A &a, const A &b)
{
    for (int i = 1; i <= (1 << n); ++i) 
        if (a.s[i] != b.s[i]) return a.s[i] > b.s[i];
    return 1;
}
int main()
{
    read(T);
    while (T--)
    {
        read(n), read(m);
        qh = 1, qt = 0;
        tot = 0;
        for (int i = 1; i <= (1 << n); ++i)
            vis[i] = f[i] = inq[i] = head[i] = 0;
        for (int i = 1; i <= m; ++i)
        {
            int a, b;
            read(a), read(b);
            add(a, b), add(b, a);
        }
        vis[1] = 1;
        for (int p = head[1], t = 0; p; p = E[p].next)
        {
            int v = E[p].to;
            f[v] = 1 << (t++);
            q[++qt] = v;
        }
        while (qt >= qh)
        {
            int u = q[qh++];
            vis[u] = 1,inq[u] = 0;
            for (int p = head[u]; p; p = E[p].next)
            {
                int v = E[p].to;
                if (vis[v]) continue;
                f[v] |= f[u];
                if (!inq[v]) q[++qt] = v, inq[v] = 1;
            }
        }
        for (int i = 0; i < n; ++i) P[i].id = i;
        for (int i = 1; i <= (1 << n); ++i) 
            for (int j = 0; j < n; ++j)
                P[j].s[i] = (f[i] >> j) & 1;
        std::sort(P, P + n, cmp);
        for (int i = 1; i <= (1 << n); ++i)
        {
            int res = 0;
            for (int j = 0; j < n; ++j) if (P[j].s[i]) res |= (1 << j);
            printf("%d ", res);
        }
        putchar('\n');
    }
    return 0;
}
本文标题:[Nowcoder]周周练15
本文作者:Clouder
本文链接: https://www.codein.icu/nowcoderweekly15/
转载请标明。
暂无评论

发送评论 编辑评论

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