G-rated

What are you waiting for?

0%

ZOJ 2013年12月月赛

本文从WordPress迁移而来, 查看全部WordPress迁移文章

zoj 3741 Eternal Reality

一个简单的DP，逆回来DP

dp[i][0]表示从第i个元素到最后的元素，不使用技能能得到的最大分数（第i个点不使用，后面的可能使用）

dp[i][1]表示从第i个元素到最后的元素，使用技能能得到的最大分数（第i个点使用技能）
对于最后的X+Y个点，先特殊处理，其余的点，就可以正常DP了

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int> 
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair
#define N 110

int used[N],dp[N][2],a[N];
int level,n,x,y;

int main(){
	while(scanf("%d%d%d%d",&level,&n,&x,&y)!=EOF){
		for(int i = 1; i <= n; i++)
			scanf("%d",&a[i]);
		for(int id = 1; id <= n; id++){
			int sum = 0;
			int lim = min(id+x-1,n);
			for(int i = id; i <= lim; i++)
				if(level + 1 >= a[i] && a[i] != 6) sum++;
			if(lim == n){
				used[id] = sum;
				continue;
			}
			lim = min(id+x+y-1,n);
			for(int i = id+x; i <= lim; i++)
				if(a[i] == 0) sum++;
			used[id] = sum;
		}
		//for(int id = 1; id <= n; id++)
		//	printf("---%d\n",used[id]);

		dp[n][0] = (level >= a[n] ? 1 : 0);
		dp[n][1] = used[n];
		int lim = max(1,n-x-y+1);
		for(int id = n-1; id >= lim; id--){
			dp[id][0] = max(dp[id+1][0],dp[id+1][1])+(level >= a[id] ? 1 : 0);
			dp[id][1] = used[id];
		}
		if(lim == 1){
			printf("%d\n",max(dp[1][0],dp[1][1]));
			continue;
		}
		for(int id = n-x-y; id >= 1; id--){
			dp[id][0] = max(dp[id+1][0],dp[id+1][1])+(level >= a[id] ? 1 : 0);
			int __id = id+x+y;
			dp[id][1] = used[id] + max(dp[__id][0],dp[__id][1]);
		}
		printf("%d\n",max(dp[1][0],dp[1][1]));
	}
	return 0;
}

zoj 3745 Salary Increasing

这个条件很吓人，但是注意看数据，发现是相互制约的

1
2
3
4
5
6
1 ≤ n ≤ 105 , 
1 ≤ Q ≤ 105 , 
1 ≤ ai ≤ 105 , 
1 ≤ li ≤ ri ≤ 105 , 
1 ≤ ci ≤ 105 , 
ri < li+1

两个关键的范围是，

1<= li <= ri <= 10^5 , 每次的操作都是在这个范围内

ri < li+1 ， 下次的操作一个更大

导致了这个问题会出现一种相互制约的情况，因而直接暴力解决即可

num[i]表示工资为i个人有多少个

工资内i的人，工资增加c，对应地 num[i+c] += num[i]; num[i] = 0;

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 100010
#define MAX 200010

int num[MAX];

int main(){
	int n,q;
	while(scanf("%d%d",&n,&q)!=EOF){
		cl(num,0);
		while(n--){
			int val;
			scanf("%d",&val);
			num[val]++;
		}
		while(q--){
			int l,r,c;
			scanf("%d%d%d",&l,&r,&c);
			for(int i = r; i >= l; i--){
				num[i+c] += num[i];
				num[i] = 0;
			}
		}
		LL ans = 0LL;
		for(int i = 1; i < MAX; i++)
			ans += ((LL)num[i] * (LL)i);
		cout << ans << endl;
	}
	return 0;
}

zoj 3738 Buy the Pets

这题，有些意思，题目说了人和猫可能有矛盾，猫和狗可能有矛盾，但是人和狗是没有矛盾的，关键在此

因为人猫狗的数量都只有10，对于人选不选猫和狗，用01表示，那就可以状态压缩了

dp1[n][s]; 是人和猫，n个人，选择的猫的状态为s，有多少方案数

dp2[n][s]; 是猫和狗，n个猫，选择的狗的状态为s，有多少方案数

关键是dp1和dp2怎么衔接起来

np，nc，nd表示人猫狗的数量

dp1的目标状态是dp1[np][s],这个s化为二进制有np个1（不是nc），因为一个人一个猫，最后肯定是np个1，所以我们一开始枚举s，当s里面有np个1的时候我们才开始dp（因为我用记忆化搜索写的）

所以，人和猫的匹配，可能有很多种，s1，s2，s3…….而每个dp1[np][si]只是代表了这种状态下有多少种方案，至于一个方案下，人和猫是怎样一一匹配的不关心，只关心方案数
对于dp1[np][si],我们马上接着就用si去dp

我们分解si，就可以知道确切地用了哪些猫（数量肯定是np），用这些猫和去所有狗匹配，找出所有的方案数，这个dp过程和之前的dp过程是几乎一样的

最后得到dp1和dp2，先乘后加即可

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int> 
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair
#define N 15
#define MAX 1111

int np,nc,nd,ans;
bool p_c[N][N],c_d[N][N];
LL dp1[N][MAX];
LL dp2[N][MAX];
int cat[N];

int check(int val){
	int cnt = 0;
	while(val){
		if(val&1) cnt++;
		val >>= 1;
	}
	return cnt;
}

void work(int val){
	int id = 0;
	for(int i = 0; i < nc; i++)
		if(val & (1<<i)) cat[id++] = i;
}

void dfs1(int n,int s){
	if(dp1[n][s] != -1) return ;
	if(n == 0){
		dp1[n][s] = 1LL;
		return ;
	}
	dp1[n][s] = 0;
	for(int c = 0; c < nc; c++)
		if((s&(1<<c)) && !p_c[n-1][c]){
			int ss = s - (1<<c);
			dfs1(n-1,ss);
			dp1[n][s] += dp1[n-1][ss];
		}
}

void dfs2(int n,int s){
	if(dp2[n][s] != -1) return ;
	if(n == 0){
		dp2[n][s] = 1LL;
		return ;
	}
	dp2[n][s] = 0;
	int CAT = cat[np-n];
	for(int d = 0; d < nd; d++)
		if((s&(1<<d)) && !c_d[CAT][d]){
			int ss = s - (1<<d);
			dfs2(n-1,ss);
			dp2[n][s] += dp2[n-1][ss];

		}
}

int main(){
	while(scanf("%d%d%d",&np,&nc,&nd)!=EOF){
		cl(p_c,false);
		cl(c_d,false);
		int m;
		scanf("%d",&m);
		while(m--){
			int a,b;
			scanf("%d%d",&a,&b);
			if(a > b) swap(a,b);
			if(1<=a && a <= np && np<b && b <= np+nc){ //p_c
				a--; b -= (np+1);
				p_c[a][b] = true;
			}
			else{ //c_d
				a -= (np+1); b -= (np+nc+1);
				c_d[a][b] = true;
			}
		}

		if(nc < np || nd < np){
			puts("0"); continue;
		}

		cl(dp1,-1);
		LL ans = 0LL;
		for(int sc = 0; sc < (1<<nc); sc++){
			if(check(sc) != np) continue;
			work(sc);
			//puts("--- --- ---");
			dfs1(np,sc);
			//printf("dp1[%d][%d] = %d\n",np,sc,dp1[np][sc]);
			cl(dp2,-1);
			
			
			for(int sd = 0; sd < (1<<nd); sd++){
				if(check(sd) != np) continue;
				dfs2(np,sd);
				//printf("dp2[%d][%d] = %d\n",np,sd,dp2[np][sd]);

				ans += ( dp1[np][sc] * dp2[np][sd] );
			}
		}
		cout << ans << endl;
	}
	return 0;
}

zoj 3742 Bellywhite’s Algorithm Homework
F.以图论为背景，但是和图论关系不大，主要是怎么去分析复杂度，学习了网上的题解
对于图中的所有点，统计它们的度，以sqrt(n)为准，大于的为高度点，小于等于的为低度点
对于更新操作，如果是操作低度点，直接暴力搞
如果是操作高度点，所有将高度点的值更新（值，指的是，这个点关联的边中，正数和，负数和多少，对这个点操作，肯定两者交换），同时对整个图的正数和，负数和，总和更新，而对于一些边，是 高—-高，那么就暴力更新，同时更新对面的点的值。对于一些边 高—-低，数量太多不能直接更新，忽略
回到前面，如果操作的点是低度点，可以我们可以暴力更新每条关联的边，如果为 低—-低，直接更新边的值和对面的点的值，对于 低—-高，要看看这个边是否被操作过。其实一条边被操作了多少次，就是这条边的两个端点被操作的总数和，我们只需要判断奇偶就能知道这个边的值，然后去更新当前点的值和对面点的值，和总的值

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int> 
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair
#define N 50010

struct edge{
	int u,v;
	LL w;
	edge(){}
	edge(int __u,int __v,LL __w){
		u = __u; v = __v; w = __w;
	}
}e[N];
int de[N]; //每个点的度
int kind[N]; //属于高度点还是低度点
vector<int>eid[N]; //记录每个点和哪些边关联
int CNT[N]; //对于每个高度点,有多少边是连向低度点的
LL value[N][2]; //每个点，正数和，负数和
LL positive,negtive,all; //所有点,正，负，总和
int n,num,Q;

void BF(int u){
	int tot = eid[u].size();
	for(int i = 0; i < tot; i++){
		int id = eid[u][i] , v;
		LL w = e[id].w;
		if(e[id].u != u) v = e[id].u;
		else v = e[id].v;
		if(kind[v] == 0){//v也是低度点
			positive -= w;
			negtive -= w;
			all = positive + negtive;
			e[id].w = -e[id].w;
		}
		else{ //v是高度点
			int cnt = CNT[u]+CNT[v];
			if(cnt % 2 == 0){ //v修改过偶数次
				value[v][1] -= w;
				value[v][0] -= w;
				positive -= w;
				negtive -= w;
				all = positive + negtive;
			}
			else{ //奇数次，这次再修改
				w = -w;
				value[v][0] -= w;
				value[v][1] -= w;
				positive -= w;
				negtive -= w;
				all = positive + negtive;
			}
		}
	}
	CNT[u]++;
}

void work(int u){
	int tot = eid[u].size();
	
	LL pos = value[u][1] , neg = value[u][0];
	positive -= pos;
	positive -= neg;
	negtive -= neg;
	negtive -= pos;
	all = positive + negtive;
	value[u][1] = -neg;
	value[u][0] = -pos;

	for(int i = 0 ; i < tot; i++){
		int id = eid[u][i] ,  v;
		LL w = e[id].w;
		if(e[id].u != u) v = e[id].u;
		else v = e[id].v;

		value[v][1] -= w;
		value[v][0] -= w;
		e[id].w = -e[id].w;
	}
	CNT[u]++;
}

void solve(){
	while(Q--){
		char op[5];
		scanf("%s",op);
		if(op[0] == 'Q'){
			scanf("%s",op);
			if(op[0] == 'A') printf("%lld\n",all);
			else if(op[0] == '+') printf("%lld\n",positive);
			else printf("%lld\n",negtive);
		}
		else{
			int u;
			scanf("%d",&u);
			if(kind[u] == 0){ //低度点
				BF(u); //直接暴力更新
			}
			else{ //高度点
				work(u);
			}
		}
	}

}

int main(){
	int cas = 0;
	while(scanf("%d%d%d",&n,&num,&Q)!=EOF){
		if(cas++) puts("");
		cl(de,0);
		cl(kind,-1);
		cl(CNT,0);
		cl(value,0);
		positive = negtive = all = 0;
		for(int i = 1; i <= n; i++)
			eid[i].clear();
		for(int i = 0; i < num; i++){
			int u,v;
			LL w;
			scanf("%d%d%lld",&u,&v,&w);
			e[i] = edge(u,v,w);
			de[u]++; 
			de[v]++;
			if(w >= 0LL){
				value[u][1] += w;
				value[v][1] += w;
				positive += w;
			}
			else{
				value[u][0] += w;
				value[v][0] += w;
				negtive += w;
			}
			all += w;
		}
		int lim = (int)sqrt(n+0.5);
		for(int i = 1; i <= n; i++){
			if(de[i] > lim) kind[i] = 1;
			else kind[i] = 0;
		}
		for(int i = 0; i < num; i++){
			int u = e[i].u , v = e[i].v;
			if(kind[u] == 1 && kind[v] == 1){ 
				eid[u].pb(i);
				eid[v].pb(i);
			}
			if(kind[u] == 0) eid[u].pb(i);
			if(kind[v] == 0) eid[v].pb(i);
		}

		solve();
	}
	return 0;
}