小吃一波分
A. Difference Operations
贪心从左往右推过去就好，首先a2肯定要是a1的倍数，不然减不到0，同样的a3也一定要是a2的倍数，但是这里a2可能被操作成a1的其他倍数，比如1 2 3，先变成 1 1 3，然后把a3清0 再清0 a2即可，也就是说a3一定要是a1的倍数，以此类推，全部模a1==0才行
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+10;
const int mod = 1e6+10;
int num[maxn];
void DE(int x){
printf("%d",x);
}
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
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>>num[i];
int j = 1;
for(int i = 2;i<=n;i++){
if(num[i]%num[1]!=0)
j = 0;
}
if(j)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
B. Difference of GCDs
构造性题目，直接构造一个大于l且小于r的并且是对应i的倍数即可。
原理的话就是，i是从1-n的，同时gcd(ai,i)必然会等于i。首先gcd(ai,i)的值必然是i的因数，那么gcd(ai,1)必然等于1，gcd(ai,2)可以等于1或者2，但因为前面已经有1了，那么这里只能选2，以此类推，gcd(ai,i)必然等于i，然后进行构造就好了。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+10;
const int mod = 1e6+10;
int num[maxn];
void DE(int x){
printf("%d",x);
}
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
int l,r;
cin>>l>>r;
int j = 1;
vector<int>ans;
int now;
for(int i = 1;i<=n;i++){
if(l%i)
now = (l/i+1)*i;
else
now = l;
if(now>r){
j = 0;
break;
}
ans.push_back(now);
}
if(j){
cout<<"YES"<<endl;
for(auto i:ans)
cout<<i<<" ";
cout<<endl;
}
else
cout<<"NO"<<endl;
}
}
C. Doremy's IQ
比当前q小或相等的任务当然要选，那么分歧点就在，比当前q大的任务到底要不要选？
如果我们做了这个任务，有两种情况，一种是不影响后面任务的选取，一种是会影响后面任务的选取，如果会影响，那么我们选择不做前面做后面的，这是因为影响后面的任务选取可能一影响就影响好几个，如果只影响一个那么选前选后都一样，综合来说选后面即可，比如q=1 任务是 2 1 1选第一个的话只做了一个任务，不做第一个能做两个，比如q = 1 任务是 2 1做前做后都一样。也就是说，我们优先做后面的所有任务。
换而言之，我们只需要在每个点进行对比，做完之后所有任务所需的最低q为多少，如果当前q大于等于最低q就可以做，否则不做。
同时我们还要从后往前对数据进行处理，比如4 5 2 3 6这个数据，很明显 做最后一个任务需要的q至少为1，因为已经是最后一个任务了，减到0也没事 然后是3这个数据 比q=1大但因为是倒数第二个任务，最低q=2就可以做完后面所有任务，然后是2这个数据，由于第四第五个任务最低q=2就可以全部做完，延续q=2就可以做完，即q=2可以做完第三第四第五个任务，推到5的时候，由于后面三个任务q=2可以全部做完，这个任务至少要以此类推。代码里我分两次进行处理了。
有点像aov网络图
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+10;
const int mod = 1e6+10;
int num[maxn];
int w[maxn];
int mi[maxn];
int mx[maxn];
void DE(int x){
printf("%d",x);
}
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--) {
int n,q;
cin>>n>>q;
for(int i = 1;i<=n;i++)
cin>>w[i];
for(int i = n;i>=1;i--){
mi[i] = min(w[i],n-i+1);
}
mx[n] = 1;
for(int i = n-1;i>=1;i--){
mx[i] = mx[i+1];
if(mi[i]>mx[i+1])
mx[i]++;
}
for(int i = 1;i<=n;i++){
if(q>=w[i])
cout<<1;
else if(q>=mx[i]){
cout<<1;
q--;
}
else{
cout<<0;
}
}
cout<<endl;
}
}
D. Difference Array
挺神秘的。。。。大概其实就是 排序好以后前面的0不用去计算，每次操作前面的0减少一个，后面的正常操作就好了。原理不是很懂，脑补一下就是由于相减，数组中的数会越来越少，相减为0会越来越多，要操作的数越来越少。0是不用处理的，因为0-0还是0，在数组中的位置也不用动，所以时间够用，剩下的暴力就行。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int maxn = 1e6+10;
const int mod = 1e6+10;
int num[maxn];
int w[maxn];
int mi[maxn];
int mx[maxn];
void DE(int x){
printf("%d",x);
}
int GCD(int a, int b) {
return b ? GCD(b, a % b) : a;
}
void show(vector<int>a){
for(int i =0;i<a.size();i++)
cout<<a[i]<<" ";
cout<<endl;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--) {
int n,x;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>num[i];
}
int tar = n;
for(int i = 1;i<=n;i++)
if(num[i]){
tar = max(i-1,1);
break;
}
while(n>1&&num[n-1]){
for(int i = tar;i<n;i++){
num[i] = num[i+1]-num[i];
}
n--;
sort(num+tar,num+n+1);
for(int i = tar;i<n;i++){
if(num[i]==0)
tar++;
else{
tar = max(tar-1,1);
break;
}
}
/* for(int i = 1;i<=n;i++){cout<<num[i]<<" ";}
cout<<endl;*/
}
cout<<num[n]<<endl;
}
}
