Codeforces Round 895 (Div. 3)
思路：找到差值，让a，b向中间靠
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int a,b,c;cin>>a>>b>>c; int s=abs(a-b); s=(s+c-1)/c; cout<<(s+1)/2<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
B - The Corridor or There and Back Again
思路：走到x后的y秒内要走回x，走到最远的距离为x+（y-1）/2，找到最小的距离
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n;cin>>n; int x,y,ans=INF; for(int i=0;i<n;++i){ cin>>x>>y; y--; y/=2; ans=min(ans,x+y); } cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
思路：暴力枚举l~r，若该数为非质数即可
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int l,r; cin>>l>>r; if(r<=3)cout<<-1<<'\n'; else{ if(l==r&&l%2){ for(int i=2;i<=l/i;++i){ if(l%i==0){ cout<<i<<' '<<l-i<<'\n';return ; } } cout<<-1<<'\n'; }else if(l==r&&l%2==0){ cout<<2<<' '<<l-2<<'\n'; }else{ int s=r; if(s%2)s--; cout<<2<<' '<<s-2<<'\n'; } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
思路：x和y的倍数的个数即为分别加的p的个数，再减去x和y的公共部分个数即最小公倍数的倍数个数，让x部分加最大的数，y部分加最小的部分
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n,x,y; cin>>n>>x>>y; int a=n/x,b=n/y; int c=__gcd(x,y); c=x/c*y; c=n/c; a-=c,b-=c;//cout<<a<<' '<<b<<' '; cout<<(n*n-(n-a)*(n-a+1)-(b+1)*b+n)/2<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }
思路：将一段中的数翻转，即将all0异或val1和val0，all1异或val0和val1（val0表示这一段所有为0的数异或和，val1同理，all0表示所有为0的数异或和，all1同理）；去掉或添加一个数的操作都为异或这个数。
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 #define double long double typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const double eps=1e-6; void solve(){ int n;cin>>n; vector<int>a(n+1),a1(n+1),a0(n+1); for(int i=1,x;i<=n;++i){ cin>>a[i]; } string s;cin>>s; s=' '+s; int all1=0,all0=0; for(int i=1;i<=n;++i){ if(s[i]=='1'){ all1^=a[i]; a1[i]=a[i]^a1[i-1]; a0[i]=a0[i-1]; }else{ all0^=a[i]; a0[i]=a[i]^a0[i-1]; a1[i]=a1[i-1]; } } int q;cin>>q; int op,l,r; while(q--){ cin>>op; if(op==1){ cin>>l>>r; int b0=a0[r]^a0[l-1]; int b1=a1[r]^a1[l-1]; all1^=b1,all1^=b0; all0^=b0,all0^=b1; }else{ cin>>l; if(l==0)cout<<all0<<' '; else cout<<all1<<' '; } } cout<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }