题目链接：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() {vcoistntint _=1;cin>>_;while(_--) solve();return 0;
}
