Shen Huang's Blog
0%

Posted on Edited on

每个前面大的后面小的都需要使他们保持平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int num[100005];
int main(){
	int n;
	///memset(b,0,sizeof(b));
	scanf("%d", &n);
	int flag = 0,cnt,Mini,Min = 1000000002;
	int tmp;
	long long ans = 0;
	for (int i = 0; i < n; i++){
		tmp = cnt;
		scanf("%d", &cnt);
		if (i !=0 && tmp > cnt)
			ans += tmp - cnt;		
	}
	cout << ans << endl;
	return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int num[100005];
int main(){
	int n;
	///memset(b,0,sizeof(b));
	scanf("%d", &n);
	int flag = 0,cnt,Mini,Min = 1000000002;
	for (int i = 0; i < n; i++){
		scanf("%d", &cnt);
		num[i] = cnt;
		if (Min > cnt)
			Mini = i;
		//if (Min == cnt) flag = 1;
		Min = min(cnt,Min);
	}
	for (int i = 0; i < n; i++)
	{
		if (Mini != i && Min == num[i])
			flag = 1;
	}
	if (flag) printf("Still Rozdiln");
	else printf("%dn", Mini + 1);
	return 0;
}

Posted on Edited on

找出树的重心

s数组表示包括此点产生的所有子树的点的和

f数组表示以此点为重心切产生的最大子树的节点数

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
/* From: Lich_Amnesia
 * Time: 2013-11-12 16:26:24
 * POJ 1655 求树的重心
 *
 * */
#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 20010
vector<int> ve[maxn];
int s[maxn],f[maxn],n,root;

void solve(int now,int fa){
	int son;
	s[now] = 1;
	f[now] = 0;
	for (int i = 0; i < ve[now].size(); i ++){
		if ((son=ve[now][i]) != fa){
			solve(son,now);
			s[now] += s[son];
			f[now] = max(f[now],s[son]);
		}
	}
	f[now] = max(f[now], n - s[now]);
	if (f[now] < f[root]) root = now;
}

int main(){
	int t,u,v;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		for (int i = 0; i <= n; i++)
			ve[i].clear();
		for (int i = 1; i < n; i++){
			scanf("%d%d", &u, &v);
			ve[u].pb(v);
			ve[v].pb(u);
		}
		f[0] = n;
		solve(1,root = 0);
		for (int i = 1; i <= n; i++)
			if (f[i] == f[root]) {
				root = i;
				break;
		}
		printf("%d %dn", root , f[root]);
	}
	return 0;
}

Posted on Edited on

树形DP

用dp[i][0]来表示该点没有放兵，以这个点为根的子树所需的最少兵数。

用dp[i][1]来表示该点有放兵，以这个点为根的子树所需的最少兵数。

那么可以得到状态方程

dp[fa][0]+=dp[son][1];//如果该父亲不放，那么儿子必须放

dp[fa][1]+=min(dp[son][0],dp[son][1]);//如果该父亲放，儿子在放和不放之间选择最小的

访问的时候，因为要先知道儿子的信息，用递归的解法

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
/* From: Lich_Amnesia
 * Time: 2013-11-12 15:30:00
 *
 * POJ 1463 树形DP
 * */
#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 1600

int dp[maxn][2];

vector<int> ve[maxn];

void solve(int fa){// 0表示父亲不放，1 表示父亲放
	dp[fa][0] = 0; dp[fa][1]= 1;
	int son;
	for (int i = 0; i < ve[fa].size(); i++){
		son = ve[fa][i];
		solve(son);
		dp[fa][0] += dp[son][1];
		dp[fa][1] += min(dp[son][1],dp[son][0]);

	}
}

int main(){
	int n;
	while (~scanf("%d", &n)){
		int u,v,num;
		int root = -1; // 设根
		for (int i = 0; i <= n; i++)
			ve[i].clear();
		for (int i = 0; i < n; i++){
			scanf("%d:(%d)", &u, &num);
			if (root == -1) root = u;
			for (int j = 0; j < num; j++){
				scanf("%d", &v);
				ve[u].pb(v);
			}
		}
		solve(root);
		printf("%dn", min(dp[root][0],dp[root][1]));
	}
	return 0;
}

Posted on Edited on

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31424#overview

自己搜集的一些SG和博弈类的题目

题目：给出一串石头，和一个集合，每次取出若干个连续的石头（数量必须为集合中的），最后取完的获胜，问有没有必胜策略。

http://acm.hdu.edu.cn/showproblem.php?pid=2999

好像不是很理解SG函数的含义， 可还是乱七八糟的搞出了SG，然后水过去。

对于一个连续的串，比如说长度为5，可行只有2，那么取了之后可能分为两段

如后继可能为：（1，3），｛（1），（4，5）｝，｛（1，2），（5）｝，｛3，5｝这四种情况。两个区间异或之后，取mex操作

虽不明但觉厉，然后就AC了。

局面是确定的，没有存在不确定的情况

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
/* 
 *
 * */
#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 n,m;
int sg[1010],ni[1010];
int mex(int num){
	if (sg[num] != -1) return sg[num];
	int judge[1010] = {0};
	int tmp;
	for (int i = 0; i < n; i++){
		tmp = num - ni[i];
		if (tmp < 0) break;
		for (int j = tmp; j >= 0; j--){
			judge[mex(j) ^ mex(num-j-ni[i])] = 1;
		}
	}
	for (int i = 0;;i++)
		if (!judge[i]) 
			return sg[num] = i;
}

int main(){
	while (~scanf("%d", &n)){
		memset(sg,-1,sizeof(sg));
		for (int i = 0; i < n; i++)
			scanf("%d", &ni[i]);
		sort(ni, ni + n);
		int i ,j;
		for (i = j = 1; i < n; i++){
			if (ni[i] != ni[j-1]) 
				ni[j++] = ni[i];
		}
		n = j;
		scanf("%d", &m);
		int num,sgans = 0;
		for (int i = 0; i < m; i++){
			scanf("%d", &num);

			//	sgans ^= mex(num);

			if (mex(num) == 0) printf("2n");
			else printf("1n");
		}
	}
	return 0;
}

Posted on Edited on

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31424#overview

自己搜集的一些SG和博弈类的题目

题目：给出一串石头，和一个集合，每次取出若干个连续的石头（数量必须为集合中的），最后取完的获胜，问有没有必胜策略。

http://acm.hdu.edu.cn/showproblem.php?pid=2999

好像不是很理解SG函数的含义， 可还是乱七八糟的搞出了SG，然后水过去。

对于一个连续的串，比如说长度为5，可行只有2，那么取了之后可能分为两段

如后继可能为：（1，3），｛（1），（4，5）｝，｛（1，2），（5）｝，｛3，5｝这四种情况。两个区间异或之后，取mex操作

虽不明但觉厉，然后就AC了。

局面是确定的，没有存在不确定的情况

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
/* 
 *
 * */
#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 n,m;
int sg[1010],ni[1010];
int mex(int num){
	if (sg[num] != -1) return sg[num];
	int judge[1010] = {0};
	int tmp;
	for (int i = 0; i < n; i++){
		tmp = num - ni[i];
		if (tmp < 0) break;
		for (int j = tmp; j >= 0; j--){
			judge[mex(j) ^ mex(num-j-ni[i])] = 1;
		}
	}
	for (int i = 0;;i++)
		if (!judge[i]) 
			return sg[num] = i;
}

int main(){
	while (~scanf("%d", &n)){
		memset(sg,-1,sizeof(sg));
		for (int i = 0; i < n; i++)
			scanf("%d", &ni[i]);
		sort(ni, ni + n);
		int i ,j;
		for (i = j = 1; i < n; i++){
			if (ni[i] != ni[j-1]) 
				ni[j++] = ni[i];
		}
		n = j;
		scanf("%d", &m);
		int num,sgans = 0;
		for (int i = 0; i < m; i++){
			scanf("%d", &num);

			//	sgans ^= mex(num);

			if (mex(num) == 0) printf("2n");
			else printf("1n");
		}
	}
	return 0;
}

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
import java.math.BigInteger;
import java.math.BigDecimal;
import java.util.Scanner;
import java.io.*;  
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		/*读入：
		 * 用Scanner 类定义的对象进行控制台读入，Scanner类在java.util.*包中
		 * Scanner input = new Scanner(System.in);
		 * int n = input.nextInt();
		 * BigInteger nn = input.nextBigInteger();
		 * ......................................
		 */
		while (input.hasNext())   //等同于!= EOF
		{
			int n;
			BigDecimal a = input.nextBigDecimal(); //读入一个BigDecimal
			n = input.nextInt();
			a = a.pow(n);  // 返回其值为 (thisn) 的 BigDecimal，准确计算该幂，使其具有无限精度。
			//pow(int n, MathContext mc)   返回其值为 (thisn) 的 BigDecimal。
			a = a.stripTrailingZeros();
			/*public BigDecimal stripTrailingZeros  (strip 脱去剥夺，trailing(拖尾，后面的))
			 * 返回数值上等于此小数，但表示形式溢出所有尾部0的BigDecimal
			 * 1.22222300000   用过之后为1.222223 类型还是BigDeciaml类型
			 */
			String str = a.toPlainString();
			/*
			 * 注意toPlainString()和toString()的区别
			 * 对于:BigDecimal s; s = (0.4321^20)
			 * String str = s.toPlainString();
			 * System.out.println(str);
			 * 输出:0.0000000514855464107。。。。。01
			 * 
			 *若String str = s.toString();
			 *输出为： 5.14855464107。。。。01E-8
			 */
			if (str.startsWith("0.")) //以什么开始
			{
				str = str.substring(1);
				/*substring是java中截取字符串的一个方法
				 * 有两种传参方式
				 * 一种是：public String substring(int deginindex)
				 * 返回一个新的字符串，它是此字符串的一个子串，该字串从指定索引处的字符开始直到字符串末尾
				 * 另一种是public String substring(int deginindex,int endindex)
				 * 返回一个新字符串，也是它的一个子串。该字串从beginindex处开始
				 * 直到索引到endindex-1处的字符。因此该字符串的长度为endindex-beginindex
				 * 
				 * 
				 * substr
				 * 该方法用于返回一个从指定位置开始的指定长度的子字符串
				 *substr(start,length);
				 */
			}
			System.out.println(str);
		}
	}
}

Posted on Edited on

大意是，在一条线上有`N个城市，它们由一个污水处理系统连接着，每个城市有三个选择：

1.把自己的污水排到河里V

2.把自己的污水送到右边>

3.把自己的污水送到左边<

至少要有一个城市排水。要求给N个城市，方案种数。

最左边只有两种选择：V，>

令 dp[i][0]:V

dp[i][1]:>

dp[i][2]:<

则：dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]

dp[i][2]=dp[i-1][0]+dp[i-1][2]//刚开始总是很但是会不会有没有城市排水的问题，但是这个方程保证了不会出现><的情况

但是这三个方程不能保证不会出现一排全是>>>>>的情况，所以在算最后一个的时候，只能算dp[n][0]+dp[n][2]

注意到dp[i][0] dp[i][1]总是相等，所以可以少列一个状态转移方程

dp[i][0]=2*dp[i-1][0]+dp[i-1][2]

dp[i][2]=dp[i-1][0]+dp[i-1][2]

即dp[i]=3*dp[i-1]-dp[i-2]

到此为止，整个状态转移方程就列出来了。

由于dp的值可能会很大，所以就要用到java里面的BigInteger

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		BigInteger dp[] = new BigInteger[110];
		dp[1] = BigInteger.valueOf(1);
		dp[2] = BigInteger.valueOf(3);
		for (int i = 3; i <= 100; i ++){
			dp[i] = dp[i-1].multiply(BigInteger.valueOf(3))
				.subtract(dp[i-2]);
		}
		while (in.hasNext()){
			int n = in.nextInt();
			System.out.println(dp[n]);
		}
	}
}

Posted on Edited on

使用

1
mysql -u root -p

启动Mysql报错

1
ERROR 2002 (HY000): Can't connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)

然后

1
2
3
su -
service mysqld start
mysql -u root -p

还是出现

1
ERROR 2002 (HY000): Can't connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)

发现是service 这里可能会有问题

用绝对路径启动就行了

1
/etc/init.d/mysqld start

启动Mysql

完整命令

1
2
3
su -
/etc/init.d/mysqld start
mysql -u root -p

Posted on Edited on

给定整数N，和一个序列的逆序数M，求以1，2…N为元素，逆序为M，且按字典序最小的那个序列。

只要知道这样一个事实：一个序列的逆序唯一决定了这个序列。

对这个问题可以采取贪心策略。

首先，如果所求序列以1为首，则1的逆序为0，可以从上表看出此时序列的逆序数最多为2+1=3<5，不满足。考虑以2为首，序列的逆序最多为3+1<5，不满足。

考虑以3为首，可见当1的逆序为3，2的逆序为2，4的逆序为0时满足要求，这时1，2，4均为最大逆序，因而只能排列为4，2，1，加上首数，所求序列为3，4，2，1。

若M=3，采取同样的贪心策略，可求得结果为1，4，3，2。

依此思路，可以得到所求序列关于N，M的关系式，具体如下：

1，2，3，…N-P, N-((p-1)p/2-M), N , N-1…N-P+1.(P是满足（P-1）P/2>=M的最小值)。

代码就容易多了。

正好按照那样的排列会出现多了几个逆序数的情况，这样只需要把多的那个值的逆序的那个数移动到前面去就可以了 

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
/* From: Lich_Amnesia
 * Time: 2013-10-24 10:44:52
 *
 *
 * */
#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 n,m;
	while (~scanf("%d%d", &n, &m) && (m!=-1 && n != -1)){
		int p = 1;
		while (p*(p-1)/2 < m) p++;
		int tmp = (p-1)*p/2;
		for (int i = 1; i <= n-p; i++)
			printf("%d ",i);
		printf("%d",n-(tmp-m));
		for (int i = n; i > n-p; i--)
			if (i != n-tmp+m) printf(" %d", i);
		puts("");
	}
	return 0;
}