Codeforces Round 919 (Div. 2)
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;
}长度为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]全变成-1
ans=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;
}
对于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++){//枚举k
if(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;
}原文地址：https://blog.csdn.net/m0_74087709/article/details/135620600
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！