A、E、F、G题解
A.再见603
简单模拟,考虑到只有6，0,3或者60，3可以拼接得到603，并且两个操作顺序对答案不干扰，所以任意先执行有一个再执行另一个即可
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 1000010;
int cnt[N];
int n;
void solve(){
cin >> n;
while(n--){
int x; cin >> x;
cnt[x]++;
}
int ans = cnt[603];
int t = min({cnt[6],cnt[0],cnt[3]});
cnt[3] -= t;
ans = ans + t + min({cnt[60],cnt[3]});
cout << ans << endl;
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
E.零域
关于后缀0的数量我们可以知道其实是看数分解质因数之后2和5的约数中最少的数量是多少，同时注意到这个阶乘那么2和5中最少的数量一定是5，如何求解有多少个5呢，我们可以考虑除法，如果我把x除以5就可以得到1-n中有多少个数是包含一个5为约数的，然后我对当前这个数接着除以5就可以得到有多少个数中包含两个5，以此类推便可以得到所有的包含5的数量，同时可以注意到明显的具有二分性质，我们考虑使用二分,由于每5个数会有一个5所以答案最多是5个数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
void solve(){
LL n,m;
cin >> n >> m;
auto get = [&](LL x){
LL sum = 0;
while(x){
sum += x / 5;
x /= 5;
}
return sum;
};
auto check = [&](LL x){
return get(x) >= m;
};
LL l = 1, r = n;
while(l<r){
LL mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(get(l) == m){
vector<LL> v;
for(LL i=l;i<=min(l+4,n);i++){
if(get(i) != m) break;
v.push_back(i);
}
cout << v.size() << endl;
for(auto&x:v) cout << x << ' ';
cout << endl;
}
else{
cout << -1 << endl;
}
}
int main(){
ios
int T = 1; cin >> T;
while(T--){
solve();
}
return 0;
}
F.神秘三人组
可以注意到下标是需要满足单调递增的，我们对式子进行推理可以得到其实是一个以一个数开头的公比为p的等比数列同时长度为3，我们考虑枚举中间的数，假设为x,这样我们只需要看前面数中x/k,后面数为x*k的数量即可，我们可以用桶去记录前后的数量同时变化即可，详情见代码
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
typedef long long LL;
const int N = 200010;
LL t,n,m;
map<LL,LL> mp1,mp2;
LL a[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
mp1[a[i]]++;// 表示后缀
}
LL ans=0;
for(int i=1;i<=n;i++){
LL x=a[i];
mp1[x]--;
if(x%m==0 and mp1[x*m] and mp2[x/m]){
ans+=mp1[x*m]*mp2[x/m];
}
mp2[x]++;
}
cout<<ans<<endl;
return ;
}
int main (){
ios
solve();
return 0;
}
可以注意到如果存在有大于k个正整数我们一定是会对其进行操作，否则我们只需要输出最大数即可，同时我们可以发现模数其实比最大的数还要小所以说我们输出最大数的时候也要注意取模
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
const int mod = 998244353;
int n,k;
void solve(){
cin >> n >> k;
priority_queue<int> q;
while(n--){
int x; cin >> x;
if(x != 0) q.push(x);
}
if(q.empty()){
cout << 0 << endl;
return ;
}
if((int)q.size() < k){
cout << (q.top()%mod) << endl;
return ;
}
LL ans = 1;
while(k--){
int t = q.top(); q.pop();
ans = ans * t % mod;
}
cout << ans << endl;
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
