牛客小白月赛79

 

给定一个数字n，你可以对它进行接下来的操作——

• 选择数字中任意一个数位删除

例如对10​24选择操作百位，数字则变成了124；对1​024选择操作千位，数字则变成了024
我们称一个数字是干净的，当且仅当数字满足以下任意一种情况：

• 这个数字是偶数且不含前导零
• 这个数字为空

请问最少需要进行多少次操作，使得数字nnn变成干净的

输入描述:

第一行包含一个整数  (1≤n≤10^9)，表示这个数字的大小
输入的数字保证不含前导零

输出描述:

输出最少需要的操作次数。

注意，因为一定能使得数字删成空，所以当前数字一定能变成干净的

示例1

输

1024

输出

0

说明

当前数字无需操作便满足条件

 想复杂了，我就说别人做这么快。

直接判断最后一位的偶数就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
signed main()
{
    cin>>s;
    
    int sz=s.size();
    
    int pos=-1;
    
    for(int i=sz-1;i>=0;i--)
    {
        int x=s[i]-'0';
        if(x%2==0)
        {
            pos=i;
            break;
        }
    }
    if(pos==-1)
    {
        cout<<sz<<"\n";
    }
    else
    {
        int pos1=0;
        int ans=0;
        for(int i=0;i<=pos;i++)
        {
            int x=s[i]-'0';
            if(x==0)
            {
                ans++;
            }
            else
            {
                break;
            }
        }
        cout<<ans+sz-1-pos<<"\n";
    }
    return 0;
} 

B、

有n个正整数，现在，你可以选择将其中一些数放进灵异背包中，使得背包里面所有数的总和为偶数且最大，求能得到的最大值是多少？

注意：如果你不将任何数放进灵异背包，此时背包总和为0

输入描述:

第一行包含一个正整数  (1≤n≤10^5)，表示数字的数量
接下来n行包含n个正整数 a1,a2...,an ​ (1≤ai​≤2×10^4)，表示数字的大小

输出描述:

输出一个整数，表示灵异背包所有数的总和为偶数且最大是多少

示例1

输入

3
2
5
6

输出

8

说明

当灵异背包里面有(2,5,6)，此时总和为2+5+6=13，为奇数，不满足条件
当灵异背包里面有(2,6)，此时总和为2+6=8，为偶数，且为最大值

示例2

输入

1
3

输出

0

说明

选择的灵异背包为空，总和为0

 

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int n;
int a[N];
int b[N],cnt;
signed main()
{cin>>n;int sum=0;fp(i,1,n){cin>>a[i];if(a[i]&1){b[++cnt]=a[i];}else{sum+=a[i];}}if(cnt&1){sort(b+1,b+1+cnt);fp(i,2,cnt){sum+=b[i];}}else{fp(i,1,cnt){sum+=b[i];}}cout<<sum<<"\n";return 0;
} 

 C、
 

给你一个长度为n的数列。求这个数列中连续区间的mex乘gcd⁡的最大值是多少？

示例1

输入

5
0 1 2 1 4

输出

3

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int n;
int a[N];
int b[N];
signed main()
{cin>>n;int cnt=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==0)cnt++;b[a[i]]++;}if(cnt==n){cout<<0<<"\n";return 0;}int mmax=0;for(int i=1;i<=n;i++){if(a[i]==0){mmax=max(mmax,a[i-1]);mmax=max(mmax,a[i+1]);}} for(int i=0;i<=n;i++){if(b[i]==0){mmax=max(mmax,i);break;}}cout<<mmax<<"\n";return 0;
} //这个区间是最少需要1个0 
//如果这个区间有1   结果为区间的mex值 
//如果这个区间没有1 结果为区间的gcd值 

 gcd（0，0）=0 qwq

D、

长途是ACM大陆一只快乐的小男孩。今天，他在cf战场上历练，遭遇了TTT波丧尸

长途快被丧尸咬死啦！幸好他手中的两把武器都还有20^{20^{20^{20}}}枚子弹，一枚子弹可以击中一个丧尸

• 武器1——【AC】：每次射击可以发射一枚子弹
• 武器2——【AK-47】：每次射击可以同时朝当前每个丧尸均发射一枚子弹

然而，丧尸有种特殊的能力，每次击中并不会死掉，反而会立刻复制出一个新的丧尸

长途有点绝望。幸好他发现当前这波的所有丧尸都处在一个特殊的圆盘上！这个圆盘被称为圆神，当丧尸的数量是2202^{20}220的倍数时，可以选择启动这个装置，消灭当前这波的全部丧尸！！！
值得注意的是，一共有TTT大波丧尸，只有当一波的丧尸被全部消灭后，下一波的丧尸才会出现，并且手中武器的子弹数也会恢复
情况很紧急，长途请你帮帮他。对于每一波丧尸，最少需要射击多少次才能消灭这一波的所有丧尸。若消耗完所有的子弹都无法消灭这一波的所有丧尸，请输出−1-1−1

输入描述:

第一行包含一个整数TTT，表示长途遭遇了 T (1≤T≤10^5) 波丧尸
对于每波丧尸：
仅输入一行，包含一个正整数 (1≤n≤10^9)，表示当前这波的丧尸数

输出描述:

对于每波丧尸：
仅输出一行，若消耗完所有的子弹都无法消灭这一波的所有丧尸，输出−1；否则输出消灭当前这波的所有丧尸所需要的最少射击次数

示例1

输入

3
1048575
1048576
1

输出

1
0
20

我不理解我写的为什么错了

错误代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int x=1048576;
int a[N];
void solve()
{int n;cin>>n;if(n%x==0){cout<<0<<"\n";return;}int mmin=20;for(int i=n;i<=n+20;i++){int cnt=20;int x=i;while(x%2==0){x/=2;cnt--;}mmin=min(mmin,cnt+i-n);}cout<<mmin<<"\n";
}
signed main()
{int T;cin>>T;while(T--){solve();}return 0;
} //这个区间是最少需要1个0 
//如果这个区间有1   结果为区间的mex值 
//如果这个区间没有1 结果为区间的gcd值 

 正确代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int x=1048576;
int a[N];
void solve()
{int n;cin>>n;if(n%x==0){cout<<0<<"\n";return;}int mmin=20;n%=x; for(int i=n;i<=n+20;i++){int cnt=20;int x=i;while(x%2==0){x/=2;cnt--;}mmin=min(mmin,cnt+i-n);}cout<<mmin<<"\n";
}
signed main()
{int T;cin>>T;while(T--){solve();}return 0;
} //这个区间是最少需要1个0 
//如果这个区间有1   结果为区间的mex值 
//如果这个区间没有1 结果为区间的gcd值 

我后来用的代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int x=1048576;
int a[N];
void solve()
{int n;cin>>n;if(n%x==0){cout<<0<<"\n";return;}int mmin=20;for(int i=0;i<=20;i++){int g=0;int N=n+i;while(N%x!=0)N<<=1,g++;mmin=min(mmin,i+g);}cout<<mmin<<"\n";
}
signed main()
{int T;cin>>T;while(T--){solve();}return 0;
} //这个区间是最少需要1个0 
//如果这个区间有1   结果为区间的mex值 
//如果这个区间没有1 结果为区间的gcd值 

E、

丧尸涌入ACM大陆，幸好宁小夏同学在厕所里面研制出了时光机回到过去，给ACM大陆的封印之门设置了密码锁

• 这个密码锁很特别，密码锁上只有六个按钮，分别是"@" "q" "." "c" "o" "m"（不包含引号）
• 密码长度是给定的，当输入的密码后缀（即密码的最后七位）是"@qq.com"时才会被解锁
• 若输入的密码错误，将需要重新输入密码

例如：我们给定密码的长度是11，如果丧尸有一次输入的密码是"[e-mail]"，则密码错误；如果丧尸有一次输入的密码是"[e-mail]"，则密码正确。即当输入的密码满足"****@qq.com"的格式我们才认为密码是正确的

幸好丧尸十分的笨拙，每一秒钟会等概率随机按下一个按钮，当输入密码错误，需要重新输入密码，它会继续一直按下去，周而复始……直至输入正确

留给ACMer的时间不多了！现在已知密码的长度，大家都想知道丧尸破解密码的期望时间是多少（注：期望时间四舍五入取整数部分）

长途同学经过周密的计算，终于得到了四舍五入后丧尸破解密码的期望时间！同时他使用了mmm个在cf战场上获得的道具——【be-jiangly】，这个道具能够使得当前丧尸破解密码的期望时间变成平方。也就是说，设当前丧尸破解密码的期望时间为xxx，使用单个道具后期望时间变为了x^2

他激动地拿着最终丧尸破解密码的期望时间的草稿纸去找教练，结果被刚从厕所出来的宁小夏同学一不小心弄脏了草稿纸上的第一个数字（个位），/(ㄒoㄒ)/~~记性不好的长途已经忘记了被弄脏的数字是什么了，你能帮帮他吗？

问：被弄脏的个位数字是什么，如果丧尸破解密码的时间趋于正无穷，请输出−1

输入描述:

输入两个整数  n (1≤n≤10^9)， (0≤m≤10^9)，分别表示密码的长度和使用道具的数量

输出描述:

若丧尸破解密码的时间趋于正无穷，请输出−1；否则请输出被弄脏的数字是什么

示例1

输入

7 1

输出

4

说明

可怜巴巴的长途已经忘记怎么算出来的结果了，所以没有样例解释……

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
string s; 
int x=1048576;
int n,m;
void solve()
{cin>>n>>m;if(n<7){cout<<-1<<"\n";return;}int ans=279936;ans*=n;ans%=10;m=min(m,2ll);while(m--){ans=ans*ans%10;}cout<<ans<<"\n";return;
}
signed main()
{solve();return 0;
} //这个区间是最少需要1个0 
//如果这个区间有1   结果为区间的mex值 
//如果这个区间没有1 结果为区间的gcd值 

 如果完成一件事情的概率是 1/7，那么完成该事情的期望时间可以通过期望的概念计算得出。

几何分布描述了进行一系列独立试验，直到成功为止所需的试验次数。对于成功概率为 1/7 的几何分布，其期望值可以通过公式 E(X) = 1/p 来计算，其中 X 是完成该事情所需的时间，p 是完成该事情的概率。

因此，完成一件事情的期望时间为 E(X) = 1 / (1/7) = 7。

所以，完成一件事情的期望时间是 7。

可以类推到本题。