日常训练(1)

6月9日：牛客算法周练10 https://ac.nowcoder.com/acm/contest/5986#question

B题：暴力出奇迹

思路：采用二进制贪心,如果当前位置贡献为连续1的则记录答案。和线性基的想法类似,选择对于当前位存在贡献的一位。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1e5+10;
 6 typedef long long ll;
 7 int main()
 8 {
 9     int a[maxn],n;
10     cin>>n;
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d",&a[i]);
14     }
15     ll ans=0;
16     for(int i=0;i<20;i++)
17     {
18         ll tmp=a[1],sum=0;
19         for(int j=1;j<=n;j++)
20         {
21             if(a[j]>>i&1)
22             {
23                 tmp&=a[j];
24                 sum+=a[j];
25                 ans=max(ans,tmp*sum);
26             }
27             else
28             {
29                 tmp=a[j+1];
30                 sum=0;
31             }
32         }
33     }
34     printf("%lld",ans);
35     return 0;
36 }

F题：树上求和

思路：每条边被计算的数目等于这条边两边的节点的个数之积。然后按照积这个权值进行排序，依次赋值1，2 ......n-1

所以我们只要统计每个边的左侧和右侧有多少顶点就可以。

这里的DFS很不一样...

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e5+10;
 8 
 9 vector<ll> q[maxn];
10 vector<ll> p;
11 ll n; 
12 
13 ll dfs(ll u,ll v)
14 {
15     ll sum=1;
16     for(int i=0;i<q[u].size();i++)
17     {
18         if(q[u][i]!=v)
19         {
20             sum+=dfs(q[u][i],u);
21         }
22     }
23     p.push_back(sum*(n-sum));
24     return sum;
25 }
26 int main()
27 {
28     ll a,b;
29     cin>>n;
30     for(int i=1;i<n;i++)
31     {
32         scanf("%d%d",&a,&b);
33         q[a].push_back(b);
34         q[b].push_back(a);
35     }
36     dfs(1,-1);
37     sort(p.begin(),p.end());
38     ll s=0,l=n-1;
39     for(int i=1;i<p.size();i++)
40     {
41         s+=p[i]*l;
42         l--;
43     }
44     printf("%lld",s);
45     return 0;
46 }

6月12日：

A题：UVALive - 3644 X-Plosives 链接：https://vjudge.net/problem/UVALive-3644

题意：给定一些组合，以”-1“结束，如果出现类似”A+B""B+C""A+C"这样的环路组合，那么此时就是危险的。按输入顺序，判断加入一个组合后是否是危险状态，如果是，那么就拒绝这个组合加入（装车）。统计拒绝的个数。

思路：判断是否存在环路的问题，可以使用并查集。

注意这里的多组输入的处理问题。

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=1e5+10;
 5 int f[maxn];
 6 int find(int x)
 7 {
 8     if(f[x]==x)
 9     return x;
10     return find(f[x]);
11 }
12 int main()
13 {
14     int n;
15     int x,y,ans=0;
16     while(~scanf("%d",&x))//多组输入 
17     {
18         ans=0;
19         for(int i=1;i<=maxn;i++)
20         {
21         f[i]=i;
22         }
23         while(x!=-1)
24         {
25         scanf("%d",&y);
26         x=find(x);
27         y=find(y);
28         if(x==y) 
29         ans++;
30         else
31         f[y]=x;
32         scanf("%d",&x);
33         }
34     printf("%d
",ans);
35 }
36     return 0;
37 }

B题： UVALive - 3027 Corporative Network 链接：https://vjudge.net/problem/UVALive-3027

题意：n个节点，若干次询问，I x y表示从x连一条边到y，权值为｜x-y｜%1000；E x表示询问x到x所指向的终点的距离。

题意也太难理解了。。。

思路：带权并查集。在本题，节点到根节点的值需要随时更新，用一个数组记录到根节点的距离。在查询时更新节点的值。

代码如下：

 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 const int maxn=20100;
 5 
 6 int f[maxn],dis[maxn];
 7 int n;
 8 
 9 int find(int x)
10 {
11     if(f[x]==x)
12         return x;
13     int tmp=f[x];
14     f[x]=find(f[x]);
15     dis[x]=dis[x]+dis[tmp];//求x到根节点的距离。注意顺序，否则dis[x]就不能代表x到新根的距离了
16     return f[x];
17 }
18 void Uion(int a,int b)
19 {
20     int ra=find(a);
21     int rb=find(b);
22     if(ra!=rb)
23     {
24         f[ra]=rb;
25         dis[ra]=(abs(a-b)%1000-dis[a]+dis[b]);//向量运算，得出ra到rb的距离
26     }
27 }
28 
29 int main()
30 {
31     int t;
32     scanf("%d",&t);
33     while(t--)
34     {
35         scanf("%d",&n);
36         for(int i=1;i<=n;i++)
37         {
38             f[i]=i;
39             dis[i]=0;
40         }
41         getchar();
42         char ch;
43         while(scanf("%c",&ch))
44         {
45             if(ch=='O')
46             break;
47             if(ch=='I')
48             {
49                 int a,b;
50                 scanf("%d %d",&a,&b);
51                 Uion(a,b);
52                 getchar();
53             }
54             else
55             {
56                 int a;
57                 scanf("%d",&a);
58                 find(a);//注意这里，查询的时候也要压缩一下，因为uion操作会更新dis数据
59                 printf("%d
",dis[a]);
60                 getchar();
61             }
62         }
63     }
64     return 0;
65 }

6月13日：

B题：Lose it! CodeForces - 1176C 链接：https://vjudge.net/problem/CodeForces-1176C

题意：一次输入两个数，代表这两个数之间可以发生化学反应，此时危险值*2，问最大的危险值是多少。

思路：一个数可能与多个数发生反应，而另外多个数可能和这个数发生反应，两两之间又多对多，想到利用并查集来解决。设定根节点，与根节点在一个集合中的元素可以和根节点发生反应，此时*2，统计即可。

注意最终结果要开long long

代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int f[200];
 6 int find(int x)
 7 {
 8     if(f[x]==x)
 9     return x;
10     else
11     return find(f[x]);
12 }
13 int main()
14 {
15     int x,y,n,m;
16     long long ans=1;
17     cin>>n>>m;
18     for(int i=1;i<=n;i++)
19     f[i]=i;
20     for(int i=1;i<=m;i++)
21     {
22         scanf("%d%d",&x,&y);
23         x=find(x);
24         y=find(y);
25         f[y]=x;
26     }
27     for(int i=1;i<=n;i++)
28     {
29         if(f[i]!=i)//根节点与自己不可能发生反应 
30         ans*=2;
31     }
32     printf("%lld",ans);
33     return 0;
34 }

A题：Lose it! CodeForces - 1176C 链接：https://vjudge.net/problem/CodeForces-1176C

题意：将 $[4, 8, 15, 16, 23, 42]$

$[4, 8, 15, 16, 23, 42]$

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 int n,m,vis[10];
 8 map<int,int>mp;
 9 int main()
10 {
11     while(cin>>n)
12     {
13         mp[4]=1;
14         mp[8]=2;
15         mp[15]=3;
16         mp[16]=4;
17         mp[23]=5;
18         mp[42]=6;
19         memset(vis,0,sizeof(vis));
20         for(int i=1;i<=n;i++)
21         {
22             cin>>m;
23             if(mp[m]==1)
24                 vis[1]++;
25             else if(vis[mp[m]-1]>0)
26             {
27                 vis[mp[m]-1]--;
28                 vis[mp[m]]++;
29             }
30         }
31         cout<<n-vis[6]*6<<endl;
32     }
33     return 0;
34 }

$[4, 8, 15, 16, 23, 42]$