Codeforces Round #321 div2
Codeforces Round #321 div2
若羽
发布于 2019-07-15 16:48:42
发布于 2019-07-15 16:48:42
好像前几场的题解忘记写了， Orz 状态太差， 平均出两题 都不好意思写了 ， 连掉4场， 都要哭晕了。
很水的一场， 写完A B C就去睡了 D题其实不难， E题研究Ing（已用一种奇怪的姿势AC了）
Problem_A:
题意：
给一个长度为n的序列， 找出最长不下降子序列。
思路：
线性扫一遍， 每读入一个数就判断下是否和前面的组成不下降子序列， 维护最大答案和当前序列长度即可（注意处理最后一个序列即可）。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 100010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int f[MAXN];
37
38 int main()
39 {
40 int ans_i = 0;
41 int max_num = 0;
42 scanf("%d", &n);
43 for(int i = 0; i < n; i ++)
44 {
45 scanf("%d", &f[i]);
46 if(i == 0) continue;
47 if(f[i] < f[i - 1])
48 {
49 max_num = max(max_num, (i - 1 - ans_i + 1));
50 ans_i = i;
51 }
52 }
53 if(ans_i != n - 1)
54 {
55 max_num = max(max_num, (n - 1 - ans_i + 1));
56 }
57 if(n == 1) max_num = 1;
58 printf("%d\n", max_num);
59 return 0;
60 }Problem_B:
题意：
你想邀请朋友来参加聚会， 每个朋友都有一个财富值和亲密度， 当你邀请的朋友中存在两个人财富值之差大于等于d， 那么就有有个朋友感到自己比较穷，但是你并不像让这种情况发生。
求使得邀请过来的朋友满足上诉要求，并求最大的亲密度和。
思路：
首先邀请朋友的第一要素是财富值， 所以先按财富值排序， 细想一下， 这个题和A题很像。这里就是找到所有满足要求的区间，然后比较得到最大财富值。
线性扫一遍， 维护区间起点即可。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 100010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 struct node
36 {
37 int m;
38 int s;
39 };
40 int n, d;
41 struct node f[MAXN];
42 bool cmp(struct node x, struct node y)
43 {
44 return x.m < y.m;
45 }
46
47 int main()
48 {
49 LL pre_id = 1;
50 LL ans = 0;
51 LL temp = 0;
52 scanf("%d %d", &n, &d);
53 for(int i = 1; i <= n; i ++)
54 scanf("%d %d", &f[i].m, &f[i].s);
55 sort(f + 1, f + n + 1, cmp);
56 for(int i = 1; i <= n; i ++)
57 {
58 if(f[i].m - f[pre_id].m < d)
59 {
60 temp += f[i].s;
61 }
62 else
63 {
64 ans = max(ans, temp);
65 while(f[i].m - f[pre_id].m >= d)
66 {
67 temp -= f[pre_id].s;
68 pre_id ++;
69 }
70 temp += f[i].s;
71 }
72 }
73 ans = max(ans, temp);
74 printf("%I64d\n", ans);
75 return 0;
76 }Problem_C：
题意：
给一棵树， 根节点是你的家， 叶子节点是饭馆，每个节点可能存在猫， 你想去饭馆吃饭， 但是又怕猫。如果存在一条路径， 路径上连续的猫的个数 > m个，那么你就可以不能去那个饭馆， 因为你怕猫。
求你能到达的饭馆个数。
思路：
搜索， dfs， 搜索出所有路径， 然后判断路径是否满足要求，搜索下一个状态时需要当前状态， 因为要判断是否是连续的。建边双向建， 叶子节点即所有边都被访问过。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 100010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n, m;
36 int ans = 0;
37 vector <int> edge[MAXN];
38 int num[MAXN];
39 bool vis[MAXN];
40 void init()
41 {
42 memset(vis, false, sizeof(vis));
43 for(int i = 0; i < MAXN; i ++)
44 edge[i].clear();
45 int ans = 0;
46 }
47 bool is_ok(int u)
48 {
49 for(int i = 0; i < edge[u].size(); i ++)
50 if(!vis[edge[u][i]]) return false;
51 return true;
52 }
53 void dfs(int root, int cat_num)
54 {
55 vis[root] = true;
56 if(cat_num > m) return ;
57 if(is_ok(root))
58 {
59 ans ++;
60 return ;
61 }
62 for(int i = 0; i < edge[root].size(); i ++)
63 {
64 int v = edge[root][i];
65 if(!vis[v])
66 {
67 if(num[v])
68 dfs(v, cat_num + num[v]);
69 else
70 dfs(v, 0);
71 }
72 }
73 }
74
75 int main()
76 {
77 init();
78 scanf("%d %d", &n, &m);
79 for(int i = 1; i <= n; i ++)
80 scanf("%d", &num[i]);
81 int x, y;
82 for(int i = 0; i < n - 1; i ++)
83 {
84 scanf("%d %d", &x, &y);
85 edge[x].push_back(y);
86 edge[y].push_back(x);
87 }
88 dfs(1, num[1]);
89 printf("%d\n", ans);
90 return 0;
91 }Problem_D：
题意：
去饭馆吃饭（又吃饭， 囧），菜单上有n道菜， 你想吃m道菜， 且每道最多吃一次， 每一道菜有一个欢乐度， 如果你吃了x 后 又吃y 那么你将得到 c的欢乐度。
求问你能获得的最大欢乐度。
思路：
最多只有18道菜， 答案又是求最优解， 第一反应就是状压。
因为x y 要按顺序， 连续吃下去才能得到c的欢乐度， 所以需要记录一下最后吃的是什么。
那么状态设为：dp[staues][last], staues为二进制集合， last为当前状态最后吃的那道菜，
so，转移方程就出来了， 因为每道菜要么吃， 要么不吃， 就成了个状压的01背包问题了。
dp[staues | (1 << i)][i] = max(dp[staues |(1 << i)][i], dp[staues][last] + a[i] + ruler[last][i])， 初始化时注意下初始为-1， 因为有可能出现0的情况（全部的a[i] = 0）
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 19
23 #define MAXM (1 << 19)
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 LL dp[MAXM][MAXN];
36 LL ruler[MAXN][MAXN];
37 LL a[MAXN];
38 int n, m, k;
39 void read()
40 {
41 int x, y;
42 LL c;
43 memset(ruler, 0, sizeof(ruler));
44 scanf("%d %d %d", &n, &m, &k);
45 for(int i = 0; i < n; i ++)
46 scanf("%lld", &a[i]);
47 for(int i = 0; i < k; i ++)
48 {
49 scanf("%d %d %lld", &x, &y, &c);
50 -- x;
51 -- y;
52 ruler[x][y] = c;
53 }
54 }
55 bool is_ok(int x)
56 {
57 int num = 0;
58 while(x)
59 {
60 if(x & 1) num ++;
61 x /= 2;
62 }
63 return num == m;
64 }
65 LL solve()
66 {
67 memset(dp, -1, sizeof(dp));
68 LL ans = 0;
69 for(int staues = 0; staues < (1 << n); staues ++)
70 {
71 for(int last = 0; last < n; last ++)
72 {
73 int u = 1 << last;
74 if(staues == 0)
75 {
76 dp[staues | u][last] = a[last];
77 }
78 else if(dp[staues][last] != -1)
79 {
80 for(int cas = 0; cas < n; cas ++)
81 {
82 int v = 1 << cas;
83 if(staues & v) continue;
84 dp[staues | v][cas] = max(dp[staues | v][cas], dp[staues][last] + a[cas] + ruler[last][cas]);
85 }
86 }
87 if(is_ok(staues)) ans = max(ans, dp[staues][last]);
88 }
89 }
90 return ans;
91 }
92
93 int main()
94 {
95 read();
96 printf("%lld\n", solve());
97 return 0;
98 }Problem_E：
题意;
给一个长度为n的字符串， 这个字符串由0~9组成， 现在有2种操作：
1：l, r, c， 将[l, r]这段区间上的数字全变成c。
2：l, r, d， 判断以l ， r开头， 长度为d的两个字符串是否相等。
对每个第二种操作， 输出结果。
思路：
这道题正解应该是线段树 + hash的， 将数字进行hash， 然后第一个操作就是线段树中的区间修改， 第二个操作就是查询是否想等。
然而， 这道题还有一个神奇的解法：仅用两个系统函数 + 一个if 就解出来了。
memset(), memcmp()
用memset将l, r 进行覆盖， 用memcmp进行判断。
这里给出第二种解法， Orz 其实第一种我还不会。
代码：
1 #include <stdio.h>
2 #include <string.h>
3 #define MAXN 100010
4 int n, m, k;
5 char s[MAXN];
6
7 int main()
8 {
9 int op, l, r, val;
10
11 memset(s, '\0', sizeof(s));
12
13 scanf("%d %d %d", &n, &m, &k);
14 scanf("%s", s);
15
16 for (int i = 0; i < m + k; ++ i)
17 {
18 scanf("%d %d %d %d", &op, &l, &r, &val);
19 -- l;
20 -- r;
21 if(op == 1)
22 memset(s + l, val + '0', r - l + 1);
23 else
24 printf(!memcmp(s + l, s + l + val, r - l + 1 - val)? "YES\n" : "NO\n");
25 }
26 return 0;
27 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-09-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读