本文共 6294 字，大约阅读时间需要 20 分钟。

A、迷路的牛牛

题目描述

• 牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。

输入

• 每个输入包含一个测试用例。 每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
  接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。

输出

• 输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。

样例输入 Copy

3LRR

样例输出 Copy

E

代码

链接：

import java.util.Scanner;public class Main {
   		public static void direction(int count_L,int count_R){
   		//左转的次数可以和右转的次数抵消，剩下的都是左转或者右转		int real = Math.abs(count_L-count_R);//剩下的		int temp = count_L > count_R ? 2:0;				if(real%4==0)			System.out.println("N");		else if(real%4==1+temp)			System.out.println("E");		else if(real%4==2)			System.out.println("S");		else if(real%4==3-temp)			System.out.println("W");	}	public static void main(String[] args) {
   		// TODO Auto-generated method stub		Scanner sc = new Scanner(System.in);		while(sc.hasNext()){
   			int n = sc.nextInt();			String str = sc.next();			int count_L = 0;			int count_R = 0;			for(int i=0;i

B、工作单位

题目描述

• 在某个城市中住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。
• 假设所有认识的人一定属于同一个单位，请计算该城市有多少个单位？

输入

• 第1行的第1个值表示总人数n，第2个值表示总信息数m；第2行开始为具体的认识关系信息

输出

• 单位的个数

样例输入 Copy

10 42 34 54 85 8

样例输出 Copy

7

链接：（嗯，就是并查集的代码）

代码

import java.util.Scanner;public class Main {
   	private static int[] parent = new int[200];	private static int[] rank = new int[200];	public static int count;	public static void init(int x){
   //初始化每个集合（树）,将每个元素作为一个集合		parent[x] = x;		rank[x] = 1;	}	public static int find_set(int x){
   //路径压缩，递归的将每个节点的根节点指向整棵树的根节点		if(parent[x]!=x)			return find_set(parent[x]);		return parent[x];	}	public static void union_set(int x,int y){
   		int a = find_set(x);		int b = find_set(y);		if(a==b)   //如果相等就代表在同一棵树，在同一个集合			return;		count--;//集合的个数少1				if(rank[a]<=rank[b]){
   //如果a的秩小于等于b的秩，则将a合并到b			parent[a] = b;			if(rank[a]==rank[b])//如果a,b的秩相等，则需要将b的秩加一				rank[b]++;		}		else			parent[b] = a;//如果b的秩小于a的秩，则将b合并到a	}	public static void main(String[] args) {
   		// TODO Auto-generated method stub		Scanner sc = new Scanner(System.in);		while(sc.hasNext()){
   			int n = sc.nextInt();//住着n个人			int m = sc.nextInt();//m条信息			for(int i=1;i<=n;i++)				init(i);			count = n;			for(int i=0;i

C、隔离14天

题目描述

• 如果实施更为严格的防控措施，一辆汽车上有一个确诊患者或者密切接触者，那么该汽车上所有的人都被认为是密切接触者，全部需要自行居家隔离或者集中隔离14天。

• 现在假定编号为0的乘客冠状病毒核酸检验呈阳性，请编写一个程序统计需隔离的总人数（包括编号为0的乘客）。

输入

• 第1行的第1个数字n表示总人数，第2个数字m表示汽车数量；从第2行开始，接下来的m行表示每辆汽车的司乘人员总人数和人员编号（人员编号是一个固定值，可以对应于我们的身份证号码），每一行的第1个数字k表示该汽车的司乘人员总数，接下来的k个数字表示每一个人的编号。

输出

• 需要被隔离的总人数。

样例输入 Copy

100 42 1 25 10 13 11 12 142 0 12 99 2

样例输出 Copy

4

链接：

代码

import java.util.Scanner;public class Main {
   	static int parent[] = new int[10000];//存放父节点	static int rank[] = new int[10000];//存放秩	static int count;		public static void init(int x){
   //初始化每个集合（树）,将每个元素作为一个集合		parent[x] = x;		rank[x] = 0;	}	public static int find_set(int x){
   //路径压缩，递归的将每个节点的根节点指向整棵树的根节点		if(parent[x]!=x)			parent[x] = find_set(parent[x]);		return parent[x];	}	public static void union_set(int x,int y){
   		int a = find_set(x);		int b = find_set(y);		if(a==b)   //如果相等就代表在同一棵树，在同一个集合			return;		if(rank[a]<=rank[b]){
   //如果a的秩小于等于b的秩，则将a合并到b			parent[a] = b;			if(rank[a]==rank[b])//如果a,b的秩相等，则需要将b的秩加一				rank[b]++;		}		else			parent[b] = a;//如果b的秩小于a的秩，则将b合并到a	}	public static void main(String[] args) {
   		// TODO Auto-generated method stub		Scanner sc = new Scanner(System.in);		while(sc.hasNext()){
   			int n = sc.nextInt();//总人数			int m = sc.nextInt();//汽车数量							for(int i=0;i<=n;i++)					init(i);//初始化，i<=0，避免为0时不能初始化								for(int i=0;i

D、最小生成树（Kruskal）

题目描述

• 编程实现Kruskal算法，求图的最小生成树(MST)的权重。

输入

• 每组数据分为两个部分，第一部分为图的点数n，和边数m, 第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

输出

• 最小生成树的权重。

样例输入 Copy

3 30 1 100 2 151 2 50

样例输出 Copy

25

链接：

代码

#include
   
    #define ll long longconst int N=1005;using namespace std;int p[N];//用来存放每个点的父节点int ran[N];//用来存放秩，用来优化，减少树的高度double sm;//用来存放结果，权重typedef struct{
   //定义每条边    int x,y;    double v;}Node;Node node[N];bool cmp(Node& a,Node& b){
   //升序    return a.v
    
     ran[b]){
               p[b]=a;            sm+=v;        }else{
               p[a]=b;            sm+=v;            if(ran[a]==ran[b])                ran[b]++;        }        return true;}int main(){
   	int n, m;    while(cin>>n>>m){
              sm=0;                for(int i=0;i
     
      >node[i].x>>node[i].y>>node[i].v;        }        sort(node,node+m,cmp);//排序        for(int j=0;j
     
    
   

E、搭建电路

Description

• 明明迷上了一个搭建电路的游戏。 在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。
  已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

Input

• 每组输入数据包含m+1行。 第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。

• 第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。

Output

• 每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。

Sample Input Copy

3 31 2 101 3 202 3 30

Sample Output Copy

50

代码

#include
   
    #define ll long longusing namespace std; const int MAXN=1010;int fa[MAXN];int ra[MAXN];ll ans; struct Edge{
       int x;    int y;    int cost;}; int cmp(const Edge &x,const Edge &y){
       return x.cost>y.cost;} int find_set(int x){
       if(x!=fa[x]){
           fa[x]=find_set(fa[x]);    }    return fa[x];} void union_set(int x,int y,int cost){
       x=find_set(x);    y=find_set(y);    if(x!=y) ans+=cost;    if(ra[x]>ra[y]) fa[y]=x;    else{
           fa[x]=y;        if(ra[x]==ra[y]){
               ra[y]++;        }    }} int main(){
       int n,m;    while(cin>>n>>m){
           Edge es[MAXN];        memset(fa,0,sizeof(fa));        memset(ra,0,sizeof(ra));        for(int i=1;i
    
     >es[i].x>>es[i].y>>es[i].cost;        }        sort(es,es+m,cmp);        ans=0;        if(m>=n-1){
               for(int i=0;i
    
   

F、单源最短路径问题

题目描述

• 编程实现Dijkstra算法，求一个有向加权图中，从源点出发到其他各个顶点的最短路径。

输入

• 第1行第1个值表示顶点个数，第2个值表示边个数；第2行开始为边（两个顶点，边的起点和终点）及权重。

输出

• 顶点0到每一个顶点的最短路径长度。

样例输入 Copy

5 70 1 100 3 300 4 1001 2 502 4 103 2 203 4 60

样例输出 Copy

0 10 50 30 60

链接 ：

代码

import java.util.Scanner;public class Main {
   	public static void dijkstra(int[][] G,int[] dist){
   		int n = dist.length;		boolean[] s = new boolean[n];//标记顶点放入或不放入		//初始化点0到各个定点的初始距离		for(int i=1;i
   
    < n;i++){
   //共扫描n-1次			int min = 1000000;			//寻找距离点0最近的点						for(int j=0;j
   

【今天和室友们浅谈了一下未来的规划，感觉未来挺迷茫的，但是周一还是要继续干学习呀！】

“我的图能不能尽量不修，如果非修的话，能不能别把我的皱纹都给我修平了，那可是我好不容易长出来的，年龄不是我的敌人，我的故事写在我的脸上，而这张脸就是对时间，对真实的致敬”

转载地址：http://rycki.baihongyu.com/