Codeforces Round 895 (Div. 3)A~E题解
1.A. Two Vessels
链接：
题解：
直接暴力枚举，假设a<b，不断让a加c，b减c，直至a>=b，输出答案即可。
AC代码：
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int a,b,c;
cin>>a>>b>>c;
if(a>b)swap(a,b);
int ans=0;
while(a<b)a+=c,b-=c,ans++;
cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}2.B. The Corridor or There and Back Again
链接：
题解：
利用vector<pair>存储，然后按照di降序排列，最后枚举n个pair，maxdis=min(maxdis,d+(t-1)/2)
AC代码：
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n;
cin>>n;
vector<pii>kk;
while(n--)
{
int td,tm;
cin>>td>>tm;
kk.push_back({td,tm});
}
sort(ball(kk));
int maxdis=0x3f3f3f3f;
for(auto pp:kk)
{
maxdis=min(maxdis,pp.first+(pp.second-1)/2);
}
cout<<maxdis<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}3.C. Non-coprime Split
链接：
题解：
枚举sum=a+b从l到r，若找一个大于2的因子（b）即为找到答案，a=sum-b，注意找因子的时候for里面的限制条件为j*j<=sum。
AC代码：
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int l,r;
cin>>l>>r;
int b=-1,a;
for(int sum=l;sum<=r;sum++)//sum==a+b
{
for(int j=2;j*j<=sum;j++)
{
if(sum%j==0)//找到一个因子大于1
{
b=j;
a=sum-b;
break;
}
}
if(b!=-1)break;
}
if(b==-1)
{
cout<<-1<<endl;
}
else
{
cout<<a<<" "<<b<<endl;
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}4.D. Plus Minus Permutation
链接：
题解：
先找到x与y的最小公倍数，且这个值一定大于等于x和y，接着算出1到n中x的倍数（不是y的倍数）即为pos，y的倍数（不是x的倍数）即为neg，要保证答案最大，只需让neg为前面1~neg，pos为后面(n-pos+1)~n，最后利用求和公式再相减即可得出答案。
AC代码：
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{
return (a*b)/gcd(a,b);
}
void ZB1()
{
ll n,x,y;
cin>>n>>x>>y;
ll tt=lcm(x,y);//最小公倍数(一定大于等于x和y)
ll pos=n/x-n/tt;//是x的倍数，但不是y的倍数
ll neg=n/y-n/tt;//是y的倍数，但不是x的倍数
ll ans=(n+(n-pos+1))*pos/2-(1+neg)*neg/2;//x取后pos个，y取前neg个
cout<<ans<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}5.E. Data Structures Fan
链接：
题解：
首先求出a的前缀异或和以及0的异或和、1的异或和，接着读入操作，若操作为2则输出xorzero或者xorone，若操作若为1，则先算出a的l到r的异或和（pre[r]^pre[l-1]），利用两数相同异或值为0，接着再更新xorzero^=val和xorone^=val，例如xorzero中在l到r中本身为0的自身相异或即为0，本身为1的反而被异或进去，到达我们的目的，xorone同理。
AC代码：
//gyeolhada...in bloom...dream...ricky
//string s="ricky";s.insert(0,"hello ");-->hello ricky
//transform(s.begin(), s.end(), s.begin(), ::tolower);
//2^30=1e9+73741824
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sall(x) (x).begin(),(x).end()
#define ball(x) (x).rbegin(),(x).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f3f3f3f3f
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
void ZB1()
{
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
int xorz=0;
int xoro=0;
string s;
cin>>s;
vector<int>pre(n+1,0);//前缀异或和
for(int i=0;i<n;i++)
{
pre[i+1]=pre[i]^a[i];
if(s[i]=='0')xorz^=a[i];
else xoro^=a[i];
}
int q;
cin>>q;
while(q--)
{
int op;
cin>>op;
if(op==2)
{
int kk;
cin>>kk;
if(kk==1)cout<<xoro<<" ";
else cout<<xorz<<" ";
}
else
{
int l,r;
cin>>l>>r;
int val=pre[r]^pre[l-1];//val为下标从l到r所有a[i]的异或和
//pre[l-1]异或两次，相同为0
xorz^=val;//在l到r中之前为0的同本身相异或为0，而为1的则被异或进去，达到目的
xoro^=val;//同理如上
}
}
cout<<endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
ZB1();
}
return 0;
}