月度归档：2020年03月

第二届BJDCTF DreamerJack题目出题人题解

2条回复

下面是DreamerJack同学的出题人题解。

Programming: Strenuous_Huffman

本题的题解需要占个坑。主要是因为吧。。。题目描述里说的是真的。。这个是本人的数据结构作业，老师还没审查，直接把整套源码发出来我作业就不用交了，所以先占个坑。后续整套源码会发布到Github上。不过可以先说下本题的难点在哪里。其实这个题只是我数据结构作业题的一部分，只涉及解压缩。难度相对于压缩部分较小。正统解法是BitMap+Trie Tree解压。如果暴力一点也可以不用Trie。难度就在于BitMap的编写上。因为这个压缩的时候都是按位压缩的，最低的操作单位是比特。而咱们C/C++操作的最低单位都是按字节。所以要求代码编写者对位运算有比较深刻的认识才能够写得出来。

主要的解题思路如下。编写一个BitMap类，要支持从文件加载内容到内部数组和将内部数组存储到文件中，还要支持按位对数组的访问。然后按照压缩编码和原始编码的对应关系，逐个的将压缩后的比特信息翻译为原始信息并保存。

整套源码发布遥遥无期（看老师啥时候查完作业），想要源码的同学可持续关注本文章。
PS:要提醒的一点是：我自己开发的压缩算法经过测试，确实压缩效果较差。本源码仅供教学用途使用。不要异想天开真的拿这玩意去压缩东西。。。

2020.05.09：此代码已开源：https://github.com/bjrjk/JackZIPPacker

Reverse: 8086 ASM

为什么想要出这道题目呢？我校最近正在学习8086汇编，因此出这道题目。
源码如下：

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
DATAS SEGMENT
    str1 DB 5dH,55H,5bH,64H,75H,7eH,7cH,74H
    DB 40H,7bH,7aH,40H,77H,6aH,2eH,7dH,2eH
    DB 7eH,71H,40H,67H,6aH,7aH,7bH,7aH,40H
    DB 77H,7aH,71H,57H,7eH,2fH,62H,59
DATAS ENDS

STACKS SEGMENT
STACKS ENDS

CODES SEGMENT
    ASSUME CS:CODES,DS:DATAS,SS:STACKS
loc:
    jmp loc
    mov CX,34
    lea BX,str1
   
lop:
    mov DI,CX
    dec DI
    xor BYTE PTR [BX][DI],31
    loop lop
    lea DX,str1
    mov AH,09H
    int 21H
    ret
START:
    MOV AX,DATAS
    MOV DS,AX
    call loc
    MOV AH,4CH
    INT 21H
CODES ENDS
    END START

本题其实很简单，str1存放的是一个MSDOS格式的以$结尾的经过异或加密的字符串。汇编代码就是把这玩意解密了一下然后syscall输出。jmp loc的死循环就是用来干扰人的。如果想要不劳而获放到DOS里直接跑会死循环。放到IDA里看的话，IDA会把lop下面那段代码当作是数据。需要把他们强转一下成代码才行。本题也可以用调试器手动改EIP执行。顺便宣传一下自己做的8086调试器套件：DOSBox-8086Assembly
PS:我汇编学的还行是真的^v^，死循环是我故意写的^v^

Misc: A Beautiful Picture

很简单的一个png隐写。说实话，图画的不怎么好看。。一看这图片长1000，高900，有没有感觉有点不对劲呢？用010HexEditor，直接把png图片高度改成1000，flag就出来了。。

更新：题目复现地址： https://buuoj.cn/
20200510更新：本人CTFd已下线。
题目下载链接：https://renjikai.com/wp-content/uploads/2020/03/BJD2_DreamerJack.zip

洛谷 P3369 【模板】普通平衡树

发表评论

手写Splay成功。庆祝能写出来的第一个BBST！
代码如下：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<iostream>
#include<cassert>
using namespace std;
class Splay {
private:
    struct Node {
        int v; //值
        Node* f, * l, * r; //父，左孩子，右孩子
        int cnts; //本子树下包含自身的所有**元素**数目
        int rep; //该值重复了多少次
        Node(int v, Node* f) :v(v), f(f), l(NULL), r(NULL), cnts(1), rep(1) {}
    };
    Node* _root;
#define root _root->r
    void update(Node* p) { //更新cnts值
        p->cnts = p->rep;
        if (p->l)p->cnts += p->l->cnts;
        if (p->r)p->cnts += p->r->cnts;
    }
    bool identify(Node* s, Node* f) { //确定本节点是左孩子还是右孩子，左孩子false，右孩子true
        return !f || s == f->r;
    }
    void connect(Node* s, Node* f, bool r) { //儿子地址,父亲地址,连接到左儿子还是右儿子
        if (f)(r ? f->r : f->l) = s; //父亲更新新儿子
        if (s)s->f = f; //儿子更新新父亲
    }
    void rotate(Node* s) { //儿子节点的旋转
        Node* f = s->f, * gf = s->f->f;
        if (!identify(s, f)) { //左孩子
            connect(s->r, f, false);
            connect(f, s, true);
            connect(s, gf, identify(f, gf));
        }
        else { //右孩子
            connect(s->l, f, true);
            connect(f, s, false);
            connect(s, gf, identify(f, gf));
        }
        update(f);
        update(s);
    }
    void splay(Node* s, Node* e) { //伸展操作，将节点s旋转到节点e所在的位置
        e = e->f;
        while (s->f != e) {
            Node* f = s->f;
            if (f->f == e)rotate(s); //s是e的直系儿子，只需做单旋
            else if (identify(f, f->f) == identify(s, f)) { //Zig-Zig或Zag-Zag，需要先旋父亲节点，再旋儿子节点
                rotate(f);
                rotate(s);
            }
            else { //Zig-Zag或Zag-Zig
                rotate(s);
                rotate(s);
            }
        }
    }

public:
    Splay() {
        _root = new Node(0, NULL);
    }
    ~Splay() {
        delete _root;
    }
    Node* find(int v) {
        Node* cur = root;
        if (!cur)return NULL;
        while (1) {
            if (cur->v == v) break;
            Node* next = v < cur->v ? cur->l : cur->r;
            if (!next)break;
            cur = next;
        }
        splay(cur, root);
        root = cur;
        if (cur->v == v)return cur;
        else return NULL;
    }
    void del(int v) {
        Node* cur = find(v);
        if (!cur)return;
        if (cur->rep > 1) { //节点个数出现多于1次
            cur->rep--;
            cur->cnts--;
            return;
        }
        if (!cur->l && !cur->r) { //删除最后一个仅剩的节点
            root = NULL;
        }
        else if (!cur->l) { //无左子树时直接把右子树拼到根
            root = cur->r;
            root->f = _root;
        }
        else { //有左子树时，把左子树的最大值旋到根的左子，将根的右子放到根的左子的右子，删根后补左子树
            Node* l = cur->l;
            while (l->r)l = l->r;
            splay(l, cur->l);
            Node* r = cur->r;
            connect(r, l, true);
            root = l;
            root->f = _root;
            update(l);
        }
        delete cur;
    }
    void insert(int v) {
        Node* cur = find(v);
        if (!root) { //特判空树
            root = new Node(v, _root);
            return;
        }
        if (cur && cur->v == v) { //元素存在，直接把次数+1
            cur->rep++;
            cur->cnts++;
            return;
        }
        Node* newNode = new Node(v, _root);
        if (root->v < v) { //将v接入右侧
            connect(root, newNode, false);
            connect(root->r, newNode, true);
            root->r = NULL;
        }
        else { //将v接入左侧
            connect(root, newNode, true);
            connect(root->l, newNode, false);
            root->l = NULL;
        }
        update(root);
        update(newNode);
        root = newNode;
        newNode->f = _root;
    }
    int rank(int v) {
        Node* cur = find(v);
        if (!cur)return -1;
        int lCnts = cur->l ? cur->l->cnts : 0;
        return lCnts + 1;
    }
    int atrank(int rank) {
        Node* cur = root;
        while (cur) {
            int lCnts = cur->l ? cur->l->cnts : 0;
            if (lCnts < rank && rank <= lCnts + cur->rep) {
                splay(cur, root);
                return cur->v;
            }
            if (rank <= lCnts)cur = cur->l;
            else {
                rank -= lCnts + cur->rep;
                cur = cur->r;
            }
        }
        return -1;
    }
    int upper(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v <= v)return atrank(lCnts + root->rep + 1);
        return root->v;
    }
    int lower(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v >= v)return atrank(lCnts);
        return root->v;
    }
#undef root
};
int main() {
    Splay splay;
    int n;
    cin >> n;
    while (n--) {
        int op1, op2;
        cin >> op1 >> op2;
        if (op1 == 1) {
            splay.insert(op2);
        }
        else if (op1 == 2) {
            splay.del(op2);
        }
        else if (op1 == 3) {
            cout << splay.rank(op2) << endl;
        }
        else if (op1 == 4) {
            cout << splay.atrank(op2) << endl;
        }
        else if (op1 == 5) {
            cout << splay.lower(op2) << endl;
        }
        else if (op1 == 6) {
            cout << splay.upper(op2) << endl;
        }
    }
}

参考资料：
https://www.luogu.com.cn/blog/user19027/solution-p3369
非常感谢rentenglong同学

CTF RSA 高精度整数开根 解一元二次方程

发表评论

做BJDCTF第二届出的RSA题目，需要解高精度整数的一元二次方程，参考着网上写了个Python脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def HPSqrt(a,b): #高精度开整数根，a为开几次根，b为要开根的数
    l=0
    r=1
    while(r**a<=b):
        l=r
        r=r*2  
    while(l+1<r):  
        mid=(l+r)//2
        if (mid**a<=b): l=mid
        else: r=mid
    if (l**a<=b): return l
    else: return r

def HPSolve12(a,b,c): #高精度解整数一元二次方程，解RSA用
    key=HPSqrt(2,b*b-4*a*c)
    return ((-b+key)//2//a,(-b-key)//2//a)

a=1
b=-2
c=1
print(HPSolve12(a,b,c)) #将方程整理成ax^2+bx+c=0的形式代入即可

参考资料：高精度Python开根 https://www.luogu.com.cn/blog/wjy666/solution-p2293

Dockerfile编写使用cron后出现无法执行定时任务的解决方法

发表评论

最近给自己的项目编写一个Dockerfile，这个项目需要用到Cron定时任务。在Dockerfile里apt安装cron后不论如何使用RUN命令启动cron都无效（包括使用service和直接执行cron命令）。后来将所有任务集成在了一个sh脚本里解决了问题。举例，我要运行的任务是apache。那么我可以写一个脚本startup.sh，把Dockerfile的ENTRYPOINT设为这个脚本。

1
2
3
#!/bin/sh
cron
apache2-foreground

原因是什么呢？

方法1和方法2不能成功，是因为docker只是一个进程隔离的沙箱环境，并不是真正的虚拟机。而service xxx start 和systemctl start xxx 分别是upstart和systemd这两个/sbin/init进程的替代者的服务管理命令。而upstart和systemd都要求系统必须是物理机或虚拟机，并不支持作为container的init进程。方法3存在问题是因为，在正常的系统中，init进程永远占用PID=1的位置，回收僵尸进程、处理未处理的信号等都是由init进程帮我们完成的，一个子进程如果失去了父进程，也会由init进程接管。但是在container中，init进程并不存在，PID=1的进程是我们在Dockerfile中定义的Entrypoint或最后一个CMD指定的命令。

参考资料：https://www.asuri.org/2018/08/25/run-multi-service-in-one-container/

而直接执行cron命令为何失败呢？我推测，Dockerfile设计RUN命令的本义是对文件系统进行一定的操作。而非监控Container在启动时需要开启什么进程。所以一定要把所有需要运行的程序都写到一个shell脚本里并且把其设为入口点才行。

CMU 15213 Bomb Lab Reverse

发表评论

被foobar科学院的朋友们拉进坑。
这些逆向题，都算还比较简单的，至少比AdWorld的有些题简单。。
主要使用IDA F5解决。里面的符号名字需配合我的加好注释的i64食用。
Phase_1：显然输入Border relations with Canada have never been better.即可。
Phase_2：程序逻辑是 读入6个数，要求每个数是前面一个数的2倍。且第一个数必须是一。故填入1 2 4 8 16 32。
Phase_3：读入两个数，有一个大Switch，只要照着Switch里的对应关系填好就行。我选0 207.
Phase_4：读入两个数，第二个数没用，但是要求小于14，第一个数调用一个递归函数。懒得看这个递归，暴力跑一下，填0即可。故输入0 0.
Phase_5：首先要求字符串长度是6.然后依次取字符串每个字符的低8位，到长为0xF的字符数组中去置换字符。拼出来是flyers即胜利。一种可能的解是ionefg。
Phase_6：这关是最麻烦的。得一点一点看。注意符号里留下的暗示，node1~node6，其实这些东西代表单链表节点，前8个字节是long long的value，后8个字节是node* 的ptr。把数都读入到arr1[6]里面。第一个大循环要求每个数小于等于6，且数组里每个数不重复。第二个循环使数组里每个数x都变为7-x。第三个循环在栈上开了空间node* v17[6]，用来存放单链表节点地址。根据arr1[i]的值来确定v17[i]该存入那个地址。即v17[i]=&node[arr1[i]]。从这里可以猜测判断，前面人输入的数不能是0.必须是1-6.第4个循环最复杂。他的实际作用是根据v17数组的前后顺序更改Node1到Node6这几个节点的连接关系。可配合i64代码自行思考。第5个循环是约束条件，要求链表前面的节点的LODWORD（即Longlong的低32bit signed int）要大于后一个节点的。由此查看Node的内存布局。按照LODWORD排序，应该是3 4 5 6 1 2.再用7去减，就得4 3 2 1 6 5.输入即可通关。

CMU链接：http://csapp.cs.cmu.edu/3e/labs.html
IDA i64下载链接、源程序下载链接：bomb

Vultr VPS BGP配置双接入点Choopa + HE

发表评论

在BGP的申请方面，下面的参考资料都说得很清楚了。但是对于两个Peer的接入网上的文章都没有说清楚。经过一番摸索。我把自己的bird配置文件贴上来供参考。可以实现Choopa和HE线路的共同运作。
Bird6.conf:

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
router id **Vultr分配的IPV4地址**;
protocol device{
scan time 5;
}
protocol bgp Vultr {
local as **你的AS号，不带AS两个字母**;
source address **Vultr分配的IPV6地址**;
neighbor **Vultr分配的IPV6网关** as 64515;
import none;
export all;
graceful restart on;
multihop 2;
password "**BGP密码**";
}
protocol bgp HE {
local as **你的AS号，不带AS两个字母**;
source address **HE分配的隧道IPV6地址**;
neighbor **HE分配的隧道IPV6网关** as 6939;
import none;
export all;
graceful restart on;
multihop 2;
}
protocol static {
route **你的IPV6宣告网段** via **Vultr分配的IPV6地址**;
}
protocol direct {
interface "**自定义网卡名**";
import all;
}

HE.NET隧道网卡linux配置命令：

1
2
3
4
ifconfig sit0 up
ifconfig sit0 inet6 tunnel ::**HE.NET IPv4接入服务器地址**
ifconfig sit1 up
ifconfig sit1 inet6 add **HE分配的隧道IPv6地址**/64

Vultr网卡Linux配置命令：

1
2
3
ip link add dev **自定义网卡名** type dummy
ip link set **自定义网卡名** up
ip addr add dev **自定义网卡名** **你的IPV6宣告网段**

参考资料：
https://blog.yuzu.im/marchives/133
https://blog.ni-co.moe/public/560.html
https://blog.ni-co.moe/public/563.html

洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

发表评论

开心啦！ THUOJ不过不知道是什么鬼畜精度问题，不管了^v^
板子好用^v^

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
struct point {
    double x, y;
    long long id;
    point() :x(0), y(0) {}
    bool operator ==(const point& p) const {
        return x == p.x && y == p.y;
    }
}PP; //PP: Polar Point
vector<point> points;
double area2(point p, point q, point s) {
    /*
    |p.x p.y 1|
    |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)
    |s.x s.y 1|
    */
    return p.x * q.y - s.x * q.y
        + q.x * s.y - q.x * p.y
        + s.x * p.y - p.x * s.y;
}
bool toLeftTest(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) > 0;
}
bool toLeftTest2(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) >= 0;
}
bool cmp(const point& p1, const point& p2) { // Sort according to polar angle
    return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2);
}
point LTL(vector<point>& points) { //Lowest then leftmost
    point ltl = points[0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)
            ltl = points[i];
    }
    return ltl;
}
vector<point> grahamScan() {
    PP = LTL(points);
    sort(points.begin(), points.end(), cmp);
    vector<point> S, T;
    S.push_back(points[0]); S.push_back(points[1]);
    for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);
    while (!T.empty()) {
        if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {
            S.push_back(T[T.size() - 1]);
            T.pop_back();
        }
        else S.pop_back();
    }
    return S;
}
double dist(point x, point y) {
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int main() {
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        point tmp;
        cin >> tmp.x >> tmp.y;
        tmp.id = i;
        points.push_back(tmp);
    }
    vector<point> result;
    if (points.size() > 2)result = grahamScan();
    else result = points;
    double res = 0;
    for (int i = 0; i < result.size(); i++) {
        res += dist(result[i % result.size()], result[(i + 1) % result.size()]);
    }
    cout.setf(ios::fixed);
    cout << setprecision(2) << res;
}

CG2017 PA1-1 Convex Hull (凸包)

发表评论

开始接触计算几何啦！！！

CG2017 PA1-1 Convex Hull (凸包)

Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

经过了第一章的学习，想必你对于凸包的认识已经非常深刻。是的，凸包是计算几何的核心问题，也是一种基础性的几何结构。因此你的第一项编程任务，就是来实现这样的一个算法。

具体地，对于平面上的任意一组点，请构造出对应的凸包，并在经过编码转换之后输出所有极点的信息。

Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

第一行是一个正整数首行为一个正整数n > 0，即输入点的总数。

随后n行中的第k行给出第k个点：

pk = (xk, yk), k = 1, 2, …, n

这里，xk与yk均为整数，且二者之间以空格分隔。

Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

若 { s1, s2, …, sh } 为所有极点的编号, h ≤ n，则作为你的解答，请输出以下整数：

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

Sample Input (输入样例)


10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8

Sample Output (输出样例)


7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)

Limitation (限制)

  • 3 ≤ n ≤ 10^5
  • Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
  • All points on extreme edges are regarded as extreme points and hence should be included in your solution.
  • Time Limit: 2 sec
  • Space Limit: 512 MB
  • 3 ≤ n ≤ 10^5
  • 所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
  • 极边上的所有点均被视作极点，故在输出时亦不得遗漏
  • 时间限制：2 sec
  • 空间限制：512 MB

Hint (提示)

Use the CH algorithms presented in the lectures.

课程中讲解过的凸包算法

 

分数：92.5
使用Graham Scan算法。凸包板子题。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
struct point {
    long long x, y, id;
    point() :x(0), y(0) {}
    point(long long x, long long y) :x(x), y(y) {}
    bool operator ==(const point& p) const {
        return x == p.x && y == p.y;
    }
}PP; //PP: Polar Point
vector<point> points;
long long area2(point p, point q, point s) {
    /*
    |p.x p.y 1|
    |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)
    |s.x s.y 1|
    */
    return p.x * q.y - s.x * q.y
        + q.x * s.y - q.x * p.y
        + s.x * p.y - p.x * s.y;
}
bool toLeftTest(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) > 0;
}
bool toLeftTest2(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) >= 0;
}
bool cmp(const point& p1, const point& p2) { // Sort according to polar angle
    return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2);
}
point LTL(vector<point>& points) { //Lowest then leftmost
    point ltl = points[0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)
            ltl = points[i];
    }
    return ltl;
}
vector<point> grahamScan() {
    PP = LTL(points);
    sort(points.begin(), points.end(), cmp);
    vector<point> S, T;
    S.push_back(points[0]); S.push_back(points[1]);
    for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);
    while (!T.empty()) {
        if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {
            S.push_back(T[T.size() - 1]);
            T.pop_back();
        }
        else S.pop_back();
    }
    return S;
}
int main() {
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        point tmp;
        cin >> tmp.x >> tmp.y;
        tmp.id = i;
        points.push_back(tmp);
    }
    vector<point> result;
    if (points.size() > 2)result = grahamScan();
    else result = points;
    long long res = 1;
    for (int i = 0; i < result.size(); i++) {
        //cout << result[i].id << endl;//debug
        res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);
    }
    res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);
    cout << res;
}

DOSBox-8086Assembly

4条回复

最近我们学校在上8086汇编课程，需要写汇编程序。而Masm套件自带的debug调试程序是命令行的，不很好用。于是我在网上搜索了一下好用的8086汇编调试器，搜到了Turbo Debugger，经过试用。发现非常好用，带有GUI界面，非常人性化。于是就想把它和DOSBox集成到一起，制作一个输入源代码文件，即可自动开始调试的程序。经过努力，我做出了这个套件。我把它称作：DOSBox-8086Assembly。

继续阅读 →