Link
A Two Vessels
十分甚至九分地简单

#include<bits/stdc++.h>
using namespace std;
int t;
int a,b,c;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&a,&b,&c);
        c<<=1;
        a=abs(a-b);
        printf("%d\n",a/c+((a%c)==0?0:1));
    }
    return 0;
}

B he Corridor or There and Back Again
我们只需要让这个小人一直往右走，然后不断更新能到达地最右边地距离就行了。
注意陷阱启动时踏入房间也不行就可以了.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
struct trap{
    int d;
    int s;
}tr[500];
int n;
int k;
int maxx;
int pl[500];
int main(){
    scanf("%d",&t);
    while(t--){
        memset(pl,0x3f,sizeof(pl));
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d%d",&tr[i].d,&tr[i].s);
            pl[tr[i].d]=min(tr[i].s,pl[tr[i].d]);
        }
        maxx=8000000;
        for(int i=1;i<=400;++i){
            if(i>maxx) {
                k=i-1;
                break;      
            }else{
                maxx=min(maxx,i+(pl[i]-1)/2);
            }
        }
        printf("%d\n",k);
    }
    return 0;
}

C. Non-coprime Split
很显然如果存在偶数在范围内的话，一般时可以的。
如果没有，那么这个奇数时质数地话就不可以
然后特判几个特殊情况即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
int l,r;
int f;
int pri;
void dis(int l){
    for(int i=2;i*i<=l;++i){
        if(l%i==0){
            if(!f){
                f=1;
                pri=i;
                return ;
            }
        }
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&l,&r);
        if(l!=r){
            if((l==2&&r==3)||(l==1&&r==2)||(l==1&&r==3)){
                printf("-1\n");
                continue;
            }else{
                if(r%2!=0) r--;
                printf("%d %d\n",r/2,r/2);
            }
        }else{
            if(l==1||l==2||l==3){
                printf("-1\n");
                continue;
            }
            f=0;
            dis(l);
            if(!f){
                printf("-1\n");
                continue;
            }else{
                printf("%d %d\n",pri,l-pri);
            }
        }
    }
    return 0;
}

D. Plus Minus Permutation
显然只要区分开只在前面，只在后面和前后都有的就可以了.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
long long ans;
long long n,x,y;
long long gcd(long long x,long long y){
    return y==0?x:gcd(y,x%y);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&x,&y);
        long long gc=gcd(x,y);
        gc=x/gc*y;
        gc=n/gc;
        x=n/x-gc;
        y=n/y-gc;
        ans=((n+n-x+1)*x/2)-(1+y)*y/2;
        cout<<ans<<endl;
    }
    return 0;
}

E. Data Structures Fan
考虑一下异或的独特性质，异或两次为0
所以一开始算出只有1和只有0的值，然后如果要改变$[l,r]$，那么就把这两个范围内的数的异或和去异或上就行了。
对于两种答案的影响是一样的.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
int n;
int a[100005];
string s;
int ans[2];
int q;
int x,y;
int f;
int sum[100005][2];
int su[100005];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(sum,0,sizeof(sum));
        ans[0]=ans[1]=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        cin>>s;
        for(int i=1;i<=n;++i){
            if(s[i-1]=='0'){
                sum[i][0]=sum[i-1][0]^a[i];
                sum[i][1]=sum[i-1][1];
            }else{
                sum[i][1]=sum[i-1][1]^a[i];
                sum[i][0]=sum[i-1][0];
            }
            su[i]=su[i-1]^a[i];
        }
        ans[1]=sum[n][1];ans[0]=sum[n][0];
        scanf("%d",&q);
        while(q--){
            scanf("%d",&f);
            if(f==1){
                scanf("%d%d",&x,&y);
                ans[0]^=(su[y]^su[x-1]);
                ans[1]^=(su[y]^su[x-1]);
            }else{
                scanf("%d",&x);
                printf("%d ",ans[x]);
            }
        }
        cout<<endl;
    }
    return 0;
}

F. Selling a Menagerie
这个非常简单的图论和贪心问题.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
#define int long long
using namespace std;
int t;
int n;
int a[100005];
int c[100005];
int du[1000001];
queue<int> q,ans;
int tem[100005];
int k;
int h;
int minn;
void dfs(int f,int now){
    if(minn>c[now]){
        k=now;
        minn=c[now];
    }
    tem[++h]=now;
    du[a[now]]--;
    if(!(a[now]==f)){
        dfs(f,a[now]);
    }
}
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
            du[a[i]]++;
        }
        for(int i=1;i<=n;++i){
            scanf("%lld",&c[i]);
        }
        for(int i=1;i<=n;++i){
            if(du[i]==0){
                q.push(i);
                ans.push(i);
            }
        }
        while(!q.empty()){
            int x=q.front();
            q.pop();
            du[a[x]]--;
            if(du[a[x]]==0){
                q.push(a[x]);
                ans.push(a[x]);
            }
        }
        for(int i=1;i<=n;++i){
            if(du[i]!=0){
                minn=1000000009;
                h=0;
                dfs(i,i);
                for(int i=1;i<=h;++i){
                    if(tem[i]==k){
                        for(int j=i+1;j<=h;++j){
                            ans.push(tem[j]);
                        }
                        for(int j=1;j<i;++j){
                            ans.push(tem[j]);
                        }
                        ans.push(k);
                        break;
                    }
                }       
            }
        }
        while(!ans.empty()){
            printf("%lld ",ans.front());
            ans.pop();
        }
        cout<<endl;
    }
    return 0;
}

G. Replace With Product
对于这个题目，首先我们可以想到，对于两边的1，显然是不应该包括进去的。
那么我们假设我们已经选定了$[l,r]$ ，现在这一部分的的贡献是$p$,然后把$a_l$删掉的话，
答案会变化$-p+\frac{p}{a_i}+a_i$,再考虑一下极端情况，剩下的有全是$1$，并且原来有$n$个数，那么答案就会变成只要$p>n$就会更优。
而该情况不满足下，很容易注意到并不会有很多不是1的数存在，就可以枚举了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
#define int long long
using namespace std;
int t;
int n;
const int maxn=200005;
int sum[200005];
int num[maxn];
int a[200005];
int tem;
int h;
long long ans,al,ar;
signed main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
        }
        long long l=1;
        h=0;
        long long r=n;
        while(l<=n&&a[l]==1) l++;
        while(r>=1&&a[r]==1) r--;
        if(l>=r){
            if(l>n) l--;
            printf("%lld %lld\n",l,l);
            continue;
        }
        int f=0;
        long long tem=1;
        for(int i=l;i<=r;++i){
            tem*=a[i];
            if(tem>(r-l+1)*2){
                f=1;
                break;
            }
        }
        if(f){
            printf("%lld %lld\n",l,r);
        }else{
            for(int i=l;i<=r;++i){
                if(a[i]!=1){
                    num[++h]=i;
                }
            }
            for(int i=1;i<=n;++i){
                sum[i]=sum[i-1]+a[i];
            }
            long long tem=1;
            ans=0;
            al=l;
            ar=r;
            for(int i=1;i<=h;++i){
                tem=1;
                for(int j=i;j<=h;++j){
                    tem*=a[num[j]];
                    if((sum[n]-sum[num[j]]+sum[num[i]-1]+tem)>ans){
                        ans=sum[n]-sum[num[j]]+sum[num[i]-1]+tem;
                        al=num[i];
                        ar=num[j];
                    }
                }
            }
            printf("%lld %lld\n",al,ar);
        }
    }
    return 0;
}