2019 BUPT Winter Training #5 div2 题解

比赛链接

A - Friends (HDU 5305)

题意

给一张图有n个点,m条无向边。让你给每条边染成红色或黑色。使得每一个点相连的所有边中,红色边和黑色边的条数相等。

问有多少种染色方式。

解法

因为最多只有8个点,28条边。直接暴力搜索即可。只要代码别写(的像我一样)挫就行。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

class Solution {
public:
    Solution(int n_, int …
more ...

2019 BUPT Winter Training #3 div2 题解

写在前面

做为一个年近半百的中年人,还能厚着脸皮蹭学弟学妹们的训练赛。真是开心啊。

A - Constellation (CF 618C)

题意

在二维平面上给定一堆整数点,求任意一个三角形,使得三角形内以及其边上,不包含其它的点。

解法

我们先从一条边想起。选定任意一个点,从这个点引出的最短边上,一定不包含其它的点。(非常直观)

与这个思路类似,选定这条边之后,从这个边引出的面积最小的三角形,一定也不包含除三角形三点以外的其它点。

求三角形面积可以使用向量的叉积。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

#define print(x) cout << x << endl …
more ...

多线程编程初步

前言

非常不喜欢这种“X一峰”式的文章。但是为了伟大的教育事业,还是要写一点的。

线程安全的定义

无论操作系统如何调度线程,无论这些线程的执行顺序如何交织。一个函数(或类)在多个线程同时访问时能表现出正确的行为,而无需调用端代码进行额外的同步或协调操作。

划重点:

  • 无论如何调度
  • 无需额外的同步或协调操作
  • 总能表现出正确的行为

竞态条件(race condition)

竞态条件描述的是一个系统或者进程的输出依赖于不受控制的事件出现顺序或者出现时机。例如两个进程“同时读写”一块内存,其结果一定是不受控制的。

“同时读写”的定义包括:

  • 一读一写
  • 一写多读
  • 多写一读
  • 多写多读
  • 多写

也就是说,只要包含“并发”和“写操作”两个特性,就会出现竞态条件。而“多读”一般来说是安全的。

同时也要注意,这里的读与写是物理意义上的读写,而不是逻辑意义上的。有一些函数看起来只有读操作,但其内部仍然包括了对数据的修改,这里需要注意甄别。

Mutex - 互斥锁 …

more ...

开通了一个新栏目

博客开通了一个新栏目“For Beginners",想把之前写的一些比较适合于初学者的文章发到这里来。

实在是不喜欢博客里都是“XXX入门”、“XXX介绍”这类东西(我并没有针对谁),但是也不想白瞎我在教育事业上付出的心血。

大家勉为其难的看一下,有问题辛苦多做自我批评。

谢谢大家。

more ...