Problem - A - Codeforces

n個約束條件
a x
求出滿足n個約束條件的整數(shù)的個數(shù)

大于等于x，取最大的
小于等于x，取最小的
然后不等于x的，記錄在區(qū)間范圍內(nèi)的個數(shù)，減去這些

#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的數(shù)組a
操作：Alice刪除最多k個元素，然后Bob最多將x個元素乘以-1
Alice想要全部數(shù)之和最大，Bob想要全部數(shù)之和最小

Bob肯定是盡可能的從大到小盡可能多的乘以-1，暴力枚舉Alice刪除的個數(shù)（從大的開始刪）

#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需要是它們所有的公因數(shù)，故求一個最大公因數(shù)，如果大于等于2的話就可以

還一種情況，就是每隔k個數(shù)都相等，那么最大公因數(shù)就是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個的兩數(shù)之差的絕對值的公因數(shù)

3.gcd（a，b），令a等于0，那么結(jié)果就是b，所以求很多數(shù)的最大公因數(shù)時，可以初始化為0，這樣比較好

4.當所有數(shù)都等于x時，如果初始化為0的話，對它們求gcd為0，如果初始化為其中一個數(shù)時，那么對它們求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;
}