牛客周赛 Round65 补题DEF

目次
D.医生
 E.降温（easy)
 F.降温（hard）

---

D.医生

   

  

  思绪：从范围来看m和k，可知我们可以将每一个字符串当作一个二进制数，将他们转换成十进制后，举行深度搜索，每种药有可选或不选两种环境，当搜到末了一种药时，我们只需将病人的十进制数与我们所选的药所构成的十进制数举行与运算，若末了效果与病人的十进制数相称，则阐明我们所选的药包罗病人的这些病，然后我们可以再加个剪枝，假如当前选的药数已经大于如今的最小值可以直接回溯。
Code:

1. int n,m,ans;
2. int medicine[15],people[10005],k;
4. void dfs(int depth,int num,int medi,int id)
5. {
6.     if(num>=ans) return ;
7.     if(depth==k+1)
8.     {
9.         if((medi&people[id])==people[id])
10.         {
11.             ans=min(ans,num);
12.         }
13.         return ;
14.     }
16.     dfs(depth+1,num+1,medi|medicine[depth],id);
17.     dfs(depth+1,num,medi,id);
19.     return ;
20. }
21. void solve()
22. {
23.    cin>>n>>m;
24.    for(int i=1;i<=n;i++)
25.    {
26.     for(int j=1;j<=m;j++)
27.     {
28.         char c;cin>>c;
29.         int x=c-'0';
30.         if(x)
31.         {
32.             people[i]|=(1<<(m-j));
33.         }
34.     }
35.    }
37.    cin>>k;
38.    for(int i=1;i<=k;i++)
39.    {
40.     for(int j=1;j<=m;j++)
41.     {
42.         char c;cin>>c;
43.         int x=c-'0';
44.         if(x)
45.         {
46.             medicine[i]|=(1<<(m-j));
47.         }
48.     }
49.    }
51.    for(int i=1;i<=n;i++)
52.    {
53.        ans=1e18;
54.        dfs(1,0,0,i);
55.        if(ans==1e18) cout<<-1<<endl;
56.        else cout<<ans<<endl;
57.    }
58. }

复制代码

 E.降温（easy)

   

  

  思绪：贪心，只有当前一项比后一项大于便是x的时间才算寒潮，以是假如要使寒潮天数最大，我们要尽大概使a变大，如许a-a[i+1]>=x的概率才更大，假如第一个数为-999，则a[1]=50，其他数假如a!=-999，a[i-1]-a>=x则寒潮天数+1，假如a=-999，若a[i-1]-x>=-50，则当a=a[i-1]-x时寒潮天数增长，反之a=50。求最小天数也一样，我们尽大概使a[i-1]-x高出-50这个界限，即a尽大概小。
Code:

1. constexpr int N=1005,mod=998244353;
3. int a[N],b[N],n,x;
5. void solve()
6. {
7.    cin>>n>>x;
8.    int ma=0;
9.    for(int i=1;i<=n;i++)
10.    {
11.     cin>>a[i];
12.     b[i]=a[i];
13.     if(i==1)
14.     {
15.         if(a[i]==-999)
16.         a[i]=50;
17.         continue;
18.     }
19.     if(a[i]!=-999)
20.     {
21.         if(a[i-1]-a[i]>=x)
22.             ma++;
23.     }
24.     else
25.     {
26.         if(a[i-1]-x>= -50)
27.         {
28.             ma++;
29.            a[i]=a[i-1]-x;
30.         }
31.         else a[i]=50;
32.     }  
33.    }
34.    cout<<ma<<' ';
35.    int mi=0;
36.    for(int i=1;i<=n;i++)
37.    {
38.     if(i==1)
39.     {
40.         if(b[i]==-999)
41.         b[i]=-50;
42.         continue;
43.     }
44.     if(b[i]!=-999)
45.     {
46.         if(b[i-1]-b[i]>=x) mi++;
47.     }
48.     else
49.     {
50.         if(b[i-1]-x >= -50)
51.         {
52.             b[i]=b[i-1]-x+1;
53.         }
54.         else b[i]=-50;
55.     }
56.    }
57.    cout<<mi;
58. }

复制代码

 F.降温（hard）

   

  思绪：与E题思绪一样，改下数据范围即可。
Code:

1. constexpr int N=1e5+5,mod=1e9+7,spj=-999999999;
2. constexpr int minn=-5*1e8,maxn=5*1e8;
3. int a[N],b[N],n,x;
5. void solve()
6. {
7.   cin>>n>>x;
8.   int ma=0;
9.   for(int i=1;i<=n;i++)
10.   {
11.     cin>>a[i];
12.     b[i]=a[i];
13.     if(i==1)
14.     {
15.         if(a[i]==spj)
16.         {
17.             a[i]=maxn;
18.         }
19.         continue;
20.     }
21.     if(a[i]!=spj)
22.     {
23.         if(a[i-1]-a[i]>=x) ma++;
24.     }
25.     else
26.     {
27.         if(a[i-1]-x>=minn)
28.         {
29.             a[i]=a[i-1]-x;
30.             ma++;
31.         }
32.         else a[i]=maxn;
33.     }
34.   }
35.   cout<<ma<<' ';
36.   int mi=0;
37.   for(int i=1;i<=n;i++)
38.   {
39.     if(i==1)
40.     {
41.         if(b[i]==spj)
42.             b[i]=minn;
43.         continue;
44.     }
45.     if(b[i]!=spj)
46.     {
47.         if(b[i-1]-b[i]>=x)
48.             mi++;
49.     }
50.     else
51.     {
52.         if(b[i-1]-x>=minn) b[i]=b[i-1]-x+1;
53.         else b[i]=minn;
54.     }
55.   }
56.   cout<<mi;
57. }

复制代码