A.小苯的ovo3.0

按题意模拟即可。

时间复杂度 。

void solve(){
    string s;cin>>s;
    cout<<((s[0]=='o'||s[0]=='O')&&(s[1]=='v'||s[1]=='V')&&(s[2]=='o'||s[2]=='O')?"YES\n":"NO\n");
}

B.小苯的双端队列

记录一下当前双端队列的开头 和结尾 。

则对于每个 ：

• 要么是 ，则把 。
• 要么是 ，则把 。
• 否则一定不行，输出 。

时间复杂度 。

void solve(){
    ll n = read();
    ll l = 1, r = n, f = 1;
    for(ll i=1;i<=n;i++){
        ll x = read();
        if(x == l) {
            l++;
        }
        else if(x == r){
            r--;
        }
        else{
            f = 0;
        }
    }
    puts(f?"YES":"NO");
}

C.小苯的整除序列

贪心的选取即可。

每次选择能被 整除的数字时，尽可能选择前面的元素一定不劣。

时间复杂度 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    ll cur = 1;
    for(ll i=1;i<=n;i++){
        if(a[i]%cur==0){
            cur++;
        }
    }
         
    print(cur-1);
}

D.小苯的幼儿园

设 ，如果 不是 的倍数则一定不行。

设 ，由于每次转移的数字只能是 ，因此所有数字必须是 ， 或 。否则不行。

即此时可将数组视为只有 。对于 ，我们要不是左右都不操作要不是都操作，此时可以视作 不存在，因此数组相当于只有 。

由于只能往下一个给，因此整个数组必须是 。

由于可以环形，因此从第一个数字和第二个数字开始判两遍即可。

时间复杂度 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    ll sum = accumulate(all(a), 0ll);
    if(sum % n){
        puts("NO");
        return;
    }
    ll tar = sum / n;
    vector<ll> aa;
    for(ll i=1;i<=n;i++){
        if(abs(tar - a[i]) > 1){
            puts("NO");
            return;
        }
        if(a[i]!=tar) aa.pb(tar-a[i]);
    }
    if(aa.size()&1){
        puts("NO");
            return;
    }
    if(aa.empty()){
        puts("YES");
        return;
    }
    ll f = 0;
    function<ll(vector<ll>)> check = [&](vector<ll> b){
        for(ll i=0;i<b.size();i+=2){
            if(b[i]!=1||b[i+1]!=-1){
                return 0ll;
            }
        }
        return 1ll;
    };
    f |= check(aa);
    aa.pb(aa.front());
    aa.erase(aa.begin());
    f |= check(aa);
    puts(f?"YES":"NO");
}

E.小苯的区间操作

结论是对于每个 ， 和 中必须有一个数字大于等于 。

如果 且 ，那么这个点无论如何都没法操作，一定不可能。

否则，以 ，我一定可以等 削到 时在操作，此时至少有两个元素连续相等。

时间复杂度 。

void solve(){
    ll n = read();
    vector<ll> a(n+2);
    for(ll i=1;i<=n;i++) a[i] = read();
    for(ll i=1;i<=n;i++){
        if(a[i-1]<a[i]&&a[i]>a[i+1]){
            puts("NO");
            return;
        }
    }
    puts("YES"); 
}

F.小苯的DFS

感觉做过树链剖分+线段树的都能秒掉

设 为 这颗子树下所有节点权值的最大值， 为 这颗子树下所有节点权值的最小值。

则对于一个节点 ，可以将 和其所有子节点的 组成一系列区间。且 必须在最左边，所有区间除了端点以外不能相交。

例如 合法。 不合法。

接下来考虑如何交换遍历顺序，如果区间长度不为 ，则一旦交换一定会不满足限制。

当区间长度为 时，即这个子节点整颗子树的权值全部相同，此时可以任意交换与其权值相同且同样整颗子树的权值全部相同的子节点。

例如 此时三个 可以任意交换仍然满足限制，方案数为 。

方案数即为每个节点下权值全部相同的子树的 之积。（一个节点下可能有多对）

求概率要乘上 的逆元。

时间复杂度 。

const ll maxn = 2e5+7;
vector<ll> fac(maxn+2), invfac(maxn+2);
void init(){
    fac[0] = 1;
    for(ll i=1;i<=maxn;i++){
        fac[i] = (fac[i-1] * i)%MOD;
    }
    invfac[maxn] = ksm(fac[maxn]);
    for(ll i=maxn-1;i>=0;i--){
        invfac[i] = (invfac[i+1] * (i+1))%MOD;
    }
}

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    vector<vector<ll>> g(n+1);
    for(ll i=1;i<=n-1;i++){
        ll u = read(), v = read();
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<ll> mx(n+1), mi(n+1, INF), deg(n+1);
    function<void(ll, ll)> dfs = [&](ll u, ll p){
        mx[u] = max(mx[u], a[u]);
        mi[u] = min(mi[u], a[u]);
        for(auto v:g[u]){
            if(v == p) continue;
            dfs(v, u);
            deg[u]++;
            mx[u] = max(mx[u], mx[v]);
            mi[u] = min(mi[u], mi[v]);
        }
    };
    dfs(1, 0);
    ll ans = 1;
    ll f = 1;
    function<void(ll, ll)> dfs3 = [&](ll u, ll p){
        vector<PLL> memo;
        ll pre = a[u];
        for(auto v:g[u]){
            if(v == p) continue;
            memo.pb({mi[v], mx[v]});
        }
        sort(all(memo));
        for(auto [l, r]:memo){
            if(l < pre){
                f = 0;
                return;
            }
            pre = r;
        }
        map<ll, ll> cnt;
        for(auto [l, r]:memo){
            if(l == r) cnt[l]++;
        }
        for(auto [k, v]:cnt){
            ans = (ans * fac[v]) % MOD;
        }
        for(auto v:g[u]){
            if(v == p) continue;
            dfs3(v, u);
            
        }
    };
    dfs3(1, 0);
    ans *= f;
    for(ll i=1;i<=n;i++){
        ans = (ans * invfac[deg[i]])%MOD;
    }
    print(ans);
}

C++火车头

// FZANOTFOUND
#include <bits/stdc++.h>
using namespace std;

#define pb push_back 
#define eb emplace_back 
#define fi first
#define se second
#define ne " -> "
#define sep "======"
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<long long,long long> PLL;
typedef tuple<ll,ll,ll> TLLL;
const ll INF = (ll)2e18+9;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const db PI = 3.14159265358979323;

//io functions
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}  
inline ll read(){ll x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;return x;}  
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
inline void print(ll x){pt(x), puts("");}
inline void print(PLL x){pt(x.fi), putchar(' '), pt(x.se), putchar('\n');}
inline void print(vector<ll> &vec){for(const auto t:vec)pt(t),putchar(' ');puts("");}
inline void print(const map<ll, ll>& g) {for(const auto& [key, value]:g){cout<<"key: "<<key<<ne<<value<<" ";}puts("");}
inline void print(vector<PLL> &vec){puts(sep);for(const auto v:vec){print(v);}puts(sep);}
inline void print(const map<ll, vector<ll>>& g) {for (const auto& [key, value] : g) { cout << "key: " << key << ne;for (const auto& v : value) {cout << v << " ";}cout << endl;}}

//fast pow
ll ksm(ll a, ll b=MOD-2, ll M=MOD){a%=M;ll res=1;while(b){if(b&1){res=(res*a)%M;}a=(a*a)%M;b>>=1;}return res;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//rng()
ull randint(ull l, ull r){uniform_int_distribution<unsigned long long> dist(l, r);return dist(rng);}


void init(){

}

void solve(){
    
}

int main(){
    init();
    ll t = 1;
    //fastio;cin>>t;
    t = read();
    while(t--){
        solve();
    }
}