最后一题 最后一分钟debug 才出来,没交上,好菜啊..
c. 4949. 末尾连续0【枚举】
类似题: 3507. 阶乘的末尾0
题目理解:
答案 末尾连续0 取决于 min(cnt2, cnt5) 【老知识了】
观察到数据范围 $ 1≤m≤10^5 $, 可以考虑 枚举 cnt2 和 cnt5 的前缀和,时间复杂度:O(n * logn)
debug:注意 计算 cnt2 和 cnt5 的数据范围 要比 m 大 【可以 开到 1e6】
y总代码,更简洁
二分,O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int f(int n, int p) // 满足 单调性,可以二分,O(n)在于 输出答案,二分 O(logn * logn(求数量))
{
int res = 0;
while (n) res += n / p, n /= p;
return res;
}
int lower_bound(int m)
{
int l = 1, r = 5e5;
while (l < r)
{
int mid = l + r >> 1;
if (f(mid, 5) >= m) r = mid;
else l = mid + 1;
}
return r;
}
int main()
{
int m;
scanf("%d", &m);
int l = lower_bound(m), r = lower_bound(m + 1) - 1;
printf("%d\n", r - l + 1);
for (int i = l; i <= r; i ++ )
printf("%d ", i);
return 0;
}
// 作者:yxc
// 链接:https://www.acwing.com/activity/content/code/content/6234217/
// 来源:AcWing
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码1:
// 枚举 O(n logn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int f(int n, int p) // 统计因子数量: cnt = n / p + (n / 2p) * 2 + ..
{
int res = 0;
while (n) res += n / p, n /= p;
return res;
}
int main()
{
int m;
scanf("%d", &m);
vector<int> res;
for (int i = 1; ; i ++ )
{
int t = f(i, 5); // 5的数量 比2 少
if (t > m) break;
else if (t == m) res.push_back(i);
}
printf("%d\n", (int)res.size());
for (int x: res)
printf("%d ", x);
return 0;
}
// 作者:yxc
// 链接:https://www.acwing.com/activity/content/code/content/6234217/
// 来源:AcWing
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000010;
int m;
int d2[N], d5[N];
vector<int> res;
bool f = 1;
void get(int x)
{
int t = x;
int cnt2 = 0, cnt5 = 0;
while(x >= 5 && x % 5 == 0) x /= 5, cnt5 ++ ;
while(x >= 2 && x % 2 == 0) x /= 2, cnt2 ++ ;
d2[t] = d2[t - 1] + cnt2; // debug: x 修改了
d5[t] = d5[t - 1] + cnt5;
if(min(d2[t], d5[t]) == m) res.push_back(t);
else if(min(d2[t], d5[t]) > m) f = false;
// printf("x = %d, cnt2 = %d, cnt5 = %d\n", t, d2[t], d5[t]);
}
int main()
{
cin >> m;
for(int i = 1;i <= 1e6;i ++ ){
get(i);
if(!f) break;
}
if(res.size() == 0) cout << 0;
else {
cout << res.size() << endl;
for(auto c : res) cout << c << ' ';
}
return 0;
}
b. 4948. 大乘积【枚举】
观察到 题意:并且这 n 个数的总长度不超过 $ 10^5 $ , 就知道 可以用 枚举
debug:题意:至少 n−1 个数是美丽数 【说明 全是美丽数 也是可以的, 例如 1 1 1 => 1】【没搞定边界 wa 2次】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
bool check(string& s)
{
bool f = true;
if(s[0] != '1') f = false;
for(int i = 1;i < s.size();i ++ ){
if(s[i] != '0') f = false;
}
return f;
}
int main()
{
cin >> n;
// 题意理解:至少 N-1个美丽数,也可能 全是 美丽数 == 至少!
string b = "";
int d = 0;
bool f = false;
for (int i = 0; i < n; i ++ )
{
string s;
cin >> s;
if(s == "0") {
f = true;
}else if(s == "1"){
}else if(check(s)){ // 是 美丽数
d += s.size() - 1;
}else{
b = s;
}
}
if(f) cout << "0";
else {
if(b == "") {
if(d) cout << "1" + string(d, '0');
else cout << "1"; // debug: 1 1 1 => 1
}
else{
cout << b + string (d, '0');
}
}
return 0;
}
a. 4947. 大整数 【字符串构造】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
cout << string(n, k + '0');
return 0;
}