Shen Huang's Blog
0%

Posted on Edited on

想了半天愣是搞不定怎么写

4

2 3 4 3

为什么这样可以用单调队列搞呢维护一个不降的序列

把2 3 4 分别入栈，然后遇到3 了，发现不能继续做了，于是先算以最上面4的那个数作为区域最小的那个数能不能实现tmp < ans，之后把4弹出

然后看3发现不小了就继续。

之后遇到-1 数组最后值为-1，那么就是说一直弹栈到最后，把每个在栈的数作为最小的数来进行算tmp

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
/* POJ 2796 单调队列 维护一个单调不降的序列，然后每次遇到比top小的数时进行
 * 出栈操作并且把值更新下
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
ll st[100100],a[100100],sum[100100];
int main(){
	int n;

	while (~scanf("%d", &n)){
		memset(a,0,sizeof(a));
		memset(st,0,sizeof(st));
		for (int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
			sum[i] += sum[i-1] + a[i];
		}
		int top = 0;
		a[n + 1] = -1;
		ll tmp,ans = -1;
		int l , r;
		for (int i = 1; i <= n + 1; i++){
			while (top != 0 && a[st[top]] > a[i]){
				tmp = a[st[top]] * (sum[i-1] - sum[st[top - 1]]);
				if (tmp > ans){
					ans = tmp;
					l = st[top-1] + 1;
					r = i - 1;
				}
				top --;
			}
			top ++;
			st[top] = i;
		}
		printf("%lldn%d %dn",ans,l,r);
	}
	return 0;
}

Posted on Edited on

原网址：https://www.chenyajun.com/2010/06/23/5078

前面几节谈到的游戏可以用图理论来描述，考虑一个图 G = (X, F)；其中 X 是顶点，也是先前游戏中可能的态势。F 是一个函数，对于 X 中的任意一个 x，F(x) 的值都出现在 X 中，对于 X 的一个元素 x，F(x) 的含义是一个玩家从 x 出发可以移动到的局势。

对于一个两人的类似前面的游戏而言，可以在一个如此这样的图上进行博弈，首先指定一个起始点 x0，并使用下面的规则：

（1）玩家 I 从 x0 开始首先移动；

（2）玩家交替移动；

（3）在 x 态势时，玩家要将态势转移到另一个态势 y，其中 y 是 F(x) 中的元素。

为简单起见，假定图中不存在环，元素个数为 n，其中最长的一条路径也不超过 n。那么对于前面我们分析的减法游戏，其中 S = {1, 2, 3}。假定游戏中指定对 n 进行减法操作。X = {0, 1, 2…, n} 是图顶点。F(0) 是空集。F(1) = {0}，F(2) = {0, 1}。 对于 2<= k <= n，F(k) = {k -3, k -2, k -1}。

因此这个游戏的图大致如下。其中 n = 10。

1 “3-1”)

边的方向代表了可能的移动。

SG 函数

这种图可以通过分析 SG 函数来分析。

所谓图 (X, F) 的 SG 函数 g 是定义在 X 上的一个函数。

g(x) = min{n ≥ 0 : n ≠ g(y) for y ∈ F(x)}。换句话说，g(x) ：是一个非负整数；尽可能的小；不出现在 x 的后缀节点的 g 函数取值中。

这是一个递归定义。但可以通过倒推来取得节点的值。对于终点 x，g(x) = 0，因为 F(x) 是空集。

如果一个态势的 g(x) = 0 那么它就是 P 态，否则就是 N 态。

下面的图描述了 g 函数的求解过程，在开始所有的顶点本是没有数字的。在开始，所有的终点 SG 函数值为 0，一共有 4 个终点，它们位于图的左边和下边。对于点 a，它的后缀 SG 函数为 0，那么它自身的 SG 值就是 1，它是所有没有出现在 a 后缀节点的 SG 值的最小值。那么 b 的 SG 值就是 2，因为它有 2 个后缀，一个是 a，令一个是终点，它们的 SG 值分别是 1 和 0，那么它的 SG 值就是 2。那么 c 的 SG 值就是 0，因为 c 只有一个后缀 a，而 a 的 SG 值为 1，那么没有出现在 c 后缀节点的 SG 值的最小值就是 0。

对于 S = {1, 2, 3} 的减法游戏其 SG 函数是多少？

终点 0， SG 值为 0, 1 只能移到 0，而 g(0) = 0，所以 g(1) = 1，同样，2 可以移动到 0 和 1，而 g(0) = 0，g(1) = 1，故 g(2) = 2，3 可以移动到 0，1，2 ，它们各自的 g(0) = 0, g(1) = 1, g(2) = 2，因此 g(3) = 3，但是对于 4 只能移动到 1，2，3，其各自的 SG 值为 1,2,3，故 g(4) = 0。

容易发现 g(x) = x( mod 4)。

考虑一种移石子游戏：每次必须移走至少剩余的一半，我们可以如下计算 SG 函数：

x     0 1 2 3 4 5 6 7 8 9 10 11 12 . . .
g(x)     0 1 2 2 3 3 3 3 4 4 4  4  4  . . .

g(x) = min{k: power(2,k) > x}。

Posted on Edited on

第一次写这样的项目，用VS的cpp写的比较简单，先放一个下载文件

 http://pan.baidu.com/share/link?shareid=694816596&uk=168774939 

要添加一个easyx的库，非常不安全，以后不这样的，这次敢时间



首先遇到了加载过多dll的问题，可以写出一个.reg文件里面内容是如下，再添加进注册表就行了

Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINESOFTWAREMicrosoftWindowsCurrentVersionExplorer]
"AlwaysUnloadDLL"="1"
VS出现了unsafe，貌似是error C4996，你用了getch什么的就不让你编译通过，可以去网上搜一个解决方案，getch的问题改成_getch就可以编译通过了，见如下

<span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; ">菜单： </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; "> </span><wbr style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; " /><span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; ">项目 | 属性 | 配置属性 | C/C++ | 命令行 | 附加选项（其他选项）,加入【/D"_CRT_SECURE_NO_DEPRECATE" 】(注：加入中括号中完整的内容)</span>

<span style="color: rgb(0, 0, 0); font-family: Arial; font-size: 14px; line-height: 26px; ">或者_CRT_SECURE_NO_WARNINGS，不过不建议，这样就全部都没了</span>

Posted on Edited on 
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
/* 博弈论题目可以用寻找必败状态的方法解决。
 * 第一个必败状态是2001.11.04。由此可以推出其他任何时间的状态。
 * 对于除2001.11.04外的其他任何时间，
 * present状态是由能移动到的下两个next状态决定的
 * （当然有些时间只有一个next状态），
 * 比如1924.12.19的状态是由1924.12.20和1925.01.19两个状态决定。
 * 如果两个next状态中有一个必败状态，则present状态为必胜状态；
 * 如果两个next状态都为必胜状态，则present状态为必败状态。
 *
 * 对于2001年11月的那4天，状态都是交替胜负的。1和3号必胜，2和4号必败。
 * 现在考虑10月份，5-31号只有一个next状态，推算可知奇数号状态为必败，
 * 偶数号状态为必胜。1-4号状态有两个next状态，推算可知也是奇数号状态为必败，
 * 偶数号状态为必胜。也就是说整个10月份奇数号状态为必败，偶数号状态为必胜。
 *
 * 由此我们可以推测如果每个月都是31天的话，那么每天的状态都是相反的，
 * 而且相邻的两个月的同一天状态也是相反的。即奇数月的奇数号状态为必胜，
 * 偶数号状态为必败；偶数月偶数号状态为必胜，奇数号状态为必败。
 * 从数学上说，就是月与号和为偶数的天状态为必胜，为奇数的天状态为必败。
 * 显然这个是成立的，可以自己推算一下。
 *
 * 接下来要考虑特殊情况，那几个只有30天的月份。
 * 有30号的有4，6，9，11这四个月。对于04.30，next状态有05.01和05.30，
 * 显然两个next状态是相反的，所以04.30的状态是必胜的。
 * 所以04.30的状态情况符合上面那个结论。06.30同样如此。
 * 对于09.30，next状态有10.01和10.30，同样10.01和10.30的状态是相反的，
 * 所以09.30的状态为必胜，这不符合上面的结论。
 * 但是我们可以证明这只是一种特殊情况，不影响整个结论。
 * 按照原来的结论，九月份的奇数号状态为必胜，偶数号状态为必败。
 * 现在30号的状态变化了，如果我们能证明29号的状态不会因此发生变化，
 * 那么特殊情况就只局限于30号了。
 * 09.29号的next状态有09.30和10.29，10.29的状态为必败，
 * 所以09.29的状态为必胜，还是符合原来的结论。11.30同样如此。
 *
 * 最后考虑特殊的2月份。如果是闰年的29天，效果和31天一个月是一样的
 * （只要是奇数都一样，哪怕一个月只有一天）。
 * 对于非闰年，2月只有28天。其实28天也等同于30天的情况，
 * 推算可知02.28和04.30，06.30一样，不影响整个结论。
 *
 * 总结，月与号和为偶数的天状态为必胜，为奇数的天状态为必败。
 * 特殊情况为09.30和11.30，这两天的状态也为必胜。
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
int main(){
	int t,year,mon,day;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d",&year,&mon,&day);
		if ((mon == 9 && day == 30) || (mon == 11 && day == 30)) printf("YESn"); 
		else if ((mon + day) & 1) printf("NOn");
		else printf("YESn");
	}
	return 0;
}

Posted on Edited on

做VS项目的时候， 据说因为我的程序出BUG了，就导致VS莫名其妙出现加载很多DLL，编译很久都不显示界面，而且还非常卡

最后找到了一个解决方案。

可以通过修改添加一个注册表文件，使得VS不会出现加载过多DLL的情况

新建一个文本文件，用vim或者sublime打开添加如下

1
2
3
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINESOFTWAREMicrosoftWindowsCurrentVersionExplorer]
"AlwaysUnloadDLL"="1"

然后保存成*******.reg文件就可以了**是你随机文件名

然后打开就行了

Posted on Edited on

外接显示器可能无法被Ubuntu检测，显示是未知然后，分辨率最高也就1024 * 768 。

可以通过下面方法修改

一.只是本次需要，关机之后回复原来状态

（1）首先使用xrandr命令查看能检测到的分辨率

Screen 0: minimum 320 x 200, current 3286 x 1080, maximum 8192 x 8192
LVDS1 connected 1366x768+0+312 (normal left inverted right x axis y axis) 344mm x 194mm
   1366x768       60.0*+   40.1  
   1360x768       59.8     60.0  
   1024x768       60.0  
   800x600        60.3     56.2  
   640x480        59.9  
VGA1 connected 1920x1080+1366+0 (normal left inverted right x axis y axis) 0mm x 0mm
   1024x768       60.0  
   800x600        60.3     56.2  
   848x480        60.0  
   640x480        59.9  


可以看到目前有两个一个LVDS1是我笔记本的，一个VGA1是我外接的显示器

（2）然后需要用xrandr命令新增加显示模式，用cvt获得显示模式

cvt X Y H 
X表示宽度，Y表示高度，H表示显示器的HZ这个可以查看你的显示器的参数，我是1920*1080 60hz的，命令为

cvt 1920 1080 60
得到

# 1920x1080 59.96 Hz (CVT 2.07M9) hsync: 67.16 kHz; pclk: 173.00 MHz
Modeline "1920x1080_60.00"  173.00  1920 2048 2248 2576  1080 1083 1088 1120 -hsync +vsync

（3）之后把cvt得到的模式用xrandr命令添加，终端输入（具体按照你自己得到的模式输入）

xrandr --newmode "1920x1080_60.00"  173.00  1920 2048 2248 2576  1080 1083 1088 1120 -hsync +vsync
xrandr --addmode VGA1 "1920x1080_60.00"
xrandr --output VGA1 --mode 1920x1080_60.00
xrandr --output VGA1 --right-of LVDS1
（4）这样直接就可以显示出效果了



二，每次开机都能这样配置的方法

（1）在你自己的主文件夹形成一个display.sh的文件里面输入

#!/bin/bash
xrandr --newmode "1920x1080_60.00"  173.00  1920 2048 2248 2576  1080 1083 1088 1120 -hsync +vsync;
xrandr --addmode VGA1 "1920x1080_60.00";
xrandr --output VGA1 --mode 1920x1080_60.00;
xrandr --output VGA1 --right-of LVDS1;
（2）打开终端输入

cd /etc/
sudo gedit profile

（3）在打开的profile文件里加一句

~/display.sh
（4）重启看看效果

Posted on Edited on

随机选取一个点，再取一个步长，朝这个方向走，如果新位置到各点距离比原来小，则走过去。直到走不动为止，再缩小步长。直到步长小于题目精度。

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
/* poj 2420 多边形费马点 用模拟退火法 逼近
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 120
struct point{
	double x,y;
	point(){
		x = 0;y = 0;
	}
	point(double a,double b){
		x = a; y = b;
	}
}p[maxn];
inline double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double format(point *p,int n,point &pt){
	point u,v,tmp;
	double step = 0,curlen = 0.0,explen,minlen;
	int i, j, k, idx;
	for (int i = 0; i < n; i++){
		step += iabs(p[i].x) + iabs(p[i].y);
		u.x += p[i].x;
		u.y += p[i].y;
	}
	u.x /= n; u.y /= n;
	int flag = 0;
	for (int id = 0; id < n; id ++)
		curlen += dis(u,p[id]);

	while (step > 1e-10){
		flag = 1;
		while (flag){
			flag = 0;
			tmp = u;	
			for (int i = -1; i <= 1; i++)
				for (int j = -1; j <= 1; j++){
					v = point(u.x + step * i,u.y + step * j);
					explen = 0.0;
					for (int id = 0; id < n; id ++){
						explen += dis(v,p[id]);
					}
					if (explen < curlen)
						curlen = explen,flag=1,tmp=v;
				}

			u = tmp;
		}
		step /= 2.0;
	}
	pt = u;
	return curlen;
}

int main(){
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++){
		scanf("%lf%lf", &p[i].x, &p[i].y);
	}
	point p_format;
	double ans = format(p,t,p_format);
	printf("%dn",(int)(ans + 0.5));
	return 0;
}

Posted on Edited on 
/*
 *
 * */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int INF = ~0u>>1;
typedef pair  P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<= len){
        if (b[0]) cout << b << endl;
        else cout << "空集" << endl;
    }
    else {
        x = s[i];
        k = strlen(b);
        b[k] = x;
        GetPowerSet(i+1,s);
        b[k] = 0;
        GetPowerSet(i+1,s);
    }
}

int main(){
    while (~scanf("%s",a)){
        printf("%s的幂集是:n", a);
        print();
        GetPowerSet(0,a);
        print();
    }
    return 0;
}

实现之后
sdfea
sdfea的幂集是:
--------
sdfea
sdfe
sdfa
sdf
sdea
sde
sda
sd
sfea
sfe
sfa
sf
sea
se
sa
s
dfea
dfe
dfa
df
dea
de
da
d
fea
fe
fa
f
ea
e
a
空集
--------

**<span style="background-color: transparent; border: 0px; margin: 0px; padding: 0px; vertical-align: baseline; color: rgb(255, 102, 0); background-position: initial initial; background-repeat: initial initial;">集合A的幂集是由集合A的所有子集所组成的的集合。</span>**

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">若![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)是集合![{a, b, c}](http://upload.wikimedia.org/math/3/2/9/3294dff896d06fea4749ce99aa43eb28.png)，则![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的全部子集如下：</span></span>
  • varnothing（空集）</span>
  • {a}</span>
  • {b}</span>
  • {c}</span>
  • {a, b}</span>
  • {a, c}</span>
  • {b, c}</span>

  • {a, b, c}</span>

    因此S的幂集为</span>

![mathcal{P}(S) = {](http://upload.wikimedia.org/math/a/6/7/a67a037c457a3bc7647aff80ac4e2990.png)![varnothing](http://upload.wikimedia.org/math/d/0/9/d096fc15d57854ec89d746709b02e52e.png), ![{a}](http://upload.wikimedia.org/math/7/f/7/7f7c00ea30e915cc552c838013f4f22d.png), ![{b}](http://upload.wikimedia.org/math/e/0/5/e059bbf69935fe421f7bad0b9b581ba4.png), ![{c}](http://upload.wikimedia.org/math/a/4/1/a41246e9a2cc0d5393df47cd461332ca.png), ![{a, b}](http://upload.wikimedia.org/math/b/2/7/b27d8e76c40e677920e4de6fd4e26022.png), ![{a, c}](http://upload.wikimedia.org/math/7/2/7/727ad386e646178a67c5be616dcc6409.png), ![{b, c}](http://upload.wikimedia.org/math/e/6/1/e61cf45c8f91a543f35476b8c1c21612.png), ![{a, b, c}](http://upload.wikimedia.org/math/3/2/9/3294dff896d06fea4749ce99aa43eb28.png)![},!](http://upload.wikimedia.org/math/c/0/3/c030341361b4ad537f4e4ad79f481a04.png)。 
<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">幂集中的每个元素是一个集合，它或是空集，或含集合A中一个元素，或含集合A中两个元素&hellip;&hellip; 或等于集合A。反之，从集合A 的每个元素来看，它只有两种状态：它或属幂集的无素集，或不属幂集的元素集。则求幂集p(A)的元素的过程可看成是依次对集合A中元素进行"取舍"的过程，并且可以用一棵二叉树来表示过程中幂集元素的状态变化过程，树中的根结点表示幂集元素的初始状态（空集）；叶子结点表示它的终结状态，而第i层的分支结点，则表示已对集合A中前i-1个元素进行了取舍处理的当前状态（左分支表示取，右分支表示舍 ）。因此求幂集元素的过程即为先序遍历这棵状态树的过程。</span></span>



<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">若![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)是有限集，有![|S|=n](http://upload.wikimedia.org/math/1/1/1/1114c80010a66a42faea3d20cfa4cbd2.png)个元素，那么![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集有![|mathcal{P}(S)| = 2^n](http://upload.wikimedia.org/math/b/6/6/b66b17bd63291fa202629e3da28af7be.png)个元素。（其实可以&mdash;&mdash;电脑也如此做&mdash;&mdash;将![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的元素表示为_n_位二进制数；第_n_位表示包含或不含![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的第_n_个元素。这样的数总共有![2^n](http://upload.wikimedia.org/math/9/a/a/9aa0ec0374c89d2f7f3d9cd2e05a4bc5.png)个。）</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">我们也可以考虑无穷集的幂集。以[康托尔对角线方法](http://zh.wikipedia.org/wiki/%E5%BA%B7%E6%89%98%E7%88%BE%E5%B0%8D%E8%A7%92%E7%B7%9A%E6%96%B9%E6%B3%95 "康托尔对角线方法")可证明集合（不论是否无穷）的幂集的[基数](http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B8 "基数")总是大于原来集合的基数（粗略的说，集合的幂集大于集合本身）。例如[自然数](http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B8 "自然数")集的幂集可以[一一对应](http://zh.wikipedia.org/wiki/%E5%8F%8C%E5%B0%84 "双射")于[实数](http://zh.wikipedia.org/wiki/%E5%AF%A6%E6%95%B8 "实数")集（把一个无穷0-1序列等同于有1出现的指数的集）。</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">集合![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集，加上并、交和补运算，就得出[布尔代数](http://zh.wikipedia.org/wiki/%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0 "布尔代数")的原始例子。我们可以证明所有有限布尔代数都是同构于某有限集的幂集的布尔代数。这结果虽然对无穷布尔代数不成立，但是所有无穷布尔代数都是某个幂集布尔代数的子代数。</span></span>

<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">集合![S](http://upload.wikimedia.org/math/5/d/b/5dbc98dcc983a70728bd082d1a47546e.png)的幂集与对称差运算构成一个[阿贝尔群](http://zh.wikipedia.org/wiki/%E9%98%BF%E8%B2%9D%E7%88%BE%E7%BE%A4 "阿贝尔群")（其中空集为幺元，每个集合的逆元为其本身），而与交运算则构成[交换](http://zh.wikipedia.org/wiki/%E4%BA%A4%E6%8F%9B%E5%BE%8B "交换律")[半群](http://zh.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4 "半群")。因此（可证明这两运算适合分配律）这两个运算使幂集成为一个[环](http://zh.wikipedia.org/wiki/%E7%92%B0 "环")。</span></span>



<span style="font-size:14px;"><span style="font-family:trebuchet ms,helvetica,sans-serif;">部分来源：</span></span>[http://www.wutianqi.com/?p=1157](http://www.wutianqi.com/?p=1157)



实现代码

Posted on Edited on

之前一直用Ubuntu自带的那个电影播放器，每次播放都弹出一个python更新的界面，可是每次都是不成功，后来就做罢了，看电影就换Windows。实在受不了，就研究了下。

<span style="line-height: 1.6em;">1.最省事的最方便的就是用VLC，我一直在用VLC，一直觉得非常好用，就听听歌就行了的就用用吧。VLC直接打开就能播放。你可以直接在软件源找到它然后安装。</span>

sudo apt-get install vlc
<span style="line-height: 1.6em;">2.也可以用Mplayer不过这个需要内核和一个前端，解码器，依次输入</span>

sudo apt-get install mplayer
sudo apt-get install smplayer
sudo apt-get install smplayer-themes
最后一句可有可无，安装两个就能播放

当然如果需要解码器，目前还没有遇到这样的情况，遇到了再写

Posted on Edited on

首先是Simpson积分公式：

（感谢维基百科）

详细讲解请戳：http://zh.wikipedia.org/wiki/%E8%BE%9B%E6%99%AE%E6%A3%AE%E7%A9%8D%E5%88%86%E6%B3%95

由于直接套这个公式很容易得出差得离谱的解，所以要稍加改进，使用自适应Simpson积分：

1.取三个点a, (a+b)/2, b

2.利用Simpson积分公式分别计算原图像在[a, b], [a, (a+b)/2], [(a+b)/2. b]的面积(分别记为S0, S1, S1)，若S0与S1+S2的值相差无几，则可以认为S0为原图像在[a, b]内的面积。

另外需要提及的是，自适应Simpson积分不仅可以求”正常”函数的积分，还可以用来求不规则图像的面积。这个时候，我们就不能狭隘地认为f[a]表示原函数在自变量为a的时候的值，而应该视为直线x=a被图像覆盖的长度（这也就是微积分的本质）。最后求出来的面积是整个图像的总面积，而不像微积分一样把x轴以下部分的面积算作负的（当然，这个自适应Simpson积分也可以做到）。

但是自适应Simpson积分很容易被数据卡掉（毕竟我们只通过5个点来大致确定一个图像的面积），所以求面积时最好分段。

然后是一道例题

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
/* 自适应辛普森 UVA 1356 
 * 二分求解高度 求解抛物线的长度是不是合适
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

// 这里为了方便，把a声明成全局的。
// 这不是一个好的编程习惯，但在本题中却可以提高代码的可读性
double a; 

//simpson 公式用的函数 (这个需要根据题目而改变函数)
double F(double x){
	return sqrt(1 + 4*a*a*x*x);
}

//三点simpson法，这里要求F是一个全局函数
double simpson(double a,double b){
	double c = a + (b-a)/2;
	return (F(a) + 4*F(c) + F(b)) * (b-a) / 6;
}

//自适应simpson公式(递归)。已知整个区间[a,b]上三点的simpson值A
double asr(double a,double b,double eps,double A){
	double c = a + (b-a)/2;
	double L = simpson(a,c),R = simpson(c,b);
	if (fabs(L+R-A) <= 15*eps) return L+R+(L+R-A)/15.0;
	return asr(a,c,eps/2,L) + asr(c,b,eps/2,R);
}

//自适应simpson公式(主过程)
double asr(double a,double b,double eps){
	return asr(a,b,eps,simpson(a,b));
}

//下面这个函数依题面而异，本题求解simpson求解宽度为w,高度为h的抛物线长度
double solve(double w,double h){
	a = 4.0 * h / (w*w); //修改全局变量a，从而改变F的行为
	return asr(0,w/2,1e-5)*2;
}

int main(){
	int t,cas = 0;
	scanf("%d", &t);
	while (cas++<t){
		int D,H,B,L;
		scanf("%d%d%d%d", &D, &H, &B, &L);
		int n = (B+D-1) / D;
		double D1 = (double) B / n;
		double L1 = (double) L / n;
		double x = 0, y = H;
		while(y-x > 1e-5){//二分求解高度
			double m = x + (y-x) / 2;
			if(solve(D1,m) < L1) x = m;
			else y = m;
		}
		if(cas > 1) puts("");
		printf("Case %d:n%.2fn", cas, H - x);
	}

	return 0;

}