#808 div2
https://codeforces.com/contest/1708
A:
题目:
现在给出一个长度为 n 的数组。
现在你可以执行任意操作的a[i]= a[i] - a[i - 1]
问你能不能吧除了第一个元素都变成0。
思路:
不难发现,对于第二个元素来说,你必须是第一个元素的倍数才可以减为 0,
同理第三个必须是第二个的倍数也才可以。以此类推,对于每个元素来说都必须是第一个元素的倍数才可以被减为0。
代码
void solved()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 1; i < n; i++)
{
if(a[i] % a[0] != 0)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
B:
题目:
现在给出三个数字 n l r,你需要构造一个长度为 n的数组,并且数组里面的值为 l - r。
对于每个数字的下标 i, 我们保证 n 个数字和他们的下标的 gcd都是不同的。
思路:
因为gcd都不同,所以就是每个数字是下标的倍数,并且不考虑重复数字使用的问题。
所以我们只需要知道,在 l - r 中是否存在 下标 i 的倍数即可。
代码
void solved()
{
int l, r;
cin >> n >> l >> r;
vector<int>ans;
for(int i = 1; i <= n; i++)
{
if(l % i == 0)
{
ans.push_back(l);
}
else
{
if((l / i + 1) * i > r)
{
cout << "NO" <<endl;
return;
}else
{
ans.push_back((l / i + 1) * i);
}
}
}
cout << "YES" << endl;
for(int i = 0; i <ans.size(); i++) cout << ans[i] << " ";
cout << endl;
}
C:
题目:
现在有 n 个问题,并且每个问题都有一个难度值 ai,一开始存在一个IQ 为 q。
现在对每个问题有两种操作
1.你可以不回答这个问题
2.回答
q >= ai, 那么不用减少q 就能回答一个问题
q < ai,那么他可以选择减少一个 q 来回答这个问题
现在问你能回答多少问题
思路:
贪心的来说,万一有很小的问题在后面,那么假如前面用光了后面没法回答,所以我们选择从后向前来回答问题。
如果说当前的 ai > 当前维护的值,那么说明我们需要增加一个iq来完成,否则就可以直接回答,这样直到我们维护到
等于给出的 q。这样就确保优先小问题。
代码
void solved()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i], st[i] = false;
int xb = 0;
string ans;
int x = 0;
for(int i = n; i >= 1; i--)
{
if(x >= a[i]) ans += '1';
else
{
if(x < k)
{
x++;
ans +='1';
}else ans += '0';
}
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
D:
题目:
现在给出一个数组 a,保证 a 升序排列。在每个操作中,存在一个 b 数组 bi = a[i + 1] - a[i], 这样b 数组就比 a 数组少一个。
同时每次更新完 b 数组,sort 一下保证升序排列,然后继续操作,直到b数组剩下一个元素。
输出这个元素。
思路:
不难发现,我们这个操作很像差分,我们模拟几个数据发现,我们经过很小的操作之后,会出现很多的0,这样sort之后很多0 并不对
我们的答案起到影响,所以我们每次只要从最后一个非0开始就能优化很多时间。
代码
void solved()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int r = n;
int x0 = upper_bound(a, a + n, 0) - a;
x0 = max(0, x0 - 1);
while(r != 1)
{
if(x0 != 0) x0--;
for(int i = x0; i <= r - 1; i++) a[i] = a[i + 1] - a[i];
r--;
sort(a + x0, a + r);
x0 = upper_bound(a, a + r, 0) - a;
}
cout << a[0] << endl;
}