首页 > > 程序设计 > C/C++ >

Day4上午解题报告

2018-06-17 21:39:38来源：未知阅读 ()

预计分数：50 +0+0=50

实际分数：50+0+10=60

毒瘤出题人，T3不给暴力分 (* ￣︿￣)

T1

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 */

50分暴力

正解

考虑如何从最终状态转移

贪心思路：

让不是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 }

View Code

T2

一开始没看懂样例

这句话我捉摸了好久，我以为他的意思是在每组里面都要重新标号。。

直到最后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 }

正解

T3

一开始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 }