A. Two Vessels
要我们找到最少操作多少次，a和b内的水一样多，从a拿出i克放到b中，之间的差距减少2i，数据范围不大，循环解决即可。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
inline void solve() {
int a,b,c;
cin>>a>>b>>c;
int k=abs(a-b);
int ans=0;
if(a==b)
{
cout<<"0\n";
return;
}
while(k>0)
{
ans++;
k-=2*c;
}
cout<<ans<<"\n";
}
signed main() {
TEST
solve();
return 0;
}B. The Corridor or There and Back Again
依次遍历每个房间，找到从这个房间开始最多前进到最大的房间是多少，依次记录最小值。
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
#include<cstring>
#include<set>
#include<map>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
struct node
{
int d,s;
}e[N];
bool cmp(node a,node b)
{
return a.d<b.d;
}
inline void solve() {
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>e[i].d>>e[i].s;
sort(e+1,e+1+n,cmp);
int mi=1e9;
for(int i=1;i<=n;i++)
{
if(e[i].d>=mi) continue;
mi=min(mi,e[i].d+(e[i].s-1)/2);
}
cout<<mi<<"\n";
}
signed main() {
TEST
solve();
return 0;
}C. Non-coprime Split
我们用贪心的办法解决，一个大于3的偶数肯定能分成两个部分，并且他们的最小公约数不为1，当出现L等于R的情况，并且L是质数，则不能满足题目要求，反之我们暴力枚举找到。
#include<bits/stdc++.h>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
int prime(int x)
{
if(x<=1) return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
inline void solve() {
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++)
{
if(i>=4&&i%2==0)
{
cout<<2<<" ";
cout<<i-2<<"\n";
return;
}
}
if(l==r)
{
if(!prime(l))
{
for(int i=2;i<=l/2;i++)
{
int j=l-i;
if(__gcd(i,j)!=1)
{
cout<<i<<" "<<j<<"\n";
return;
}
}
}
}
cout<<"-1\n";
}
signed main() {
TEST
solve();
return 0;
}D. Plus Minus Permutation
n除以x可以找到x在1到n中可以占几个位置，同理也能找到y在1到n中占几个为止，n除以x和t的最小公倍数可以这个共同位置，这样就可以用贪心解决，x单独占的位置我们设为尽可能大，y占的位置我们设为尽可能小，共同位置不讨论，最后得到正确答案。
#include<bits/stdc++.h>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
inline void solve() {
int n,x,y;
cin>>n>>x>>y;
int t=__gcd(x,y);
t=x*y/t;
int num1=n/x,num2=n/y,num3=n/t;
num1-=num3;
num2-=num3;
int ans=(n-num1+1+n)*num1/2;
ans-=(1+num2)*num2/2;
cout<<ans<<"\n";
}
signed main() {
TEST
solve();
return 0;
}E. Data Structures Fan
在写这个题的时候可以了解一下异或的一下公式。
a^a=0
a^0=a
所以我们可以知道，当我们在选择区间L和R时，无非就是将答案异或整个区间。
#include<bits/stdc++.h>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
int a[N],sum[N];
inline void solve() {
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
string s;
cin>>s;
int q;
cin>>q;
s='8'+s;
for(int i=1;i<=n;i++)
{
if(s[i]=='1') ans^=a[i];
sum[i]=sum[i-1]^a[i];
}
for(int i=1;i<=q;i++)
{
int x;
cin>>x;
if(x==2)
{
int flag;
cin>>flag;
if(flag==1)
{
cout<<ans<<"\n";
}
else cout<<(ans^sum[n])<<"\n";
}
else
{
int l,r;
cin>>l>>r;
ans^=sum[l-1]^sum[r];
}
}
}
signed main() {
TEST
solve();
return 0;
}F. Selling a Menagerie
其实就是i向a[i]建一条有向边，利用拓扑排序将入度为0的点先输出，因为他们没有任何动物害怕，所以直接输出即可，后面就会留下n个联通块，我们按照贪心，牺牲价值最小的，而一个联通块中其余都可与以两倍价格卖出。
拓扑排序：去除入度为0的点
并查集：查找联通块
从每个联通块价值最小的点出发，遍历并且输出完整个联通块的点，最后输出自己，最终得到最优序列。
#include<bits/stdc++.h>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 1e9 + 7;
const int bit = 63;
int a[N],c[N],cnt,x[N],y[N],head[N],v[N],pre[N],b[N],mi[N];
int n;
struct node
{
int v,id;
}e[N];
void add(int u,int v)
{
x[++cnt]=v;
y[cnt]=head[u];
head[u]=cnt;
}
int Find(int x)
{
if(x==pre[x]) return x;
return pre[x]=Find(pre[x]);
}
void clear()
{
cnt=0;
for(int i=1;i<=n;i++) head[i]=x[i]=y[i]=v[i]=a[i]=mi[i]=0;
}
inline void solve() {
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>b[i];
add(i,b[i]);
a[b[i]]++;
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
pre[i]=i;
}
//找到入队为0的点
queue<int>q;
for(int i=1;i<=n;i++)
{
if(a[i]==0)
{
q.push(i);
}
}
while(!q.empty()){
int k=q.front();
q.pop();
v[k]=1;
cout<<k<<" ";
for(int i=head[k];i;i=y[i])
{
int t=x[i];
a[t]--;
if(a[t]==0)
q.push(t);
}
}
vector<node>f;
for(int i=1;i<=n;i++)
{
if(v[i]==0)
{
pre[Find(i)]=Find(b[i]);//寻找连通块
}
}
for(int i=1;i<=n;i++)
{
if(v[i]==0&&(!mi[Find(i)]||c[mi[pre[i]]]>c[i]))
{
mi[pre[i]]=i;
}
}
for(int i=1;i<=n;i++)
{
if(v[i]==0&&i==mi[pre[i]])
{
for(int j=b[i];j!=i;j=b[j])
{
cout<<j<<" ";
}
cout<<i<<" ";
}
}
cout<<"\n";
clear();
}
signed main() {
TEST
solve();
return 0;
}G. Replace With Product
选择一对区间，将区间所有数变成区间数的乘积，保证最大化最后数组各个元素的和。
利用贪心我们发现我们的边界肯定不能为1，所以我们把每个不为1的位置找到，在这些点内暴力枚举。
查看数据范围，我们可以知道每个数之和最大不大于2x10^5x10^9，所以我们从头开始累乘，直到大于这个值时，我们就输出左右两侧不为1的点的位置，这是最优的。
现在开始暴力枚举，用值记录选择两个边界能给数组增加的值，一直更新最大值和最优区间。
#include<bits/stdc++.h>
#define int long long
#define TEST int T;cin>>T;while(T--)
#define lowbit(x) x&(-x)
using namespace std;
const int N = 200010;
const int M = 2e14+10;
const int bit = 63;
inline void solve() {
int n,sum=0;
cin>>n;
vector<int>a(n+1);
vector<int>pos;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=1) pos.push_back(i);
sum+=a[i];
}
int l=1,r=n;
while(a[l]==1) l++;
while(a[r]==1) r--;
if(l>=r)
{
cout<<1<<" "<<1<<"\n";
return;
}
int res=1;
for(int i=1;i<=n;i++)
{
res*=a[i];
if(res>=1e9)
{
cout<<l<<" "<<r<<"\n";
return;
}
}
//开始暴力枚举
int L=1,R=1,ans=sum;
for(int i=0;i<pos.size();i++)
{
int cnt=1,s=0;
for(int j=i;j<pos.size();j++)
{
int l=pos[i],r=pos[j];
cnt*=a[r];
s+=a[r]-1;
int now=sum-(r-l+1)-s+cnt;
if(now>ans)
{
L=l,R=r;
ans=now;
}
}
}
cout<<L<<" "<<R<<"\n";
}
signed main() {
TEST
solve();
return 0;
}
