Shen Huang's Blog
0%

Posted on Edited on

分组背包，finger先n^2预处理出来

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

char name[][100]={"Head", "Shoulder", "Neck", "Torso", "Hand", "Wrist", "Waist", 
"Legs", "Feet", "Shield", "Weapon", "Two-Handed", "Finger"};
int num[15],d[15][310],t[15][310],dp[15][50010];
char s[100];
int main(int argc, char const *argv[])
{
    int T,n,m;
    cin >> T;
    while (T--){
        memset(num,0,sizeof(num));
        cin >> n >> m;
        for (int i = 0; i < n; i ++){
            scanf("%s", s);
            int j;
            for (j = 0; ;j ++){
                if (strcmp(s,name[j]) == 0) break;
            }
            j ++;
            num[j] ++;
            scanf("%d%d", &d[j][num[j]], &t[j][num[j]]);
        }
        memset(dp,-1,sizeof(dp));
        dp[0][0] = 0;
        //注意每次都是从0到num[i]因为dp[i][j] = dp[i - 1][j]的就是说可能某个位置没有
        //预处理时候finger可以是0,1,2的混合
        //预处理出只有finger的情况
        for (int i = 0; i <= num[13]; i ++){
            for (int j = i + 1; j <= num[13]; j ++){
                dp[0][min(m,t[13][i] + t[13][j])] = max(dp[0][min(m,t[13][i] + t[13][j])],
                 d[13][i] + d[13][j]);
            }
        }

        for (int i = 1; i <= 11; i ++){
            for (int j = 0; j <= m; j ++){
                if (dp[i - 1][j] == -1) continue;
                for (int k = 0; k <= num[i]; k ++){
                    dp[i][min(m, j + t[i][k])] = max(dp[i][min(m, j + t[i][k])],
                     dp[i - 1][j] + d[i][k]);
                }
            }
        }
        //i - 1  = 9 在Feet i = 12
        for (int j = 0; j <= m; j ++){
            if (dp[9][j] == -1) continue;
            for (int k = 0; k <= num[12]; k ++){
                dp[11][min(m, j + t[12][k])] = max(dp[11][min(m, j + t[12][k])], 
                    dp[9][j] + d[12][k]);
            }
        }
        printf("%dn",max(-1,dp[11][m]));
    }
    return 0;
}

Posted on Edited on

看了ACdreamers的解题http://blog.csdn.net/acdreamers/article/details/23039571

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 20:49:38
 *
 *
 * */
#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;
#define maxn 100005
const ll mod = 1000000009;
ll fac[maxn],A[maxn],B[maxn];

void init(){
	fac[0] = 1;
	for (int i = 1; i < maxn; i ++){
		fac[i] = fac[i-1] * i % mod;
	}
	A[0] = B[0] = 1;
	for (int i = 1; i < maxn; i++){
		A[i] = A[i-1] * 691504013 % mod;
		B[i] = B[i-1] * 308495997 % mod;
	}
}

ll quick_mod(ll n,ll k,ll mod){
	ll ret = 1;
	n %= mod;
	while (k){
		if (k & 1) ret = ret * n % mod;
		k >>= 1;
		n = n * n % mod;
	}
	return ret;
}

ll solve(ll n, ll k){
	ll ret = 0;
	for (int r = 0; r <= k; r ++){
		ll t = A[k - r] * B[r] % mod;
		ll x = fac[k];
		ll y = fac[k-r] * fac[r] % mod;
		ll c = x * quick_mod(y, mod - 2, mod) % mod;
		ll tmp = t * (quick_mod(t, n, mod) - 1) % mod 
			* quick_mod(t-1,mod-2,mod) % mod;
		if (t == 1) tmp = n % mod;
		tmp = tmp * c % mod;
		if (r & 1) ret -= tmp;
		else ret += tmp;
		ret %= mod;
	}
	ll m = quick_mod(383008016,mod-2,mod);
	ret = ret * quick_mod(m,k,mod) % mod;
	ret = (ret % mod + mod) % mod;
	return ret;
}

int main(){
	int T;
	ll n,k;
	init();
	cin >> T;
	while (T--){
		cin >> n >> k;
		cout << solve(n,k) << endl;
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 F 单点更新线段树

把递推式子写成矩阵的形式，这样f[r]就相当于一个矩阵连成的形式

注意矩阵连乘时候的方向

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 20:02:21
 *
 *
 * */
#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 lson l, m , rt << 1
#define rson m + 1, r , rt << 1 | 1

#define maxn 400040
typedef long long ll;
#define mod 1000000007
struct mat{
	ll a[2][2];
	mat(){
		memset(a,0,sizeof(a));
	}
	mat(ll x){
		a[0][0] = a[1][0] = 1;
		a[1][1] = 0;
		a[0][1] = x;
	}
	mat operator * (const mat &b) const{
		mat ret = mat();
		for (int i = 0; i < 2; i ++){
			for (int j = 0; j < 2; j ++){
				for (int k = 0; k < 2; k ++){
					ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
				}
			}
		}
		return ret;
	}
};

ll num[maxn];
mat sum[maxn];

void PushUp(int rt){
	sum[rt] = sum[rt << 1 | 1] * sum[rt << 1];//会不会有问题
}

void build(int l, int r, int rt){
	if (l == r) {
		sum[rt] = mat(num[l]);
		return;
	}
	int m = MID(l,r);
	build(lson);
	build(rson);
	PushUp(rt);
}

mat query(int L,int R, int l, int r, int rt){
	if (L <= l && r <= R) return sum[rt];
	int m = MID(l, r);
	if (R <= m) return query(L, R, lson);//lson包括mid
	if (L > m) return query(L, R, rson);//rson从mid+1开始
	return query(L,R,rson) * query(L,R,lson);//会不会反了
}

int main(){
	int T,n,m;
	cin >> T;
	mat t;
	while (T--){
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i ++){
			scanf("%lld", &num[i]);
		}
		build(1, n, 1);
		int l,r;
		for (int i = 0; i < m; i ++){
			scanf("%d%d", &l, &r);
			if (l == r || r == l + 1){
				printf("%lldn", num[r]);continue;
			}
			t = query(l + 2,r,1,n,1);
			printf("%lldn", (t.a[0][0] * num[l + 1] + t.a[0][1] * num[l]) % mod);
		}
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 I

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: 2014-04-06 14:00:10
 *
 *
 * */
#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

char str[20] = "Hello, world!";
int main(){
	int t;
	cin >> t;
	getchar();	
	char s1[300],s2[3000];
	while (t--){
		int cnt = 0;
		cin.getline(s1,256);
		int len1 = strlen(s1);
		bool flag = 1;
		for (int i = 0; i < len1; i ++){
			if (cnt > len1) {flag = 0;break;}
			if (s1[i] == &#39;_&#39;){
				for (int j = 0; j < len1; j ++){
					s2[cnt ++] = s1[j];
				}
			}
			if (s1[i] == &#39;!&#39;){
				for (int j = 0; j < strlen(str); j ++){
					s2[cnt ++] = str[j];
				}
			}
		}
		if (cnt != len1) flag = 0; 
		if (flag){
			for (int i = 0; i < len1; i ++){
				if (s1[i] != s2[i]) {flag = 0;break;}
			}
		}
	//	cout << s1 << " s2: "<< s2 << endl;
		if (!flag){
			puts("No");
		}else puts("Yes");
	}
	return 0;
}

Posted on Edited on

2014 浙大校赛 D 排序题

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
/* From: Lich_Amnesia
 * Time: 2014-04-06 14:17:00
 *
 *
 * */
#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
struct Info{
	int i,id,day,va;
}p[2200];
int le[2200];
bool cmp(Info a,Info b){
	if (a.va == b.va){
		if (a.day == b.day){
			return a.id < b.id;
		}else return a.day < b.day;
	}else return a.va > b.va;
}
double val[10] = {0,0,0.4,0.3,0.2,0.07,0.03};
int main(){
	int t;
	cin >> t;
	int n,day,mon,year;
	while (t--){
		int nozero = 0;
		scanf("%d", &n);
		memset(le,-1,sizeof(le));
		for (int i = 0; i < n; i ++){
			scanf("%d", &p[i].id);
			scanf("%d/%d/%d", &year, &mon, &day);
			p[i].day = year * 10000 + mon * 100 + day;
			scanf("%d", &p[i].va);
			p[i].i = i;
			if (p[i].va > 0){ nozero ++;
				le[i] = 2;
			}
			if (p[i].va == 0) le[i] = 1;
		}
		sort(p,p + n,cmp);
		//for (int i = 0; i < n; i ++){
		//	cout << p[i].i << ' ' << p[i].id << ' '<< p[i].day<< ' ' << p[i].va << endl;
		//}
		int cnt = 0;
		for (int k = 6; k > 1; k --){
			int now = val[k] * nozero;
			while (now){
				le[p[cnt].i] = k;
				cnt ++;
				now --;
			}
		}
		for (int i = 0; i < n; i ++){
			printf("LV%dn",le[i]);
		}
	}
	return 0;	
}

Posted on Edited on

2014 浙大校赛 B

其实就是找到规律最多只可能是1，2，3种分割

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
/* From: Lich_Amnesia
 * Time: 2014-04-07 11:22:09
 *
 * ZOJ 3768
 * */
#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 check(int n){
	int k = max(0,(int)sqrt(2 * n) - 4);
	for (int i = k; i * i <= 2 * n; i ++){
		if (i * i  + i == 2 * n) return i;
	}
	return 0;
}

int main(){
	int T,n;
	cin >> T;
	while (T--){
		scanf("%d", &n);
		int l,k = check(n);
		if (k){
			printf("%dn", k);
		}else {
			bool flag = 0;
			for (int i = 1; i * i + i <= 2 * n; i ++){
				l = check(n - (i + 1) * i /2);
				if (l){
					printf("%d %dn", i, l);
					flag = 1;
					break;
				}
			}
			if (!flag){
				for (int i = 1; i * i + i <= 2 * n && !flag; i ++){
					int mod = n - (i + 1) * i / 2;
					for (int j = 1; j * (j + 1) / 2 <= mod && !flag; j ++){
						l = check(n - (j*(j+1)/2) - i * (i + 1) /2);
						if (l){
							printf("%d %d %dn", i, j ,l);
							flag = 1;
							break;
						}
					}
				}
			}
		}
	}
	return 0;
}

Posted on Edited on

2014年浙大校赛 A

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
/* From: Lich_Amnesia
 * Time: 2014-04-06 13:33:57
 *
 * ZOJ 3767
 * */
#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;
	int n,m;
	cin >> t;
	while (t--){
		scanf("%d%d", &n, &m);
		int sum = 0,cnt;
		for (int i = 0; i < n; i ++){
			scanf("%d",&cnt);
			sum += cnt;
		}
		if (sum > m) puts("Warning");
		else puts("Safe");
	}
	return 0;
}

Posted on Edited on

使用pppoeconf命令拨号

第一次用的时候：

启用有线连接：

1
sudo ifconfig eth0 up

在终端中输入:

1
sudo pppoeconf

之后在需要的时候启动ADSL连接，可以在终端中输入：

1
sudo pon dsl-provider

断开ADSL连接，可以在终端中输入：

1
sudo poff dsl-provider

如果你发现连接正常工作，尝试手动去调整你之前ADSL连接的配置。

需要查看日志，可以在终端中输入：

1
plog

获得接口信息，可以在终端中输入：

1
ifconfig ppp0

　

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info

Posted on Edited on

dp[i][0]表示从上面落到i的左边的横向最短距离

dp[i][0]表示从上面落到i的右边的横向最短距离

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_VAL 999999999
#define maxn 1010
struct Node{
	int l,r,h;
}p[maxn];
int dp[maxn][3];//dp[i][0] 表示从上面落到i的左边的最短

bool cmp(Node a,Node b){
	if (a.h == b.h) return a.l < b.l;
	return a.h > b.h;
}

int main(int argc, char const *argv[])
{
	int MAX,x,n,y,T,ans;
	scanf("%d", &T);
	while (T--){
		memset(dp, 0, sizeof(dp));
		ans = MAX_VAL;
		scanf("%d%d%d%d", &n, &x, &y, &MAX);
		for (int i = 1; i <= n; i ++){
			scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].h);
			dp[i][0] = dp[i][1] = MAX_VAL;
		}
		p[0].h = y;
		p[0].l = p[0].r = x;
		sort(p, p + n + 1, cmp);
		p[n + 1].h = 0;
		p[n + 1].l = -20000;
		p[n + 1].r =  20000;
		dp[0][0] = 0;dp[0][1] = 0;
		for (int i = 0; i <= n ; ++i){
			//bleft和bright用于标记从第i块木板左右两端下落是否找到了下一个落脚点
			bool bl = true, br = true;
			for (int j = i + 1; j <= 1 + n; j ++){
				if (!bl && !br || p[i].h - p[j].h > MAX) break;
				if (p[j].l <= p[i].l && p[j].r >= p[i].l && p[i].h != p[j].h && bl){
					bl = false;
					if (j == n + 1){
						ans = min(ans,dp[i][0]);
					}else {
						dp[j][0] = min(p[i].l - p[j].l + dp[i][0],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].l + dp[i][0],dp[j][1]);
					}
				}
				if (p[i].r <= p[j].r && p[i].r >= p[j].l && p[i].h != p[j].h && br){
					br = false;
					if (j == n + 1){
						ans = min(ans,dp[i][1]);
					}else {
						dp[j][0] = min(p[i].r - p[j].l + dp[i][1],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].r + dp[i][1],dp[j][1]);
					}
				}
			}
		}
		printf("%dn", ans + y);
	}
	return 0;
}

Posted on Edited on

dp[i][0]表示从上面落到i的左边的横向最短距离

dp[i][0]表示从上面落到i的右边的横向最短距离

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_VAL 999999999
#define maxn 1010
struct Node{
	int l,r,h;
}p[maxn];
int dp[maxn][3];//dp[i][0] 表示从上面落到i的左边的最短

bool cmp(Node a,Node b){
	if (a.h == b.h) return a.l < b.l;
	return a.h > b.h;
}

int main(int argc, char const *argv[])
{
	int MAX,x,n,y,T,ans;
	scanf("%d", &T);
	while (T--){
		memset(dp, 0, sizeof(dp));
		ans = MAX_VAL;
		scanf("%d%d%d%d", &n, &x, &y, &MAX);
		for (int i = 1; i <= n; i ++){
			scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].h);
			dp[i][0] = dp[i][1] = MAX_VAL;
		}
		p[0].h = y;
		p[0].l = p[0].r = x;
		sort(p, p + n + 1, cmp);
		p[n + 1].h = 0;
		p[n + 1].l = -20000;
		p[n + 1].r =  20000;
		dp[0][0] = 0;dp[0][1] = 0;
		for (int i = 0; i <= n ; ++i){
			//bleft和bright用于标记从第i块木板左右两端下落是否找到了下一个落脚点
			bool bl = true, br = true;
			for (int j = i + 1; j <= 1 + n; j ++){
				if (!bl && !br || p[i].h - p[j].h > MAX) break;
				if (p[j].l <= p[i].l && p[j].r >= p[i].l && p[i].h != p[j].h && bl){
					bl = false;
					if (j == n + 1){
						ans = min(ans,dp[i][0]);
					}else {
						dp[j][0] = min(p[i].l - p[j].l + dp[i][0],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].l + dp[i][0],dp[j][1]);
					}
				}
				if (p[i].r <= p[j].r && p[i].r >= p[j].l && p[i].h != p[j].h && br){
					br = false;
					if (j == n + 1){
						ans = min(ans,dp[i][1]);
					}else {
						dp[j][0] = min(p[i].r - p[j].l + dp[i][1],dp[j][0]);
						dp[j][1] = min(p[j].r - p[i].r + dp[i][1],dp[j][1]);
					}
				}
			}
		}
		printf("%dn", ans + y);
	}
	return 0;
}