牛客周赛 Round 7
目录
A 游游的you矩阵
题目：
题解：
AC 代码：
B 游游的01串操作
题目：
题解：
AC 代码：
C 游游的正整数
题目：
题解：
AC 代码：
D 游游的选数乘积
题目：
题解：
AC 代码：
A 游游的you矩阵
题目：
游游拿到了一个字符矩阵。她想知道有多少个2*2的子矩阵同时包含了'y'、'o'和'u'这三种字符？
输入描述:
第一行输入两个正整数n和m，代表矩阵的行数和列数。 接下来的n行，每行输入一个长度为m的、仅由英文小写字母组成的字符串，代表游游拿到的矩阵。 1≤n,m≤1e3输出描述:
一个整数，代表同时包含了'y'、'o'和'u'三种字符的2*2的子矩阵数量。
输入
3 3
yuo
uiy
our输出
1只有一个2*2的子矩阵同时包含了'y'、'o'和'u'三种字符。
题解：
两层for循环遍历求解
AC 代码：
#include<bits/stdc++.h>
using namespace std;
int d[4][2]={0,0,0,1,1,0,1,1};
void solve()
{int m,n,a=0,b=0,c=0,sum=0;cin>>n>>m;string x[1001];for(int i=0;i<n;i++){cin>>x[i];}for(int i=0;i<n-1;i++){for(int j=0;j<m-1;j++){a=0,b=0,c=0;for(int k=0;k<4;k++){if(x[i+d[k][0]][j+d[k][1]]=='y')a++;else if(x[i+d[k][0]][j+d[k][1]]=='o')b++;else if(x[i+d[k][0]][j+d[k][1]]=='u')c++;}if(a&&b&&c)sum++;}}cout<<sum<<endl;
}
signed main()
{int t=1;//cin>>t;while(t--)solve();return 0;
}B 游游的01串操作
题目：
游游拿到了一个01串（仅由字符'0'和字符'1'构成的字符串）。游游每次操作可以选择对其中一个字符取反（即1变0，或者0变1），对第 iii 个字符取反的代价为 iii。（代价从1开始计算，即第一个字母的代价是1）
游游希望最终字符串任意两个相邻的字符都不相同，她想知道花费代价之和的最小值的多少？
输入描述:
一行仅由 '0' 、 '1' 组成的字符串，长度不超过 100000。
输出描述:
一个整数，代表代价之和的最小值。
样例 1
输入
11101输出
2说明
把第二个字母取反，代价为2。字符串变成10101。
样例 2
输入
0111111输出
13说明
取反第1、2、4、6个字符，总代价为1+2+4+6=13.
题解：
分别判断从0开始和从1开始，输出最小操作
AC 代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{int m,n,sum=0,num=0,l;string x;cin>>x;l=x.size();for(int i=0;i<l;i++){if(((x[i]-'0')&1)==(i&1))num+=i+1;elsesum+=i+1;}cout<<min(sum,num)<<endl;
}
signed main()
{int t=1;//cin>>t;while(t--)solve();return 0;
}C 游游的正整数
题目：
游游拿到了一个正整数a，她每次操作可以选择将a加上x，但必须满足l≤x≤r。游游希望操作结束后a恰好等于b。游游想知道，最少需要多少次操作，最多需要多少次操作？
输入描述:
共有t组询问。 每组询问输入四个正整数a,b,l,r。 1≤t≤1e4 1≤l≤r≤1e9 1≤a≤b≤1e9输出描述: 对于每组询问，输出一行答案。 如果无论如何都不能让a等于b，则输出-1。 否则输出两个整数，分别代表最少操作次数和最多操作次数。
示例1
输入
3
1 6 2 5
1 4 2 2
2 10 2 6输出
1 2
-1
2 4说明
第一组询问，操作一次的方案：直接使a加5。操作2次的方案：先加2再加3。 第二组询问，由于只能加2，显然无法使得1变成4。 第三组询问，操作2次的方案：先加3再加5（方案不唯一）。操作4次的方案：加4次2。
题解：
算出a和b的差值，分别除以 l 向下取整为maxx和 除以 r向上取整为minn，判断两者大小，如果maxx小于minn，输出-1，否则输出maxx和minn
AC 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int a,b,l,r;int maxx,minn;cin>>a>>b>>l>>r;maxx=floor((b-a)*1.0/l);minn=ceil((b-a)*1.0/r);if(maxx<minn)cout<<"-1"<<endl;elsecout<<minn<<" "<<maxx<<endl;return ;
}
signed main()
{int t=1;cin>>t;while(t--)solve();return 0;
}D 游游的选数乘积
题目：
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
游游拿到了一个数组，她准备在其中选择两个数，使得乘积的末尾至少有xxx个0。游游想知道，至少有多少种不同的取数方法？
输入描述:
第一行输入两个正整数n和x，代表数组的大小以及乘积末尾0的数量。 第二行输入n个正整数ai，代表游游拿到的数组。 1≤n,x≤1e5 1≤ai≤1e9输出描述:
输出一个整数，代表游游选择的方案数。
示例1
输入
5 2
3 5 50 2 80输出
3说明
5*80=400，末尾有2个0。 50*2=100，末尾有2个0。 50*80=4000，末尾有3个0。 有以上3种方案满足乘积至少有2个0。
题解：
计算每个数ai分别被2，5整除的次数x,y,则a[x][y]+1； 2、枚举x,y(x,y<32),计算最小值大于等于目标值。
AC 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<pair<int,int>,int> m;
void solve()
{int n,x,a,sum=0,num=0,ans=0;cin>>n>>x;for(int k=1;k<=n;k++){cin>>a;sum=0,num=0;while(a%5==0){sum++;a/=5;}while(a%2==0){num++;a/=2;}for(int i=x;i>=max(x-sum,0ll);i--){for(int j=x;j>=max(x-num,0ll);j--){ans+=m[{i,j}];}}m[{min(x,sum),min(x,num)}]++;}cout<<ans<<endl;
}
signed main()
{int t=1;//cin>>t;while(t--)solve();return 0;
}下一篇：逆元（求乘法逆元的几种方法）
推荐音乐：if We Ever Broke Up