牛客练习赛39 题解
A走方格
链接：https://ac.nowcoder.com/acm/contest/368/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
在一个n*n的方格中，你只能斜着走。
你还有一次上下左右走的机会
给你一个起点(sx,sy)，和终点(ex,ey)，询问从起点到终点最少走多少步。
输入描述:
一行5个整数，n,sx,sy,ex,ey。
1≤sx,sy,ex,ey≤n≤10181≤sx,sy,ex,ey≤n≤1018
输出描述:
一行一个整数，表示从起点到终点最少走多少步。示例1
输入
8 2 3 7 5输出
5
分析：
签到题，画一下图，就出来了。
import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
//Scanner in = new Scanner (new BufferedInputStream(System.in));
Scanner in = new Scanner(new BufferedInputStream(System.in));
Reader.init(System.in);
Long n=in.nextLong();
Long sx=in.nextLong();
Long sy=in.nextLong();
Long ex=in.nextLong();
Long ey=in.nextLong();
if(Math.abs(sx-ex)==Math.abs(sy-ey))
{
System.out.println(Math.abs(sx-ex));
}
else
{
System.out.println(Math.max(Math.abs(sx-ex), Math.abs(sy-ey)));
}
}
}
class Reader
{
static BufferedReader reader;
static StringTokenizer tokenizer;
static void init(InputStream input)
{
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
static String next() throws IOException
{
while(!tokenizer.hasMoreTokens())
{
String str=reader.readLine();
//System.out.println(str);
tokenizer = new StringTokenizer(str);
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException
{
return Integer.parseInt(next());
}
static double nextDouble() throws IOException
{
return Double.parseDouble(next());
}
}
B选点
链接：https://ac.nowcoder.com/acm/contest/368/B
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树，都要满足：
如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；
如果在左子树选了一个点，在右子树中选的其他点要比它小。
输入描述:
第一行一个整数n。
第二行n个整数wi，表示每个点的权值。
接下来n行，每行两个整数a,b。第i+2行表示第i个节点的左右儿子节点。没有为0。
n,a,b≤105,−2×109≤wi≤2×109n,a,b≤105,−2×109≤wi≤2×109
输出描述:
一行一个整数表示答案。示例1
输入
5
1 5 4 2 3
3 2
4 5
0 0
0 0
0 0 输出
3
分析：
因为题意要求根节点的权值最小，其次是右子树的点，最后是左子树的点，所以按照先根，再右子树，再左子树的顺序dfs整棵树，求出dfs序，在dfs序上求最长上升子序列即可。
java手写了一个二分，但一直错，改成c++就对了，郁闷
C++通过代码
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100005;
int w[N], ls[N], rs[N], q[N], f[N], tot;
void dfs(int u) {
if (!u) return ;
q[++tot] = u;
dfs(rs[u]);
dfs(ls[u]);
}
int solve(int key ,int n)
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(f[mid]>=key)
{
r=mid;
}
else
l=mid+1;
}
//System.out.println(l);
return l;
}
int main() {
int n;
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
for (int i=1; i<=n; ++i) scanf("%d%d", &ls[i], &rs[i]);
dfs(1);
for (int i=1; i<=n; ++i) q[i] = w[q[i]];
int cnt = 1;
f[1] = q[1];
for (int i=2; i<=n; ++i) {
if (q[i] > f[cnt]) f[++cnt] = q[i];
else {
int pos =solve(q[i],cnt);
//cout<<pos<<endl;
f[pos] = q[i];
}
}
cout << cnt;
return 0;
}
java越界代码
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100005;
int w[N], ls[N], rs[N], q[N], f[N], tot;
void dfs(int u) {
if (!u) return ;
q[++tot] = u;
dfs(rs[u]);
dfs(ls[u]);
}
int solve(int key ,int n)
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(f[mid]>=key)
{
r=mid;
}
else
l=mid+1;
}
//System.out.println(l);
return l;
}
int main() {
int n;
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
for (int i=1; i<=n; ++i) scanf("%d%d", &ls[i], &rs[i]);
dfs(1);
for (int i=1; i<=n; ++i) q[i] = w[q[i]];
int cnt = 1;
f[1] = q[1];
for (int i=2; i<=n; ++i) {
if (q[i] > f[cnt]) f[++cnt] = q[i];
else {
int pos =solve(q[i],cnt);
//cout<<pos<<endl;
f[pos] = q[i];
}
}
cout << cnt;
return 0;
}其他题待补，先上标准答案
C流星雨
链接：https://ac.nowcoder.com/acm/contest/368/C
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
现在一共有n天，第i天如果有流星雨的话，会有wiwi颗流星雨。
第i天有流星雨的概率是pipi。
如果第一天有流星雨了，那么第二天有流星雨的可能性是p2+Pp2+P，否则是p2p2。相应的，如果第i−1 (i≥2)i−1 (i≥2)天有流星雨，第i天有流星雨的可能性是pi+Ppi+P，否则是pipi。
求n天后，流星雨颗数的期望。
输入描述:
第一行三个整数，n,a,b，其中n为天数，P=abP=ab
第二行n个整数wiwi。
接下来n行，每行两个整数，x,y，第i+2行表示第i天有流星雨的概率pi=xypi=xy。
1≤n≤105, 1≤a,b,x,y,wi≤109, pi+P≤1.01≤n≤105, 1≤a,b,x,y,wi≤109, pi+P≤1.0
输出描述:
一行一个整数，为答案对109+7109+7 取模的结果。
即设答案化为最简分式后的形式为abab，其中a和b互质。输出整数 x 使得bx≡a(mod 109+7)bx≡a(mod 109+7)且0≤x<109+70≤x<109+7。可以证明这样的整数x是唯一的。
示例1
输入
2 1 3
1 1
1 2
1 2输出
166666669说明
第一天有流星雨第二天也有流星雨的概率是12×(12+13)12×(12+13)，然后乘以流星雨的颗数2
第一天有流星雨第二天没有流星雨的概率是12×1612×16，乘以颗数1
第一天没有，第二天有的概率12×1212×12，乘以颗数1
第一天没有，第二天也没有的概率12×1212×12，乘以颗数0。
所以流星雨颗数的期望是7676
示例2
输入
3 1 5
1 1 2
1 2
1 4
2 3输出
763333341分析：
D动态连通块
链接：https://ac.nowcoder.com/acm/contest/368/D
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
小T有n个点，每个点可能是黑色的，可能是白色的。
小T对这张图的定义了白连通块和黑连通块：
白连通块：图中一个点集V，若满足所有点都是白点，并且V中任意两点都可以只经过V中的点互相到达，则称V中的点构成了一个白连通块。
黑连通块：类似白连通块的定义。
小T对这n个点m次操作。
1、在两个点之间连一条边。
2、询问白（黑）连通块个数。
3、给出x,y两个点，保证同色（为了方便描述，x,y都是白点，黑色同理）。询问存在多少个黑点，将它改变颜色后，x,y所在的白连通块会合并为一个。如果x,y已经在一个白连通块内了，输出-1。（注意：这里不会对点的颜色改变，只统计个数）
输入描述:
第一行两个整数n,m，分别表示点的个数和操作的个数。
第二行n个整数，第i个整数描述第i个点的颜色，0表示白色，1表示黑色。
接下来m行，每行包含2个或者3个整数，描述三种操作。
操作1：1,x,y，表示在x,y之间加入一条边。
操作2：2,x，若x=0，询问白连通块的个数，否则询问黑连通块的个数。
操作3：3,x,y，表示第三种操作。
n,m≤50000,x,y≤nn,m≤50000,x,y≤n
输出描述:
对于询问操作，输出一个整数。示例1
输入
6 7
0 1 0 0 0 1
1 3 2
1 2 4
3 3 4
1 1 3
2 0
3 1 4
3 1 3输出
1
3
1
-1说明
第一次询问：2号点变成白色后，3,4所在的白连通块合并为一个。
第二次询问：白连通块的个数为3，分别是{1,2}，{3}，{4}。
第三次询问：2号点变成白色后，1,4所在的白连通块合并为一个。
第四次询问：1,3已经是同一个白连通块了，输出-1。分析：