Codeforces Round 919 (Div. 2)

Problem - A - Codeforces

n个约束条件
a x
求出满足n个约束条件的整数的个数

大于等于x，取最大的
小于等于x，取最小的
然后不等于x的，记录在区间范围内的个数，减去这些

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n;
void solve() {cin>>n;vector<int>ans;int l=0,r=2e9;for(int i=0;i<n;i++){int a,x;cin>>a>>x;if(a==1) l=max(l,x);else if(a==2) r=min(r,x);else ans.push_back(x);}int sum=r-l+1;if(sum<0){cout<<0<<endl;return;}int cnt=0;for(auto v:ans){if(v>=l&&v<=r) cnt++;}cout<<sum-cnt<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - B - Codeforces

长度为n的数组a
操作：Alice删除最多k个元素，然后Bob最多将x个元素乘以-1
Alice想要全部数之和最大，Bob想要全部数之和最小

Bob肯定是尽可能的从大到小尽可能多的乘以-1，暴力枚举Alice删除的个数（从大的开始删）

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int pre[N];
int n,k,x;
void solve() {cin>>n>>k>>x;int sum=0;memset(pre,0,sizeof pre);for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];int ans=-2e9;for(int i=0;i<=k;i++){//枚举删除i个int r=n-i;//[r+1,n]删除int l=max((int)1,r-x+1);//[l,r]全变成-1ans=max(ans,sum-2*(pre[r]-pre[l-1])-(pre[n]-pre[r]));}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - C - Codeforces 

 

对于x，y，x=y（mod m）等价于（x-y）mod m=0，即如果m是|x-y|的因子，那么x，y在模m的意义下同余

所以对于某个k值（k是n的因子，一个一个枚举即可），如果存在m大于等于2，满足a1，a1+k，a1+2 * k...在模m的意义下同余，a2，a2+k，a2+2 * k...在模m的意义下同余...那么k就是一个合法解，答案就加1，也就是说每隔k个的在模m的意义下同余，所以直接从头遍历，看其和其后第k个即可，然后都是模m等于0，所以m需要是它们所有的公因数，故求一个最大公因数，如果大于等于2的话就可以

还一种情况，就是每隔k个数都相等，那么最大公因数就是0，也是可行的

trick：

1.对于x，y，x=y（mod m）等价于（x-y）mod m=0，即如果m是|x-y|的因子，那么x，y在模m的意义下同余

2.a1，a1+k，a1+2 * k...在模m的意义下同余，a2，a2+k，a2+2 * k...在模m的意义下同余...也就是说每隔k个的在模m的意义下同余，所以直接从头遍历，看其和其后第k个是否同余即可，由于都是模m为0，所以m是每差k个的两数之差的绝对值的公因数

3.gcd（a，b），令a等于0，那么结果就是b，所以求很多数的最大公因数时，可以初始化为0，这样比较好

4.当所有数都等于x时，如果初始化为0的话，对它们求gcd为0，如果初始化为其中一个数时，那么对它们求gcd则为

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int n;
int gcd(int a,int b){if(b==0) return a;return gcd(b,a%b);
}
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int k=1;k<=n;k++){//枚举kif(n%k==0){int tmp=0;for(int i=1;i+k<=n;i++){tmp=gcd(tmp,abs(a[i+k]-a[i]));}if(tmp>=2||tmp==0) ans++;}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}