提前开香槟，应该无人赛中看见?。

A. Medium Number

求三个数的和减去最大最小值即可

B. Atilla’s Favorite Problem

求给定字符串中的最大字符减去a加一即可

C. Advantage

首先排序判断最大值是否唯一，不唯一就全部减最大值即为答案，否则除最大值减去次大值外其余均减去最大值

D. Challenging Valleys

容易发现如果存在$a_i < a_{i+1}$，那么$\forall i \leqslant j$，均有$a_j \leqslant a_{j+1}$，否则就为No

Code:

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,a[(int)2e5+9];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>n;
        f(i,1,n)cin>>a[i];
        int st=0;
        bool ok=true;
        f(i,2,n){
            if(a[i]>a[i-1]){st=i;break;}
        }
        if(st){
            for(int i=st;i<=n;++i){
                if(a[i]<a[i-1]){
                    ok=false;
                    break;
                }
            }
        }
        cout<<(ok?"YES\n":"NO\n");
    }
    return 0;
}

E. Binary Inversions

不考虑改变的话，答案就是每个$0$前面的$1$的个数的和。

求改变就可以遍历每个$a_i$，计算改变该处值后的答案取max即可。

Code:

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,a[(int)2e5+9],b[(int)2e5+9];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>n;
        f(i,1,n)cin>>a[i],b[i]=b[i-1]+a[i];
        ll ans=0;
        f(i,1,n)if(a[i]==0)ans+=b[i-1];
        ll tmp=ans;
        f(i,1,n){
            if(a[i]){
                ans=max(ans,tmp+b[i-1]-((n-i)-(b[n]-b[i])));
            }else ans=max(ans,tmp+((n-i)-(b[n]-b[i]))-b[i-1]);
        }
        cout<<ans<<"\n";
    }
    return 0;
}

F. Quests

首先排序求前缀和，然后考虑一些特殊情况： Infinity的情况就是前$d$个任务的金币已经够了，Impossible就是连续$d$天都取金币最多的任务也不能完成的情况。

接下来就是求$k$了，二分即可。

Code:

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,c,d,a[(int)2e5+9],s[(int)2e5+9];

ll solve(int l,int r){
    while(l<r){
        ll mid=(l+r+1)>>1;
        ll res=s[min(mid+1,n)]*(d/(mid+1))+s[min(d%(mid+1),n)];
        if(c<=res)l=mid;
        else r=mid-1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        cin>>n>>c>>d;
        f(i,1,n)cin>>a[i];
        sort(a+1,a+1+n,[](ll x,ll y){return x>y;});
        f(i,1,n)s[i]=s[i-1]+a[i];
        if(s[min(d,n)]>=c){
            cout<<"Infinity\n";
        }else if(a[1]*d<c){
            cout<<"Impossible\n";
        }else cout<<solve(0,d-2)<<"\n";
    }
    return 0;
}

G. SlavicG’s Favorite Problem

容易发现是不会走回头路的，所以我们从点$a$开始dfs，记录到每个点时$x$的值，然后判断是否可以直接到点$b$，是直接返回true即可，dfs时注意不要过点$b$。

接下来就可以从点$b$开始dfs，并判断从$a$开始dfs的点中是否存在相同值的点，注意要删除经过的路径上的点的贡献，存在便返回true。

Code:

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,a,b,dp[(int)1e5+9],f[(int)1e5+9];
int tot,hd[(int)1e5+9];
bitset<(int)1e5+9> vis;
struct Edge{
	int to,nxt,v;
}e[(int)4e5+9];
void add(int u,int v,int w){
	e[++tot]={u,hd[v],w},hd[v]=tot;
	e[++tot]={v,hd[u],w},hd[u]=tot;
}

void dfs(int u,int val){
	if(vis[u])return ;
	vis[u]=1;
	dp[u]=val;
	if(u==b)return ;
	for(int eg=hd[u];eg;eg=e[eg].nxt){
		dfs(e[eg].to,e[eg].v^val);
	}
}
map<int,int> exi;
bool dfs2(int u,int val){
	if(vis[u])return 0;
	vis[u]=1;
	bool ok=false;
	f[u]=val;
	//cerr<<u<<"::"<<val<<"\n";
	if(exi.count(f[u])&&u!=b)if(exi[f[u]])return true;
	//cerr<<u<<"__\n";
	//if(u==a)return 0;
	for(int eg=hd[u];eg;eg=e[eg].nxt){
		if(~dp[e[eg].to]&&e[eg].to!=b)exi[dp[e[eg].to]]-=1;
		ok|=dfs2(e[eg].to,e[eg].v^val);
		if(~dp[e[eg].to]&&e[eg].to!=b)exi[dp[e[eg].to]]+=1;
	}
	return ok;
}

bool solve(){
	exi.clear();
	cin>>n>>a>>b;
	tot=1,vis.reset();
	f(i,1,n)hd[i]=0,dp[i]=-1,f[i]=-1;
	for(int i=2,x,y,z;i<=n;++i){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dfs(a,0);
	vis.reset();
	if(dp[b]==0)return true;
	f(i,1,n)if(~dp[i]&&i!=b)exi[dp[i]]+=1;
	//f(i,1,n)cout<<dp[i]<<" \n"[i==n];
	return dfs2(b,0);
	return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt)cout<<(solve()?"YES\n":"NO\n");
    return 0;
}