Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)(A,B,C,E1)

题目链接：Dashboard - Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) - Codeforces

A. String

思路

可以发现最小反转次数就是把每个1单独反转为0就行，即统计1的个数

代码

void solve(){
    string s;
    cin>>s;
    int sum=0;
    for(int i=0;i<s.size();i++){
        sum+=(s[i]-'0');
    }
    cout<<sum<<"\n";
}

B. Clockwork

思路

我们要保证每个i都要到达因为要重置，对于i节点我们要从i-n-i或从i-1-i，只要a[i]>=max((n-i)*2,(i-1)*2)即可满足无限循环

代码

void solve(){
    int n;
    cin>>n;
    vi a(n+10);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    bool f=true;
    for(int i=1;i<=n/2;i++){
        if(a[i]<=(n-i)*2) f=false;
    }
    for(int i=n/2;i<=n;i++){
        if(a[i]<=(i-1)*2) f=false;
    }
    if(f){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

C. Cirno and Operations

思路

操作1为反转，操作2为差序列替换，我们可以发现在进行操作2之后和就变成了a[n]-a[1]，再进行操作1之后和为a[1]-a[n]，所以只要把原始序列的和拿出来，之后操作1改变的只是答案的正负号，把所有的可能取绝对值求最大即可，注意要把原始序列单独拿出来因为还没有进行操作2所以和不能按绝对值来算

代码

void solve(){
    int n;
    cin>>n;
    vi a(n+10);
    int x=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        x+=a[i];        
    }
    if(n==1){
        cout<<a[1]<<"\n";return;
    }
    int t=n;
    while(t){
        int sum=0;
        sum=a[t]-a[1];
        x=max(abs(sum),x);
        t--;
        for(int i=1;i<=t;i++){
            a[i]=a[i+1]-a[i];
        }
    }
    cout<<x<<"\n";
}

E1. The Game (Easy Version)

思路

首先这是一道博弈题，发现Cirno可能选择的节点必须满足以下两个条件:

1.Cirno选择的节点u，存在一个节点v，v不在u的子树里面并且

2.这样的节点v只能存在1个，意思是当Daiyousei选择节点v之后并把v的子树给删掉，Cirno没有其他节点可以选择了，这样Cirno就胜利了

关于第一个条件。我们可以用dfn序维护前后缀来实现，具体来说，dfn序就是把树的节点按DFS的顺序放在一条链上进行处理，我们用dfn[i]表示节点i第一次出现的位置，low[i]表示dfs搜索完节点i出来的节点，即[dfn[i]，low[i]]表示节点i及其子树所在的区间，我们用pre[i]表示前缀最大值，suf[i]表示后缀最大值，那么遍历到i节点时，只要满足就说明存在一个节点v，v不在u的子树里面并且

关于第二个条件。我们要贪心地去想，我们只要选择满足条件1的最大的w的节点即可，这样就一定会满足条件二

代码

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

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcount
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=1e6+10;
const int inf=1e18;
const int mod=998244353;

int n,id;
int w[N],dfn[N],nfd[N],low[N];
vb vis(N);
vector<int> e[N];

void dfs(int u){
    if(vis[u]) return;
    vis[u]=true;
    dfn[u]=++id;
    nfd[id]=u;
    for(auto v:e[u]) dfs(v);
    low[u]=id;
    vis[u]=false;
}

void solve(){

    id=0;
    for(int i=1;i<=n;i++){
        e[i].clear();
    }

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    vi pre(n+10),suf(n+10);
    for(int i=1;i<=n;i++){
        pre[i]=max(pre[i-1],w[nfd[i]]);
    }
    for(int i=n;i>=1;i--){
        suf[i]=max(suf[i+1],w[nfd[i]]);
    }
    int mx=0;
    for(int i=1;i<=n;i++){
        if(max(pre[dfn[i]-1],suf[low[i]+1])>w[i]&&w[i]>w[mx]){
            mx=i;
        }
    }
    cout<<mx<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}