PREV50 对局匹配
题目描述
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。
现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, ... AN。
小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？
输入格式
第一行包含两个个整数N和K。
第二行包含N个整数A1, A2, ... AN。
对于30%的数据，1 <= N <= 10
对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000
输出格式
一个整数，代表答案。
样例输入
10 0
1 4 2 8 5 7 1 4 2 8
样例输出
6
算法分析
image.png
时间复杂度 )
第一个for遍历k次，第二个for遍历a / k次
Java 代码
import java.util.Scanner;
public class Main {
static int N = 100010;
static int n,k;
static int[] a = new int[N];
static int maxv = 0;
static int[] f = new int[N];
static int[] val = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
k = scan.nextInt();
for(int i = 0;i < n;i ++)
{
int x = scan.nextInt();
maxv = Math.max(maxv, x);
a[x] ++;
}
int res = 0;
if(k == 0)
{
for(int i = 1;i <= maxv;i ++)
{
if(a[i] != 0) res ++;
}
}
else
{
for(int i = 0;i < k;i ++)
{
f[i] = a[i];
f[i + k] = a[i + k];
int cnt = Math.max(f[i], f[i + k]);
for(int j = i + 2 * k;j <= maxv;j += k)
{
f[j] = Math.max(f[j - 2 * k] + a[j], f[j - k]);
cnt = Math.max(cnt, f[j]);
}
res += cnt;
}
}
System.out.println(res);
}
}
PREV49 发现环
题目描述
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
输入格式
第一行包含一个整数N。
以下N行每行两个整数a和b，表示a和b之间有一条数据链接相连。
对于30%的数据，1 <= N <= 1000
对于100%的数据, 1 <= N <= 100000， 1 <= a, b <= N
输入保证合法。
输出格式
按从小到大的顺序输出在环路上的电脑的编号，中间由一个空格分隔。
样例输入
5
1 2
3 1
2 4
2 5
5 3
样例输出
1 2 3 5
算法分析
- 1、并查集判断是否存在环，枚举所有的边
a,b若a,b点不在同一集合，则合并a和b所在的两个集合，若在同一个集合则表示a和b连接一定会存在环，以将起点start赋值为a，终点end赋值为b - 2、从
start开始dfs，搜到end为止，记录从start到end中的路径，并对路径的点的编号进行排序
时间复杂度)
并查集接近，搜索
，排序
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 100010, M = N * 2;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static boolean[] st = new boolean[N];
static int[] ans = new int[N];
static int[] p = new int[N];
static int start,end;
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
static void dfs(int u,int father,int len)
{
if(u == end)
{
Arrays.sort(ans,0,len);
for(int i = 0;i < len;i ++)
{
if(i != len - 1) System.out.print(ans[i] + " ");
else System.out.print(ans[i]);
}
return;
}
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(j == father) continue;
ans[len] = j;
dfs(j,u,len + 1);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Arrays.fill(h, -1);
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = 0; i < n;i ++)
{
String[] s1 = br.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
add(a,b);
add(b,a);
int pa = find(a);
int pb = find(b);
if(pa != pb)
{
p[pa] = pb;
}
else
{
start = a;
end = b;
}
}
ans[0] = start;
dfs(start,end,1);
}
}
网友评论