1 |
|
POJ 2079 Triangle (凸包上的点组成最大三角形)
1 | #include <iostream> |
POJ 3608 Bridge Across Islands (两凸包的距离)
1 | #include <iostream> |
ZOJ 1450 Minimal Circle (最小圆覆盖)
1 | #include <iostream> |
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的那个调度要计算的实在太多就写了个程序帮我跑了。
题目如下:
1 | #include <iostream> |
结果如下,有可能出现两种调度,具体怎样还不清楚是哪种
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 |
关于linux下Qt中使用OpenGL的问题汇总
最近在帮某陆老师搞一个小车的程序,虽然只是一小个模块,不过已经弄得吃不消了。
接触了一下Qt下的编程,然后好不容易才把OpenGL给调试了不会出错。
把遇到的问题汇总一下。
首先,安装Qt+openGL,官网上下+google基本不会有多大问题。(评判装成功就是你Qt能不能跑Qt中的样例程序,那个3d的hello Qt程序)
可以看这个:http://blog.csdn.net/silangquan/article/details/7845501
然后就开始蛋疼了。
找到了那个经典的Nehe的教程,然后就开始头文件找不到,什么reference出错,然后看Qt的样例又貌似没用到glut.h
之类的头文件。
网上的代码的看到的都是#include <GL/GLUT.h>
之类的形式,怎么都找不到,火起来就直接在ubuntu下搜glut.h
这个文件,然后发现竟然是小写的,改成小写就行了。大概如下:
1 | #include <GL/glut.h> |
之后又报错。原来是.pro
文件得加opengl才行,于是就把所有的都添加了
1 | QT += core gui opengl widgets |
还是不行,有好些函数全都是reference出错,又没有引用错误,到stackoverflow上查到了,还得在.pro
文件下加lib,如下
1 | LIBS+=-lglut -lGLU |
上面两个头文件所需要的。
这样子基本就行了。
还有一点要搞清的,opengl可绘图,Qt下也有绘图的库,搞混了就不好了,函数什么的都不一样。