08-26 23:12 已编辑東京大学 golang 发布于上海

关注

牛客周赛 Round 57 解题报告 | 珂学家

小红喜欢1

https://ac.nowcoder.com/acm/contest/88888/A

前言

alt

题解

难度比较适宜，这场周赛出的不错。

A. 小红喜欢1

题型: 签到+语法

arr = list(map(int, input().split()))
 
print (arr.index(1) + 1)

B. 小红的树切割

思路：思维

统计边两端为同一颜色的边数即可

n = int(input())
 
s = input()
 
res = 0
for i in range(n - 1):
    u, v = list(map(int, input().split()))
    if s[u - 1] == s[v - 1]:
        res += 1
         
print (res)

C. 小红的双好数（easy）

思路: 数论 + 分类讨论

首先，2进制是天然好进制

同时需要借用一个经典结论

$相邻两个自然数互质，自然n满足(n - 1)的好进制$

因此，对于大部分n，只要 $2, n - 1$ 两数即可

所以需要考虑的是例外是

n = 1,3

2，3为解
n = 2

无解

n = int(input())

if n == 1 or n == 3:
    print ("YES")
    print (2, 3)
elif n == 2:
    print ("NO")
else:
    print ("YES")
    print (2, n - 1)

D. 小红的线段

思路: 数学 + 贪心

$如果和 y = k * x b, 直线，有交点，则该线段两端点在直线的两侧$

${根据 y= f(x_i) = k * x_i b, 和 y_i 进行大小比较}$

$y \lt y_i$ , 则在直线下方, 构建点集 $S_{neg}$
$y \gt y_i$ , 则在直线上方, 构建点集 $S_{pos}$
${y == y_i}$ , 则该点恰好在直线上, 构建点集 $S_{zero}$

优先利用 $S_{neg}, S_{pos}$ 构建线段
次之使用 $S_{zero} 和多余的S_{neg}, S_{pos}构建线段$
再次之使用 $S_{zero} 两两配对$
剩下的都是没有交点的情况

n, k, b = list(map(int, input().split()))

def xl(x, y):
    y1 = k * x + b
    if y == y1:
        return 0
    elif y > y1:
        return 1
    return -1

pos = []
neg = []
zero = []

for i in range(2 * n):
    x, y = list(map(int, input().split()))
    d = xl(x, y)
    if d==0:
        zero.append(i + 1)
    elif d > 0:
        pos.append(i + 1)
    else:
        neg.append(i + 1)

ans = 0
res = []
while len(pos) > 0 and len(neg) > 0:
    t1, t2 = pos.pop(), neg.pop()
    res.append((t1, t2, 'Y'))
    ans += 1
    
while len(zero) > 0 and len(pos) > 0:
    t1, t2 = zero.pop(), pos.pop()
    res.append((t1, t2, 'Y'))
    ans += 1
    
while len(zero) > 0 and len(neg) > 0:
    t1, t2 = zero.pop(), neg.pop()
    res.append((t1, t2, 'Y'))
    ans += 1
    
while len(zero) >= 2:
    t1, t2 = zero.pop(), zero.pop()
    res.append((t1, t2, 'Y'))
    ans += 1
        
while len(pos) >= 2:
    t1, t2 = pos.pop(), pos.pop()
    res.append((t1, t2, 'N'))
    
while len(neg) >= 2:
    t1, t2 = neg.pop(), neg.pop()
    res.append((t1, t2, 'N'))
        
print (ans)
for e in res:
    print (*e, sep=' ')

E. 小红的双好数（hard）

题型: 数论+枚举

所求的数，满足

$z = \sum a_i * k1^i, a_i \in (0, 1)$

同时满足

$z = \sum b_i * k2^i, b_i \in (0, 1)$

因为 $k1 < k2$ , 所以尝试构造枚举 $\{b_i * k2^i\}$ 的序列出发，然后验证满足某个 $\{a_j * k1 ^ j\}$

因为 ${2 \le k1 \lt k2}$

所以在 $[2, 10^{18}]$ 范围内

满足序列的个数，最多为

$2 ^ x, x = log(10^{18}) / log(k2)$

k2	最大的指数	状态数
3	${log_3 10^{18} = 37.7}$	$2^{38}$
4	${log_4 10^{18} = 29.8}$	$2^{30}$
5	${log_5 10^{18} = 25.7}$	$2^{26}$
6	${log_6 10^{18} = 23.1}$	$2^{23}$

分类讨论下

${k2 \le 6}$ ，其实可以打表（实际上不需要，解空间很小）
${k2 \ge 7}$ , 状态空间已经很小，可暴力全枚举

def check(v, k):
    while v > 0:
        r = v % k
        if r > 1:
            return False
        v //= k
    return True

def solve():
    k1, k2 = list(map(int, input().split()))
    dp = [0]
    base = k2
    while base <= 10 ** 18:
        dp2 = dp[:]
        for v in dp:
            if check(v + base, k1):
                return v + base
            dp2.append(v + base)
        base = base * k2
        dp = dp2
    return -1

ans = solve()
if ans == -1:
    print ("NO")
else:
    print ("YES")
    print (ans)

G. 小红的双排列构造

思路: 构造

其实这题的指向很明确

$假设存在一个1~n的排列$

然后把剩下的1~n围绕其左右侧，使得正好的排列数为K

策略:

先左侧构建一个 1~N的数组
那右侧天然就是一个1~N的数组
然后从左侧，依次构造 k - 2的排列数
剩下的何如阻断呢？其实打断它的循环节即可

对于特殊的情况，比如k=0,n=1，这些组合需要特判

写了一个很奇怪的代码

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt(), k = sc.nextInt();

        if (k == 0) {
            if (n <= 2) {
                System.out.println("-1");
            } else {
                List<Integer> res = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    res.add(i + 1);
                    res.add(i + 1);
                }
                System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            }
        } else {
            if (n == 1) {
                if (k == 1) {
                    System.out.println(-1);
                } else if (k==2) {
                    System.out.println("1 1");
                }
            } else if (k == 1) {
                List<Integer> res = new ArrayList<>();
                res.add(1);
                for (int i = 0; i < n; i++) {
                    res.add(i + 1);
                }
                for (int i = 1; i < n; i++) {
                    res.add(i + 1);
                }
                System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            } else {
                List<Integer> res = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    res.add(i + 1);
                }
                for (int i = 0; i < k - 2; i++) {
                    res.add(i + 1);
                }
                for (int i = k - 2; i < n; i++) {
                    res.add(n - (i - k + 2));
                }
                System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            }
        }
    }
}

写在最后

alt

全部评论

推荐最新楼层

11-25 19:36

华北电力大学（保定） Java

26日常实习，求指点

陆陆续续投了一个月了，一个面试也没有，是简历太差了吗，之前是黑马点评➕学成在线，后来把两个合并了下，又手写了个rpc，简历还需要怎么改改😭😭，救救孩子吧，之前有两个笔试，自己太差没把握住机会

我是一盘牛肉：简历没毛病，但就是没什么岗位了

投了多少份简历才上岸你的简历改到第几版了

点赞评论收藏

11-23 10:48

门头沟学院 Java

秋招0offer，感觉心气被磨没了

忙碌了两三个月，收获的只有几个烂意向，全部拒了，到头来还是一场空，怀疑自己读研的意义现在的心态有点像三和大神，感觉事情都是没有意义的，提不起劲，刚入学时意气风发的少年去哪了

Hanak01_offer多多版：+1

点赞评论收藏

10-21 17:38

桂林理工大学 Java

秋招现状

霁华Tel：秋招结束了，好累。我自编了一篇对话，语言别人看不懂，我觉得有某种力量在控制我的身体，我明明觉得有些东西就在眼前，但身边的人却说啥也没有，有神秘人通过电视，手机等在暗暗的给我发信号，我有时候会突然觉得身体的某一部分不属于我了。面对不同的人或场合，我表现出不一样的自己，以至于都不知道自己到底是什么样子的人。我觉得我已经做的很好，不需要其他人的建议和批评，我有些时候难以控制的兴奋，但是呼吸都让人开心。

点赞评论收藏