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

Before the Beginning

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

前言

A:阅读理解

B:模拟

C:博弈

D:最短路dp

E:dp

A 红包期望

这题真是令人难以理解……
根据直觉,我们知道期望为 $\dfrac{n}{m}$,其他的描述都是无用的。
这期望居然是个整数,用浮点会WA。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
#define DEBUG
const int bufSize = 1e6;
#define int long long
int n,m,T;
signed main()
{
    scanf("%lld %lld %lld",&m,&n,&T);
    int size =  n / m;
    int final = n - size * (m - 1);
    while(T--)
    {
        int x;
        scanf("%lld",&x);
        if(x <= m) printf("%lld\n",size);
//        else if(x == m) printf("%lld\n",final);
        else printf("0\n");
    }
    return 0;
}

B 死肥宅的冲分计划

按题意模拟即可。至于那两个特殊情况,其实就是超出值域时拉回来。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int maxn = 20;
int a[maxn];
int main()
{
    while(scanf("%d %d %d %d %d %d %d %d %d %d",a + 1,a + 2,a +3,a+4,a+5,a+6,a+7,a+8,a+9,a+10) != EOF)
    {
        int start = 2;
        int final = 6;
        for(int i = 1;i<=10;++i)
        {
            if(a[i] == 1) ++start;
            else if(a[i] == 0) continue;
            else if(a[i] == 7) --start;
            if(start < 0) start = 0;
            else if(start > final) start = final;
        }
        if(start == final) puts("666");
        else puts("777");
    }
    return 0;
}

C 树链博弈

每层黑色节点数都为偶数时,先手必败。
假设先手选择一个黑点,不翻转祖先,则后手选择同层黑点,不翻转祖先,状态不变。
假设先手翻转祖先,则后手翻转对应层的祖先,状态不变。
这样逐层消去,末状态为与根节点相连的黑点为偶数个,此时翻转祖先不改变结果,依次取黑,后手胜。

否则,若有一层为奇数,则先手可以一步将所有层设为偶数,随后将后手代入上述推导,便是先手胜局。

#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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    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 = 1100;
const int maxm = maxn * 2;
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 n;
int col[maxn],dep[maxn];
int cnt[maxn][2];
void dfs(int u,int fa)
{
    dep[u] = dep[fa] + 1;
    cnt[dep[u]][col[u]]++;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs(v,u);
    }
}
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(col[i]);
    for(int i = 1;i<n;++i)
    {
        int a,b;
        read(a),read(b),add(a,b),add(b,a);
    }
    //不加边都能过样例...
    dfs(1,0);
    for (int i = 1; i <= n; ++i) if(cnt[i][1] & 1) {puts("First");return 0;}
    puts("Second");
    return 0;
}

D Rinne Loves Dynamic Graph

显然变动函数是一个周期函数,相信大家都做过类似的数学题。

$f_0(x) = x$
$f_1(x) = \dfrac{1}{1 – x}$
$f_2(x) = 1 – \dfrac{1}{x}$
$f_3(x) = x \ldots$

设经过边数为 $t$,边权为 $x$,将 $t \bmod 3$ 代入即可求得当时边权。
随后就是经典的分层图、图上dp问题。
设计状态为,到达 $i$ 点,经过边数模三结果为 $t$,跑个最短路就行了。
$dis(i,t)$ 代表上述状态的最小距离。

#include <cstdio>
#include <queue>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    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;
const int maxm = 1e6 + 100;
int n,m;
template<typename T>
inline T abs(const T &a){return a > 0 ? a : -a;}
inline double getdis(int x,int t)
{
    if(t == 0) return abs(1.0 * x);
    else if(t == 1) return abs(1.0 / (1.0 - x));
    else return abs(1.0 - 1.0 / x);
}
struct node
{
    int to,next,val;
}E[maxm];
int head[maxn];
inline void add(const int &x,const int &y,const int &val)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,E[tot].val = val,head[x] = tot;
}
double dis[maxn][5];
using namespace std;
struct aaa
{
    int id,t;
    double dis;
    bool operator<(const aaa &b) const{return dis > b.dis;}
};
priority_queue<aaa> q;
bool vis[maxn][5];
inline void dij()
{
    for (int i = 1; i <= n; ++i) dis[i][0] = dis[i][1] = dis[i][2] = 1e30;
    dis[1][0] = 0;
    aaa t;
    t.id = 1,t.t = 0,t.dis = dis[1][0];
    q.push(t);
    while(!q.empty())
    {
        int u = q.top().id;
        int t = q.top().t;
        q.pop();
        if(vis[u][t]) continue;
        vis[u][t] = 1;
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            int nt = (t + 1) % 3;
            double nv = getdis(E[p].val,t);
            if(vis[v][nt]) continue;
            if(dis[v][nt] > dis[u][t] + nv)
            {
                dis[v][nt] = dis[u][t] + nv;
                aaa ne;
                ne.id = v,ne.t = nt;
                ne.dis = dis[v][nt];
                q.push(ne);
            }
        }
    }
}
int main()
{
    read(n),read(m);
    while(m--)
    {
        int a,b,c;
        read(a),read(b),read(c);
        add(a,b,c),add(b,a,c);
    }
    dij();
    int viss = (vis[n][0] | vis[n][1] | vis[n][2]);
    double anss = std::min(dis[n][0],dis[n][1]);
    anss = std::min(anss,dis[n][2]);
    if(!viss) puts("-1");
    else printf("%.3f",anss);
    return 0;
}

E 1408

似乎网上没这道题题解,于是全场……
一开始看错题了,以为黑白球必须分别扎堆,其实不需要。
可以使用动态规划来解决,由于要求顺序,那么:
设前 $i$ 个球中,有 $a$ 个白球,$b$ 个黑球,那么对应的黑白球编号一定是 $1,2,3,\ldots,a$ 和 $1,2,3,\ldots,b$。
此时决定第 $i + 1$ 个球,选择白球或者黑球进行转移,即满足了最优子结构。
设 $f(i,j)$ 为前 $i$ 个球,$j$ 个白球,$i – j$ 个黑球的状态。
如果决定第 $i$ 个球为白球,$f(i,j) = f(i-1,j-1) + val$,其中 $val$ 为编号为 $j$ 的球移到 $i$ 的代价。
黑球同理。
考虑如何计算这个代价,显然可以记录 $pos(i)$ 代表编号为 $i$ 的球的坐标,代价即 $pos(i) – i$。
然而在前面的过程中,即移动前 $i – 1$ 个球时,$pos(i)$ 可能发生了变化。
如果移动的球在 $pos(i)$ 前,则对其无影响,如果在其后,则 $pos(i) + 1$。
统计当前状态,编号 $1,2,3,\ldots,j$ 的白球与 $1,2,3,\ldots,i – j$ 的黑球中,有多少个在 $[pos + 1,2 \times n]$ 中,即可知道该球的 $pos$ 向后了多少。
计算出相应代价进行DP即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
const int maxn = 4e3 + 100;
int n;
int wnum,bnum;
char s[10];
int f[maxn][maxn];//前i个,白色前j个
int id[maxn],col[maxn];
int wpos[maxn],bpos[maxn];
int wcnt[maxn][maxn],bcnt[maxn][maxn];
inline int getw(int l,int r,int x){return wcnt[r][x] - wcnt[l - 1][x];}
inline int getb(int l,int r,int x){return bcnt[r][x] - bcnt[l - 1][x];}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n * 2; ++i)
    {
        scanf("%s", s + 1), scanf("%d", id + i);
        col[i] = (s[1] == 'B');
        if(col[i]) bpos[id[i]] = i;
        else wpos[id[i]] = i;
    }
    for(int i = 1;i<=2*n;++i) 
    {
        if (col[i] == 0) for (int j = id[i]; j <= n; ++j) wcnt[i][j]++;
        else for (int j = id[i]; j <= n; ++j) bcnt[i][j]++;
        for (int j = 1; j <= n; ++j) wcnt[i][j] += wcnt[i - 1][j], bcnt[i][j] += bcnt[i - 1][j];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= 2 * n; ++i)
    {
        for (int j = 0; j <= n && j <= i; ++j)
        {
            int bl = i - j;
            if (j <= i - 1)
            {
                //choose black to fill i
                int bp = bpos[bl];
                f[i][j] = f[i - 1][j] + bp - i + getw(bp + 1, 2 * n, j) + getb(bp + 1, 2 * n, bl - 1);
            }
            if (j)
            {
                //choose white to fill i
                int wp = wpos[j];
                f[i][j] = std::min(f[i][j], f[i - 1][j - 1] + wp - i + getw(wp + 1, 2 * n, j - 1) + getb(wp + 1, 2 * n, bl));
            }
        }
    }
    printf("%d\n",f[2*n][n]);
    return 0;
}
本文标题:[Nowcoder]周周练16题解
本文作者:Clouder
本文链接: https://www.codein.icu/nowcoderweekly16/
转载请标明。

评论

  1. 6月前
    2020-7-23 1:58:54

    Clouder太强啦!

发送评论 编辑评论

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