problem A 最小的数字
题目大意:给一个n,求出最小整数x,使得x >= n且x可以被3整除
思路:太简单了,略
数据范围:0 <= n <= 1e9
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int n; cin >> n;
int k = n / 3;
if (n % 3 == 0) cout << k * 3 << endl;
else cout << k * 3 + 3 << endl;
return 0;
}
problem B 优美的GCD
题目大意:给出一个n,求两个不同的数使得它们的gcd是n
思路:一个等于n,一个等于2 * n即可
数据范围 1 <= n <= 1e6
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
cout << n << " " << 2 * n << endl;
}
return 0;
}
problem C 优美的序列
题目大意:给定一个序列,对其进行任意操作使其变成优美的序列,优美序列满足对于任意i, j而言abs(a[i] - a[j]) >= abs(i - j),输出优美序列
思路:个人认为非常像codeforces 860 DIV2 A. Showstopper,采用贪心的策略,越大的越应该放到后面
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1);
bool suc = true;
for (int i = 1; i <= n; i ++)
{
for (int j = i; j <= n; j ++)
{
if (abs(a[i] - a[j]) < abs(i - j))
{
suc = false;
break;
}
}
if (!suc) break;
}
if (suc) for (int i = 1; i <= n; i ++) cout << a[i] << " ";
else cout << -1;
cout << endl;
}
return 0;
}
赛后补题
problem D&E Kevin喜欢零
题目大意:给出一个序列a和一个整数k,对于一个区间[l, r]而言,x = al * a(l + 1) * a(l + 2) * … * ar,x后缀0的个数刚好为k,求满足要求的区间个数
思路:对于D而言,可以预处理前缀积,然后二分求答案,重点写一下E的,看题解都看了大半天,难受呜呜呜,首先对于x而言,我们可以得到x = p * qmi(10, k) p不能被10整除,因此得到x = p * qmi(2, k) * qmi(5, k),我们令ca[i]等于ai中质因子2的数量,cb[i]等于ai中质因子5的数量, 我们不难发现,假设n个数的乘积为q, k = min(ca[q], cb[q]),例如125 * 8中k等于3,因此我们预处理出ca的前缀和和cb的前缀和,然后枚举一下每一个边界l会有多少中情况,接着将l除去,再看后面的边界(注意,除去l的操作非常神奇,头一次见)
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, k;
int a[N];
int ca[N], cb[N];
void solve()
{
cin >> n >> k;
for(int i = 0; i <= n; i ++) ca[i] = cb[i] = 0;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
int u = a[i];
while(u % 2 == 0) u /= 2, ca[i] ++;
while(u % 5 == 0) u /= 5, cb[i] ++;
}
for(int i = 1; i <= n; i ++)
{
ca[i] += ca[i - 1];
cb[i] += cb[i - 1];
}
int ans = 0;
// for (int i = 1; i <= n; i ++) cout << ca[i] << " ";
// cout << endl;
// for (int i = 1; i <= n; i ++) cout << cb[i] << " ";
// cout << endl;
//注意这里前缀和一定是单调递增的,因此必定存在r>=l
for(int l = 1; l <= n; l ++)
{
int v1 = k + ca[l - 1];//将前一个枚举的边界除去,这里通过让k + ca, k + cb除去,其实和除一个数就在另一边乘这个数是一个道理
int v2 = k + cb[l - 1];
int l1 = lower_bound(ca + 1, ca + 1 + n, v1) - ca;//找到大于等于v1的第一个下标
// cout << "l1 = " << l1 << " " << v1 << endl;
int r1 = upper_bound(ca + 1, ca + 1 + n, v1) - ca - 1;
// cout << "r1 = " << r1 << endl;
//upper_bound用于找到大于v1的第一个数,-1作用在于找到小于等于v1的最后一个下标
int l2 = lower_bound(cb + 1, cb + 1 + n, v2) - cb;//找到大于等于v2的第一个下标
int r2 = upper_bound(cb + 1, cb + 1 + n, v2) - cb - 1;//找到小于等于v2的最后一个下标
// cout << "l2 = " << l2 << " " << v2 << endl;
// cout << "r2 = " << r2 << endl;
int L = max(l1, l2);
int R = max(r1, r2);
// cout << "L = " << L << " " << " R = " << R << endl;
if(L > R) continue;//说明L越界了,此处也可以写成L == n + 1
L = max(L, l);
ans += (R - L + 1);
// cout << "ans = " << ans << endl;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
请问为啥R=max(r1,r2)
因为k=min(ca[q],cb[q]),所以只要满足一个等于k,另一个尽量往后放才能获得最大值
!thanks