【BFS】营救天使

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. 

Angel’s friends want to save Angel. Their task is: approach Angel. We assume that “approach Angel” is to get to the position where Angel stays. When there’s a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards. 

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.) 

继续阅读【BFS】营救天使

POJ1258【MST】Agri-Net

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 29613 Accepted: 11750

Description

Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. 
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. 
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. 
The distance between any two farms will not exceed 100,000. 

【思维题】 Disturbed People

思维题: 题目链接
思路:

会打扰别人的灯满足条件:

1.前一个灯是灭的。

2.前面的第二个灯和现在的灯是开着的。

arr.get(i-1).equals(0)&&arr.get(i).equals(1)&&(!arr.get(i-2).equals(0)))

注意:

如果满足了上述条件,需要把这个灯关掉再进行以后的判断

import java.math.BigInteger;
import java.util.*;
import java.lang.*;
public class Main {
  
  public static void main(String[] args) {
    Scanner cin=new Scanner(System.in);
    int n=cin.nextInt();
    List<Integer> arr=new ArrayList<Integer>();
    for(int i=0;i<n;i++) {
      arr.add(cin.nextInt());
    }
    int ans=0;
    for(int i=2;i<n;i++) {
      if(arr.get(i-1).equals(0)&&arr.get(i).equals(1)&&(!arr.get(i-2).equals(0))){
          arr.set(i, 0);
          ans++;
        }
    }
  System.out.println(ans);
  }	
}

 

 

【数学规律】A、 Frog Jumping

数学规律题: 题目链接

思路:分情况讨论,①跳奇数次s=(n-1)/2*(a-b)+a②跳偶数次s=(n)/2*(a-b)

注意:结果可能很大,用lld或者BigInteger解决

import java.math.BigInteger;
import java.util.Scanner;
import java.util.*;
import java.lang.*;
public class Main {
  
  public static void main(String[] args) {
    Scanner cin=new Scanner(System.in);
    int n=cin.nextInt();
    while(n--!=0)
    {
      int a=cin.nextInt(),b=cin.nextInt(),dis=a-b;
      BigInteger c=cin.nextBigInteger();
      if((c.mod(BigInteger.valueOf(2))).equals(BigInteger.ZERO))
      {
        c=c.divide(BigInteger.valueOf(2));
        System.out.println(c.multiply(BigInteger.valueOf(dis)));
      }
      
      else {
        c=c.subtract(BigInteger.ONE);
        c=c.divide(BigInteger.valueOf(2));
        c=c.multiply(BigInteger.valueOf(dis));
        System.out.println(c.add(BigInteger.valueOf(a)));
      }
      
    
    }
  
  }	
}

 

六度分离

六度分离

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12785    Accepted Submission(s): 5135

Problem Description

1967年,美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small world phenomenon)”的著名假说,大意是说,任何2个素不相识的人中间最多只隔着6个人,即只用6个人就可以将他们联系在一起,因此他的理论也被称为“六度分离”理论(six degrees of separation)。虽然米尔格兰姆的理论屡屡应验,一直也有很多社会学家对其兴趣浓厚,但是在30多年的时间里,它从来就没有得到过严谨的证明,只是一种带有传奇色彩的假说而已。 继续阅读六度分离