牛客小白月赛92

A

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    cout<<8*n<<'\n';
}

B

本题其实非常容易，由于不能进行左右移动，只需要先判断能不能全拿了，在判断以1的代价去拿，如果能够左右移动，解法大概率就是连通块了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
char a[6][1010];
int n,h;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int cnt[4030];
int num[4030];
int cnt_=0;
int num_=0;
int sum;
int main()
{
    cin>>n>>h;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
for(int i=1;i<=5;i++)
{
    if(i==1||i==3||i==5)
    {
        continue;
    }
for(int j=1;j<=n;j++)
{
if(i==2)
{
    if(a[i][j]=='*'&&a[i-1][j]=='*')
    {
if(h>=2)
{
h-=2;
ans+=2;
a[i][j]='.';
a[i-1][j]='.';
}
else
{
    cout<<ans+h;
    return 0;
}
    }
    else if(a[i][j]=='*')
    {
        if(h>=1)
        {
            h-=1;
            ans+=1;
            a[i][j]='.';
        }
        else
{
    cout<<ans+h;
    return 0;
}
    }
}

if(i==4)
{
    if(a[i][j]=='*'&&a[i+1][j]=='*')
    {
if(h>=2)
{
h-=2;
ans+=2;
a[i][j]='.';
a[i+1][j]='.';
}
else
{
    cout<<ans+h;
    return 0;
}
    }
    else if(a[i][j]=='*')
    {
        if(h>=1)
        {
            h-=1;
            ans+=1;
            a[i][j]='.';
        }
        else
{
    cout<<ans+h;
    return 0;
}
    }
}


}
}



for(int j=1;j<=n;j++)
{
    if(a[1][j]=='*')
    {
      if(h>=2)
{
h-=2;
ans+=1;
a[1][j]='.';
}
else
{
    cout<<ans;
    return 0;
}  
    }
}
for(int j=1;j<=n;j++)
{
    if(a[5][j]=='*')
    {
      if(h>=2)
{
h-=2;
ans+=1;
a[5][j]='.';
}
else
{
    cout<<ans;
    return 0;
}  
    }
}

   cout<<ans; 
}

如果可以左右移动解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
char a[6][1010];
int n,h;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int cnt[4030];
int num[4030];
int cnt_=0;
int num_=0;
int sum;
int main()
{
    cin>>n>>h;
    h--;
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
   for(int i=1;i<=5;i++)
   {
for(int j=1;j<=n;j++)
{
    if(a[i][j]!='*')
    {
        continue;
    }
   // cout<<i<<' '<<j<<'\n';
    a[i][j]='.';
    queue<pair<int,int>>q;
    q.push({i,j});
    int ans=1;
    bool falg=0;
        if(i==2||i==4)
        {
            falg=1;
        }
        while(!q.empty())
        {
        pair<int,int> h=q.front();
        q.pop();
       for(int k=0;k<=3;k++)
    {
           int tx=h.first+dx[k],ty=h.second+dy[k];
           if(tx<1||tx>5||ty<1||ty>n)
           {
               continue;
           }
           if(a[tx][ty]=='*')
           {
        if(tx==2||tx==4)
        {
            falg=1;
        }
               ans++;
               q.push({tx,ty});
               a[tx][ty]='.';
           }
      }    
        }
if(falg)
{
sum+=ans;
}
else
{
    num[++num_]=ans;
}
    
}
   }
   sort(num+1,num+1+num_);
   if(h<=sum)
   {
       cout<<h;
   } 
    else
    {
        h-=sum;
        for(int i=1;i<=num_;i++)
        {
            h--;
            if(h-num[num_]>=0)
            {
                h-=num[num_];
                sum+=num[num_];
            }
            else
            {
                sum+=h;
                break;
            }
        }
        cout<<sum;
    }
    
    
    
    
}

C

3的20次方已经大于1e9了，因此只需要开一个map就可以，一个记录时间维度，一个记录数字维度，值就是次数

很容易的模拟，不过一开始也要算，本人因为一开始没有算进去导致wa1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//每次都要看获得x最大有多少
//获得两株3向上取整（+3-1）/3就是向上取整
//10的9次方最多可以除多少次3呢？
//最多除20次，因此直接开一次数组直接去存储
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
using ll=long long;
map<pair<int,ll>,ll>mp;
ll n,x;

ll a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    mp[{0,a[i]}]++;
}
cin>>x;
    for(int j=1;j<=n;j++)
    {
        ll cnt=1;
        for(int i=1;i<=20;i++)
{
        cnt*=2;
        if(((a[j]+2)/3)==0)
        {
            continue;
        }
        mp[{i,(a[j]+2)/3}]+=cnt;
        a[j]=(a[j]+2)/3;
}
    }
    ll maxn=0;
    for(int i=0;i<=20;i++)
    {
        maxn=max(maxn,mp[{i,x}]);
    }
    cout<<maxn;
}

D

推个式子，然后二分，最后小范围穷举一下

式子大概就是后一项减去前一项，发现有递增性质，然后直接求刚刚好大于0和刚刚好小于0那个时候，具体答案还得是穷举啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
using ll=long long;
ll a[N];
int n;
bool check(ll x)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=(2*x+1-2*i)*a[i];
    }
    return ans<=0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int l=0;
    int r=n+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }
    ll ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=(l-i)*a[i]*(l-i);
        }
        ll sum=0;
        l++;
           for(int i=1;i<=n;i++)
        {
            sum+=(l-i)*a[i]*(l-i);
        }
                for(int i=1;i<=n;i++)
        {
            ans+=(l-i)*a[i]*(l-i);
        }
        ll res=0;
        l-=2;
           for(int i=1;i<=n;i++)
        {
            res+=(l-i)*a[i]*(l-i);
        }
        ll tmp=0;
        for(int i=1;i<=n;i++)
        {
            tmp+=(r-i)*a[i]*(r-i);
        }
        

    ans=min(min(ans,tmp),min(sum,res));
    cout<<ans;
    
}

E

很朴素的思路，赛时没时间写了

代码很明确：分为不使用这一块，不使用魔法，和使用魔法三种情况。

然后三维dp即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
using ll=long long;
using PII=pair<ll,ll>;
ll n,m;
ll x[N];
ll y[N];
int main()
{
cin>>n>>m;
for(int  i=1;i<=n;i++)
{
    cin>>x[i]>>y[i];
}
vector<vector<vector<ll>>>dp(n+1,vector<vector<ll>>(m+1,vector<ll>(2,LONG_MAX/2)));
//dp[i][j][0]表示融化到第i个下标融化j个矿石所需要的最短时间（还没使用过魔法）
//同理dp[i][j][1]则是
dp[0][0][1]=dp[0][0][0]=0;
for(int i=1;i<=n;i++)
{
    for(int j=0;j<=m;j++)
    {
        dp[i][j][0]=dp[i-1][j][0];
        dp[i][j][1]=dp[i-1][j][1];
        //不使用魔法
        dp[i][j][1]=min(dp[i][j][1],dp[i-1][max(j-x[i],0ll)][1]+y[i]);
        dp[i][j][0]=min(dp[i][j][0],dp[i-1][max(j-x[i],0ll)][0]+y[i]);
        //使用魔法
        dp[i][j][1]=min(dp[i][j][1],dp[i-1][max(j-2*x[i],0ll)][0]+y[i]/2);
    }
}
cout<<min(dp[n][m][1],dp[n][m][0]);
return 0;
}