dp[i][0]表示从上面落到i的左边的横向最短距离
dp[i][0]表示从上面落到i的右边的横向最短距离
1 |
|
POJ 1043 What's In A Name? (判断二分图最大匹配的必须边)
1 |
|
POJ 2079 Triangle (凸包上的点组成最大三角形)
1 |
|
POJ 3608 Bridge Across Islands (两凸包的距离)
1 |
|
ZOJ 1450 Minimal Circle (最小圆覆盖)
1 |
|
HDU 1007 Quoit Design (分治法求最近点对)
最近点对可能在下面三种情况
[l,mid] [mid + 1,r] 以及 mid 的左右 d区域
1 | //hdu1007 |
POJ 1511 Invitation Cards (SPFA + JAVA)
尝试了一下Java写SPFA各种不习惯各种蛋疼，不过最终竟然以非常高的时间给过了``貌似是C的N倍了，没做java的IO优化，如果按照petr的那种IO的话应该会快点的
放上代码，觉得写的还不错
先MLE了，由于每次new的时候是new [maxn]这个maxn开的比较大，所以``
然后MLE是由于每个样例都new Graph了，开太多空间了
WA是因为SPFA函数类型是int其实超过int了得用long
RE是因为init的时候head数组初始化是1-M其实应该是1-N``
1 | import java.util.*; |
Gantt图 解释抢先式SJF调度算法
这是操作系统课上的作业，SJF的那个调度要计算的实在太多就写了个程序帮我跑了。
题目如下：
**进程 到达时间 执行时间**
**P1 0 10**
** P2 1 8**
** P3 2 2**
** P4 3 4**
** P5 4 8**
**画****Gantt****图说明使用****FCFS****、非抢先式****SJF****、抢先式****SJF****、****RR****（时间片＝****3****）调度算法进程调度情况。并分别求四种算法的平均周转时间，平均等待时间。平均权周转时间。**
用程序模拟了下实践过程
1 |
|
结果如下，有可能出现两种调度，具体怎样还不清楚是哪种
| Time:0 P1 | Time:0 P1 |
| Time:1 P1 | Time:1 P2 |
| Time:2 P2 | Time:2 P1 |
| Time:3 P3 | Time:3 P3 |
| Time:4 P3 | Time:4 P3 |
| Time:5 P4 | Time:5 P4 |
| Time:6 P4 | Time:6 P4 |
| Time:7 P4 | Time:7 P4 |
| Time:8 P4 | Time:8 P4 |
| Time:9 P2 | Time:9 P2 |
| Time:10 P2 | Time:10 P2 |
| Time:11 P2 | Time:11 P2 |
| Time:12 P2 | Time:12 P2 |
| Time:13 P2 | Time:13 P2 |
| Time:14 P2 | Time:14 P2 |
| Time:15 P2 | Time:15 P2 |
| Time:16 P1 | Time:16 P1 |
| Time:17 P1 | Time:17 P1 |
| Time:18 P1 | Time:18 P1 |
| Time:19 P1 | Time:19 P1 |
| Time:20 P1 | Time:20 P1 |
| Time:21 P1 | Time:21 P1 |
| Time:22 P1 | Time:22 P1 |
| Time:23 P1 | Time:23 P1 |
| Time:24 P5 | Time:24 P5 |
| Time:25 P5 | Time:25 P5 |
| Time:26 P5 | Time:26 P5 |
| Time:27 P5 | Time:27 P5 |
| Time:28 P5 | Time:28 P5 |
| Time:29 P5 | Time:29 P5 |
| Time:30 P5 | Time:30 P5 |
| Time:31 P5 | Time:31 P5 |
| P1 wait_time: 14 | P1 wait_time: 14 |
| P2 wait_time: 7 | P2 wait_time: 7 |
| P3 wait_time: 1 | P3 wait_time: 1 |
| P4 wait_time: 2 | P4 wait_time: 2 |
| P5 wait_time: 20 | P5 wait_time: 20 |
| P1 cycling_time: 24 | P1 cycling_time: 24 |
| P2 cycling_time: 15 | P2 cycling_time: 15 |
| P3 cycling_time: 3 | P3 cycling_time: 3 |
| P4 cycling_time: 6 | P4 cycling_time: 6 |
| P5 cycling_time: 28 | P5 cycling_time: 28 |
Java 约瑟夫环 链表实现
数据结构的编程实验，源码如下：
利用Java的泛型编程，以及链表类全部手动实现
// 循环链表
import java.io.*;
import java.util.*;
@SuppressWarnings("unchecked")
class LinkList>{
private Node head;
LinkList(){
head = null;
}
static class Node>{
T data;
Node next;
Node(T data, Node next){//中间节点使用此构造方法
this.data = data;
this.next = next;
}
Node(T data){ //头尾节点使用此构造方法
this.data = data;
this.next = this;
}
}
void addHead(T point){ //为链表增加头节点
head = new Node(point);
}
//void addTail(T point){ //为链表增加尾节点
// tail = new Node(point);
// head.next = tail;
//}
void insert(T point){
if (point.compareTo(head.data) < 0){
Node newNode = new Node(point,head);
head = newNode;
}else {
Node preNext = head;
while (preNext.next != head &&
point.compareTo(preNext.next.data) > 0){
preNext = preNext.next;
}
Node newNode = new Node(point,preNext.next);
preNext.next = newNode;
}
}
void show(){//打印链表
Node cur = head;
if (!isEmpty()){
System.out.print(cur.data + " ");
cur = cur.next;
while (cur != head){
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}else {
System.out.println("链表错误");
}
return ;
}
boolean isEmpty(){ //判断链表是否为空
if(head != null){
return false;
}
return true;
}
void delete(T data){ //删除某一节点
Node curr = head,prev = head;
boolean b = false;
//System.out.println(head.data);
if (curr.data.equals(data)){
while (prev.next != head) prev = prev.next;
prev.next = head.next;
head = prev;
b = true;
return ;
}
curr = head.next;
while(curr != head){
if(curr.data.equals(data)){
//判断是什么节点
if(curr == head){ //如果删除的是头节点
//System.out.println("delete head node");
head = curr.next;
b = true;
return;
}
if(curr.next == head){ //如果删除的是尾节点
//System.out.println("delete tail node");
prev.next = head;
b = true;
return;
}
else{ // 如果删除的是中间节点（即非头节点或非尾节点）
//System.out.println('n'+"delete center node");
prev.next = curr.next;
b = true;
return;
}
}
prev = curr;
curr = curr.next;
}
if(b == false){
System.out.println("没有这个数据" + data);
}
}
void solve(int n,int m){
Node preNext = head;
//T[] ans = new T[n + 1];
int ansnum = 0;
while (preNext.next != preNext){
int cnt = 1;
while (cnt < m){
preNext = preNext.next;
cnt ++;
}
System.out.print(preNext.data + " ");
//ans[ansnum ++] = preNext.data;
delete(preNext.data);
preNext = preNext.next;
}
//for (int i = 0; i < ansnum; i ++){
// System.out.print(ans[i] + " ");
//}
System.out.println(preNext.data);
}
}
public class ex1{
public static void main(String[] args){
LinkList mylist = new LinkList();
Scanner in = new Scanner(System.in);
while (in.hasNext()){
Integer n = in.nextInt();
Integer m = in.nextInt();
mylist.addHead(1);
for (int i = 2; i <= n; i ++){
mylist.insert(i);
}
System.out.println("原顺序");
mylist.show();
System.out.println("出列顺序");
mylist.solve(n,m);
}
}
}
/* 显示结果
* 30 6
* 原顺序
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
* 21 22 23 24 25 26 27 28 29 30
* 出列顺序
* 6 12 18 24 30 7 14 21 28 5 15 23 2 11 22 3 16 27 10
* 26 13 1 20 17 9 19 29 25 8 4
* 10 6
* 原顺序
* 1 2 3 4 5 6 7 8 9 10
* 出列顺序
* 6 2 9 7 5 8 1 10 4 3
* 8 2
* 原顺序
* 1 2 3 4 5 6 7 8
* 出列顺序
* 2 4 6 8 3 7 5 1
* 40 9
* 原顺序
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
* 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
* 出列顺序
* 9 18 27 36 5 15 25 35 6 17 29 40 12 24 38 11 26 1
* 16 32 8 28 4 23 7 31 14 39 30 20 13 10 19 22 37 33 34 21 2 3
* */
SGU 119 Magic Pairs (数学题)
网上找到一个写的不错的证明：
要证明一个东西：若
，则
是
的充要条件。
证明：
1)充分性：显然。
2)必要性：
若
，则
=> 若
，则
=> 
即 
上面的网址：http://d.ream.at/sgu-119/
自己想的时候并没有那么复杂
ax + by = kn，那么acx + by = kcn的，如果c > n 的话，就可以提取出一个anx + bny = knn出来约去，所以所有的可能就是枚举c 为 0到n - 1，每次(ac % n, bc % c)就是一组。
其实这样子还是有重复的，这个式子首先得除掉gcd(a,b,n)然后得出来的r作为c枚举的范围，不然范围比较大？反正减小范围，因为枚举0到n-1会有重复的ab组。
还有那个上面的移位再比较实在有点赞～少写点代码
1 | /* From: Lich_Amnesia |