https://www.luogu.org/problem/show?pid=T15564
一眼贪心,
但是不知道怎么维护。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=1e6;
8 const int INF=0x7ffff;
9 inline int read()
10 {
11 char c=getchar();int flag=1,x=0;
12 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
13 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
14 }
15 int zero;
16 int n;
17 int a[MAXN];
18 int tmp[MAXN];
19 int main()
20 {
21 // freopen("multiset.in","r",stdin);
22 // freopen("multiset.out","w",stdout);
23 n=read();
24 for(int i=1;i<=n;i++) a[i]=read();
25 sort(a+1,a+n+1);
26 int now=0;
27 int num=n;
28 int bg=INF;
29 int ans=0;
30 while(num!=1)
31 {
32 zero=0;bg=INF;
33 for(int i=1;i<=num;i++)
34 {
35 if(a[i]==0) zero++;
36 if(a[i]>=1)
37 {
38 a[i]--;
39 if(bg==INF)bg=i;
40 }
41
42 }
43 int nownum=0;
44 for(int i=1;i<=zero/2;i++)
45 tmp[++nownum]=0;
46 if(zero%2==1)
47 tmp[++nownum]=0;
48 for(int i=bg;i<=num;i++)
49 tmp[++nownum]=a[i];
50 for(int i=1;i<=nownum;i++) a[i]=tmp[i];
51 num=nownum;
52 ans++;
53 }
54 printf("%d",ans);
55 return 0;
56 }
57
58
59 /*
60 5
61 0 0 0 3 3 //5
62 2
63 2 1//3
64 4
65 1 0 2 3//4
66
67 */
正解
考虑如何从最终状态转移
贪心思路:
让不是0的变小。
让0的个数变少。
暴力——》50
考虑如何优化
用一个桶记录,
a[0]->(a[0]+1)/2->a[1]
1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 #include <cstring>
5 #include <climits>
6 #include <cstdlib>
7 #include <cmath>
8 #include <queue>
9 #include <vector>
10 #include <utility>
11 using namespace std;
12 const int MAXN = 5e6 + 60, MX = 1e6;
13 int N, a[MAXN], cnt[MAXN], res, lim;
14
15 int main()
16 {
17 freopen("multiset.in", "r", stdin);
18 freopen("multiset.out", "w", stdout);
19 scanf("%d", &N);
20 for (int i = 1; i <= N; ++i) {
21 scanf("%d", &a[i]);
22 lim = max(lim, a[i]);
23 ++cnt[a[i]];
24 }
25 int l = 0, z = cnt[0];
26 for (int i = 1; i <= lim; ++i) {
27 ++res;
28 z = (z + 1) / 2;
29 z += cnt[i];
30 }
31 for (; z > 1; z = (z + 1) / 2) ++res;
32 printf("%d\n", res);
33 return 0;
34 }
一开始没看懂样例
这句话我捉摸了好久,我以为他的意思是在每组里面都要重新标号。。
直到最后20分钟问了一下zzx才恍然发现居然有50分的暴力分!!!!(lyq实测有80){{{(>_<)}}}
正解:
做法①:暴力加边,每次BFS,可以加一个剪枝,每次只有做到过要加的点才BFS,复杂度:$O(m)$
做法②:单向并查集
做法③:对于每个点
倍增分割的长度,保证2^p-1~2^p,再在这段区间内二分,时间复杂度O(m*log)
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<algorithm>
6 #include<cmath>
7 #include<vector>
8 using namespace std;
9 const int N=500010;
10 typedef long long ll;
11
12 int n, m;
13 int vis[N], u[N], v[N];
14 vector<int> vec[N];
15
16 bool dfs(int u)
17 {
18 if (vis[u]) return false;
19 if (u == n) return true;
20 vis[u] = 1;
21 bool ret = false;
22 for (int i = 0; i < vec[u].size(); i++)
23 {
24 ret = dfs(vec[u][i]);
25 if (ret) return true;
26 }
27 return false;
28 }
29
30 int read()
31 {
32 char ch = getchar();
33 int x = 0;
34 while (!isdigit(ch)) ch = getchar();
35 while (isdigit(ch)) {x = x*10+(ch-'0');ch=getchar();}
36 return x;
37 }
38
39 bool check(int sta, int las)
40 {
41 for (int i = sta; i <= las; i++)
42 vec[u[i]].push_back(v[i]);
43
44 bool ret = dfs(1);
45
46 for (int i = sta; i <= las; i++)
47 {
48 vis[u[i]] = vis[v[i]] = 0;
49 vec[u[i]].clear();
50 }
51 vis[1] = 0;
52 return ret;
53 }
54
55
56
57 int main()
58 {
59 freopen("road.in","r",stdin);
60 freopen("road.out","w",stdout);
61 n = read(), m = read();
62 for (int i = 0; i < m; i++)
63 {
64 //scanf("%d%d", &u[i], &v[i]);
65 u[i] = read(); v[i] = read();
66 }
67 int now = 0, ans = 0;
68 while (now < m)
69 {
70 int i;
71 for (i = 1; i + now <= m; i <<= 1)
72 if (check(now, now + i - 1)) break;
73 i >>= 1;
74 int nowtmp = now + i;
75 for (; i > 0; i >>= 1)
76 if (nowtmp + i <= m && !check(now, nowtmp + i - 1))
77 nowtmp += i;
78 ans++;
79 now = nowtmp;
80
81 }
82 cout << ans << endl;
83 }
一开始yy了一个自以为正确的贪心
然后花了一个多小时打了暴力
发现暴力只能过n<=10,贪心两组错一组。
GG。。。
后来莫名其妙多过了一个点。。。。
正解
贪心
期望的序列:1 2 3 4 5
5 5 5 5 5
4 3 2 1 0
1 2 3 4 5
f[i][j]血量为i的兵,空了j刀
变形的背包。。
用一个栈维护
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <algorithm>
5 #include <cmath>
6 #include <cstring>
7 using namespace std;
8
9 const int MAXN = 1000 + 10;
10 int a[MAXN];
11 int cnt[MAXN], sta[MAXN], c[MAXN];
12 int f[MAXN][MAXN];
13
14 int main()
15 {
16 freopen("cs.in", "r", stdin);
17 freopen("cs.out", "w", stdout);
18 int T;
19 scanf("%d", &T);
20 for (int num = 1; num <= T; ++num)
21 {
22 int N, maxn = 0;
23 scanf("%d", &N);
24 memset(cnt, 0, sizeof(cnt));
25 memset(c, 0, sizeof(c));
26 memset(f, 0, sizeof(f));
27 for (int i = 1; i <= N; ++i)
28 {
29 scanf("%d", &a[i]); ++cnt[a[i]];
30 maxn = max(maxn, a[i]);
31 }
32 int top = 0;
33 for (int i = 1; i <= maxn; ++i)
34 if (cnt[i] == 0) sta[++top] = i; else
35 {
36 while (cnt[i] > 1 && top > 0) {c[sta[top--]] = i; --cnt[i];}
37 c[i] = i;
38 }
39
40 int ans = 0;
41 for (int i = 1; i <= maxn; ++i)
42 for (int j = 0; j <= i; ++j)
43 {
44 if (j > 0) f[i][j] = f[i - 1][j - 1];
45 if (c[i] != 0 && j + c[i] - i < i)
46 f[i][j] = max(f[i][j], f[i - 1][j + c[i] - i] + 1);
47 ans = max(ans, f[i][j]);
48 }
49 printf("%d\n", ans);
50 }
51 return 0;
52 }
总结
这场考试策略失误太大了。。
T2明明有80的暴力分
还要死刚T3。。。。